Definition 1.
- SparseArray is a key-value mapping pair with basic int as key and Object as value. Similar SparseIntArray, SparseLongArray, SparseBooleanArray.
- It has better memory efficiency because there is no automatic boxing and unboxing and no need to create other entities (such as entries in a HashMap).
- It uses binary search to search, insert and delete, so it is not suitable for the case of large amount of data. In terms of search efficiency, it is generally not as good as HashMap, which is more prominent when the amount of data is large.
2. Application scenarios
SparseArray works with small amounts of data and can access values of specified types, such as Boolean, Long, int, to avoid auto-boxing and unboxing problems.
3. Source code analysis
private static final Object DELETED = new Object();
private boolean mGarbage = false;
@UnsupportedAppUsage(maxTargetSdk = 28) // Use keyAt(int)
private int[] mKeys;
@UnsupportedAppUsage(maxTargetSdk = 28) // Use valueAt(int), setValueAt(int, E)
private Object[] mValues;
@UnsupportedAppUsage(maxTargetSdk = 28) // Use size()
private int mSize;
Copy the codeLet’s take a look at the property definition of SparseArray. The DELETED object looks like it’s associated with deletion. The mGarbage attribute is a bool, and garbage is also associated with deletions, which can be looked at when analyzing deleted code. MKeys, mValues, and mSize
- MKeys is an array of stored keys.
- MValues is an array of stored values.
- MSize should be the number of keys stored.
public SparseArray(a) {
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 codeHere we see that the constructor needs to pass in an initial size. If the initial size is 0., it creates an empty array of int and an empty array of Object assignments. Otherwise, newUnpaddedObjectArray calls the native method vmruntime.geTrunTime (). NewUnpaddedArray (Object.class, minLen), which will create an unfilled array, Return an array of at least minLen length, but possibly larger. Therefore, mKeys are initialized using the length of the Object array instead of initialCapacity.
public E get(int key) {
// Default value is null
return get(key, null);
}
@SuppressWarnings("unchecked")
public E get(int key, E valueIfKeyNotFound) {
// Get index by binary search, negative if not present
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i < 0 || mValues[i] == DELETED) {
// Return the default value if not found or deleted
return valueIfKeyNotFound;
} else {
// Find the corresponding value to return
return(E) mValues[i]; }}Copy the codeFind the corresponding two methods, one for the default value, the other for the default value return null.
/** * Removes the mapping from the specified key, if there was any. */
public void delete(int key) {
// Get the index by binary search, invert the nearest small value if none exists
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
// I >=0
if (i >= 0) {
// If the corresponding value is not DELETED
if(mValues[i] ! = DELETED) {// Set the corresponding value to DELTED and mGarbage to true
mValues[i] = DELETED;
mGarbage = true; }}}Copy the codeDELETE and mGarbage are associated with deletions. Deletions are marked, not array compression. When is array compression performed?
private void gc(a) {
// Log.e("SparseArray", "gc start with " + mSize);
int n = mSize;
int o = 0;
int[] keys = mKeys;
Object[] values = mValues;
/ / traverse
for (int i = 0; i < n; i++) {
Object val = values[i];
// If the value is not DELETED
if(val ! = DELETED) {// And the new subscript is not equal to the old subscript
if(i ! = o) {// Move the key and value from the old location to the new location
keys[o] = keys[i];
values[o] = val;
values[i] = null;
}
// The new subscript is moved one bit backo++; }}// The flag is set to false to indicate array compression
mGarbage = false;
// The size is set to the number of key-value pairs in the new array
mSize = o;
// Log.e("SparseArray", "gc end with " + mSize);
}
Copy the codeYou can see that the gc method compresses the array and removes the NULL key. When will GC be called?
This is where all the GC methods are called. The above functions can be summarized as adding elements to the array, modifying the mValues array, and getting the SparseArray properties (key, value, size). Both methods determine whether gc is required by reading the mGarbage attribute true.
/** * Adds a mapping from the specified key to the specified value, * replacing the previous mapping from the specified key if there * was one. */
public void put(int key, E value) {
// Binary search to get the index
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
// If the array already contains
if (i >= 0) {
mValues[i] = value;
} else {
// get the array index
i = ~i;
// If the value corresponding to the location being searched is marked to be reclaimed
if (i < mSize && mValues[i] == DELETED) {
// Overwrite the value to be reclaimed
mKeys[i] = key;
mValues[i] = value;
return;
}
// If the array needs to be compressed and the number of key/value pairs exceeds or is equal to the number of key/value pairs in the array, then the array is full and needs to be expanded.
if (mGarbage && mSize >= mKeys.length) {
/ / recycling
gc();
// Research index because the array has changedi = ~ContainerHelpers.binarySearch(mKeys, mSize, key); } mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); mSize++; }}Copy the codeYou can see the overall flow of the PUT method:
-> Replace the key if the value corresponding to the key is marked as Delete. -> Replace the key and value. -> Recycle the key and recalculate the index if necessary
/** * Primitive int version of {@link #insert(Object[], int, int, Object)}. */ public static int[] insert(int[] array, int currentSize, int index, int element) { assert currentSize <= array.length; If (currentSize + 1 <= array.length) {// If (currentSize + 1 <= array.length) { System. Arraycopy (array, index, array, index + 1, currentSize - index); // Array [index] = element; return array; } / / if more than the length of the array, then super-popular int [] newArray = ArrayUtils. NewUnpaddedIntArray (growSize (currentSize)); System. Arraycopy (array, 0, newArray, 0, index); // set newArray[index] = element; Copy the old array index into the new array index+1 Arraycopy (array, index, newArray, index + 1, array.length-index); return newArray; } public static int growSize(int currentSize) {return growSize <= 4? 8 : currentSize * 2; }Copy the codeIf the size of the key does not exceed the size of the array, you can directly add the key; otherwise, you need to expand before adding the key. The method of adding the value is exactly the same.
Add also has a method append,
/** * Puts a key/value pair into the array, optimizing for the case where * the key is greater than all existing keys in the array. */
public void append(int key, E value) {
If the key is less than or equal to the maximum key, the normal method is called
if(mSize ! =0 && key <= mKeys[mSize - 1]) {
put(key, value);
return;
}
if (mGarbage && mSize >= mKeys.length) {
gc();
}
// Put the data directly into the mSize location, where you can see the append method called GrowingArrayUtils
mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
mValues = GrowingArrayUtils.append(mValues, mSize, value);
mSize++;
}
Copy the codeIf you know that the key is greater than all the keys in the array, you simply add the data to the last position of the array in order.