SpareArray

两个数组，一个存 key，一个存 value ，key 是一个有序数组。

  1. private int[] mKeys;
  2. private Object[] mValues;
  4. public void put(int key, E value) {
  5.     //查找 key 对应的 index， 如果查找不到，则返回应该在的位置 index 取反。
  6.     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
  8.     if (i >= 0) {
  9.         //找到了，直接赋值
  10.         mValues[i] = value;
  11.     } else {
  12.         //没找到，取反，就是应该在的位置。
  13.         i = ~i;
  15.         if (i < mSize && mValues[i] == DELETED) {
  16.             mKeys[i] = key;
  17.             mValues[i] = value;
  18.             return;
  19.         }
  21.         if (mGarbage && mSize >= mKeys.length) {
  22.             gc();
  24.             // Search again because indices may have changed.
  25.             i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
  26.         }
  28.         mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
  29.         mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
  30.         mSize++;
  31.     }
  32. }

ArrayMap

也是两个数组，一个存key 的 hash，一个存key 和 value，两个为一体，一个 key，一个 value，key 在偶数位，value 在奇数位。所以 存放 hash 值的数组长度是 存放 键值对的数组长度的 1/2。 

  1. public V put(K key, V value) {
  2.     final int osize = mSize;
  3.     final int hash;
  4.     int index;
  5.     if (key == null) {
  6.         hash = 0;
  7.         index = indexOfNull();
  8.     } else {
  9.         //hash 值直接就是 
  10.         hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
  11.         //寻找 index，这里存在 hash 冲突。具体看后面的分析。
  12.         index = indexOf(key, hash);
  13.     }
  14.     if (index >= 0) {
  15.         //找到 index ，也就是说之前存在相同的 key。
  16.         //计算 value 的位置。就是 key 的 index+1，key 的 index = index<<1。
  17.         index = (index<<1) + 1;
  18.         final V old = (V)mArray[index];
  19.         mArray[index] = value;
  20.         return old;
  21.     }
  22.     //没找到，取反，得到应该在的位置。
  23.     index = ~index;
  24.     if (osize >= mHashes.length) {
  25.         final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
  26.             : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
  28.         if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);
  30.         final int[] ohashes = mHashes;
  31.         final Object[] oarray = mArray;
  32.         allocArrays(n);
  34.         if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
  35.             throw new ConcurrentModificationException();
  36.         }
  38.         if (mHashes.length > 0) {
  39.             if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0");
  40.             System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
  41.             System.arraycopy(oarray, 0, mArray, 0, oarray.length);
  42.         }
  44.         freeArrays(ohashes, oarray, osize);
  45.     }
  47.     if (index < osize) {
  48.         if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (osize-index)
  49.                          + " to " + (index+1));
  50.         System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);
  51.         System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
  52.     }
  54.     if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
  55.         if (osize != mSize || index >= mHashes.length) {
  56.             throw new ConcurrentModificationException();
  57.         }
  58.     }
  59.     mHashes[index] = hash;
  60.     mArray[index<<1] = key;
  61.     mArray[(index<<1)+1] = value;
  62.     mSize++;
  63.     return null;
  64. }

indexOf(key, hash)

  1. int indexOf(Object key, int hash) {
  2.     final int N = mSize;
  4.     // Important fast case: if nothing is in here, nothing to look for.
  5.     if (N == 0) {
  6.         return ~0;
  7.     }
  9.     int index = binarySearchHashes(mHashes, N, hash);
  11.     // If the hash code wasn't found, then we have no entry for this key.
  12.     if (index < 0) {
  13.         //没找到
  14.         return index;
  15.     }
  17.     // If the key at the returned index matches, that's what we want.
  18.     if (key.equals(mArray[index<<1])) {
  19.         //找到了 index，并且 key 相同。
  20.         return index;
  21.     }
  23.     // Search for a matching key after the index.
  24.     //找到了 index，但是 该 index 对应的 key并不是我们要存放的 key，这是存在 hash 冲突，所以先往右找是否有相同的 key。
  25.     int end;
  26.     for (end = index + 1; end < N && mHashes[end] == hash; end++) {
  27.         if (key.equals(mArray[end << 1])) return end;
  28.     }
  30.     // Search for a matching key before the index.
  31.     //右边没找到，往左边找是否有相同的 key。
  32.     for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
  33.         if (key.equals(mArray[i << 1])) return i;
  34.     }
  36.     // Key not found -- return negative value indicating where a
  37.     // new entry for this key should go.  We use the end of the
  38.     // hash chain to reduce the number of array entries that will
  39.     // need to be copied when inserting.
  40.     return ~end;
  41. }

从上面代码可以看出，如果存在 hash 冲突，并且之前没有存放过这个键值对，则在头部插入(因为是先往右边找，然后往左边找)。