Collections are the most common thing used in the software development. In general whenever we required to store data in key value pairs, the very first data structure that comes to our mind is HashMap. It is quite flexible hence it is the most preferred data structure choice to store key value pairs.
To improve the performance of Android application, Android system provides set of collections build especially for mobile development.
So ArrayMap and SparseArray are intended to be more memory efficient than using a HashMap.
How HashMap works?
HashMap is basically an Array of HashMap.Entry objects. Entry is inner class of HashMap which holds the key and values.
When a key-value pair is inserted into a HashMap, a hashCode of the key is calculated, and that value is assigned to the hashCode variable of EntryClass. Now using hashCode, we can get the index of the bucket where it will be stored. In case bucket has a pre-existing element, the new element is inserted with the last element pointing to new one essentially making the bucket a linked list.
It has a constant time, or O(1) time requirement for retrieving an element from the array. This means that it takes the same time to pull any element from the array, regardless of the size. This is possible by using a hashing function, which generates the array indices, given the input key.
A Hashmap is used to map Integer keys to an object.
Below are the example code to create HashMap and fetch keys and values:
How ArrayMap works?
ArrayMap contains two small array instead of one in a HashMap. The first array (Hash-Array) contains the specified hash keys in sorted order. The second array (Key Value Array) stores the keys and values of the objects according to the first array.
When we fetch an item, a binary-search is done on the Hash-Array to find a matching hash the index and then directly return the key-value pair from the second array (Key Value Array). If the key in the second array (Key Value Array), doesn’t match then a linearly walk is done over the second array (Key Value Array) to resolve the collision.
Below are the example code to create ArrayMap and fetch keys and values:
How SparseArray works?
The main difference from ArrayMap is that, in SparseArray key is always primitive types. In other respects the principle of operation is similar. Sparse arrays can be used to replace hash maps when the key is a primitive type. SparseArray is designed to remove the auto-boxing problem (ArrayMap does not avoid the auto-boxing problem). This approach affects the memory consumption.
Below are the example code to create SparseArray:
Class appear even in the API 1, but has been redesigned in the API 11. The updated version SparseArrayCompat also available for older devices in the compatibility library.
There are several other types of SparseArray:
LongSparseArray, SparseIntArray, SparseBooleanArray etc.
HashMap can be replaced by the followings Array Class:
Continuous allocation and de-allocation of memory along with garbage collection will cause lag in Android application and it reduces the application performance. Other than this ArrayMap & SparseArray avoid memory problem by using 2 small arrays rather than one big one.
Benefits to use SparseArray over HashMap is:
· More memory efficient by using primitives
· No auto-boxing
· For large collections, it is slower
· It only available for Android
In general if inserts or deletes are fairly infrequent, and the number of items is < 1000 then ArrayMap / SparseArray classes are really good replacement classes.
This video from Android developers will provide you further details.
As we can conclude that the SparseArray is a more efficient solution than using a Hashmap to map Integers to objects. The theory is that the SparseArray can add and retrieve elements quicker than a HashMap (<1000), in this case, by removing the hashing function processing time.
Thanks for reading. To help others please click ❤ to recommend this article if you found it helpful.
Check out my blogger page for more interesting topics on Software development.