3.基础知识Android_ArrayMap

1>. 必备的相关知识 之 ArrayMap<键值对>

1<. 抽象概念：

创建两个数组 KArray[] = {1, 2, 3, 4 , 5};
             VArray[] = {one, two, three, four , fire};

根据在KArray里面，找到对应的数字
然后根据对应数字的数组index，找到VArray[]里对应的值

[补充]：Java里面 object是所有类的父类

2<. 在Android系统里怎么实现的:

假如：
    创建一个数组 ObjectArray[] = {Ka, Va, Kb, Vb, Kc, Vc};
    从index = 0;开始，如果满足就取出和它相邻的下一项。否则就index += 2;再次判断，以此类推。
    关键就是索引值：K->index; 但是这样的效率很低下;

事实上：ArrayMap.java ->  public V put(){};
    1<. 首先根据 K 值得到一个 Hash（哈希） 值
      hash = key.hashCode();
    2<. 然后根据 Hash 值在数组中确定 K 所对应的 index
      index = indexOf(key, hash);

    [强行解释]：
    int[] mHashes;   ：{  H1 ,   H2 ,   H3,    H4 ,   H5 ,   H6 };
    Object[] mArray; ：{k1|v1, k2|v2, k3|v3, k4|v4, k5|v5, k6|v6}；

get过程:

根据K, 得到V, 假设得到的索引值H 为 3,那么可以找到mArray里面的 ((3 * 2) + 1)的项;

public V get(Object key) {
final int index = indexOfKey(key);
return key == null ? indexOfNull() : indexOf(key, key.hashCode());
int index = ContainerHelpers.binarySearch(mHashes, N, hash);
return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}

1<. 根据K, 得到Hash ：H
2<. 在 mHashes 使用二分法找到跟 H 值相等的所有项：H3, H4
    并且假设 H3, H4 都等于 H;

3<. 再次比较 K 值: 
  mArray[2 * 2] == K
  mArray[3 * 2] == K

4<. 假设是 mArray[3 * 3] == K满足条件, 那么返回index = 3;

put过程:

public V put(K key, V value) {
index = indexOf(key, hash);
if (index >= 0) {                   /* 表示已经有(k, v`), 那么只需要修改v` => v */
index = (index<<1) + 1;
final V old = (V)mArray[index];
        mArray[index] = value;
return old;
    }
if (index < 0) {                    /* 则 index = ~index, 表示要新添加键值对 */
1<. 有必要的话 数组扩容 : 
if (mSize >= mHashes.length){
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
            allocArrays(n);

if (mHashes.length > 0) {
if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");
                System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
                System.arraycopy(oarray, 0, mArray, 0, oarray.length);
            }

            freeArrays(ohashes, oarray, mSize);
          }

2<. 如果 index 是在数组中间, 这需要移动数据
if (index < mSize) {
if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index)
                    + " to " + (index+1));
            System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);
            System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
          }

3<. 赋值： 
            mHashes[index] = hash;
            mArray[index<<1] = key;
            mArray[(index<<1)+1] = value;
            mSize++;
    }