This time, thoroughly understand the SparseArray implementation principle

I've been sorting out SparseArray This knowledge point , Find most of the Internet SparseArray There are many problems in the articles of principle analysis （ It can be said that many authors did not understand SparseArray Source code ）, That's why , That's why this article . We know ,SparseArray And ArrayMap yes Android Medium efficient storage K-V Data structure of , It's also Android Frequent visitors in the interview , It is necessary to understand their implementation principles , This article is based on SparseArray Take the source code of .

One 、SparseArray Class structure of

SparseArray Can be translated as Sparse array , It can be understood literally as a loose and discontinuous array . Although it's called Array, But it is storage K-V A data structure of . among Key Can only be int type , and Value yes Object type . Let's take a look at its class structure ：

public class SparseArray<E> implements Cloneable {
    //  The value used to mark here has been deleted 
    private static final Object DELETED = new Object();
    //  Used to mark whether any elements have been removed 
    private boolean mGarbage = false;
    //  Used to store key Set 
    private int[] mKeys;
    //  Used to store value Set 
    private Object[] mValues;
    //  Number of elements stored 
    private int mSize;
    
    //  The default initial capacity is 10
    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;
    }
    
    // ... Omit other code 

}

You can see SparseArray Just implemented Cloneable The interface does not implement Map Interface , also SparseArray One was maintained internally int Array and a Object Array . A parameterized constructor was called in a nonparametric constructor , And set its initial capacity to 10.

Two 、SparseArray Of remove() Method

Do you think it's strange ？ As a container class , No first put Method how to first remove Well ？ This is because remove Some operations of the method will affect put The operation of . Only after first understanding remove To make it easier to understand put Method . Let's see remove Code for ：

// SparseArray
public void remove(int key) {
    delete(key);
}

public void delete(int key) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED;
            mGarbage = true;
        }
    }
}

You can see remove The method is called directly delete Method . And in the delete In the method, you will first find by bisection （ Binary search code back analysis ） find key Where it is , And then put the... In this position value Value is set to DELETE, Be careful , There will also be mGarbage Set up in order to true To mark the presence of deleted elements in the collection . Imagine , After deleting multiple elements, whether there may be discontinuities in the collection ？ Maybe this is also SparseArray The origin of the name .

3、 ... and 、SparseArray Of put() Method

As a storage K-V Type of data structure ,put The method is key and value Entrance . It's also SparseArray One of the most important methods in . Let's start with put Method code ：

// SparseArray
public void put(int key, E value) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) { //  Means before mKeys There is already a corresponding key There is , The first i The three positions correspond to key.
        mValues[i] = value; //  Direct updating value
    } else { //  A negative number is returned indicating that the mKeys Look for to key
      
        //  Invert to get to be inserted key The location of 
        i = ~i;
      
    //  If the insertion position is less than size, And in this position value It happened to be deleted , So directly key and value Insert separately mKeys and mValues Of the i A place 
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }
    // mGarbage by true Indicates that an element has been removed , here mKeys Is already full , however mKeys The inside is marked as DELETE The elements of 
        if (mGarbage && mSize >= mKeys.length) {
            //  call gc Method move mKeys and mValues The elements in , This method can be analyzed later 
            gc();
                    
            //  because gc Method moves the array , Therefore, the insertion position may change , So you need to recalculate the insertion position 
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        } 
    // GrowingArrayUtils Of insert Method will move all data after the insertion position back one bit , And then key and value Insert into mKeys and mValue The corresponding i A place , If the array space is insufficient, capacity expansion will be started , We will analyze this later insert Method 
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

Although this method has only a few lines , But it is not easy to fully understand , It's not easy to read even if you write detailed notes . We might as well analyze it in detail . The first line of code gets a by binary search index. Look at the code of binary search ：

// ContainerHelpers
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
}

We are all familiar with binary search , This algorithm is used to find the position of an element in an ordered array . If this element exists in the array , Return the corresponding position of this element to . If it does not exist, then at this time lo Is the best place to store this element . The code above will lo The inverse is taken as the return value . because lo Must be greater than or equal to 0 Number of numbers , Therefore, the return value after negation must be less than or equal to 0. I understand that , Look again. put Method if...else Is it easy to understand ？

// SparseArray
public void put(int key, E value) {
 
    if (i >= 0) { 
        mValues[i] = value; //  Direct updating value
    } else { 
        i = ~i;
        // ...  Omit other code 
    }
}

If i>=0, It means the current key Already in existence mKeys It's in , So at this time put Just put the latest value Update to mValues Then you can . And if the i<=0 Means mKeys There is no corresponding before key. So we need to put key and value Insert into mKeys and mValues in . And the best place to insert is right i Take the opposite .

After getting the insertion position , If this location is an element marked for deletion , It can be directly covered for so long , Therefore, there is the following code ：

