ANDROID SparseIntArray
원문
SparseIntArray는 HashMap 보다 메모리를 절약하는 자료구조. 안드로이드에서만 사용 가능. 1000개 이하의 작은 수의 키-값 매핑이 필요할 때 사용하면 좋음. 검색을 자주하거나 아이템 추가 제거를 적게 하는 경우에는 HashMap 보다 효율 좋음
| 시간복잡도 | |
|---|---|
| O(1) | size(), keyAt(index), valueAt(index), setValueAt(index), clear() |
| O(lgN) | get(key), indexOfKey(key) |
| O(N) | delete(key), removeAt(index), put(key, value), indexOfValue(value), append(key, value) |
SparseIntArrays map integers to integers. Unlike a normal array of integers, there can be gaps in the indices. It is intended to be more memory efficient than using a HashMap to map Integers to Integers, both because it avoids auto-boxing keys and values and its data structure doesn't rely on an extra entry object for each mapping.SparseIntArray는 정수를 정수와 매핑해준다. 일반적인 정수 배열과는 다르게 인덱스들 사이에 빈 공간이 있을 수 있다. HashMap
Note that this container keeps its mappings in an array data structure, using a binary search to find keys. The implementation is not intended to be appropriate for data structures that may contain large numbers of items. It is generally slower than a traditional HashMap, since lookups require a binary search and adds and removes require inserting and deleting entries in the array. For containers holding up to hundreds of items, the performance difference is not significant, less than 50%.매핑을 하기 위해서 배열 자료구조를 이용하고, 키를 찾기 위해서 이진탐색을 이용함. 이 구현은 많은 수의 아이템을 가지는 자료구조에는 적합하지 않다. 이 경우에는 일반적으로 기존 HashMap 보다 느려지게 된다. 검색을 위해서 이진 탐색을 이용하고, 아이템을 추가, 삭제하는 경우에는 배열에서 연산을 수행하기 때문에 O(N)의 시간 복잡도를 사용한다. 100개 정도의 아이템을 관리하는 경우에는 성능 차이는 그리 크지 않다고 한다.
It is possible to iterate over the items in this container using keyAt(int) and valueAt(int). Iterating over the keys using keyAt(int) with ascending values of the index will return the keys in ascending order, or the values corresponding to the keys in ascending order in the case of valueAt(int).keyAt(int) 와 valueAt(int) 를 이용해서 컨테이너를 순회할 수 있다. key 값은 오름차순으로 저장되어 있기 때문에 int값을 0 부터 size-1 까지 돌리면 된다.
for(int i = 0; i < sparseArray.size(); i++) { int key = sparseArray.keyAt(i); // get the object by the key. Object obj = sparseArray.get(key); }
구현 자체가 매우 간단하기 때문에 스튜디오에서 구현을 확인하는 것을 추천.