SparseArray and ArrayMap are both alternatives to HashMap. The main purpose is to save memory, which is valuable on mobile phones. There is a slight efficiency sacrifice, but if the number of stored elements is less than 1000, there is no difference between the efficiency of a HashMap;
A, SparseArray
1. Member variables and constructors
Let’s start by looking at some of the more important member variables and constructors
Member variables
DELETED at comment 1 is used to mark elements when they are DELETED, as we will see later in the remove method;
MGarbage at comment 2 is also used to mark the removal of elements, as seen in the remove method;
Note 3: the mKeys array is used to hold keys of int.
Note 4: The mValues array is used to store key-value pairs of value of type Object.
MSize in comment 5 indicates the number of key-value pairs stored.
//1
private static final Object DELETED = new Object();
//2
private boolean mGarbage = false;
@UnsupportedAppUsage(maxTargetSdk = 28) // Use keyAt(int)
//3
private int[] mKeys;
@UnsupportedAppUsage(maxTargetSdk = 28) // Use valueAt(int), setValueAt(int, E)
//4
private Object[] mValues;
@UnsupportedAppUsage(maxTargetSdk = 28) // Use size()
//5
private int mSize;
Copy the codeA constructor
The two constructors are shown below. The default no-parameter constructor has a capacity of 10. We can also initialize the capacity value by passing an int value;
/**
* Creates a new SparseArray containing no mappings.
*/
public SparseArray() {
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];
}
mSize = 0;
}
Copy the codeNow let’s look at some of the more important ones;
2, put method
The put method is as follows. The key can only be an int.
The binarySearch method at note 1, also known as binarySearch, is described separately below;
Note 2: There is a key-value pair corresponding to the key. In this case, update the mValues array directly.
Note that I =~ I in comment 3, and we’ll see what that means after we analyze binary lookup;
Note 4: The value of index I corresponding to this key has been deleted, and index I is smaller than mSize.
Note 5 The branch indicates that key/value pairs marked DELETED are cleared and the index value is re-evaluated by binary lookup because the index of the element may change after deletion.
The insert method in comment 6 is recreated as an array copy, which we’ll cover separately below.
/** * 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) { //1 int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { //2 mValues[i] = value; } else { //3 i = ~i; if (i < mSize && mValues[i] == DELETED) { //4 mKeys[i] = key; mValues[i] = value; return; } if (mGarbage && mSize >= mKeys.length) { //5 gc(); // Search again because indices may have changed. i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); } //6 mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); mSize++; }}Copy the codeLet’s start with the binary lookup method in comment 1 above
There’s nothing special about this method. It’s just a traditional binary lookup, but it does not return null or -1 if a key is not found in the array. If no key is found, return ~lo, i.e. the index value of the left edge of the key in the array is reversed. This explains why I =~ I in comment 3 above does that;
// 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 (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
return mid; // value found
}
}
//1
return ~lo; // value not present
}
Copy the codeIf you look at insert, comments 1, 2, and 3 call arrayCopy (arrayCopy).
/**
* Inserts an element into the array at the specified index, growing the array if there is no
* more room.
*
* @param array The array to which to append the element. Must NOT be null.
* @param currentSize The number of elements in the array. Must be less than or equal to
* array.length.
* @param element The element to insert.
* @return the array to which the element was appended. This may be different than the given
* array.
*/
public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
assert currentSize <= array.length;
if (currentSize + 1 <= array.length) {
//1
System.arraycopy(array, index, array, index + 1, currentSize - index);
array[index] = element;
return array;
}
@SuppressWarnings("unchecked")
T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(),
growSize(currentSize));
//2
System.arraycopy(array, 0, newArray, 0, index);
newArray[index] = element;
//3
System.arraycopy(array, index, newArray, index + 1, array.length - index);
return newArray;
}
Copy the codeInsert key (mKeys); insert key (mKeys); insert key (mKeys);
3. Get method
After looking at the PUT method, let’s look at the get method. Now that we understand the PUT method, the get method is easier to understand.
Comment 1 indicates that the get method calls the get method with two parameters. The second parameter indicates that if no corresponding value is found, the value of the second parameter is used.
Note 2: binary search is used to find index I by key.
Note 3 If the index I is less than 0, the corresponding index is not found. MValues [I]==DELETED indicates that the key-value pair at the index has been DELETED.
Note 4 indicates that it has been found.
/** * Gets the Object mapped from the specified key, or <code>null</code> * if no such mapping has been made. */ public E get(int key) { //1 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) { //2 int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i < 0 || mValues[i] == DELETED) { //3 return valueIfKeyNotFound; } else { //4 return (E) mValues[i]; }}Copy the code4, remove method
Add, delete, change, and check is still missing the delete method, so let’s go on to the remove method
The delete method is also called in comment 1, so the two methods are the same; Let’s move on to the delete method;
Note 2 also uses binary lookup to convert key to index I.
If the branch I at comment 3 is greater than or equal to 0, there is a key-value pair corresponding to this key.
Note 4: mValues[I] = DELETED,mGarbage = true, these two operations perform the deletion process, so it can be seen that the deletion is not actually DELETED, but marked as DELETED.
/** * Alias for {@link #delete(int)}. */ public void remove(int key) { //1 delete(key); } /** * Removes the mapping from the specified key, if there was any. */ public void delete(int key) { //2 int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { //3 if (mValues[i] ! = DELETED) { //4 mValues[i] = DELETED; mGarbage = true; }}}Copy the code5. Gc method
After the introduction of the main knowledge points, we found that SparseArray is borrowed from the idea of HashMap, with the help of binary search to improve efficiency; The most important of these is the memory reduction. In the PUT method, we found that the array size is only expanded when the size is insufficient, and gc is performed before the expansion to ensure that no space is wasted. Let’s take a look at how gc operates. The GC method is shown below.
Note 1 indicates that each element in the mValues array is iterated and saved only if it is not marked as DELETED, thus removing the elements marked as DELETED from the list. Thus reducing memory;
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) { //1 if (i ! = o) { keys[o] = keys[i]; values[o] = val; values[i] = null; } o++; } } //2 mGarbage = false; mSize = o; // Log.e("SparseArray", "gc end with " + mSize); }Copy the codeSecond, ArrayMap
The idea of ArrayMap is similar to SparseArray. The purpose of ArrayMap is to solve the limitation of SparseArray’s key can only be int. In ArrayMap, key and value are both generic. A few key member attributes are introduced before analyzing the methods;
1. Member attributes
The mHashes array at comment 1 is used to store the hash value corresponding to the key, because the key can only be int like SparseArray at this time, so if we want to use array to save, we need to use the hash value corresponding to the key in the array.
The mArray array in comment 2 is used to hold key and value pairs. You might be wondering how an array holds both key and value, as we’ll see in the put method;
MSize in note 3 indicates the number of key-value pairs stored;
@UnsupportedAppUsage(maxTargetSdk = 28) // Hashes are an implementation detail. Use public key/value API.
//1
int[] mHashes;
@UnsupportedAppUsage(maxTargetSdk = 28) // Storage is an implementation detail. Use public key/value API.
//2
Object[] mArray;
@UnsupportedAppUsage(maxTargetSdk = 28) // Use size()
//3
int mSize;
Copy the code2, put method
The put method is a little long, so let’s just look at a couple of key points;
Comment 1 is used to obtain the hash value corresponding to the key.
In comment 2, the hash value is changed to the index index by the indexOf method, which is described separately below.
The branch at comment 3 indicates that there is a key/value pair corresponding to this key. You just need to overwrite oldValue with the new value and return oldValue.
The following very long part is mainly for expansion and reduction of capacity and other operations, we do not introduce in detail;
Let’s move on to comment 4, where we’ve already seen that the mHashes array is used to hold hash values for keys, and the mArray array is used to hold key-value pairs; MHashes [index]=hash; mHashes[index]=hash; But when the key-value pair is saved, index is moved one bit left and one bit left and then incremented by one, so that index 0 in the mArray array corresponds to indexes 0 and 1, 1 to indexes 2 and 3, 2 to indexes 4 and 5, and 3 to indexes 6 and 7…… Isn’t that clever?
/** * Add a new value to the array map. * @param key The key under which to store the value. If * this key already exists in the array, its value will be replaced. * @param value The value to store for the given key. * @return Returns the old value that was stored for the given key, or null if there * was no such key. */ @Override public V put(K key, V value) { final int osize = mSize; final int hash; int index; if (key == null) { hash = 0; index = indexOfNull(); } else { //1 hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode(); //2 index = indexOf(key, hash); } if (index >= 0) { //3 index = (index<<1) + 1; final V old = (V)mArray[index]; mArray[index] = value; return old; } index = ~index; if (osize >= mHashes.length) { final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1)) : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); final int[] ohashes = mHashes; final Object[] oarray = mArray; allocArrays(n); if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize ! = mSize) { throw new ConcurrentModificationException(); } if (mHashes.length > 0) { if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0"); System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); System.arraycopy(oarray, 0, mArray, 0, oarray.length); } freeArrays(ohashes, oarray, osize); } if (index < osize) { if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (osize-index) + " to " + (index+1)); System.arraycopy(mHashes, index, mHashes, index + 1, osize - index); System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1); } if (CONCURRENT_MODIFICATION_EXCEPTIONS) { if (osize ! = mSize || index >= mHashes.length) { throw new ConcurrentModificationException(); } } //4 mHashes[index] = hash; mArray[index<<1] = key; mArray[(index<<1)+1] = value; mSize++; return null; }Copy the codeLet’s take a look at the indexOf method in comment 2 above. This method is also quite long, but the key part is only one place, in comment 1.
@UnsupportedAppUsage(maxTargetSdk = 28) // Hashes are an implementation detail. Use indexOfKey(Object).
int indexOf(Object key, int hash) {
final int N = mSize;
// Important fast case: if nothing is in here, nothing to look for.
if (N == 0) {
return ~0;
}
//1
int index = binarySearchHashes(mHashes, N, hash);
// If the hash code wasn't found, then we have no entry for this key.
if (index < 0) {
return index;
}
// If the key at the returned index matches, that's what we want.
if (key.equals(mArray[index<<1])) {
return index;
}
// Search for a matching key after the index.
int end;
for (end = index + 1; end < N && mHashes[end] == hash; end++) {
if (key.equals(mArray[end << 1])) return end;
}
// Search for a matching key before the index.
for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
if (key.equals(mArray[i << 1])) return i;
}
// Key not found -- return negative value indicating where a
// new entry for this key should go. We use the end of the
// hash chain to reduce the number of array entries that will
// need to be copied when inserting.
return ~end;
}
Copy the codeSo let’s look at the binarySearchHashes method, and then in comment 1 we call the binarySearch method of ContainerHelpers, which is what we talked about in SparseArray, binarySearch;
private static int binarySearchHashes(int[] hashes, int N, int hash) {
try {
//1
return ContainerHelpers.binarySearch(hashes, N, hash);
} catch (ArrayIndexOutOfBoundsException e) {
if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
throw new ConcurrentModificationException();
} else {
throw e; // the cache is poisoned at this point, there's not much we can do
}
}
}
Copy the code3. Get method
So with put out of the way, let’s look at get;
The indexOfKey method is called again in comment 1; Let’s look at the indexOfKey method next;
Annotation 2 also calls the indexOf method, which we introduced in the PUT method;
Add value to mArray array by moving index left 1 bit and incremented by 1.
/**
* Retrieve a value from the array.
* @param key The key of the value to retrieve.
* @return Returns the value associated with the given key,
* or null if there is no such key.
*/
@Override
public V get(Object key) {
//1
final int index = indexOfKey(key);
//3
return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}
/**
* Returns the index of a key in the set.
*
* @param key The key to search for.
* @return Returns the index of the key if it exists, else a negative integer.
*/
public int indexOfKey(Object key) {
//2
return key == null ? indexOfNull()
: indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
}
Copy the code4, remove method
Finally, look at the remove method;
The index index is evaluated by the indexOfKey method as described in the get method.
In comment 2, the index calls the removeAt method to perform the deletion.
/**
* Remove an existing key from the array map.
* @param key The key of the mapping to remove.
* @return Returns the value that was stored under the key, or null if there
* was no such key.
*/
@Override
public V remove(Object key) {
//1
final int index = indexOfKey(key);
if (index >= 0) {
//2
return removeAt(index);
}
return null;
}
Copy the codeLet’s take a look at the removeAt method, which is also quite long, so let’s just look at the main operations;
Note 1 obtains the value to be deleted from the mArray array through the index;
Set key and value in mArray array to NULL;
OldValue returns at comment 3;
/** * Remove the key/value mapping at the given index. * * <p>For indices outside of the range <code>0... size()-1</code>, the behavior is undefined for * apps targeting {@link android.os.Build.VERSION_CODES#P} and earlier, and an * {@link ArrayIndexOutOfBoundsException} is thrown for apps targeting * {@link android.os.Build.VERSION_CODES#Q} and later.</p> * * @param index The desired index, must be between 0 and {@link #size()}-1. * @return Returns the value that was stored at this index. */ public V removeAt(int index) { if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) { // The array might be slightly bigger than mSize, in which case, indexing won't fail. // Check if exception should be thrown outside of the critical path. throw new ArrayIndexOutOfBoundsException(index); } //1 final Object old = mArray[(index << 1) + 1]; final int osize = mSize; final int nsize; if (osize <= 1) { // Now empty. if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); final int[] ohashes = mHashes; final Object[] oarray = mArray; mHashes = EmptyArray.INT; mArray = EmptyArray.OBJECT; freeArrays(ohashes, oarray, osize); nsize = 0; } else { nsize = osize - 1; if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { // Shrunk enough to reduce size of arrays. We don't allow it to // shrink smaller than (BASE_SIZE*2) to avoid flapping between // that and BASE_SIZE. final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2); if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); final int[] ohashes = mHashes; final Object[] oarray = mArray; allocArrays(n); if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize ! = mSize) { throw new ConcurrentModificationException(); } if (index > 0) { if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); System.arraycopy(ohashes, 0, mHashes, 0, index); System.arraycopy(oarray, 0, mArray, 0, index << 1); } if (index < nsize) { if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + nsize + " to " + index); System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index); System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, (nsize - index) << 1); } } else { if (index < nsize) { if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + nsize + " to " + index); System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index); System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, (nsize - index) << 1); } //2 mArray[nsize << 1] = null; mArray[(nsize << 1) + 1] = null; } } if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize ! = mSize) { throw new ConcurrentModificationException(); } mSize = nsize; //3 return (V)old; }Copy the code