Android ArrayMap source code analysis

int indexOf(Object key, int hash) {
    final int N = mSize;

    // Important fast case: if nothing is in here, nothing to look for.
    //The array is empty, return directly    if (N == 0) {
      return ~0;
    }

    //Binary search, I won't go into details    int index = (mHashes, N, hash);

    // If the hash code wasn't found, then we have no entry for this key.
    //The hashCode was not found, return index, a negative number    if (index < 0) {
      return index;
    }

    // If the key at the returned index matches, that's what we want.
    //Compare the key value, return index if the same    if ((mArray[index<<1])) {
      return index;
    }

    // Search for a matching key after the index.
    //If the key value corresponding to the returned index is not equal to the key value passed, the corresponding key may be after the index    int end;
    for (end = index + 1; end < N && mHashes[end] == hash; end++) {
      if ((mArray[end << 1])) return end;
    }

    // Search for a matching key before the index.
    //Continue with the previous sentence, if there is no later, it must be in front.    for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
      if ((mArray[i << 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.
    //I haven't found the hair, so there must be no more. Return a negative number    return ~end;
  }

public V put(K key, V value) {
    final int hash;
    int index;
    //The key is empty, then search for the corresponding index through indexOfNull; if it is not empty, search for the corresponding index through indexOf    if (key == null) {
      hash = 0;
      index = indexOfNull();
    } else {
      hash = ();
      index = indexOf(key, hash);
    }
    
    //Index is greater than or equal to 0, it must have put the same key before, and directly replace the corresponding value.  Because mArray not only saves value, but also key.    //Its structure is [key1,value1,key2,value2,key3,value3,...]    //So, you need to multiply index 2 and correspond to key, index 2 and add 1 corresponding value    if (index >= 0) {
      index = (index<<1) + 1;
      final V old = (V)mArray[index];
      mArray[index] = value;
      return old;
    }

    //Take a positive number    index = ~index;
    //The size of mSize, that is, the amount of data saved is the same as the length of mHashes, and it needs to be expanded.    if (mSize >= ) {
      //The size after expansion has the following gears, BASE_SIZE (4), 2 times (8), mSize+(mSize>>1) (1/2 expansion of the previous data volume)      final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
          : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);

      if (DEBUG) (TAG, "put: grow from " +  + " to " + n);

      final int[] ohashes = mHashes;
      final Object[] oarray = mArray;
      //Implementation of capacity expansion method      allocArrays(n);

      //After expansion, the original data needs to be copied to the new array      if ( > 0) {
        if (DEBUG) (TAG, "put: copy 0-" + mSize + " to 0");
        (ohashes, 0, mHashes, 0, );
        (oarray, 0, mArray, 0, );
      }

      //See if the abandoned array still has value      //If the data volume of the discarded array is 4 or 8, it means that it may be useful, and it can be used directly when it is used in the future.      //If the amount of discarded data is too large, just throw it away, it will not take up too much memory.  If memory is wasted, it will take such a lot of effort. What should I do if I add classes?      freeArrays(ohashes, oarray, mSize);
    }

    //The hashcode sort corresponding to the key of put this time is not ranked last (index does not indicate to the end of the array), so the data behind the index needs to be moved    if (index < mSize) {
      if (DEBUG) (TAG, "put: move " + index + "-" + (mSize-index)
          + " to " + (index+1));
      (mHashes, index, mHashes, index + 1, mSize - index);
      (mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
    }

    //Save data to array.  I saw it, the key and value are both in mArray; put hashCode in mHashes    mHashes[index] = hash;
    mArray[index<<1] = key;
    mArray[(index<<1)+1] = value;
    mSize++;
    return null;
  }

 /**
   * Remove the key/value mapping at the given index.
   * @param index The desired index, must be between 0 and {@link #size()}-1.
   * @return Returns the value that was stored at this index.
   */
  public V removeAt(int index) {
    final Object old = mArray[(index << 1) + 1];
    //If the data volume is less than or equal to 1, it means that after deleting the element, no array is empty, and the two arrays are cleared.    if (mSize <= 1) {
      // Now empty.
      if (DEBUG) (TAG, "remove: shrink from " +  + " to 0");
      //A description has been made in put      freeArrays(mHashes, mArray, mSize);
      mHashes = ;
      mArray = ;
      mSize = 0;
    } else {
      //If the maximum number of data contained in the array applied for is greater than 2 times (8) of BASE_SIZE, and the amount of data stored now only 1/3 of the number of applications is required.      //The space needs to be reallocated, which has reduced the memory usage      if ( > (BASE_SIZE*2) && mSize < /3) {
        // Shrunk enough to reduce size of arrays. We don't allow it to
        // shrink smaller than (BASE_SIZE*2) to avoid flapping between
        // that and BASE_SIZE.
        //The size of the new array        final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2);

        if (DEBUG) (TAG, "remove: shrink from " +  + " to " + n);

        final int[] ohashes = mHashes;
        final Object[] oarray = mArray;
        allocArrays(n);

        mSize--;
        //Copy the data before index into the new array        if (index > 0) {
          if (DEBUG) (TAG, "remove: copy from 0-" + index + " to 0");
          (ohashes, 0, mHashes, 0, index);
          (oarray, 0, mArray, 0, index << 1);
        }
        //Copy the data after index into a new array and combine it with the branch of (index>0) to delete the data at the index position        if (index < mSize) {
          if (DEBUG) (TAG, "remove: copy from " + (index+1) + "-" + mSize
              + " to " + index);
          (ohashes, index + 1, mHashes, index, mSize - index);
          (oarray, (index + 1) << 1, mArray, index << 1,
              (mSize - index) << 1);
        }
      } else {
        mSize--;
        //Transfer the data after index forward        if (index < mSize) {
          if (DEBUG) (TAG, "remove: move " + (index+1) + "-" + mSize
              + " to " + index);
          (mHashes, index + 1, mHashes, index, mSize - index);
          (mArray, (index + 1) << 1, mArray, index << 1,
              (mSize - index) << 1);
        }
        //The last data after shifting is cleared        mArray[mSize << 1] = null;
        mArray[(mSize << 1) + 1] = null;
      }
    }
    return (V)old;
  }

private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
    //The number of arrays that have been abandoned is twice (8) of BASE_SIZE, then use mTwiceBaseCache to save the abandoned array;    //If the number is BASE_SIZE(4), use mBaseCache to save the abandoned array    if ( == (BASE_SIZE*2)) {
      synchronized () {
        if (mTwiceBaseCacheSize < CACHE_SIZE) {
          //array is an array that has just been abandoned. If there is any content in mTwiceBaseCache, it will be placed in the array[0] position.          //In allocArrays, it will be taken out from array[0] and put back into mTwiceBaseCache          array[0] = mTwiceBaseCache;
          //array[1] stores hash array.  Because each element in an array is an Object object, each element can store an array          array[1] = hashes;
          //Clear the data after index is 2 and          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) {
      synchronized () {
        if (mBaseCacheSize < CACHE_SIZE) {
          //Refer to the above for the comments of the code, and do not repeat the explanation.          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");
        }
      }
    }
  }