[android] ArrayMap 과 SparseArray 를 이용한 최적화

[android] ArrayMap 과 SparseArray 를 이용한 최적화

https://medium.freecodecamp.com/android-app-optimization-using-arraymap-and-sparsearray-f2b4e2e3dc47#.pg0eea2cx

ArrayMap vs. HashMap

-

ArrayMap 은 android.util.ArrayMap 과 android.support.v4.util.ArrayMap 두 가지 형태가 있다.

뒤의 녀석은 compat 이슈를 위한 것.

-

ArrayMap 은 HashMap 보다 더 memory 최적화된 데이터 구조를 가진다.

ArrayMap 은 array 를 이용해 mapping 을 관리한다.

Hash integer 를 가지고 있는 array 와, key, value 를 담는 Object array 를 가지고 있다.

이 구조때문에 map 의 각 entry 를 추가로 만들 필요가 없다.

Size 도 더 공격적으로 관리한다. Map 의 크기가 커지면 array 를 copy 만 할 뿐 hash map 처럼 rebuilding 하지 않는다.

-

ArrayMap 은 큰 데이터를 담기 위해 설계된 것이 아니기 때문에, Large data case 의 일반적인 성능은 HashMap 이 더 좋다.

HashMap 은 O(1) 의 complexity 를 갖지만, ArrayMap 은 O(log n)의 binary search lookup 을 사용하기 때문이다.

몇백개의 item들에 대해서는 성능 차이가 크지 않거나 오히려 ArrayMap 이 빠를 수도 있다.

HashMap

-

HashMap 은 기본적으로 HashMap.Entry 의 Array 이다.

-

HashMap 에 key->value pair 가 추가되면..

1. hashcode 가 계산되고 Entry 의 hashCode 변수에 할당된다.

2. hashCode 를 이용하여 bucket 이 위치한 혹은 위치해야할 index 를 계산한다.

3. bucket 이 존재하면 그 곳에 추가하고, 그렇지 않으면 새로 생성하며 추가한다. ( 보통 bucket 은 linked list )

-

HashMap 은 O(1) 의 성능을 가지지만, memory 는 더 사용하게 된다.

메모리를 더 사용하는 이유는, 사용하지 않는 공간을 allocate 해놓고, 불필요한 class 인 HashMap.Entry 사용 이슈 때문,

또 하나는 HashMap 이 축소되거나 확장될 때마다 bucket 이 rearrange 된다는 점이다.

cf) HashMap 이 LinkedList 를 사용하는데.. 빠른 검색을 위해 hash array 의 size 가 커지거나 작아지거나, bucket 의 linked list 의 size 가 커지거나 등의 이슈등을 기준으로 HashMap 전체를 확대 축소를 한다. 이 때 전체 bucket 에 대한 rearrange 가 일어난다. ( Java 버전에 따라 다를 수 있다. Java8 에서는 HashMap 의 Bucket container 를 Tree 로 변경했다고 한다. 그래서 O(logn) 의 성능이라고.. )

ArrayMap

-

ArrayMap 은 int[] (mHashes)와 Object[] (mArray) 총 두 개의 array 를 사용하여 map 을 관리한다.

-

key->value pair 가 추가되면..

1. key -> value pair 가 autobox 된다. ( 필요한 경우 )

2. key object 가 Object[] array 에 추가된다.

3. value object 는 2에서 insert 된 key object 다음에 추가된다.

4. key 의 hashCode 가 계산되어 int[] 에 들어간다.

-

key 로 검색할 때에는..

1. key hashCode 가 계산된다.

2. int[] array 에 대해 binary search 를 한다. O(log n) 성능을 보인다.

3. hash index 를 얻으면 Object[] array 의 2*index 에 key 가 있고, 2*index+1 에 value 가 있음을 알 수 있다.

-

ArrayMap 은 index 를 통한 iteration 도 가능하다.

cf) 이 녀석은 collision 이 발생하면 어케 할까? 나중에 소스 코드 봐야지 ㅋ

Recommended data-structures

-

ArrayMap, ArraySet, SparseArray, SparseBooleanArray, SparseIntArray, SparseLongArray, LongSparseArray

언제 ArrayMap 을 사용하면 좋을까?

-

자료양이 1000개 미만일 때

-

Map 이 Map 을 containing 하고 있을 때

allocate, array, ArrayMap, arraymap best condition, arraymap vs hashmap, ArraySet, autoboxing, binary search lookup, Bucket, bucket rearrange, compat, complexity, containing, COPY, entry, hash integer, hash map, hashcode, HashMap, hashmap.entry, index, index iteration, int[], Key, key value, key value pair, Linked List, LongSparseArray, map, mapping, memory 최적화, o(1), o(logn), object array, object[], Rebuilding, Recommended data-structures, Size, sparsearray, SparseBooleanArray, SparseIntArray, SparseLongArray, [android] ArrayMap 과 SparseArray 를 이용한 최적화