Android’s hashmap optimization

Jieyi Wu

Follow

Feb 23, 2017 · 2 min read

Optimize the Android’s memory usage by using SparseArray and ArrayMap to instead of HashMap.

HashMap’s default capacity is 16 for keeping the data. Inside of the data struct we will explain as below.

Data struct of HashMap

I think everyone know this HashMap’s data struct as well. The data struct is as below.

Entry 0 --> Entry --> Entry 
Entry 1 --> Entry 
Entry 2 --> Entry --> Entry 
Entry 3 --> Entry --> Entry --> Entry 
Entry 4 --> Entry --> Entry
   .
   .
   . 
Entry n-1 --> Entry --> Entry --> Entry 
Entry n --> Entry

Inside of Entry’s variables

final K key;
V value; 
final int hash; 
HashMapEntry<K, V> next;

According to the variables of the HashMap, the next of Entry’s data is still an Entry data struct. The hash value is calculated by the key. So we can know if the result of the key hashed is always the same value, the specific Entry’s link will be long, cause wasting the memory and the redundant operation of allocate and free.

More detail, if the capacity is full so the mechanism is that HashMap’s space will be double. Suppose to there are a billion data. HashMap will keep all of them then HashMap will make enough space many times and calculate the hash code of each single data.

As a result, there are huge data let system become slow. In normal situation, it’s better to use SparseArray or ArrayMap instead HashMap.

SparseArray

Using SparseArray is more saving memory usage than using HashMap.
After see the variables of inside of SparseArray, we can know why SparseArray is better in some situations.

SparseArray Variable

private int[] mKeys;
private Object[] mValues;

The way of the mechanism of putting and getting

public void put(int key, E value) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    ...
}public E get(int key, E valueIfKeyNotFound) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    ...
}

In the SparseArray, it just uses Integer type for keeping the key value. And it’s using binary search for putting and getting a data.
Because the operation of the SparseArray is using binary search, the searching speed is faster than HashMap.
Time complexity of the worst case of HashMap is O(N), SparseArray is O(logN).

Using Scenario of SparseArray

• The amount of data is less than thousand.
• The data type of key must be Integer.

ArrayMap

It’s designed for optimizing the memory usage. The data type of ArrayMap is a . The operations’ mechanism of Put and Get are the same as SparseArray. So the using scenario is total same as SparseArray.

Using Scenario of ArrayMap

• The amount of data is less than thousand.
• The data type is Map.