Public number: byte array, hope to help you 🤣🤣
This series of articles will be on the Java and Android collection framework (JDK 1.8, Android SDK 30) in several common containers combined with the source code to introduce, understand different containers in the data structure, application scenarios, advantages of the different points, I hope to help you 🤣🤣
This article will take a look at SparseArray and ArrayMap, two collections framework classes unique to Android. These two containers are similar in usage to HashMap, and are used to store key-value pairs. Since The Android system is sensitive to memory, SparseArray and ArrayMap are relatively restrained in memory usage. Here we analyze the implementation principles and advantages of SparseArray and ArrayMap
A, SparseArray
If you declare a Map
variable in your code, Android Studio will tell you: Use new SparseArray
Here’s a look at SparseArray’s internals and what performance advantages it has over HashMap
1. Basic concepts
How to use SparseArray:
SparseArray<String> sparseArray = new SparseArray<>();
sparseArray.put(100."leavesC");
sparseArray.remove(100);
sparseArray.get(100);
sparseArray.removeAt(29);
Copy the codeSparseArray< E > is equivalent to Map< Integer, E >, and the key value is fixed as an int. When initializing SparseArray, you only need to declare the data type of value. It uses two arrays to store the key and value respectively: int[] mKeys ; Object[] mValues
MKeys and mValues correspond according to the following rules:
- If you want to store a key/value pair with key 10 and value 200 to SparseArray, store 10 in mKeys first. If the index value of 10 in mKeys is 2, store value in mValues[2]
- Element values in mKeys are stored incrementally, and keys are inserted into mKeys each time a new pair is stored by binary lookup
- To obtain the value from SparseArray, the binary search method is used to find the index corresponding to the key in mKeys, and then the value is obtained from mValues based on the index
SparseArray avoids the boxing and unboxing of the HashMap each time the value is stored. The key value is kept as the basic data type int, reducing the performance overhead
Class declaration
SparseArray itself does not inherit directly from any classes, nor does it use the Java native collection framework internally, so SparseArray is a collection container class implemented by Android
public class SparseArray<E> implements Cloneable
Copy the code3. Global variables
MGarbage is one of the optimization points of SparseArray and is used to indicate whether there are currently elements that need to be garbage collected (GC). When this value is set to true, it means that there are currently invalid elements that need to be garbage collected, but the collection does not happen immediately, but in a later operation
// When the key-value pair is removed, the corresponding value becomes this value, which is used as a GC flag bit
private static final Object DELETED = new Object();
// The element used to mark whether the current is awaiting garbage collection (GC)
private boolean mGarbage = false;
private int[] mKeys;
private Object[] mValues;
// The number of elements in the current collection
// The value does not always have to be in the correct state, as it is possible to delete either key or value
// So the size() method is always GC first
private int mSize;
Copy the codeconstructor
The default size of both the key and value arrays is 10. If the final data size is known during initialization, you can directly specify the initial capacity to avoid subsequent expansion operations
// Set the default initial size of the array to 10
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 code5. Add elements
There are several methods for adding elements, including the put(int key, E value) method, which stores key and value pairs
As SparseArray stores key-value pairs, the PUT method determines whether the current mKeys already have the same key value, and overwrites the old value in mValues with value. If the same key value does not exist, insert value in the same index position of mValues after inserting key into mKeys. Since mKeys are stored by sorting element values by size, inserting a key into mKeys may cause elements to be reordered, which in turn causes mValues to be reordered
The put method finds keys from mKeys using the binary search method provided by ContainerHelpers: The binarySearch method returns the current index of the key in mKeys (if the key exists) or the index of the location where the key should be stored (if the key does not exist).
- If the corresponding key exists in mKeys, the corresponding index value is returned
- If no corresponding key exists in mKeys
- This method returns ~presentIndex, assuming that there is a presentIndex in mKeys whose value is greater than key and closest in size to key
- If there is no value greater than key in mKeys, the return value is ~ mkeys.length
// 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}}return ~lo; // value not present
}
Copy the codeAs you can see, if mKeys has a target key, then the return value is the corresponding index location. If there is no target key, the return value also points to the location where the key should be stored, because when there is no target key, the return value of the calculated index value after ~ calculation must be negative, thus distinguishing it from the case of “if the target key is found (the return value is greater than or equal to zero)”. A single return value can distinguish between multiple cases, and storing data in such a way that the internal values of mKeys are always sorted incrementally
Let’s look at the logic of the PUT method
public void put(int key, E value) {
// use binary search to find the index value of the specified key in mKeys
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) { // The same key already exists
mValues[i] = value;
} else {
// get the real index position
i = ~i;
// If the target location has not been assigned a value, the data can be saved directly
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
// If there is redundant data, GC is performed first
if (mGarbage && mSize >= mKeys.length) {
gc();
// Look again after GC because the value may have changed
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
// The index I location is already used to store other data, so the array elements need to be migrated
// So all data from index I needs to be moved back one bit and stored in mKeys[I]mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); mSize++; }}// Assign the element at index to value
// If you know the target location, you can directly assign to mValues
public void setValueAt(int index, E value) {
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);
}
// Do garbage collection first if necessary
if (mGarbage) {
gc();
}
mValues[index] = value;
}
// This is similar to the put method
// The size of the mKeys is determined before storing the data, which is useful to reduce the number of binary search for mKeys
// This method performs better than the put method in cases where the stored key is larger than the existing mKeys
public void append(int key, E value) {
if(mSize ! =0 && key <= mKeys[mSize - 1]) {
put(key, value);
return;
}
if (mGarbage && mSize >= mKeys.length) {
gc();
}
mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
mValues = GrowingArrayUtils.append(mValues, mSize, value);
mSize++;
}
Copy the code6. Remove elements
As mentioned above, the Boolean variable mGarbage is used to mark elements that are currently awaiting garbage collection (GC). When this value is set to true, it means that the current state needs to be garbage collected, but not immediately, but later
The following methods remove elements only by severing the reference to value from mValues. MKeys are not reclaimed, and this operation is left to GC ()
public void delete(int key) {
// use binary search to find the index value of the specified key in mKeys
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if(mValues[i] ! = DELETED) { mValues[i] = DELETED;// marks the current need for garbage collection
mGarbage = true; }}}public void remove(int key) {
delete(key);
}
The delete method is the same as the delete method, except that it returns the value of the element corresponding to the key
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;
returnold; }}return null;
}
// Deletes the element value corresponding to the specified index
public void 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);
}
if(mValues[index] ! = DELETED) { mValues[index] = DELETED;// marks the current need for garbage collection
mGarbage = true; }}// Delete the size of the element after index
public void removeAtRange(int index, int size) {
// Avoid array out of bounds
final int end = Math.min(mSize, index + size);
for (inti = index; i < end; i++) { removeAt(i); }}// Remove all element values
public void clear(a) {
int n = mSize;
Object[] values = mValues;
for (int i = 0; i < n; i++) {
values[i] = null;
}
mSize = 0;
mGarbage = false;
}
Copy the code7. Find elements
There are many ways to find elements, and the logic is quite simple
// Find the corresponding element value according to the key, if not, return the default value
@SuppressWarnings("unchecked")
public E get(int key, E valueIfKeyNotFound) {
// use binary search to find the index value of the specified key in mKeys
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
// If the key cannot be found or has not been assigned, the default value is returned
if (i < 0 || mValues[i] == DELETED) {
return valueIfKeyNotFound;
} else {
return(E) mValues[i]; }}// Find the corresponding element value based on key, return null if not found
public E get(int key) {
return get(key, null);
}
// Because the element values in mValues are not necessarily consistent, they may be mixed with DELETED
// GC is required before traversal so that the values retrieved through the array are correct
@SuppressWarnings("unchecked")
public E valueAt(int index) {
if (mGarbage) {
gc();
}
return (E) mValues[index];
}
// Find the corresponding key based on index
public int keyAt(int index) {
if (mGarbage) {
gc();
}
return mKeys[index];
}
// Based on the index value corresponding to key
public int indexOfKey(int key) {
if (mGarbage) {
gc();
}
return ContainerHelpers.binarySearch(mKeys, mSize, key);
}
// Find the corresponding index value according to value
public int indexOfValue(E value) {
if (mGarbage) {
gc();
}
for (int i = 0; i < mSize; i++) {
if (mValues[i] == value) {
returni; }}return -1;
}
// indexOfValue is similar to indexOfValue except that it is the same object by comparing ==
// The equals method is used to check whether the object is the same
public int indexOfValueByValue(E value) {
if (mGarbage) {
gc();
}
for (int i = 0; i < mSize; i++) {
if (value == null) {
if (mValues[i] == null) {
returni; }}else {
if (value.equals(mValues[i])) {
returni; }}}return -1;
}
Copy the code8. Recycling
Because SparseArray removes only one of the keys and values, not all of the valid data in the current array is right next to each other, that is, there are invalid values, so gc() depends on how much valid data there is in mValues, Rearrange the data in mKeys and mValues so that the meaningful element values are sorted next to each other
private void gc(a) {
int n = mSize;
int o = 0;
int[] keys = mKeys;
Object[] values = mValues;
for (int i = 0; i < n; i++) {
Object val = values[i];
//val is not DELETED, indicating that data may need to be moved
if(val ! = DELETED) {// Assign the value at index I to index o
// So if I == o, there is no need to execute the code
if(i ! = o) { keys[o] = keys[i]; values[o] = val; values[i] =null;
}
o++;
}
}
mGarbage = false;
mSize = o;
}
Copy the code9. Summary of advantages and disadvantages
From the introduction above, SparseArray has the following major advantages:
- Avoid packing and unpacking the basic int data type
- Unlike HashMap, where each storage node is a class object, SparseArray does not require a structure for wrapping keys, and individual elements are cheaper to store
- High search efficiency in the case of small amount of data (binary search method)
- It delays garbage collection and only takes place once and for all when needed
Disadvantages are as follows:
- A key must be of type int
- Inserting key-value pairs may require moving a large number of array elements
- When the amount of data is large, the search efficiency (binary search method) will be significantly reduced, and the target data can be located only after multiple half-search. In the case of HashMap, it only needs one hash calculation to locate the target element without hash conflict, and it only needs to compare the elements in the linked list or red-black tree with hash conflict
10. Association classes
SparseArray is a generic class, so even if a value is a basic data type, it gets boxed and unboxed, and if you want to save on that, You can use the SparseBooleanArray, SparseIntArray, and SparseLongArray container classes. These three containers are implemented in the same way as SparseArray, but value is still a basic data type
In addition, the system also provides the LongSparseArray container class. Its implementation principle is similar to SparseArray, but the key is fixed as long, and the value is declared by generics. Useful for daily development is the ability to store view objects according to viewId
Second, ArrayMap
ArrayMap is a generic class that inherits the Map interface. The usage of ArrayMap is basically the same as that of HashMap, but its internal logic is very different. Therefore, you need to understand the implementation principle of ArrayMap to understand which scenarios ArrayMap is suitable for
public final class ArrayMap<K.V> implements Map<K.V>
Copy the code1. Storage mechanism
The ArrayMap contains the following two arrays. The mHashes store the hash value of the key in the key-value pair, and the mArray store the key and value, that is, each key-value pair is stored together in the mArray
// Hashes are an implementation detail. Use public key/value API.
int[] mHashes;
// Storage is an implementation detail. Use public key/value API.
Object[] mArray;
Copy the codeWhen inserting a key-value pair into an ArrayMap, the hash of the key is calculated, the keyHash is stored in the mHashes in order of size, and its location index index is retrieved. The key is stored in the index<<1 position of mArray, and the value is stored in the (index<<1 + 1) position of mArray. That is, the key and value are stored in adjacent positions. From this position correspondence, the required capacity of mArray should be at least twice that of mHashes, and the arrangement of each key-value should be consistent with that of keyHash
When the key object is evaluated to the ArrayMap, the keyHash is computed, and then the binary search method is used to find the index of the keyHash position in the mHashes, and then the value is obtained from mArray at (index<<1 + 1)
2. Add elements
There are several methods for adding elements, of which the put method is the most important. Other methods for adding elements rely on this method. As mentioned above, key-values are eventually stored in mArray side by side, and the location of key-values in mArray is determined by keyHash and mHashes. The overall logic of put method is as follows:
- Obtain the index of the keyHash position in the mHashes by binary search
- If index is greater than or equal to 0, the key already exists in mArray. In this case, overwrite the old value to end the process
- If index is less than 0, key does not exist in mArray. ~index now represents the position where the keyHash should be inserted into the mHashes in ascending order
- Determine whether capacity expansion is required and expand capacity if necessary. If the cache criteria are met, the pre-expanded array is cached
- Migrate the final array, inserting key-value and keyHash
@Override
public V put(K key, V value) {
final int osize = mSize;
final int hash;
int index;
/ / the first step
if (key == null) {
hash = 0;
index = indexOfNull();
} else {
hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
index = indexOf(key, hash);
}
/ / the second step
if (index >= 0) {
index = (index<<1) + 1;
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
/ / the third step
index = ~index;
/ / step 4
if (osize >= mHashes.length) {
//ArrayMap's capacity expansion mechanism is more restrained than HashMap's
// When the size of the array exceeds BASE_SIZE*2, the size of the array is increased by 1.5 times
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);
}
/ / step 5
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();
}
}
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1) +1] = value;
mSize++;
return null;
}
Copy the codeThe append method is also used to add elements, with a bit of “append” meaning. If the external can determine that the hash value of the inserted key is larger than all existing values, then the data can be inserted directly to the end of the mHashes, saving binary lookup. So the append method compares the value of the last element in the mHashes. If the keyHash is larger than that value, it can be saved directly to the end. If the checksum fails, the put method is still called
public void append(K key, V value) {
int index = mSize;
final int hash = key == null ? 0
: (mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
if (index >= mHashes.length) {
throw new IllegalStateException("Array is full");
}
// If the current last value of the mHashes is larger than the hash, the hash cannot be inserted directly into the tail, then we still need to call the put method
if (index > 0 && mHashes[index-1] > hash) {
RuntimeException e = new RuntimeException("here");
e.fillInStackTrace();
Log.w(TAG, "New hash " + hash
+ " is before end of array hash " + mHashes[index-1]
+ " at index " + index + " key " + key, e);
put(key, value);
return;
}
// Insert key-value directly into the end of the array
mSize = index+1;
mHashes[index] = hash;
index <<= 1;
mArray[index] = key;
mArray[index+1] = value;
}
Copy the code3. Get elements
IndexOf (Object Key, int Hash), ArrayMap, ArrayMap, ArrayMap, ArrayMap, ArrayMap
The indexOf method is used to obtain the index position in the mHashes of the hash value of the element corresponding to and key. We know that keyHash is stored in mHashes and key-value is stored in mArray, but we cannot accurately match key-value according to keyHash, because different keys may have the same hash value. That is, hash conflicts need to be considered, so indexOf needs to compare the equality of keys as well as hash values
- Obtain index of mHashes equal to hash by binary search
- If index is less than 0, the key does not exist, then index is returned. ~index is the index of the hash position after insertion of the mHashes. The end of the process
- If index is greater than or equal to 0, the key may exist. It is possible because different keys have the same hash value
- Check whether the elements in mArray at index<<1 are equal to the key. If they are equal, the target location has been found. The end of the process
- At this point, it can be determined that hash conflict has occurred, so it is necessary to compare the equality of mArray, and the reason why the two for loops are divided is also to reduce the number of iterations, because the same hash value will be close together, so the two sides of the traversal search. If the key and keyHash are equal, the corresponding index is returned. The end of the process
- If the hash index is still not found, the hash index should be stored in the mHashes
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;
}
/ / the first step
int index = binarySearchHashes(mHashes, N, hash);
// If the hash code wasn't found, then we have no entry for this key.
/ / the second step
if (index < 0) {
return index;
}
// If the key at the returned index matches, that's what we want.
/ / step 4
if (key.equals(mArray[index<<1]) {return index;
}
/ / step 5
// 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.
/ / step 6
return ~end;
}
Copy the code4. Caching mechanism
It makes sense that ArrayMap contains a mechanism for caching mHashes and mArray arrays to avoid memory jitter caused by frequent array creation. Bundle is one of the most frequently used classes in The Android system. It stores key-value pairs internally through an ArrayMap, as can be seen from the Bundle’s parent class, BaseBundle. So ArrayMap’s array caching mechanism is more of an optimization measure in the face of system runtime in my opinion
public class BaseBundle {
@UnsupportedAppUsage
ArrayMap<String, Object> mMap = null;
public void putBoolean(@Nullable String key, boolean value) {
unparcel();
mMap.put(key, value);
}
void putByte(@Nullable String key, byte value) {
unparcel();
mMap.put(key, value);
}
void putChar(@Nullable String key, char value) { unparcel(); mMap.put(key, value); }...}Copy the codeThe put method uses an array caching and reuse mechanism inside
@Override
public V put(K key, V value) {...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;
// Try to initialize mHashes and mArray with array reuse mechanism
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);
}
// Try to reclaim ohashes and oarrayfreeArrays(ohashes, oarray, osize); }...return null;
}
Copy the code1. Cache arrays
The implementation of the array cache logic corresponds to the freeArrays method, which is used to cache mHashes and Marrays. This method is called whenever The Array is expanded, but not all arrays are cached. Instead, the size of the array and the total number of caches are limited
First, ArrayMap contains several global static variables and constants to control and implement array caching. As you can see from the freeArrays method, the logic of the if and else blocks is basically the same, except that the conditions that trigger the cache and the cache pool used are different
For example, if the hashes array length is BASE_SIZE * 2, and the current cache total does not exceed CACHE_SIZE, the cached array is stored in a one-way linked list constructed by mTwiceBaseCache. MTwiceBaseCache uses the structure of a one-way list to concatenate multiple arrays. The first array element value of the mArray to be cached will first point to mTwiceBaseCache, the second array element value will point to mHashes, and then mArray will become the new head of the one-way list. MArray became the new mTwiceBaseCache. In this caching mechanism, the final mTwiceBaseCache points to the mArray of this cache, the first element value of mArray points to the mArray of the last cache, and the second element value points to the mHashes of this cache, thus forming a one-way linked list structure
// Cache BASE_SIZE arrays
static Object[] mBaseCache;
MBaseCache Specifies the number of cached arrays
static int mBaseCacheSize;
// Cache arrays of BASE_SIZE * 2 length
static Object[] mTwiceBaseCache;
//mTwiceBaseCache Number of cached arrays
static int mTwiceBaseCacheSize;
private static final int BASE_SIZE = 4;
// Maximum number of caches for mBaseCacheSize and mTwiceBaseCacheSize
private static final int CACHE_SIZE = 10;
// Use it as a synchronization lock
private static final Object sBaseCacheLock = new Object();
private static final Object sTwiceBaseCacheLock = new Object();
// Cache hashes and array
private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
if (hashes.length == (BASE_SIZE*2)) {
synchronized (sTwiceBaseCacheLock) {
if (mTwiceBaseCacheSize < CACHE_SIZE) {
// The first element points to mTwiceBaseCache
array[0] = mTwiceBaseCache;
// The second element points to hashes
array[1] = hashes;
for (int i=(size<<1) -1; i>=2; i--) {
// Remove redundant references to avoid memory leaks and facilitate GC
array[i] = null;
}
// Array becomes the head of a single linked list
mTwiceBaseCache = array;
mTwiceBaseCacheSize++;
if (DEBUG) Log.d(TAG, "Storing 2x cache " + array
+ " now have " + mTwiceBaseCacheSize + " entries"); }}}else if (hashes.length == BASE_SIZE) {
synchronized (sBaseCacheLock) {
if (mBaseCacheSize < CACHE_SIZE) {
array[0] = mBaseCache;
array[1] = hashes;
for (int i=(size<<1) -1; i>=2; i--) {
array[i] = null;
}
mBaseCache = array;
mBaseCacheSize++;
if (DEBUG) Log.d(TAG, "Storing 1x cache " + array
+ " now have " + mBaseCacheSize + " entries"); }}}}Copy the code2. Reuse arrays
The purpose of caching arrays is naturally for subsequent reuse. The reuse logic of arrays corresponds to the allocArrays method, which is used to apply for a larger array space for mHashes and mArray, which is obtained by reusing arrays or new initialization
When the array is cached, the array length will be judged. Only when the array length is BASE_SIZE * 2 or BASE_SIZE will the cache be carried out, so naturally, only when the array target length size is one of these two values will the reuse condition be met. The logic of the allocArrays method is also very simple. You just need to get the header of the one-way linked list and assign it to mHashes and mArray, and make the second node of the linked list become the new header. If the reuse criteria are not met or the reuse fails, then two new array objects need to be rebuilt
// Cache BASE_SIZE arrays
static Object[] mBaseCache;
MBaseCache Specifies the number of cached arrays
static int mBaseCacheSize;
// Cache arrays of BASE_SIZE * 2 length
static Object[] mTwiceBaseCache;
//mTwiceBaseCache Number of cached arrays
static int mTwiceBaseCacheSize;
private static final int BASE_SIZE = 4;
// Maximum number of caches for mBaseCacheSize and mTwiceBaseCacheSize
private static final int CACHE_SIZE = 10;
// Use it as a synchronization lock
private static final Object sBaseCacheLock = new Object();
private static final Object sTwiceBaseCacheLock = new Object();
private void allocArrays(final int size) {
if (mHashes == EMPTY_IMMUTABLE_INTS) {
throw new UnsupportedOperationException("ArrayMap is immutable");
}
if (size == (BASE_SIZE*2)) {
synchronized (sTwiceBaseCacheLock) {
if(mTwiceBaseCache ! =null) {
final Object[] array = mTwiceBaseCache;
mArray = array;
try {
// The next node that points to the header becomes the new header of the list
mTwiceBaseCache = (Object[]) array[0];
mHashes = (int[]) array[1];
if(mHashes ! =null) {
// Remove redundant references
array[0] = array[1] = null;
mTwiceBaseCacheSize--;
if (DEBUG) {
Log.d(TAG, "Retrieving 2x cache " + mHashes
+ " now have " + mTwiceBaseCacheSize + " entries");
}
return; }}catch (ClassCastException e) {
}
// Whoops! Someone trampled the array (probably due to not protecting
// their access with a lock). Our cache is corrupt; report and give up.
Slog.wtf(TAG, "Found corrupt ArrayMap cache: [0]=" + array[0]
+ " [1]=" + array[1]);
// The cache mechanism has found a problem, and all previous caches are deprecated
mTwiceBaseCache = null;
mTwiceBaseCacheSize = 0; }}}else if (size == BASE_SIZE) {
synchronized (sBaseCacheLock) {
if(mBaseCache ! =null) {
final Object[] array = mBaseCache;
mArray = array;
try {
mBaseCache = (Object[]) array[0];
mHashes = (int[]) array[1];
if(mHashes ! =null) {
array[0] = array[1] = null;
mBaseCacheSize--;
if (DEBUG) {
Log.d(TAG, "Retrieving 1x cache " + mHashes
+ " now have " + mBaseCacheSize + " entries");
}
return; }}catch (ClassCastException e) {
}
// Whoops! Someone trampled the array (probably due to not protecting
// their access with a lock). Our cache is corrupt; report and give up.
Slog.wtf(TAG, "Found corrupt ArrayMap cache: [0]=" + array[0]
+ " [1]=" + array[1]);
mBaseCache = null;
mBaseCacheSize = 0;
}
}
}
mHashes = new int[size];
mArray = new Object[size<<1];
}
Copy the code3, summarize
As mentioned above, only BASE_SIZE or BASE_SIZE * 2 arrays will be reused by cache, and the capacity expansion operations of mHashes and mArray will try to make the size of the expanded array be one of these two values, which can be seen from the algorithm used to calculate the capacity expansion by the PUT method
@Override
public V put(K key, V value) {
final int osize = mSize;
final inthash; ...if (osize >= mHashes.length) {
// Calculate the size of the expanded array
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;
finalObject[] oarray = mArray; allocArrays(n); ... freeArrays (ohashes oarray, osize); }...return null;
}
Copy the codeTherefore, although the constructor of ArrayMap does not directly use BASE_SIZE as the default length of the array, it tries to align the values of BASE_SIZE and BASE_SIZE * 2 during the expansion process, which is helpful for array reuse
In addition, the capacity expansion operation of ArrayMap is also relatively restrained when applying for memory. When the array length exceeds BASE_SIZE * 2, the capacity expansion is only 1.5 times of the current size, and the capacity expansion mechanism will only be triggered when the mHashes capacity is insufficient. The HashMap, on the other hand, triggers the expansion mechanism when the load factor ratio is reached (when the array is not full), and it also expands to twice its capacity. So ArrayMap is more efficient with memory space
5. Summarize the advantages and disadvantages
ArrayMap can be seen in its caching mechanism, which caches and reuses arrays of size 4 or 8, both of which are relatively small. The Android system is sensitive to memory, and when it needs to store key-value pairs, it often faces scenarios with high usage frequency but small data volume. For example, when we jump to an Activity, we usually store the jump parameters through the Bundle, but the amount of data is usually very small. Therefore, ArrayMap is used to store the key-value pairs inside the Bundle. ArrayMap is more restrained in memory requisitions than HashMap, storing key-value pairs together in a tighter data structure and using more memory
On the other hand, ArrayMap’s storage structure also leads to a much lower search efficiency than HashMap. When there is a large amount of data, ArrayMap may need several binary lookups to locate elements, while HashMap only needs one hash calculation to locate elements without hash conflicts, and even if there are hash conflicts, it only needs to traverse part of the conflicting elements
Therefore, ArrayMap is suitable for scenarios with small amounts of data, where search efficiency is not affected much and memory utilization can be significantly improved. If you have a large amount of data, consider using HashMap instead
6. Association classes
The system also includes a collection framework class for storing values of non-repeating elements: ArraySet, which, as its name suggests, implements the Set interface. An ArraySet uses two arrays to store hash and value, namely, mHashes and mArray. The implementation logic is basically the same as that of an ArrayMap, except that it will determine whether the value is duplicate when storing the value, which will not be described here