3.基础知识Android_ArrayMap

时间:2021-09-21 15:38:51

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++;
}