About SparseArray

SparseArray is a container provided with the Android SDK for mapping Integers to objects. It is more memory efficient than a HashMap because it avoids automatic boxing of keys and does not require additional objects to represent mappings.

SparseArray uses binary lookup for keys, which means keys are stored in order and are not suitable for large amounts of data. In general, its lookup is slower than a HashMap.

To improve performance, SparseArray does not immediately adjust the data structure when deleting a key, but instead marks the entry as deleted, which can be reused later when using the same key or adjusted during garbage collection operations.

Garbage collection occurs when you need to expand, get size, or retrieve item values

Source code analysis

The constructor

SparseArray has two constructors

private int[] mKeys;
private Object[] mValues;
public SparseArray() {                                                  
    this(10);                                                           
}                                                                       
                                                                                                                                            
public SparseArray(int initialCapacity) {                               
    if (initialCapacity == 0) {                                         
        mKeys = EmptyArray.INT;                                         
        mValues = EmptyArray.OBJECT;                                    
    } else {                                                            
        mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);   
        mKeys = new int[mValues.length];                                
    }                                                                   
    mSize = 0;                                                          
}
Copy the code

If you use an unspecified initialization capacity, the default is 10, and you can see that SparseArray internally uses two arrays to store keys and values

put

If the key does not exist, add it; otherwise, replace it

public void put(int key, E value) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); If (I >= 0) {// key already exists, replace mValues[I] = value; } else {// key does not exist, I = ~ I; If (I < mSize && mValues[I] == DELETED) {// Reuse the entry marked as DELETED mKeys[I] = key; mValues[i] = value; return; } if (mGarbage &&msize >= mkeys.length) {// Garbage (); // Search again because indices may have changed. i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); } // insert new entries mKeys = GrowingArrayUtils. Insert (mKeys, mSize, I, key); mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); mSize++; } } static int binarySearch(int[] array, int size, int value) { int lo = 0; int hi = size - 1; while (lo <= hi) { final int mid = (lo + hi) >>> 1; final int midVal = array[mid]; if (midVal < value) { lo = mid + 1; } else if (midVal > value) { hi = mid - 1; } else { return mid; // value found } } return ~lo; // value not present }Copy the code

BinarySearch is an implementation of the binarySearch algorithm. Note that ~lo is returned if no binarySearch is found

Here,
loIt can be considered that, although the specified value was not found, this is the closest, in other words, this is where the specified value should be inserted

For example, if you look for 5 in 1,2,3,4,6,7, binarySearch will return ~4

get

Get operation is relatively simple, the same binary search key, return if there is, otherwise return the default value

public E get(int key, E valueIfKeyNotFound) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i < 0 || mValues[i] == DELETED) { return valueIfKeyNotFound; } else { return (E) mValues[i]; }}Copy the code

remove

The remove operation actually calls the delete method

public void delete(int key) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { if (mValues[i] ! = DELETED) {// Only marked as DELETED mValues[I] = DELETED; MGarbage = true; }}}Copy the code

size

After calling size, the first check is made to see if a GC or reclaim operation is required

public int size() {   
    if (mGarbage) {   
        gc();         
    }                 
                      
    return mSize;     
}
Copy the code

gc

Gc is checked whenever size and index-related methods, such as keyAt, are called

private void gc() { // Log.e("SparseArray", "gc start with " + mSize); int n = mSize; int o = 0; int[] keys = mKeys; Object[] values = mValues; for (int i = 0; i < n; I ++) {// Delete DELETED Object val = values[I]; if (val ! = DELETED) { if (i ! = o) { keys[o] = keys[i]; values[o] = val; values[i] = null; } o++; } } mGarbage = false; mSize = o; // Log.e("SparseArray", "gc end with " + mSize); }Copy the code

conclusion

SparseArray uses two arrays to store keys and values respectively. Key is int[], which avoids automatic boxing and is in ascending order. Therefore, binary search can be used to find keys, which is less memory than HashMap, but slower retrieval speed. SparseArray can be used instead of HashMap for small data volumes