Previous post we discussed about SparseArray and its friends in Android. While they can replace HashMap when integer and long are used as key. It doesn’t work when the key is an arbitrary object.
Actually similar ideas can be applied to create more memory efficient generic map data structure. This post will go through ArrayMap, ArraySet and their friends, which replaces HashMap and HashSet in a more memory efficient way.
ArrayMap implements Map<K, V> interface, and it’s fully compatible with HashMap. There’a simplified version of ArrayMap: SimpleArrayMap, which doesn’t have the burden of maintaining compatibility with Java Map inteface, but still provides most of the commonly needed methods.
Correspondingly there’s ArraySet implements the Set<V> interface.
We should consider using ArrayMap and ArraySet at the following cases.
1. The number items is less than 1000.
2. Frequent reading, insertion and removal are less frequent.
And if we don’t need to maintain compatibility with Java interface, we can use SimpleArrayMap where ArrayMap is used.
We have described how HashMap works internally at SparseArray and its friends in Android. Basically it uses an array of linked list, and lots of unused space is allocated in the array.
For ArrayMap, two arrays are used. One is used to store the hash code of all keys, and the other is used to store the key value pairs. Key is stored at the even index, and value is saved at odd index.
Figure 1. Internal arrays in ArrayMap [image from ref 1]
Binary search is applied on the hash code array to locate the index, and the same index is used in the second array to store and retrieve key and value. Specifically,
1. For get, the hash code of key is computed and used in binary search to find the index. Then two searches are performed to find the equal key in the second array. One is searching forward, and the other is search backward. If no equal key is found, null is returned.
2. For put, if an equal key is found, the value is updated; otherwise a new key, value pair is inserted at the end of the equal hash code range. Array resizing might be applied in the process.
3. ArrayMap internally caches the arrays of size 4 and 8, to avoid spamming garbage. This further improves the memory efficiency when number of items in the map is small.
Advantages and Disadvantages
The internals of ArrayMap offers the following advantages compared with HashMap.
1. It’s more memory efficient. There’s no unused space allocated.
2. When there’s no element, ArrayMap doesn’t allocate memory, whereas HashMap allocates unused space.
3. Iteration with keyAt and valueAt is just like iterating an array. It’s very efficient. HashMap uses Iterator, which is slower and takes more memory.
But these advantages are not free,
1. Accessing a value from ArrayMap is O(logn), whereas in HashMap is O(1). This makes not much difference when number of elements in the Map is less than 1000.
2. Insertion and Deletion are relatively expensive, since we need to shift array elements, or allocate new array and copy elements over.
1. Android Fun with ArrayMaps performance video.