• What is SparseArray?
• What data structure does its internal implementation adopt?
• What are the advantages and disadvantages of SparseArray compared with HashMap?

What is SparseArray?

SparseArray stores key value pairs, with int as the key and Object as the value. Sparse means sparse and missing. SparseArray application scenarios are relatively scarce data, usually within a few hundred.

What data structure does SparseArray use?

SparseArray does not use one-dimensional array + single linked list and binary tree structure like HashMap, but two one-dimensional arrays, one for storing key(int type) and the other for storing value object.

    private int[] mKeys; // Store key
    private Object[] mValues; // Store value object
    private int mSize; // Record the number of stored key value pairs

The subscripts used in reading and writing mKeys and mValues correspond one-to-one.

What is the default capacity of SparseArray?

SparseArray specifies its default capacity size in the default constructor. The default is 10

After initialization, mSize = 0, instantiate mKeys and mValues.

Process analysis of SparseArray get method

Enter an int key and find the matching subscript by dichotomy. If no corresponding subscript is found, null or user specified default object is returned.

Keys are stored incrementally. When searching for subscripts by dichotomy, a negative value may be returned, which means that the corresponding key is not found in mKeys.

    public E get(int key) {
        return get(key, null);
    }

    /**
     * Gets the Object mapped from the specified key, or the specified Object
     * if no such mapping has been made.
     */
    @SuppressWarnings("unchecked")
    public E get(int key, E valueIfKeyNotFound) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key); // Dichotomy lookup subscript

        if (i < 0 || mValues[i] == DELETED) { 
        // If the index found is negative or the current position element is deleted, it indicates that it is not found
            return valueIfKeyNotFound;
        } else {
            return (E) mValues[i]; // The specified element was found
        }
    }

Process analysis of SparseArray put method

public void put(int key, E value) {
       // Find the subscript of key by dichotomy
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i >= 0) {
            // Represents the existing key and its corresponding value, and directly replaces value
            mValues[i] = value;
        } else {
            // Indicates that there is no key currently, a new key value pair should be added
            // i negates to get the subscript of the array position to be added. Binary search returns the subscript of the "should" storage location of the key.
            i = ~i;

            if (i < mSize && mValues[i] == DELETED) {
                // The element in the original position has been deleted and replaced by direct assignment
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }

            if (mGarbage && mSize >= mKeys.length) {
                // Insufficient capacity for recycling
                gc();
                // Rediscover target subscript
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }
            // The target subscript is i, and the key is added to the mKeys array
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            // The target subscript is i, and the value is inserted into the mValues array
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            // Number of stored data plus 1
            mSize++;
        }
}

// GrowingArrayUtils.java
public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
        assert currentSize <= array.length;

        if (currentSize + 1 <= array.length) {
            // The current array has sufficient capacity, and the elements starting with index are moved back by 1 bit
            System.arraycopy(array, index, array, index + 1, currentSize - index);
            array[index] = element;
            return array;
        }

        // Insufficient capacity, expand the capacity to generate a new array newArray
        @SuppressWarnings("unchecked")
        T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(),
                growSize(currentSize));
        // Copy the part before the original array index to the new array object
        System.arraycopy(array, 0, newArray, 0, index);
        newArray[index] = element; // Insert element
        // Copy the elements after index+1 of the original array to the new array
        System.arraycopy(array, index, newArray, index + 1, array.length - index);
        return newArray;
    }

// Expansion calculation rule: if the current capacity is less than or equal to 4, 8 is returned; Otherwise, it returns twice the capacity
// The minimum capacity after expansion is 8
public static int growSize(int currentSize) {
        return currentSize <= 4 ? 8 : currentSize * 2;
}

Analysis of binary search method for key subscript

Binary lookup method containerhelpers binarySearch(int[] array, int size, int value)

    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
    }

If the subscript corresponding to the input value is not found, a bitwise reversed value (generally a negative value) will be returned.

For example, the input array is [1,2,4,5], size is 4, and value is 3; Then you get the inverse of 2. And 2 is the target position subscript of value.

What is the maximum capacity of SparseArray? How much is each expansion?

SparseArray does not define the maximum capacity like HashMap. The maximum capacity can reach integer MAX_ Value, may report oom. During each capacity expansion, if the current capacity is less than 5, the capacity expansion is 8, otherwise the capacity expansion is twice the original capacity.

public static int growSize(int currentSize) {
        return currentSize <= 4 ? 8 : currentSize * 2;
}

What is the application scenario of SparseArray compared with HashMap?

• SparseArray does not use hash algorithm, but HashMap uses hash algorithm.
• SparseArray uses two one-dimensional arrays to store keys and values respectively. HashMap uses one-dimensional array + one-way linked list or binary tree.
• SparseArray key can only be int type, while HashMap key is Object.
• SparseArray key is an ordered storage (in ascending order), while HashMap is not.
• The default capacity of SparseArray is 10, while the default capacity of HashMap is 16.
• SparseArray defaults to twice the original capacity for each expansion, while HashMap defaults to 0.75 times the original capacity for each expansion
• SparseArray value storage is not wrapped with an additional entity class (Node) like HashMap
• Generally speaking, sparsearay search elements are inferior to HashMap, because sparsearay search needs to go through the process of dichotomy, and HashMap has no conflict. The subscript corresponding to hash in the technical department can get the value directly.

For the above comparison with HashMap, SparseArray or HashMap is recommended to be selected according to the following requirements:

• If you have high memory requirements and no great requirements for query efficiency, you can use SparseArray
• SparseArray with a number of hundreds has better advantages than HashMap
• The key is required to be of type int, because HashMap will change the custom packing of int to Integer
• The key s are required to be ordered and in ascending order

[Android zero foundation tutorial video reference]