SparseArray
Sparse [sp ɑ ː rs]
The document is introduced
/** * <code>SparseArray</code> maps integers to Objects and, unlike a normal array of Objects, * its indices can contain gaps. <code>SparseArray</code> is intended to be more memory-efficient * than a * <a href="/reference/java/util/HashMap"><code>HashMap</code></a>, because it avoids * auto-boxing keys and its data structure doesn't rely on an extra entry object * for each mapping. * * <p>Note that this container keeps its mappings in an array data structure, * using a binary search to find keys. The implementation is not intended to be appropriate for * data structures * that may contain large numbers of items. It is generally slower than a * <code>HashMap</code> because lookups require a binary search, * and adds and removes require inserting * and deleting entries in the array. For containers holding up to hundreds of items, * the performance difference is less than 50%. * * <p>To help with performance, the container includes an optimization when removing * keys: instead of compacting its array immediately, it leaves the removed entry marked * as deleted. The entry can then be re-used for the same key or compacted later in * a single garbage collection of all removed entries. This garbage collection * must be performed whenever the array needs to be grown, or when the map size or * entry values are retrieved. * * <p>It is possible to iterate over the items in this container using * {@link #keyAt(int)} and {@link#valueAt(int)}. Iterating over the keys using * <code>keyAt(int)</code> with ascending values of the index returns the * keys in ascending order. In the case of <code>valueAt(int)</code>, the * values corresponding to the keys are returned in ascending order. */
Copy the codeSparseArray is a k-V key-value pair storage class provided by Google. The key is fixed to int and the value is generic (internally Object). although
Internal main method
ContainerHelpers
Utility class, binary search method to find int or long, find return index, not find return negative value (negative).
PS:
>>: Move right with sign >>>: The unsigned right shift with the highest digit 1 is negative, Negative value an invert 01111111111111111111111111111111 int fill very much: 01111111111111111111111111111111 10000000000000000000000000000000 Int minVal fill: 11111111111111111111111111111111 because in the computer system, numerical net complement and storage. The complement of 0 is in the positive range, so the high range of int values (positive range) is minus 1: -2^31~2^31-1Copy the code// 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 codeput
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
mValues[i] = value;
} else {
i = ~i;
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
// It may need to be rearranged, if rearranged, the index position is recalculated.
if (mGarbage && mSize >= mKeys.length) {
gc();
// Search again because indices may have changed.i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); } mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); mSize++; }}Copy the codeThe binary search method is used to find the index of the search value. If the index is greater than 0, it exists in the set. If the index is smaller than 0, it does not exist. Find the update; If no element is found, the index position to be inserted is obtained (the negative number returned is the insertion position is reversed), and the key array and value array are inserted into the corresponding index element respectively. That is, the elements are sorted by the size of the key. Insert elements by calling System. arrayCopy inside growingArrayUtils.insert, where the size of the internal real array is changed.
delete
Delete a key-value pair; instead of actually deleting it, it marks its value as DELETED and mGarbage as true. The member GC method is then triggered in the put, SIZE, keyAt, valueAt, setValueAt, indexForKey, indexOfValue, indexOfValue, indexOfValueByValue, Append and other methods.
/** * Removes the mapping from the specified key, if there was any. */
public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if(mValues[i] ! = DELETED) { mValues[i] = DELETED; mGarbage =true; }}}Copy the codegc
Iterate through the array, place elements not marked as DELETE in front of the array, and refresh the size. (Size is not the size of the two arrays in memory, but the size of the significant bits)
private void gc(a) {
// 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) {if(i ! = o) { keys[o] = keys[i]; values[o] = val; values[i] =null;
}
o++;
}
}
mGarbage = false;
mSize = o;
// Log.e("SparseArray", "gc end with " + mSize);
}
Copy the codeget
Get elements by key. Returns default or NULL if not obtained by calling method.
/** * Gets the Object mapped from the specified key, or null * if no such mapping has been made. */
public E get(int key) {
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) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i < 0 || mValues[i] == DELETED) {
return valueIfKeyNotFound;
} else {
return(E) mValues[i]; }}Copy the codeappend
In contrast to PUT, append is appended to the end if the append element is larger than the largest, rather than binary search and then insert. Put is called when it’s not greater than the last one.
/** * Puts a key/value pair into the array, optimizing for the case where * the key is greater than all existing keys in the array. */
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 codeAdvantages and disadvantages of SparseArray compared to HashMap and ArrayMap:
SparseArray’s limitations are that the key must be int and the value must be Object. This prevents the automatic boxing of keys from generating too many objects. However, if the key value is the same, the data will be overwritten directly.
SparseArray is not guaranteed to preserve their insertion order, so be careful when iterating. SparseArray does not have iterators. SparseArray implements only the Cloneable interface and does not inherit the Collection, List, or Map interface.
Finding data using dichotomy is significantly slower than using HashCode, so the larger the data, the slower the disadvantage of finding data is more obvious, so SparseArray is suitable for scenarios with less than 1,000 data.
Advantages:
- Avoid boxing basic data types
- No additional structures are required and the storage cost of individual elements is lower
- Random access is more efficient when the amount of data is small
Disadvantages:
- Insert operations need to copy the array, reducing the efficiency of adding and deleting
- When there is a large amount of data, copying the array is expensive, and so is gc()
- When the amount of data is large, the query efficiency decreases significantly
— — — — — — — —
References:
Summary of the pros and cons: blog.csdn.net/b1480521874…