mHashes[index] = hash;
mArray[index<<1] = key;  //等同于 mArray[index * 2] = key;
mArray[(index<<1)+1] = value; //等同于 mArray[index * 2 + 1] = value;

int indexOf(Object key, int hash) {
    final int N = mSize;
    //快速判断是ArrayMap是否为空,如果符合情况快速跳出
    if (N == 0) {
        return ~0;
    }
    //二分查找确定索引值
    int index = ContainerHelpers.binarySearch(mHashes, N, hash);

    // 如果未找到，返回一个index值，可能为后续可能的插入数据使用。
    if (index < 0) {
        return index;
    }

    // 如果确定不仅hashcode相同，也是同一个key，返回找到的索引值。
    if (key.equals(mArray[index<<1])) {
        return index;
    }

    // 如果key的hashcode相同，但不是同一对象，从索引之后再次找
    int end;
    for (end = index + 1; end < N && mHashes[end] == hash; end++) {
        if (key.equals(mArray[end << 1])) return end;
    }

    // 如果key的hashcode相同，但不是同一对象，从索引之前再次找
    for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
        if (key.equals(mArray[i << 1])) return i;
    }
    //返回负值，既可以用来表示无法找到匹配的key，也可以用来为后续的插入数据所用。
    // 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;
}

public V put(K key, V value) {
    final int hash;
    int index;
    if (key == null) {
        hash = 0;//如果key为null，其hashcode算作0
        index = indexOfNull();
    }
  ...
}

/**
 * The minimum amount by which the capacity of a ArrayMap will increase.
 * This is tuned to be relatively space-efficient.
*/
private static final int BASE_SIZE = 4;
final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
  : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);

private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
    if (hashes.length == (BASE_SIZE*2)) {
        synchronized (ArrayMap.class) {
            if (mTwiceBaseCacheSize < CACHE_SIZE) {
                array[0] = mTwiceBaseCache;
                array[1] = hashes;
                for (int i=(size<<1)-1; i>=2; i--) {
                    array[i] = null;
                }
                mTwiceBaseCache = array;
                mTwiceBaseCacheSize++;
                if (DEBUG) Log.d(TAG, "Storing 2x cache " + array
                        + " now have " + mTwiceBaseCacheSize + " entries");
            }
        }
    } else if (hashes.length == BASE_SIZE) {
        synchronized (ArrayMap.class) {
            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) Log.d(TAG, "Storing 1x cache " + array
                        + " now have " + mBaseCacheSize + " entries");
            }
        }
    }
}

private void allocArrays(final int size) {
    if (mHashes == EMPTY_IMMUTABLE_INTS) {
        throw new UnsupportedOperationException("ArrayMap is immutable");
    }
    if (size == (BASE_SIZE*2)) {
        synchronized (ArrayMap.class) {
            if (mTwiceBaseCache != null) {
                final Object[] array = mTwiceBaseCache;
                mArray = array;
                mTwiceBaseCache = (Object[])array[0];
                mHashes = (int[])array[1];
                array[0] = array[1] = null;
                mTwiceBaseCacheSize--;
                if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes
                        + " now have " + mTwiceBaseCacheSize + " entries");
                return;
            }
        }
    } else if (size == BASE_SIZE) {
        synchronized (ArrayMap.class) {
            if (mBaseCache != null) {
                final Object[] array = mBaseCache;
                mArray = array;
                mBaseCache = (Object[])array[0];
                mHashes = (int[])array[1];
                array[0] = array[1] = null;
                mBaseCacheSize--;
                if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes
                        + " now have " + mBaseCacheSize + " entries");
                return;
            }
        }
    }

    mHashes = new int[size];
    mArray = new Object[size<<1];
}