[android] ArrayMap 과 SparseArray 를 이용한 최적화
[android] ArrayMap 과 SparseArray 를 이용한 최적화
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 하고 있을 때