public void put(int key, E value) {
    // ...
    if (i >= 0) {
        // ...
    } else {    
        //  If i The corresponding position is deleted , It can be directly overwritten 
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }
        // ...
    }
    
}

If the above conditions are not met , So keep looking down ：

public void put(int key, E value) {
    // ...
    if (i >= 0) {
        // ...
    } else {    
    // mGarbage by true Indicates that an element has been removed , here mKeys Is already full , however mKeys The inside is marked as DELETE The elements of 
        if (mGarbage && mSize >= mKeys.length) {
            //  call gc Method move mKeys and mValues The elements in , This method can be analyzed later 
            gc();
                    
            //  because gc Method moves the array , Therefore, the insertion position may change , So you need to recalculate the insertion position 
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        } 
        // ...
    }
    
}

We already know above , stay remove When the elements mGarbage Will be set to true, This code means that there are removed elements , The position to be removed is not the position to be inserted , And if the mKeys Is already full , So call gc Method to move the element fill where it was removed . because mKeys The position of the element in has changed , therefore key The insertion position may also change , So you need to call the dichotomy again to find key Where to insert .

The above code will be finalized key Where it's inserted , Next call GrowingArrayUtils Of insert Method to do key Insert operation of ：

// SparseArray
public void put(int key, E value) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) { 
        // ...
    } else { 
         // ...

    // GrowingArrayUtils Of insert Method will move all data after the insertion position back one bit , And then key and value Insert into mKeys and mValue The corresponding i A place , If the array space is insufficient, capacity expansion will be started , We will analyze this later insert Method 
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

GrowingArrayUtils Of insert The method code is as follows ：

// GrowingArrayUtils
public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
    assert currentSize <= array.length;
    //  If the array is inserted size Less than array length , Able to insert 
    if (currentSize + 1 <= array.length) {
        //  take index All subsequent elements move backward one bit 
        System.arraycopy(array, index, array, index + 1, currentSize - index);
        //  take key Insert into index The location of 
        array[index] = element;
        return array;
    }

    //  Coming here shows that the array is full , Capacity expansion is required .newArray That is, the expanded array 
    T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(),
            growSize(currentSize));
    System.arraycopy(array, 0, newArray, 0, index);
    newArray[index] = element;
    System.arraycopy(array, index, newArray, index + 1, array.length - index);
    return newArray;
}

//  Return to the expanded size
public static int growSize(int currentSize) {
    return currentSize <= 4 ? 8 : currentSize * 2;
}

insert Method code is easy to understand , If the array has enough capacity , Then we will index The next element moves one bit backward , And then key Insert index The location of . If the array capacity is insufficient , Then you need to expand the capacity , Then insert .

Four 、SparseArray Of gc() Method

This method is actually easy to understand , We know Java When the virtual machine is out of memory, it will GC operation , In order to avoid memory fragmentation after garbage objects are collected, the mark removal method , Will move the living object to one end of memory . and SparseArray In this gc In fact, the method refers to the idea of garbage collection and defragmentation .

About mGarbage This parameter has been mentioned above , This variable will be set to when the element is deleted true. as follows ：

// SparseArray In all methods that remove elements in the mGarbage Set as true

public E removeReturnOld(int key) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        if (mValues[i] != DELETED) {
            final E old = (E) mValues[i];
            mValues[i] = DELETED;
            mGarbage = true;
            return old;
        }
    }
    return null;
}

public void delete(int key) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED;
            mGarbage = true;
        }
    }
}

public void removeAt(int index) {
    if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {
        throw new ArrayIndexOutOfBoundsException(index);
    }
    if (mValues[index] != DELETED) {
        mValues[index] = DELETED;
        mGarbage = true;
    }
}

and SparseArray All methods of inserting and finding elements in the will determine if mGarbage by true, also mSize >= mKeys.length Called when the gc, With append Methods as an example , The code is as follows ：

public void append(int key, E value) {

    if (mGarbage && mSize >= mKeys.length) {
        gc();
    }
  
   // ...  Omit irrelevant code 
}

Call in source code gc There are as many ways as 8 It's about , Are methods related to adding and finding elements . for example put()、keyAt()、setValueAt() Among other methods .gc The implementation of is actually relatively simple , Is to move all the data after deleting the location forward , The code is as follows ：

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++) {
        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);
}

5、 ... and 、SparseArray Of get() Method

This method is relatively simple , because put Is to maintain an ordered array , Therefore, through binary search, we can directly determine key Position in the array .

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];
    }
}

6、 ... and 、 summary

so SparseArray Is a very simple data structure to use , But its principle seems not so easy to understand . This is also the correspondence of most articles on the Internet SparseArray The analysis of is ambiguous . I believe that the study of this article must be right SparseArray Has a new understanding of the implementation of ！

In this paper, from https://juejin.cn/post/6972985532397649933, If there is any infringement , Please contact to delete .