/ Today’s Tech News /
Yesterday，IDC released the current competitive landscape of the 5G mobile phone market in China based on its monthly tracking report on the Chinese smartphone market.According to the IDC report, the competitive layout of the first batch of 5G terminals has begun, with the overall shipment of 5G mobile phones in China in the third quarter of 2019 being about 485,000 units, with vivo accounting for over 54.3% of the market share, followed by Samsung, Huawei, and Xiaomi.
/ Author Profile /
This article is contributed byYe Zhichen, who shares his understanding of SparseArray, which is believed to be helpful to everyone! Thanks to the author for the wonderful article.
Ye Zhichen’s blog address:
https://juejin.im/user/57c2ea9befa631005abd00c6
/ Introduction /
Developers using Android Studio as their IDE may encounter a phenomenon where if a variable of type Map<Integer, Object> is declared in the code, Android Studio will prompt: Use new SparseArray<Object>(…) instead for better performance … This means that using SparseArray<Object> is more efficient and can replace HashMap. Here we will introduce the internal principles of SparseArray.
/ Main Text /
Basic Concepts
Let’s take a look at how to use SparseArray:
SparseArray<String> sparseArray = new SparseArray<>();
sparseArray.put(100, "leavesC");
sparseArray.remove(100);
sparseArray.get(100);
sparseArray.removeAt(29);
SparseArray< E > is equivalent to Map< Integer,E >, where the key is fixed as an int type. During initialization, only the data type of the value needs to be declared. Internally, it uses two arrays to store the key list and value list: int[] mKeys and Object[] mValues.
The elements in mKeys and mValues correspond as follows:
-
Assuming we want to store the key-value pair with key 10 and value 200 in SparseArray, we first store 10 inmKeys, and if 10 corresponds to the index index in mKeys, we store the value in mValues[index]
-
The elements in mKeys are stored in increasing order, and each time a new key-value pair is stored, mKeys is sorted using a binary search method
The most important point is that SparseArray avoids the boxing and unboxing operations every time a value is accessed in Map, as the key values are all of the primitive data type int, which helps improve performance.
Global Variables
The boolean variablemGarbageis also one of the optimization points of SparseArray, which is used to mark whether there are elements pending garbage collection (GC). When this value is set totrue, it means that garbage collection is needed, but the collection operation does not occur immediately; it will be performed later in subsequent operations.
// Default element value for array elements when no external value is specified
private static final Object DELETED = new Object();
// Used to mark whether there are elements pending garbage collection (GC)
private boolean mGarbage = false;
private int[] mKeys;
private Object[] mValues;
// Current collection element size
// This value may not always be accurate, as it may occur that only one of the key and value is deleted
// Therefore, GC needs to be performed before calling size() method
private int mSize;
Constructor
The default size of the key array and value array is 10. If the estimated size of the data is known during initialization, the initial capacity can be specified directly to avoid subsequent expansion operations.
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;
}
Adding Elements
There are several methods to add elements, mainly looking atput(int key, E value)method, which uses the binary search method provided byContainerHelpersclass:binarySearch, to find the current index of the target key inmKeys(if the key already exists) or the target index (if the key does not exist).
The return value of the binarySearch method has two cases:
-
If the corresponding key exists in mKeys, it directly returns the corresponding index
-
If the corresponding key does not exist in mKeys
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
}
It can be seen that even if the target key does not exist in mKeys, its return value still points to the position where the key should be stored. By performing the ~ operation on the calculated index value, the return value will definitely be 0 or negative, thus distinguishing it from the situation where the target key is found (return value greater than 0).
This shows the cleverness of this method, as a single return value can distinguish multiple situations, and using this method to store data ensures that the internal values of mKeys are always sorted in increasing order.
public void put(int key, E value) {
// Use binary search to find the index of the specified key in mKeys
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
// If found, directly assign the value
if (i >= 0) {
mValues[i] = value;
} else {
i = ~i;
// If the target position has not yet been assigned a value, store the data directly, which corresponds to case 2.1
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
// The following operations correspond to cases 2.1 and 2.2:
if (mGarbage && mSize >= mKeys.length) {
gc();
// Re-search after GC, as values may have changed
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
// Store the data in the array by copying or expanding the array
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
Removing Elements
As mentioned above, the boolean variable mGarbage is used to mark whether there are elements pending garbage collection (GC). When this value is set to true, it means that garbage collection is needed, but the collection operation does not occur immediately; it will be completed later. The following methods only cut off the reference in mValues when removing elements, while mKeys are not collected; this operation will be handled in gc().
// If there exists an element value corresponding to the key, remove it
public void delete(int key) {
// Use binary search to find the index of the specified key in mKeys
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
// Mark that garbage collection is needed
mGarbage = true;
}
}
}
// Basically the same as the delete method, except that it will return the element value 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;
return old;
}
}
return null;
}
// Omitted other simpler methods for removing elements
Finding Elements
There are many methods for finding elements, but the logic is quite simple.
// Find the corresponding element value based on the key, return default value if not found
@SuppressWarnings("unchecked")
public E get(int key, E valueIfKeyNotFound) {
// Use binary search to find the index of the specified key in mKeys
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
// If the key is not found or has not been assigned a value, return the default value
if (i < 0 || mValues[i] == DELETED) {
return valueIfKeyNotFound;
} else {
return (E) mValues[i];
}
}
// Find the corresponding index based on the value
public int indexOfValue(E value) {
if (mGarbage) {
gc();
}
for (int i = 0; i < mSize; i++) {
if (mValues[i] == value) {
return i;
}
}
return -1;
}
// Similar to the indexOfValue method, but indexOfValue method compares == to determine if they are the same object
// This method uses equals method to determine if they are the same object
public int indexOfValueByValue(E value) {
if (mGarbage) {
gc();
}
for (int i = 0; i < mSize; i++) {
if (value == null) {
if (mValues[i] == null) {
return i;
}
} else {
if (value.equals(mValues[i])) {
return i;
}
}
}
return -1;
}
// Omitted other methods
Garbage Collection
Because there may be cases in SparseArray where only either the value or the key is removed, leading to invalid references in the array, thegc()method is used to remove invalid references and merge the positions of valid elements together.
private void gc() {
int n = mSize;
// o value is used to represent the number of elements after GC
int o = 0;
int[] keys = mKeys;
Object[] values = mValues;
for (int i = 0; i < n; i++) {
Object val = values[i];
// If the element value is not the default value DELETED, it means that this position may need to move data
if (val != DELETED) {
// The following code snippet assigns the value at index i to index o
// So if i == o, no code execution is needed
if (i != o) {
keys[o] = keys[i];
values[o] = val;
values[i] = null;
}
o++;
}
}
mGarbage = false;
mSize = o;
}
/ Conclusion /
From the above interpretation, the main advantages of SparseArray are as follows:
-
Avoids boxing and unboxing operations of primitive data types
-
Unlike Map where each storage node is a class object, SparseArray does not require a structure for wrapping, making the storage cost of a single element much lower
-
In cases with a small amount of data, the lookup efficiency is high (binary search)
-
Delays the timing of garbage collection, only performing it when needed
The disadvantages are as follows:
-
Inserting new elements may cause a large number of array elements to be moved
-
When the amount of data is large, the lookup efficiency (binary search) will significantly decrease
The complete detailed source code annotation of SparseArray.java is as follows:
https://github.com/leavesC/JavaKotlinAndroidGuide/blob/master/android_collections/SparseArray.java
Recommended Reading:
Custom View in Kotlin: Implementing an Arched Progress Bar
Can Android still execute background tasks? Try WorkManager
Show off some multi-threading operation skills, and learn new knowledge points
Welcome to follow my public account
Learning technology or contributing articles
Long press the image above to identify the QR code to follow