Cover image by Peter Wormstetter on Unsplash
Introduction to the
ArrayMap is a generic-enabled hash table, located under the Android.util package, that implements the Map interface, but is more memory efficient than HashMap.
ArrayMap is internally based on array and binary lookup, so it is not as efficient as HashMap and is suitable for a small number of elements.
To make better use of memory, ArrayMap caches arrays that have already been created to avoid garbage collection caused by frequent array creation.
This article takes a look at the core of ArrayMap’s source code to figure out how ArrayMap stores mapping pairs and how array caching works.
attribute
The main properties of ArrayMap are as follows:
// Whether HashCode should be unique
final boolean mIdentityHashCode;
// Hold an array of HashCode
int[] mHashes;
// Hold an array of keys and values
Object[] mArray;
// ArrayMap stores the number of mappings
int mSize;
Copy the codeWhere the mHashes is an integer array used to store the hash values of all keys; MArray is used to store keys and values.
In addition, ArrayMap has some important static variables and constants:
// Whether to throw an exception during concurrent modification
private static final boolean CONCURRENT_MODIFICATION_EXCEPTIONS = true;
private static final int BASE_SIZE = 4;
// The maximum number of cached arrays
private static final int CACHE_SIZE = 10;
static final int[] EMPTY_IMMUTABLE_INTS = new int[0];
public static final ArrayMap EMPTY = new ArrayMap<>(-1);
// Cache an array of size 4
static Object[] mBaseCache;
static int mBaseCacheSize;
// Cache arrays of size 4*2
static Object[] mTwiceBaseCache;
static int mTwiceBaseCacheSize;
Copy the codeMBaseCache and mTwiceBaseCache are used to cache arrays that have already been created. For details on how to cache arrays, see the constructor of ArrayMap.
A constructor
ArrayMap exposes three constructors, as shown in the code below, which eventually call the constructor with two arguments, but which is marked by @hide and therefore cannot be called directly. As you can see from the constructor call relationship, mIdentityHashCode is always false, that is, hash collisions are allowed.
public ArrayMap(ArrayMap<K, V> map) {
// Call the no-argument constructor
this(a);if(map ! =null) { putAll(map); }}public ArrayMap(a) {
this(0.false);
}
public ArrayMap(int capacity) {
this(capacity, false);
}
/ * * {@hide} * /
public ArrayMap(int capacity, boolean identityHashCode) {
mIdentityHashCode = identityHashCode;
// If this is immutable, use the sentinal EMPTY_IMMUTABLE_INTS
// instance instead of the usual EmptyArray.INT. The reference
// is checked later to see if the array is allowed to grow.
if (capacity < 0) {
mHashes = EMPTY_IMMUTABLE_INTS;
mArray = EmptyArray.OBJECT;
} else if (capacity == 0) {
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
} else {
allocArrays(capacity);
}
mSize = 0;
}
Copy the codeIn the constructor, except for the special handling of capacity <=0, the allocArrays method is mainly called to create and assign arrays to mHashes and mArray.
The allocArrays method is as follows:
private void allocArrays(final int size) {
if (mHashes == EMPTY_IMMUTABLE_INTS) {
throw new UnsupportedOperationException("ArrayMap is immutable");
}
// Use cached arrays first
if (size == (BASE_SIZE*2)) {
synchronized (ArrayMap.class) {
if(mTwiceBaseCache ! =null) {
final Object[] array = mTwiceBaseCache;
mArray = array;
mTwiceBaseCache = (Object[])array[0];
mHashes = (int[])array[1];
// Empty the first two elements
array[0] = array[1] = null;
mTwiceBaseCacheSize--;
return; }}}else if (size == BASE_SIZE) {
synchronized (ArrayMap.class) {
if(mBaseCache ! =null) {
final Object[] array = mBaseCache;
mArray = array;
mBaseCache = (Object[])array[0];
mHashes = (int[])array[1];
array[0] = array[1] = null;
mBaseCacheSize--;
return; }}}// There is no cached array or the cached array length does not meet the condition
mHashes = new int[size];
// The capacity of mArray is twice the size
mArray = new Object[size<<1];
}
Copy the codeThe first part of the allocArrays method might seem a little confusing at first, so don’t get bogged down in the details. If you want the size of an ArrayMap to be BASE_SIZE or twice as large as BASE_SIZE, then you will use the array that is already cached first. If there is no cached array or the size of the array does not match the two conditions, you will create a new array. How arrays are cached and reused will be explained later.
The last two lines of code show that mArray is twice as big as mHashes, depending on how ArrayMap stores keys and values. Let’s start with the PUT method, and as we study the PUT method, all the questions will be answered.
Put method
The put method is rewritten from the Map interface to store a key-value pair, update the value of the value if the key exists and return the old value, insert the key if the key does not exist and return null.
The put method looks like this:
public V put(K key, V value) {
final int osize = mSize;
final int hash;
int index;
// Find the hash index in the mHashes array
if (key == null) {
hash = 0;
index = indexOfNull();
} else {
// As you can see from the previous constructor, mIdentityHashCode is always false, so hash= key.hashcode ();
hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
index = indexOf(key, hash);
}
// There is already a mapping to the key, update the value directly and return the old value
if (index >= 0) {
//index is the index of the key hash in the mHashes array,
// In the mArray array, the index of the key is index*2, and the index of the value is index*2+1
index = (index<<1) + 1;
final V old = (V)mArray[index];
mArray[index] = value;
// Return the old value
return old;
}
// No corresponding key is found
//index is the position to insert
index = ~index;
if (osize >= mHashes.length) {
// The array space is insufficient, need to expand first
If the current size is larger than BASE_SIZE*2=4*2=8, the capacity expansion policy is 1.5 times that of the original one
// If the current size is less than 8 but greater than 4, then the array size is 8;
// If the current size is less than 4, expand to 4
final int n = osize >= (BASE_SIZE*2)? (osize+(osize>>1))
: (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
// Create arrays from allocArrays and assign them to mHashes and mArray
allocArrays(n);
if(CONCURRENT_MODIFICATION_EXCEPTIONS && osize ! = mSize) {// Concurrent changes exist, an exception is thrown
throw new ConcurrentModificationException();
}
if (mHashes.length > 0) {
// Copy the value from the old array to the new array
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
// Free the array space
freeArrays(ohashes, oarray, osize);
}
if (index < osize) {
// To insert in the middle of the array, you need to move the element after the insertion position
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) {// Concurrent changes exist, an exception is thrown
throw newConcurrentModificationException(); }}// Insert new values into mHashes and mArray
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1) +1] = value;
//mSize + 1
mSize++;
return null;
}
Copy the codeThe main logic of the PUT method is as follows: First, the hash value of the key is searched in the mHashes array to see if the hash value exists. If the hash value exists and the corresponding position of mArray also exists, then the value is updated and the old value is returned. Otherwise, insert is performed, expanding the array if necessary.
The put method is a little long, and there’s a lot of detail in it, so let’s look at it paragraph by paragraph.
Find the key that is null
The indexOfNull method is called for the lookup when the key is null, and the code is as follows:
int indexOfNull(a) {
final int N = mSize;
// If there is no data, return directly
if (N == 0) {
return ~0;
}
// Use binary search to find if 0 exists in the range 0~ n-1 of the mHashes array
int index = binarySearchHashes(mHashes, N, 0);
// Not found
if (index < 0) {
return index;
}
// 0 exists in the mHashes array
// The key corresponding to mArray is also null
if (null == mArray[index<<1]) {
return index;
}
// The mHashes array contains 0, but the mArray position key is not null
// Hash conflicts exist, continue to look back
int end;
for (end = index + 1; end < N && mHashes[end] == 0; end++) {
if (null == mArray[end << 1]) return end;
}
// The mHashes array contains 0, but the mArray position key is not null
// Hash conflict exists, continue to find
for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {
if (null == mArray[i << 1]) return i;
}
// If no hash index is found, return the hash index
return ~end;
}
Copy the codeIn the code, first call binarySearchHashes to search for 0(hash value corresponding to null)** in mHashes by binary search method. ** Binary search method binarySearchHashes code is as follows:
private static int binarySearchHashes(int[] hashes, int N, int hash) {
try {
return ContainerHelpers.binarySearch(hashes, N, hash);
} catch (ArrayIndexOutOfBoundsException e) {
//CONCURRENT_MODIFICATION_EXCEPTIONS=true
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 codeCan see call ContainerHelpers binarySearch, source, the method is as follows:
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
}
Copy the codeThis method has been explained in the analysis of SparseArray source code. When the target value is not found, the first subscript greater than the target value will be reversed and returned, so that the caller can get the subscript value after negating the return result again, which also ensures that the mHashes are in order.
If a hash is found in the mHashes array, but a key is not found in the mArray array, then a further search is needed.
// The mHashes array contains 0, but the mArray position key is not null
// Hash conflicts exist, continue to look back
int end;
for (end = index + 1; end < N && mHashes[end] == 0; end++) {
if (null == mArray[end << 1]) return end;
}
// The mHashes array contains 0, but the mArray position key is not null
// Hash conflict exists, continue to find
for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {
if (null == mArray[i << 1]) return i;
}
// If no hash index is found, return the hash index
return ~end;
Copy the codeIf the mHashes element is [-2,-1,0,0,0,0, 0,3,4] and the hash value is 0, then the binary search method returns the subscript 3, the second 0. If the corresponding key in mArray is not null, then the logic of the above code will be applied to search backwards, assuming that no null is found in mArray until the last 0, then **end=6, and ** is the position of element 3.
The next step is to search forward and, assuming no NULL is found, return -7 (bitwise inverse of 6).
So why not return the first index equal to the target hash value?
Because when you insert a new key, you need to move both the insertion position and the element that follows it. In the example above, if the index returned is 6, you only need to move 3 and 4 elements. If you return the first index 0, you need to move 6 elements. So this is done to reduce the number of elements that are moved backwards when a new key is inserted.
To sum up, indexOfNull returns a negative value by reversing the subscript of the first hash value greater than the key in the mHashes if the key does not exist.
You can also see from the above code that ArrayMap uses linear detection to handle hash collisions.
Find keys that are not null
IndexOf (key,hash) is called for non-null keys as follows:
int indexOf(Object key, int hash) {
final int N = mSize;
// No data is returned directly
if (N == 0) {
return ~0;
}
// Use binary search to find the hash in the mHashes array
int index = binarySearchHashes(mHashes, N, hash);
// Hash not found, no mapping pair exists
if (index < 0) {
return index;
}
// Hash exists and mArray matches the key
if (key.equals(mArray[index<<1]) {return index;
}
// The hash exists but the key does not match
int end;
for (end = index + 1; end < N && mHashes[end] == hash; end++) {
if (key.equals(mArray[end << 1])) return end;
}
// Hash exists but key does not match. Continue searching
for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
if (key.equals(mArray[i << 1])) return i;
}
// No matching key is found, return a negative number. Also return the first index that does not equal hash
// Move as few elements as possible during the next insertion
return ~end;
}
Copy the codeIndexOf and indexOfNull use the same logic except that keys are compared using equals.
Update the value corresponding to the existing key
When index >=0, that is, there is already a mapping with the same key in the ArrayMap, you only need to update the value. This part of the operation corresponds to the following code:
if (index >= 0) {
// Index is the index of the key's hashCode in the mHashes
// In the mArray array, the index of the key is index*2 and the index of the value is index*2+1
index = (index<<1) + 1;
final V old = (V)mArray[index];
mArray[index] = value;
// Return the old value
return old;
}
Copy the codeFor a hashCode key whose subscript is index in the mHashes array, the value is index*2+1 and the key is index*2 in the mArray array. This can also be seen from the previous search logic for keys.
For example, for a key whose hashCode is subscript 1 in mHashes, the key’s subscript is 1*2=2 in mArray, and its corresponding value is 1*2+1=3 in mArray.
We can verify this again by inserting the new value logic. The code in the PUT method looks like this:
/ /...
// Insert new values into mHashes and mArray
mHashes[index] = hash;
// Insert key at index*2
mArray[index<<1] = key;
// Insert value at index*2+1
mArray[(index<<1) +1] = value;
//mSize + 1
mSize++;
Copy the codeThis shows how ArrayMap stores hashCode, key, and value, as shown below:
Insert a new mapping
In the PUT method, when the key does not exist, there is code like this before performing an insert:
index = ~index;
Copy the codeAs you saw earlier, the search returns a negative value when the key does not exist. This negative value is the bit-inverse value of the first hash value greater than the key in the mHashes array. Here, by taking the inverse again, you get this subscript, which is where the key is going to be inserted.
Determine the location of the new mapping. If the mHashes capacity is sufficient, add the hashCode, key and value of the new mapping directly to the array.
The code for inserting a new value is as follows:
if (index < osize) {
// To insert in the middle of the array, you need to move the position to be inserted and the following element
System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);
System.arraycopy(mArray, index << 1, mArray, (index + 1) < <1, (mSize - index) << 1);
}
// Insert new values into mHashes and mArray
mHashes[index] = hash;
// The key index is index*2
mArray[index<<1] = key;
// Index *2+1
mArray[(index<<1) +1] = value;
// mSize + 1
mSize++;
Copy the codeThis part of the code is easier to understand, but the size of the array is sufficient. If no, expand the capacity first.
Array capacity
The code for array expansion is as follows:
if (osize >= mHashes.length) {
// The array space is insufficient, need to expand first
final int n = osize >= (BASE_SIZE*2)? (osize+(osize>>1))
: (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
// Save the old array
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
// Create allocArrays and assign them to mHashes and mArray
allocArrays(n);
if(CONCURRENT_MODIFICATION_EXCEPTIONS && osize ! = mSize) {// Concurrent changes exist, an exception is thrown
throw new ConcurrentModificationException();
}
if (mHashes.length > 0) {
// Copy the value from the old array to the new array
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
// Free (cache) array space
freeArrays(ohashes, oarray, osize);
}
Copy the codeExpansion policies are as follows:
- If the current ArrayMap size is greater than 8 (BASE_SIZE*2), increase the size by 1.5 times
- If size is less than 8 but greater than 4 (BASE_SIZE), then the array size is 8 after expansion
- If size is less than 4, expand to 4.
After the capacity is determined, the allocArrays method is used to create arrays and assign new arrays to mHashes and mArray.
We’ve already seen this method in the constructor section, but we’ve only looked at the general logic. Here’s the code for this method:
private void allocArrays(final int size) {
if (mHashes == EMPTY_IMMUTABLE_INTS) {
throw new UnsupportedOperationException("ArrayMap is immutable");
}
// Use cached arrays first
if (size == (BASE_SIZE*2)) {
synchronized (ArrayMap.class) {
if(mTwiceBaseCache ! =null) {
final Object[] array = mTwiceBaseCache;
mArray = array;
mTwiceBaseCache = (Object[])array[0];
mHashes = (int[])array[1];
array[0] = array[1] = null;
mTwiceBaseCacheSize--;
return; }}}else if (size == BASE_SIZE) {
synchronized (ArrayMap.class) {
if(mBaseCache ! =null) {
/ / 1.
final Object[] array = mBaseCache;
mArray = array;
/ / 2.
mBaseCache = (Object[])array[0];
/ / 3.
mHashes = (int[])array[1];
/ / 4.
array[0] = array[1] = null;
/ / 5.
mBaseCacheSize--;
return; }}}// There is no cached array or the cached array length does not meet the condition
mHashes = new int[size];
// The capacity of mArray is twice the size
mArray = new Object[size<<1];
}
Copy the codeIn the method, the cache array is preferentially used when the capacity is BASE_SIZE or BASE_SIZE *2. We analyze the situation when the capacity is BASE_SIZE. The code logic is as follows:
- Assign mArray to mBaseCache
- Assign mBaseCache to mArray[0]
- Assign mHashes to mArray[1]
- Empty the value of mArray[0] mArray[1]
- Number of caches minus one
To understand this logic, we need to know exactly what mBaseCache stores. Let’s look at the comment:
/** * Caches of small array objects to avoid spamming garbage. The cache * Object[] variable is a pointer to a linked list of array objects. * The first entry in the array is a pointer to the next array in the * list; the second entry is a pointer to the int[] hash code array for it. */
static Object[] mBaseCache;
Copy the codeTo be honest, I’ve read this note several times and I’m still a little confused. **mBaseCache is a pointer to a linked list made up of arrays. ** Where mBaseCache[0] points to the next cached array, mBaseCache[1] points to the mHashes array of the current array.
So the contents of mBaseCache look like this:
Although BASE_SIZE is 4, the actual array capacity of the mBaseCache cache is 8, and 4 is the number of mapping pairs, which is the size of the mHashes.
MTwiceBaseCache is the same as mTwiceBaseCache except that the size of the cached array is different.
So when are mBaseCache and mTwiceBaseCache assigned? Must be when you recycle an array. In the PUT method, after allocating the new array and copying the elements from the old array, we call the freeArrays method to release the old array:
freeArrays
private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
if (hashes.length == (BASE_SIZE*2)) {
synchronized (ArrayMap.class) {
if (mTwiceBaseCacheSize < CACHE_SIZE) {
// Form a linked list structure
array[0] = mTwiceBaseCache;
array[1] = hashes;
for (int i=(size<<1) -1; i>=2; i--) {
array[i] = null; } mTwiceBaseCache = array; mTwiceBaseCacheSize++; }}}else if (hashes.length == BASE_SIZE) {
synchronized (ArrayMap.class) {
if (mBaseCacheSize < CACHE_SIZE) {
/ / 1.
array[0] = mBaseCache;
/ / 2.
array[1] = hashes;
/ / 3.
for (int i=(size<<1) -1; i>=2; i--) {
array[i] = null;
}
/ / 4.mBaseCache = array; mBaseCacheSize++; }}}}Copy the codeYou can see that the cache is only cached if the mHashes array length is BASE_SIZE and BASE_SIZE *2. Again, just look at BASE_SIZE:
- Points array[1] to the corresponding hashes array
- Point array[0] to mBaseCache
- Empty elements with subscripts greater than 1 in the array; otherwise, memory leaks occur.
- MBaseCache is pointing to array
Step 2 and step 4 organize the cached array into a linked list. MBaseCache always points to the array at the head of the list. This step is easier to understand by referring to the diagram above.
That’s the logic of how arrays are cached and reused, and that’s what I find most difficult to understand about ArrayMap.
The logic of the PUT method is finished. If you are not clear about it for a while, you can read it several times and draw some diagrams to help you understand.
The get method
The code for the get method is relatively simple:
@Override
public V get(Object key) {
final int index = indexOfKey(key);
return index >= 0 ? (V)mArray[(index<<1) +1] : null;
}
Copy the codeLocate the hash value of the key in the mHashes array by indexOfKey. If the key exists, fetch the value from the corresponding position in the mArray array.
IndexOfKey code is as follows:
public int indexOfKey(Object key) {
return key == null ? indexOfNull()
: indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
}
Copy the codeCall indexOfNull or indexOf if the key is null.
remove
The remove method is used to remove a mapping pair by key.
@Override
public V remove(Object key) {
final int index = indexOfKey(key);
if (index >= 0) {
return removeAt(index);
}
return null;
}
Copy the codeAfter finding the key’s index, the main removal logic is in the removeAt method:
public V removeAt(int index) {
final Object old = mArray[(index << 1) + 1];
final int osize = mSize;
final int nsize;
if (osize <= 1) {
// Empty after removal
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) {
// If the mHashes array length is greater than (BASE_SIZE*2) and the remaining space is greater than 2/3, reduce the array length
// The size of the array must not be smaller than BASE_SIZE*2, mainly to take advantage of the cached array
final int n = osize > (BASE_SIZE*2)? (osize + (osize>>1)) : (BASE_SIZE*2);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
// Reassign mHashes and mArray
allocArrays(n);
if(CONCURRENT_MODIFICATION_EXCEPTIONS && osize ! = mSize) {throw new ConcurrentModificationException();
}
if (index > 0) {
// Copy the element before the position to be removed to the new array
System.arraycopy(ohashes, 0, mHashes, 0, index);
System.arraycopy(oarray, 0, mArray, 0, index << 1);
}
if (index < nsize) {
// Copy the element after the position to be removed into the new array
System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index);
System.arraycopy(oarray, (index + 1) < <1, mArray, index << 1,
(nsize - index) << 1);
}
// The removal is complete
} else {
// No need to shrink the array
if (index < nsize) {
// Move the element after the position to be deleted one bit forward (the last element is redundant)
System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index);
System.arraycopy(mArray, (index + 1) < <1, mArray, index << 1,
(nsize - index) << 1);
}
// Empty the last element to complete the deletion
mArray[nsize << 1] = null;
mArray[(nsize << 1) + 1] = null; }}if(CONCURRENT_MODIFICATION_EXCEPTIONS && osize ! = mSize) {throw new ConcurrentModificationException();
}
mSize = nsize;
return (V)old;
}
Copy the codeThe logic of remove method is also easy to understand. The focus is to reduce the array when the mHashes array is larger than BASE_SIZE*2 and the space utilization is less than 1/3. The reduced size is no less than BASE_SIZE*2, mainly to make use of the cached array first.
The code for the other methods of ArrayMap is easier to understand and won’t be the focus of this article.
conclusion
ArrayMap is a utility class provided by Android for storing key-value mappings, but it is more memory efficient than HashMap. Mainly reflected in
- You don’t need an extra wrapper class to wrap keys and values,
- By caching allocated arrays, frequent creation and destruction of arrays and the resulting unnecessary garbage collection are reduced.
ArrayMap uses two arrays internally to store mapping pairs: an integer array mHashes is used to store hash values of all keys. MHashes is ordered, and binary search is used to search keys, which is also the reason why ArrayMap’s search efficiency is lower than that of HashMap. There is also an array mArray used to store keys and values, where keys and values are stored in pairs. The corresponding relationship between their positions ki and vi in mArray and the subscript Hi of the hash value of keys in mHashes is:
ki = hi*2=hi<<1;
vi = ki+1 = hi*2+1=(hi<<1) +1;
Copy the codeBecause arrays occupy contiguous memory, and with many objects being created and destroyed, there is no guarantee that there will always be enough contiguous memory to allocate arrays. If you need to allocate space to the array, you can only do garbage collection first. If you create and destroy arrays frequently, you can cause unnecessary garbage collection, which affects application performance. ArrayMap caches a certain number of arrays that have been allocated to ensure that arrays can be used immediately without creating arrays or even garbage collection, effectively improving application performance.
ArrayMap creates and assigns arrays to mHashes and mArray via the allocArrays method. Inside the method, when size=4 or size=8, ArrayMap preferentially uses the cached arrays. The cached mArray array is organized as a linked list. The list heads are mBaseCache(size=4) and mTwiceBaseCache(size=8). The first element of mBaseCache points to the next mArray array. The second element points to the mHashes array corresponding to mBaseCache.
The caching of arrays is done in the freeArrays method, which organizes arrays created when the ArrayMap has a capacity of 4 or 8 into linked lists stored by mBaseCache and mTwiceBaseCache.
To make full use of the cached array, if the current array capacity is less than 4, it will be expanded to 4(you can reuse the array stored by mBaseCache). If the capacity is larger than 4 and smaller than 8, the system expands to 8(you can reuse the array stored by mTwiceBaseCache). If the capacity is larger than 8, the system expands to 1.5 times the original capacity.
When the mapping is removed, if the mHashes length is larger than BASE_SIZE*2 and the space utilization is less than 1/3, the array length will be reduced, mainly in order to timely release the large array and make full use of the cached array.
If we use ArrayMap more often in our applications, we can make the most of the arrays already claimed, reducing the garbage collection caused by the frequent creation and destruction of arrays and the resulting negative impact on application performance.