Android data structure optimization tutorial

transient Entry[] table = (Entry<K,V>[]) EMPTY_TABLE;

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, );
    for (Entry<K, V> e = table[i]; e != null; e = ) {
        Object k;
        if ( == hash && ((k = ) == key || (k))) {
            V oldValue = ;
             = value;
            (this);
            return oldValue;
        }
    }
    modCount++;	
    addEntry(hash, key, value, i);
    return null;
}

final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return .stringHash32((String) k);
        }
        h ^= ();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    static int indexFor(int h, int length) {
        return h & (length-1);
    }

void addEntry(int hash, K key, V value, int bucketIndex) {
    	//sizi is greater than the threshold 2 times the capacity expansion        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * );
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, );
        }
        createEntry(hash, key, value, bucketIndex);
    }

void createEntry(int hash, K key, V value, int bucketIndex) {  
        Entry<K,V> e = table[bucketIndex]; 
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }  

public V get(Object key) {   
    if (key == null)   
        return getForNullKey();   
    int hash = hash(());   
    for (Entry<K,V> e = table[indexFor(hash, )];   
        e != null;   
        e = ) {   
        Object k;   
        if ( == hash && ((k = ) == key || (k)))   
            return ;   
    }   
    return null;   
}

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = ;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);//Use to move all the elements of the original table into the newTable    table = newTable;  //Assign newTable to table    threshold = (int)(newCapacity * loadFactor);//Recalculate the critical value}

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = ;
        //Transfer the old table        for (Entry<K,V> e : table) {
            // Hash all nodes            while(null != e) {
                Entry<K,V> next = ;
                if (rehash) {
                     = null ==  ? 0 : hash();
                }
                int i = indexFor(, newCapacity);
                 = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);
    threshold = (int) (capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);//Initialize hashSeed variable}
private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    return number >= MAXIMUM_CAPACITY
        ? MAXIMUM_CAPACITY
        : (number > 1) ? ((number - 1) << 1) : 1;
}

public class SparseArray<E> implements Cloneable {
    private static final Object DELETED = new Object();
    private boolean mGarbage = false;
    private int[] mKeys;
    private Object[] mValues;
    private int mSize;

public void put(int key, E value) {
    int i = (mKeys, mSize, key);
    //It turns out that there is already a key. It may be that after removing, the value stores DELETED, or it may store the old value, so replace it    if (i >= 0) {
        mValues[i] = value;
    } else {
        //Not found, inverse i, get i=lo()        i = ~i;
        //If i is less than the array length, and mValues==DELETED (the corresponding key of i is deleted delayed)        if (i < mSize && mValues[i] == DELETED) {
            //Directly replace it to realize the real deletion of the original key-value pair            mKeys[i] = key;
            mValues[i] = value;
            return;
        }
        //There may be delayed deletion elements in the array and the current array length is full, so it cannot be added        if (mGarbage && mSize >= ) {
            //Real deletion, clear all delayed deleted elements from the array;            gc();
            //After clearing, redetermine the target position of the current key in the array;            // Search again because indices may have changed.
            i = ~(mKeys, mSize, key);
        }
        //There is no garbage or the current array can still be added, and there is no need to expand the capacity. All the elements after i will be moved back, and there will still be a garbage key in the array that is DELETED;        mKeys = (mKeys, mSize, i, key);
        mValues = (mValues, mSize, i, value);
        //The new element is successfully added, the number of potentially available elements + 1        mSize++;
    }
}

// This is (), but doesn't do any argument validation.
//The first parameter array is an array with keys, the second is the number of elements in the array (the length of keys is not necessarily equal), and the third value is the target keystatic int binarySearch(int[] array, int size, int value) {
    //lo is the left boundary of binary search    int lo = 0;
    //hi is the right boundary of binary search    int hi = size - 1;
    //Not found yet, continue to search    while (lo <= hi) {
        //Two at the left border + right border to get the index of mid        final int mid = (lo + hi) >>> 1;
        //Get intermediate elements        final int midVal = array[mid];
        // The target key is in the right part.  .  .  .  I feel this part is too simple        if (midVal < value) {
            lo = mid + 1;
        } else if (midVal > value) {
            hi = mid - 1;
        } else {
            //Equal, found, return the subscript corresponding to the key in the array;            return mid;  // value found
        }
    }
    //The element was not found, reversed to lo!  !  !  !  !  Very important    return ~lo;  // value not present
}

public void delete(int key) {
    //Look for the subscript of the corresponding key in the array. If it exists, return the subscript. If it does not exist, return the inverse of the subscript;    int i = (mKeys, mSize, key);
    //The key exists in the mKeys array, delete the element, replace the original value with DELETED, and serves as a marker;    if (i >= 0) {
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED;
            mGarbage = true;
        }
    }
}
/**
 * @hide
 * Removes the mapping from the specified key, if there was any, returning the old value.
 */
