1. Features of ArrayMap

1.1 Capacity Expansion Mechanism

  • HashMap If the capacity of the current map multiplied by the capacity expansion factor is less than or equal to the current number, the capacity expansion mechanism is triggered. Each expansion doubles the size of the current element.
  • The capacity expansion mechanism of ArrayMap causes capacity expansion when the capacity is already full. The capacity of each expansion is 1.5 times that of the working capacity
  • ArrayMap also has a scaling mechanism, which is triggered when the number of elements in the ArrayMap is less than a third of its capacity, and finally shrinks to 1.5 times the current number of elements.
  • Cache mechanism during capacity expansion. The cache can only be expanded to mBaseSize (8) or scaled down to (4).

1.2 Handling Hash Conflicts

  • The HashMap uses the zipper method.
  • ArrayMap opens the address method if a hash conflict occurs.

1.3 Storage Structure of ArrayMap

An array holds the hash value of a key, an existing key value. The structure is as follows.

1.3 Non-thread-safe

Well, as the title suggests, it’s not thread-safe, and there are data inconsistencies when multiple threads share an ArrayMap.

2, about saving/fetching/deleting elements

2.1 to save data

If the key already exists in the HashMap, it is replaced with the new value. If there is no key, the value and key are stored in the ArrayMap. The general process is like this.

  • Calculates the hashCode value of the key.
  • Use binary lookup to index the position of hashCode in mHash[] and compare it to see if it is equal to key. Note here that hash equality does not mean two values are equal, any more than I and you being male does not mean our ID numbers.
  • If key finds that it already exists in Array, the value is replaced by the hash value in the Array mHashp[]. Index *2 is the key position in the Array mArray. Index times 2 plus 1 is where value is.
  • If it does not exist, the new key-value pair is entered.

2.1.2 capacity

When the capacity of ArrayMap is full, you need to use the expansion mechanism, how to expand the specific source to find the answer.

   if (osize >= mHashes.length) {
            final int n = osize >= (BASE_SIZE*2)? (osize+(osize>>1))
                    : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
            final int[] ohashes = mHashes;
            finalObject[] oarray = mArray; allocArrays(n); .Copy the code

A wave of triadic arithmetic tells the truth:

  • When the current capacity is greater than or equal to 8, it is only expanded by 1.5 times
  • If the current capacity is greater than or equal to 4 and smaller than 8, expand the capacity to 8.
  • If the value is smaller than 4, expand the value to 4

2.2 the data

There’s nothing to say. What underlying source code? What design patterns

   @Override
    public V get(Object key) {
        final int index = indexOfKey(key);
        return index >= 0 ? (V)mArray[(index<<1)+1] : null;
    }
Copy the code

2.3 delete elements

2.3.1 delete

Delete, which is essentially copying an array, normally,

2.3.2 Capacity reduction Mechanism

When the number of elements in the ArrayMap is less than one third of the capacity, the capacity is reduced to 1.5 times the current number (not the capacity). If the number is less than 8, the capacity is expanded to 8.

     if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
              final int n = osize > (BASE_SIZE*2)? (osize + (osize>>1)) : (BASE_SIZE*2); . }Copy the code

3. Caching

  static Object[] mBaseCache;// Capacity 4, ArrayMap cache linked list
  static int mBaseCacheSize;// The number of caches with capacity 4
  static Object[] mTwiceBaseCache;// Array cache list with capacity 8
  static int mTwiceBaseCacheSize;// The number of caches with capacity 8
Copy the code
  • ArrayMap caches two arrayMaps of capacity 4 and 8.
  • There is also a limit to the number of ArrayMap caches per type :10.

3.1 recycling

    private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
    // The length of the current hashs data is 8
        if (hashes.length == (BASE_SIZE*2)) {... }else if (hashes.length == BASE_SIZE) {
            synchronized (ArrayMap.class) {
                if (mBaseCacheSize < CACHE_SIZE) {
                    array[0] = mBaseCache;// The first element of the array points to the current mBaseCache
                    array[1] = hashes;// Point the second element of the array to the hash array
                    for (int i=(size<<1) -1; i>=2; i--) {// empty all elements after the second
                        array[i] = null;
                    }
                    mBaseCache = array;/ / array mBaseCache execution
                    mBaseCacheSize++;// Add 1 to the number}}}}Copy the code

If you look at the notes, it should make sense, but if you don’t, look at the picture below.

FreeArrays () ¶ Synchronized is not a thread that is safe

The essence of thread-safety is that mutable data is shared across multiple threads. Both mBaseCache and mTwiceBaseCache are static, which means they can be accessed by multiple ArrayMap objects. Conversely, an ArrayMap object created for use in a single thread will have thread-safety problems if it is scaled up or downsized without adding synchronized blocks.

3.2 the reuse

Cache maps of two sizes, 4 and 8

 private void allocArrays(final int size) {
    if (size == (BASE_SIZE*2)) {
        // When the size of the array to be allocated is 8. }else if (size == BASE_SIZE) {
        // When the size of the allocated array is 4
       synchronized (ArrayMap.class) {
            if(mBaseCache ! =null) {
             final Object[] array = mBaseCache;
               mArray = array;//mArray points to the first array in the cache list
               mBaseCache = (Object[])array[0];//mBaseCache points to the next array
               mHashes = (int[])array[1];// The mHashes array points to the first element of arry
               array[0] = array[1] = null;/ / empty
               mBaseCacheSize--;     
               return;
           }
        }
     }
     mHashes = new int[size];
     mArray = new Object[size<<1];
    }
Copy the code

3. Applicable conditions

  • Google officially recommends using ArrayMap when the amount of data is less than 1000, but using HashMap after 1000. The query efficiency of ArrayMap is O(logN). It is inefficient to move the array when deleting and adding elements. The query change rate for HashMap is O(1). But ArrayMap has the advantage of saving money!

  • In addition to ArrayMap, there is SpareArray, which is similar to ArrayMap, but its key is of int type, avoiding the efficiency problems caused by unboxing basic data types. When determining the value of the value of the int/long/when can use Boolean SparseIntArray/SparseLongArray/SpareseBoolean.

The appendix

Add a binary search algorithm

public static int binarySearch(int[] array,int value){
    if (array == null) {throw new IllegalArgumetsException("Can't be empty.");
    }
     int lo = 0;
     int li = array.length - 1;
     while(lo<=li){
         int index = (lo+li)/2;
         int midValue = array[index];
         if(value>midValue){
             li= index+1;
         }else if(value<midValue){
             lo = index-1;
         }else{
             returnindex; }}return ~lo;   
}
Copy the code