ArrayMap結(jié)構(gòu)
arrayMap中主要存儲(chǔ)的數(shù)據(jù)的是兩個(gè)數(shù)據(jù)
int[] mHashes; // 存儲(chǔ)出的是每個(gè)key的hash值，并且在這些key的hash值在數(shù)組當(dāng)中是從小到大排序的。
Object[] mArray; // 長(zhǎng)度是mHashs的兩倍，每?jī)蓚€(gè)元素分別是key和value况既，這兩元素對(duì)應(yīng)mHashs中的hash值。
//如果key存在组民，則返回oldValue
public V put(K key, V value) {
//key的hash值
final int hash;
//下標(biāo)
int index;
// 如果key為null棒仍，則hash值為0.
if (key == null) {
hash = 0;
//尋找null的下標(biāo)
index = indexOfNull();
} else {
//根據(jù)mIdentityHashCode 取到 hash值
hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
//根據(jù)hash值和key 找到合適的index
index = indexOf(key, hash);
}
//如果index>=0,說(shuō)明是替換（改）操作
if (index >= 0) {
//只需要更新value 不需要更新key。因?yàn)閗ey已經(jīng)存在
index = (index<<1) + 1;
//返回舊值
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
//index<0,說(shuō)明是插入操作邪乍。 對(duì)其取反降狠，得到應(yīng)該插入的下標(biāo)
index = ~index;
//如果需要擴(kuò)容
if (mSize >= mHashes.length) {
//如果容量大于8，則擴(kuò)容一半庇楞。
//否則容量大于4榜配，則擴(kuò)容到8.
//否則擴(kuò)容到4
final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
: (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
//臨時(shí)數(shù)組
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
//分配空間完成擴(kuò)容
allocArrays(n);
//復(fù)制臨時(shí)數(shù)組中的數(shù)組進(jìn)新數(shù)組
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);
}
//釋放臨時(shí)數(shù)組空間
freeArrays(ohashes, oarray, mSize);
}
//如果index在中間，則需要移動(dòng)數(shù)組吕晌，騰出中間的位置
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);
}
//hash數(shù)組蛋褥，就按照下標(biāo)存哈希值
mHashes[index] = hash;
//array數(shù)組，根據(jù)下標(biāo)睛驳，乘以2存key烙心，乘以2+1 存value
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
mSize++;//修改size
return null;
}
//根據(jù)key和key的hash值，返回index
int indexOf(Object key, int hash) {
//N為當(dāng)前集合size
final int N = mSize;
//如果當(dāng)前集合是空的乏沸，返回~0
if (N == 0) {
return ~0;
}
//根據(jù)hash值淫茵，通過(guò)二分查找，查找到目標(biāo)index
int index = ContainerHelpers.binarySearch(mHashes, N, hash);
//如果index《0蹬跃，說(shuō)明該hash值之前沒(méi)有存儲(chǔ)過(guò)數(shù)據(jù)
if (index < 0) {
return index;
}
//如果index>=0,說(shuō)明該hash值匙瘪，之前存儲(chǔ)過(guò)數(shù)據(jù)，找到對(duì)應(yīng)的key蝶缀，比對(duì)key是否相等丹喻。相等的話，返回index翁都。說(shuō)明要替換碍论。
if (key.equals(mArray[index<<1])) {
return index;
}
//以下兩個(gè)for循環(huán)是在出現(xiàn)hash沖突的情況下，找到正確的index的過(guò)程：
//從index+1,遍歷到數(shù)組末尾柄慰，找到hash值相等鳍悠，且key相等的位置，返回
int end;
for (end = index + 1; end < N && mHashes[end] == hash; end++) {
if (key.equals(mArray[end << 1])) return end;
}
//從index-1,遍歷到數(shù)組頭坐搔，找到hash值相等贼涩，且key相等的位置，返回
for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
if (key.equals(mArray[i << 1])) return i;
}
// key沒(méi)有找到薯蝎，返回一個(gè)負(fù)數(shù)遥倦。代表應(yīng)該插入的位置
return ~end;
}
擴(kuò)容優(yōu)化
freeArrays方法中，傳入的是oldhashes和oldarray，和新的mSize袒哥。當(dāng)長(zhǎng)度不夠用缩筛，我們需要廢棄掉老的數(shù)組，使用新的數(shù)組的時(shí)候堡称，把老的數(shù)組句柄（包含mHashes和mArray）的數(shù)據(jù)緩存到 mArray 的前兩個(gè)位置瞎抛，其他的數(shù)據(jù)清空，如果長(zhǎng)度是 4却紧， 則使用 mBaseCache桐臊， 如果是 8 ，則使用 mTwiceBaseCache晓殊。
這些緩存空間是留給其它的ArrayMap的断凶，而不是當(dāng)前的ArrayMap的。