public E removeReturnOld(int key) {
    int i = (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;
}
/**
 * Alias for {@link #delete(int)}.
 */
public void remove(int key) {
    delete(key);
}

@Override
    public V put(K key, V value) {
        //Current capacity        final int osize = mSize;
        //The hash value of key        final int hash;
        //Subscript of key hash        int index;
        if (key == null) {
            //The key is empty hash value is 0            hash = 0;
            // Find the subscript of the hash value of the key            index = indexOfNull();
        } else {
            //The hash value of key            hash = mIdentityHashCode ? (key) : ();
            // Find the subscript of the hash value of the key            index = indexOf(key, hash);
        }
        if (index >= 0) {
            //The element to be added already exists, then the replacement operation is performed directly            index = (index<<1) + 1;
            final V old = (V)mArray[index];
            mArray[index] = value;
            return old;
        }
        //Inverse to get the position of the element to be added        index = ~index;
        if (osize >= ) {
            //Expand new capacity            final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
                    : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
            if (DEBUG) (TAG, "put: grow from " +  + " to " + n);
            //Original hash array            final int[] ohashes = mHashes;
            //Original scatter list            final Object[] oarray = mArray;
            //Expand operation            allocArrays(n);
            if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
                throw new ConcurrentModificationException();
            }
            if ( > 0) {
                if (DEBUG) (TAG, "put: copy 0-" + osize + " to 0");
                //Copy the original array back to the new array                (ohashes, 0, mHashes, 0, );
                (oarray, 0, mArray, 0, );
            }
            //Recycling and Release Operation            freeArrays(ohashes, oarray, osize);
        }
        if (index < osize) {
            if (DEBUG) (TAG, "put: move " + index + "-" + (osize-index)
                    + " to " + (index+1));
            //Move the data at index (including index) and afterwards back            (mHashes, index, mHashes, index + 1, osize - index);
            (mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
        }
        if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
            if (osize != mSize || index >= ) {
                throw new ConcurrentModificationException();
            }
        }
        //Add data to index        mHashes[index] = hash;
        mArray[index<<1] = key;
        mArray[(index<<1)+1] = value;
        mSize++;
        return null;
    }
private void allocArrays(final int size) {
        if (mHashes == EMPTY_IMMUTABLE_INTS) {
            //If mHashes is immutable during expansion, an exception will be thrown            throw new UnsupportedOperationException("ArrayMap is immutable");
        }
        if (size == (BASE_SIZE*2)) {
            //If the capacity expansion is 8 (BASE_SIZE=4)            synchronized () {
                if (mTwiceBaseCache != null) {
                    /**
                       If there is currently an int cache reusable array with capacity 8 and an object cache reusable array with capacity 16, then multiplex these arrays without renew
                      */
                    final Object[] array = mTwiceBaseCache;
                    mArray = array;
                    mTwiceBaseCache = (Object[])array[0];
                    mHashes = (int[])array[1];
                    array[0] = array[1] = null;
                    mTwiceBaseCacheSize--;
                    if (DEBUG) (TAG, "Retrieving 2x cache " + mHashes
                            + " now have " + mTwiceBaseCacheSize + " entries");
                    return;
                }
            }
        } else if (size == BASE_SIZE) {
             //If the capacity expansion is 4 (BASE_SIZE=4)            synchronized () {
                if (mBaseCache != null) {
                    /**
                       If there is currently an int cache reusable array with capacity 4 and an object cache reusable array with capacity 8, then multiplex these arrays without renew
                      */
                    final Object[] array = mBaseCache;
                    mArray = array;
                    mBaseCache = (Object[])array[0];
                    mHashes = (int[])array[1];
                    array[0] = array[1] = null;
                    mBaseCacheSize--;
                    if (DEBUG) (TAG, "Retrieving 1x cache " + mHashes
                            + " now have " + mBaseCacheSize + " entries");
                    return;
                }
            }
        }
        mHashes = new int[size];
        mArray = new Object[size<<1];
    }
    private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
        if ( == (BASE_SIZE*2)) {
            //If the current capacity is 8 (BASE_SIZE=4)            synchronized () {
                if (mTwiceBaseCacheSize < CACHE_SIZE) {
                    //Cache the current array and set the data after the array subscript is 2 to null                    array[0] = mTwiceBaseCache;
                    array[1] = hashes;
                    for (int i=(size<<1)-1; i>=2; i--) {
                        array[i] = null;
                    }
                    mTwiceBaseCache = array;
                    mTwiceBaseCacheSize++;
                    if (DEBUG) (TAG, "Storing 2x cache " + array
                            + " now have " + mTwiceBaseCacheSize + " entries");
                }
            }
        } else if ( == BASE_SIZE) {
            //If the current capacity is 4 (BASE_SIZE=4)            synchronized () {
                //Cache the current array and set the data after the array subscript is 2 to null                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) (TAG, "Storing 1x cache " + array
                            + " now have " + mBaseCacheSize + " entries");
                }
            }
        }
    }

 @Override
  public V get(Object key) {
        //Get the index of mHashes where the key hashcode is located,        final int index = indexOfKey(key);
        /**
         According to the data storage structure of mArray, if you know the subscript *2 of mHashes (index << 1), you will get the subscript of its corresponding element at the starting subscript of mArray. The first is the key and the second is the value
         */
        return index &gt;= 0 ? (V)mArray[(index&lt;&lt;1)+1] : null;
  }
public int indexOfKey(Object key) {
        return key == null ? indexOfNull()
                : indexOf(key, mIdentityHashCode ? (key) : ());
}
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;
        }
        //Dialogram to find the subscript where hash is located        int index = binarySearchHashes(mHashes, N, hash);
        // If the hash code wasn't found, then we have no entry for this key.
        if (index &lt; 0) {
            //Not found, return directly            return index;
        }
        // If the key at the returned index matches, that's what we want.
        if ((mArray[index&lt;&lt;1])) {
            //If the hash subscript corresponds to the key in mArray and the key to be found, return directly to the current subscript            return index;
        }
        //Conflict handling plan        //Travel over the element after the current index and find the subscript of the matching key where the matching key is located        // Search for a matching key after the index.
        int end;
        for (end = index + 1; end &lt; N &amp;&amp; mHashes[end] == hash; end++) {
            if ((mArray[end &lt;&lt; 1])) return end;
        }
        //Transf the element before the current index and find the subscript of the matching key where the matching key is located        // Search for a matching key before the index.
        for (int i = index - 1; i &gt;= 0 &amp;&amp; mHashes[i] == hash; i--) {
            if ((mArray[i &lt;&lt; 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.
        return ~end;
}