- The analysis of HashMap shows that when the capacity reaches 75%, it needs to be expanded, which means that 25% of the memory space is wasted. To solve this problem, SparseArray was created.
- This article uses JDK1.8, different versions of the source code is different.
- Can first eat Android development to understand the data structure – HashMap source code.
1. The SparseArray characteristics
- SparseArray is structured as a binary array, meaning that the key and value are arrays with one-to-one subscripts.
- SparseArray is key-valye, but keys can only be int instead of HashMap
, which is also a disadvantage, and LongSparseArray.
- HashMap handles keys of type int that need to be bogged down into integers, consuming some resources, whereas SparseArray does not need to be bogged down and is faster.
- A HashMap stores data in Entry objects and computes a hashCode, which is larger in memory than SparseArray.
- SparseArray is faster and uses binary search, which requires keys to be ordered.
- Binary lookup is fast, but it has no advantage over HashMap for large amounts of data.
2. Common methods of SparseArray
2.1 Basic Parameters
- DELETED is the location of the DELETED item, and SparseArray deletion is similar to marking, which eliminates the need to move the array and reduces the time it takes to move the array.
- The mGarbage flag is a flag that is true if there is deletion and is used in subsequent GC () methods.
- You can see that SparseArray’s keys and values are arrays.
- There is also a length mSize, like List and Map, which is the actual length of the data, not the size of the capacity.
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 code2.2 Construction method
- There are two ways to construct it. You can either fill in the capacity or leave it blank. The default capacity is 10.
- If the capacity is zero, a very lightweight array is created.
/** * Creates a new SparseArray containing no mappings. */
public SparseArray(a) {
this(10);
}
/** * Creates a new SparseArray containing no mappings that will not * require any additional memory allocation to store the specified * number of mappings. If you supply an initial capacity of 0, the * sparse array will be initialized with a light-weight representation * not requiring any additional array allocations. */
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
// No data has been put in yet, so mSize is 0.
mSize = 0;
}
Copy the code2.3 binary search ContainerHelpers. BinarySearch (mKeys, mSize, key)
- Use dichotomy to find the subscript of the key to be placed in the element. If not, return the inverse of the small value of the dichotomy range.
// A simple binary search
// This is Arrays.binarySearch(), but doesn't do any argument validation.
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 the middle number is less than the target value
if (midVal < value) {
// The minimum range to retrieve is the middle +1
lo = mid + 1;
} else if (midVal > value) {
// If greater than, the maximum range is in the middle of -1
hi = mid - 1;
} else {
// Return the subscript position
return mid; // value found}}// if no, return lo
return ~lo; // value not present
}
Copy the codePut (int key, E value)
- If the key position already exists, overwrite it directly.
- If no subscript is found for key, and there is an idle position deleted in the range, the current data is placed in that position.
- If none of these satisfy the criteria, the gc() method is called to sort through the data, mark the deleted location, dry it out, and insert the data.
- If the original capacity is less than 4, expand to 8; otherwise, double the size.
- The insertion of an array requires moving the elements behind it.
/** * 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) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
mValues[i] = value;
} else {
/ / the not
i = ~i;
// If I is less than the length and there is nothing at I, place it at I.
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
// If there is garbage (deleted things) and the data capacity is greater than or equal to the length of the key array
if (mGarbage && mSize >= mKeys.length) {
// Get the data sorted
gc();
// find the index position again
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
// Insert datamKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); mSize++; }}//GrowingArrayUtils.insert
/**
* 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) {
System.arraycopy(array, index, array, index + 1, currentSize - index);
array[index] = element;
return array;
}
int[] newArray = new int[growSize(currentSize)];
System.arraycopy(array, 0, newArray, 0, index);
newArray[index] = element;
System.arraycopy(array, index, newArray, index + 1, array.length - index);
return newArray;
}
//GrowingArrayUtils.growSize
If the capacity is less than 4, expand the capacity to 8, otherwise double the size.
/** * Given the current size of an array, returns an ideal size to which the array should grow. * This is typically double the given size, but should not be relied upon to do so in the * future. */
public static int growSize(int currentSize) {
return currentSize <= 4 ? 8 : currentSize * 2;
}
Copy the code2.5 Collating Data GC ()
- Move data from non-deleted locations forward one by one.
- MGarbage is set to false.
private void gc(a) {
// 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);
}
Copy the codeRemove (int key) or delete(int key)
- We know that the real array deletion is to move the following elements, which will cause a lot of operations each time, so we change to mark clear, mark first, you can reuse the free space on the element, or later on the gc clean once again.
/**
* Alias for {@link #delete(int)}.
*/
public void remove(int key) {
delete(key);
}
/** * Removes the mapping from the specified key, if there was any. */
public void delete(int key) {
// Use dichotomy to find the subscript corresponding to the data to be deleted
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if(mValues[i] ! = DELETED) { mValues[i] = DELETED; mGarbage =true; }}}Copy the codeGet (int key)
- Use binary lookup to find the subscript for the key and return the value of the same subscript position.
- The two-parameter method can also be set to a default value that cannot be found and returned if not, otherwise null.
/** * Gets the Object mapped from the specified key, or null * if no such mapping has been made. */
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);
if (i < 0 || mValues[i] == DELETED) {
return valueIfKeyNotFound;
} else {
return(E) mValues[i]; }}Copy the code2.8 Finding the Subscript of a Key indexOfKey(Int Key)
- If there is marked garbage, clean it up first and then put back the subscript corresponding to the key.
/**
* Returns the index for which {@link #keyAt} would return the
* specified key, or a negative number if the specified
* key is not mapped.
*/
public int indexOfKey(int key) {
if (mGarbage) {
gc();
}
return ContainerHelpers.binarySearch(mKeys, mSize, key);
}
Copy the code2.9 Finding indexOfValue(E value)
- We’re still going to sort through the data before we look it up, so it might be stored in different places, so after we go through it, we’ll return the first one, and if we can’t find it, we’ll return -1.
/**
* Returns an index for which {@link #valueAt} would return the
* specified value, or a negative number if no keys map to the
* specified value.
* <p>Beware that this is a linear search, unlike lookups by key,
* and that multiple keys can map to the same value and this will
* find only one of them.
* <p>Note also that unlike most collections' {@code indexOf} methods,
* this method compares values using {@code ==} rather than {@code equals}.
*/
public int indexOfValue(E value) {
if (mGarbage) {
gc();
}
for (int i = 0; i < mSize; i++) {
if (mValues[i] == value) {
returni; }}return -1;
}
Copy the code2.10 the length of the size ()
- The length of the returned data.
/** * Returns the number of key-value mappings that this SparseArray * currently stores. */
public int size(a) {
if (mGarbage) {
gc();
}
return mSize;
}
Copy the code