Want to see more articles from me: [Xutong Zhang’s blog] blog.csdn.net/zxt0601 Want to come to gayHub and ME gaygayup: [McXtzhang’s Github home page] github.com/mcxtzhang
1 overview
In the previous article, we talked about HashMap and LinkedHashMap ArrayMap. [root@linkedhashMap] [root@linkedhashMap] [root@linkedhashMap] [root@linkedhashMap] [root@linkedhashMap] [root@linkedhashMap]
This article will start with a few common ways to read the source code for SparseArray. Read the source code in order of constructor -> common API (add, delete, change, search), and explain the meaning of some of the variables involved in the reading method. Understand the features and application scenarios of SparseArray.
If this article has incorrect conclusion, statement, please put forward and I discuss, common progress, thank you.
2 profile
In general, SparseArray
is a data structure used to replace a HashMap on the Android platform. More specifically, it is used to replace a HashMap with a key of type INT and a value of type Object. Similar to ArrayMap, its implementation is more space-efficient than HashMap, and because the key is specified as an int, it also saves the performance cost of int-INTEGER boxing and unboxing operations.
It implements only the Implements Cloneable interface, so you can’t use Map as a declaration type.
It is also thread-unsafe, allowing value to be null.
In principle, its internal implementation is also based on two arrays. An int[] array mKeys is used to hold the key of each item. The key itself is of type int. An Object[] array mValues that holds value. It has the same capacity as the key array.
Like ArrayMap, it is more suitable for scaling up, requiring only array copying and no rebuilding of hash tables.
It is also not suitable for large data storage. When storing large amounts of data, its performance degrades by at least 50%.
Less efficient than traditional HashMap time. Because it sorts the key from smallest to largest, use dichotomy to query the index of the key in the array. When adding, deleting and searching data, the binary search method is first used to get the corresponding index, and then the operations such as adding, searching and deleting are carried out through index.
So it’s stored in order of the size of the key.
In addition, SparseArray makes some optimizations when deleting to improve performance: When deleting an element, instead of immediately removing it from the value array and compressing the array, it marks it as deleted in the Value array. This allows you to reuse this space when storing the value of the same key. If the space is not reused, then gc (garbage collection) is performed at an appropriate time to compress the array so as not to waste space.
Applicable scenarios:
- Small amount of data (within thousands)
- Space is more important than time
- You need to use
MapAnd,keyforintType.
Sample code:
SparseArray<String> stringSparseArray = new SparseArray<>();
stringSparseArray.put(1,"a");
stringSparseArray.put(5,"e");
stringSparseArray.put(4,"d");
stringSparseArray.put(10,"h");
stringSparseArray.put(2,null);
Log.d(TAG, "onCreate() called with: stringSparseArray = [" + stringSparseArray + "]");Copy the codeOutput:
OnCreate () called with: stringSparseArray = [{1=a, 2=null, 4=d, 5=e, 10=h}]Copy the code3 constructors
Private static final Object DELETED = new Object(); Private Boolean mGarbage =false; Private int[] mKeys; Private Object[] mValues; Private int mSize; // The default constructor, initialized to 10 publicSparseArray() { this(10); } public SparseArray(int initialCapacity) {// if the initialCapacity is 0, two lightweight references are assignedif (initialCapacity == 0) {
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else{/ / initializes the corresponding to the length of the array mValues = ArrayUtils. NewUnpaddedObjectArray (initialCapacity); mKeys = new int[mValues.length]; } // Set size to 0 mSize = 0; }Copy the codeConstructor has no bright spot, passing by. Focus on a few variables:
- The underlying data structure is
int[]andObject[]Type array. mGarbage: Whether GC is requiredDELETED: is used to mark the value array as a deleted tag
4 increase and change
4.1 Individual addition and modification:
Public void put(int key, E value) { Found to be inserted into the key of the subscript index int I = ContainerHelpers. BinarySearch (mKeys, mSize, key); // If index is positive, the key exists, and value is overriddenif (i >= 0) {
mValues[i] = value;
} else{// If the index is negative, the key does not exist. // If the index is negative, the key does not exist. // If I is not out of bounds and the corresponding position is a deleted mark, the space is reusedif(I < mSize && mValues[I] == DELETED) {// After assignment, return mKeys[I] = key; mValues[i] = value;return; } // If GC is required and capacity expansion is requiredif(mGarbage &&msize >= mkeys.length) {// Trigger the garbage collector (); // after gc, subscript I may change, So again, use the position of the binary Search to find should insert I / / Search again because indices have changed. I = ~ ContainerHelpers. BinarySearch (mKeys, mSize. key); MKeys = GrowingArrayUtils. Insert (mKeys, mSize, I, key); // Insert value (may need to be expanded) mValues = GrowingArrayUtils. // set size increment mSize++; Static int binarySearch(int[] array, int size, int value) {int lo = 0; int hi = size - 1;whileFinal int mid = (lo + hi) >>> 1; final int midVal = array[mid];if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
returnmid; // value found}} // If not found, lo is a positive number. Take the positive and take the negative and return the negativereturn~lo; // value not present} // garbage collection function private voidgc() {// save the collection size before GC int n = mSize; Int o = 0; int o = 0; int[] keys = mKeys; Object[] values = mValues; Delete all elements whose values are DELETED from the values arrayfor(int i = 0; i < n; i++) { Object val = values[i]; // If the current value is not marked as deletedif(val ! = DELETED) {// compress keys and values arraysif(i ! = o) { keys[o] = keys[i]; values[o] = val; Values [I] = null; } // increment o o++; }} // Change the identity without GC mGarbage =false; MSize = o; }Copy the codeGrowingArrayUtils.insert:
//
public static int[] insert(int[] array, int currentSize, int index, int element) {
Asserts that the current collection length is less than or equal to the array length
assert currentSize <= array.length;
// If no capacity expansion is required
if (currentSize + 1 <= array.length) {
// Move the array element one bit from index
System.arraycopy(array, index, array, index + 1, currentSize - index);
// Assign to index
array[index] = element;
/ / return
return array;
}
// Capacity needs to be expanded
// Build a new array
int[] newArray = new int[growSize(currentSize)];
// Copy the data before index in the original array to the new array
System.arraycopy(array, 0, newArray, 0, index);
// Assign to index
newArray[index] = element;
// Assign index and subsequent data from the original array to the new array
System.arraycopy(array, index, newArray, index + 1, array.length - index);
/ / return
return newArray;
}
// Return the appropriate capacity based on the current size
public static int growSize(int currentSize) {
If the current size is less than or equal to 4, return 8, otherwise return twice the current size
return currentSize <= 4 ? 8 : currentSize * 2;
}Copy the code-
Binary search, if not found return subscript, JDK implementation, return -(low + 1); // key not found. In this way, at the function call, we can determine whether index is found based on the return value. Take the opposite of negative index to get the insertion position.
-
If the current capacity is less than or equal to 4, the capacity after expansion is 8. Otherwise, the capacity is twice the current capacity. Unlike ArrayList and ArrayMap (doubled),ArrayMap is the same as Vector (doubled).
-
Capacity expansion is still done by copying and overwriting arrays. Similar to the ArrayList.
5 delete
5.1 Deleting a vm by Key
Public void remove(int key) {delete(key); } public void the delete (int key) {/ / delete binary search to get the key place of the index int I = ContainerHelpers. BinarySearch (mKeys, mSize, key); // If >=0, it existsif(I >= 0) {// Change the location of values array to a DELETED flagif(mValues[i] ! = DELETED) { mValues[i] = DELETED; // And modify mGarbage to indicate that GC mGarbage = is required latertrue; }}}Copy the code5.2 Deleting a vm by Index
Public void removeAt(int index) {// Remove the index from the specified positionif(mValues[index] ! = DELETED) { mValues[index] = DELETED; mGarbage =true; }}Copy the code5.3 Deleting data in Batches
Public void removeAtRange(int index, int size) {// Final int end = math.min (mSize, index + size); //forLoop through a single delete operationfor(int i = index; i < end; i++) { removeAt(i); }}Copy the code6 check
6.1 Querying Information By Key
Public E get(int key) {public E get(int key) {returnget(key, null); } // Query by key, if key does not exist, ValueIfKeyNotFound public E get(int key, E valueIfKeyNotFound) {/ / binary search to index key int I = ContainerHelpers. BinarySearch (mKeys, mSize, key); / / does not existif (i < 0 || mValues[i] == DELETED) {
return valueIfKeyNotFound;
} else{/ /return(E) mValues[i]; }}Copy the code6.2 Query By subscript
Public int keyAt(int index) {public int keyAt(int index) {public int keyAt(int index)if (mGarbage) {
gc();
}
returnmKeys[index]; } public E valueAt(int index)if (mGarbage) {
gc();
}
return (E) mValues[index];
}Copy the code6.3 Querying subscripts
Public int indexOfKey(int key) {public int indexOfKey(int key) {public int indexOfKey(int key)if(mGarbage) { gc(); } // Binary search returns the corresponding subscript, which may be negativereturnContainerHelpers.binarySearch(mKeys, mSize, key); } public int indexOfValue(E value)if(mGarbage) { gc(); } // Binary lookup is not used like key. If there are multiple keys corresponding to the same value, then only the first index will be returned. If there are multiple keys corresponding to the same value, then the first index will be returnedfor (int i = 0; i < mSize; i++)
if (mValues[i] == value)
return i;
return- 1; }Copy the code- Binary lookup is not used like key when querying subscripts by value. Is a directLinear traversalTo compare, and unlike other collection classes
equalsThe comparison is directly used here= = - If there are multiple keys corresponding to the same value, only the first index is returned
conclusion
SparseArray source code is relatively simple, after the previous several collections of source baptism, it is very easy to grasp the general process and the key idea: time for space.
The Android SDK also provides three sets of similar ideas:
SparseBooleanArray.valueforbooleanSparseIntArray.valueforintSparseLongArray.valueforlong
The only difference between them and SparseArray is the type of value, which can be of any type. And these are the three basic types that are commonly used out of the box.