| 存儲(chǔ)結(jié)構(gòu) |默認(rèn)大小 | 線程安全 | 擴(kuò)容機(jī)制 | 刪除策略 |
|--|--|--|--|--|--|--|--|
| 雙數(shù)組 |0 |否|n<4:4; n<8:8;n>=8:1.5n;|直接刪除邓嘹，并帶有部分內(nèi)存收縮操作|||||||
成員變量
static Object[] mBaseCache;//緩存的長(zhǎng)度為4的key和value的內(nèi)存她混，其結(jié)構(gòu)下文會(huì)詳細(xì)說明
static int mBaseCacheSize;//緩存的個(gè)數(shù)，大小在10個(gè)以內(nèi)
static Object[] mTwiceBaseCache;//緩存的長(zhǎng)度為8的key和value的內(nèi)存
static int mTwiceBaseCacheSize;//緩存的個(gè)數(shù)，大小在10個(gè)以內(nèi)
final boolean mIdentityHashCode;//生成hashcode的方法，mIdentityHashCode ? System.identityHashCode(key) : key.hashCode()System.identityHashCode
int[] mHashes;//存儲(chǔ)key的hash值，升序
Object[] mArray;//存儲(chǔ)key和value的值，key的下一個(gè)數(shù)據(jù)項(xiàng)就是該key對(duì)應(yīng)的value
int mSize;//當(dāng)前集合存儲(chǔ)的數(shù)據(jù)個(gè)數(shù)
創(chuàng)建集合
public ArrayMap(int capacity) {
this(capacity, false);
}
/** {@hide} */
public ArrayMap(int capacity, boolean identityHashCode) {
mIdentityHashCode = identityHashCode;
if (capacity < 0) {
mHashes = EMPTY_IMMUTABLE_INTS;
mArray = EmptyArray.OBJECT;
} else if (capacity == 0) {
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
} else {
allocArrays(capacity);
}
mSize = 0;
}
可以看到传透，ArrayMap設(shè)置小于0的容量時(shí)，并不會(huì)直接報(bào)錯(cuò)极颓，然后大于0時(shí)主要使用allocArrays去初始化集合
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--;
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--;
return;
}
}
}
mHashes = new int[size];
mArray = new Object[size<<1];
}
allocArrays方法主要分為3步：
- 如果之前設(shè)置了容量小于0朱盐，則不允許申請(qǐng)內(nèi)存
- 如果當(dāng)前申請(qǐng)的size為4或者8，而且當(dāng)前對(duì)應(yīng)緩存存在可用菠隆，則使用緩存
- 否則直接初始化新的數(shù)組兵琳，mHashes長(zhǎng)度為size，mArray長(zhǎng)度為2倍mHashes骇径，其原因是因?yàn)閙Array中存儲(chǔ)的是key和value躯肌，而mHasher中存儲(chǔ)的僅為key的hash值
關(guān)于緩存結(jié)構(gòu)
在緩存結(jié)構(gòu)上，mBaseCache和mTwiceBaseCache是一致的既峡，只是在存在的數(shù)據(jù)的長(zhǎng)度上不一樣羡榴，如上圖碧查，長(zhǎng)度為2的數(shù)int類型的數(shù)組运敢，對(duì)應(yīng)于mHashes校仑，長(zhǎng)度為4的是Object類型的數(shù)組，對(duì)應(yīng)于mArray传惠∑可以看出Object數(shù)組中的第一項(xiàng)指向下一個(gè)緩存，第二項(xiàng)為當(dāng)前緩存的存儲(chǔ)hash值的int緩存數(shù)組
插入數(shù)據(jù)
@Override
public V put(K key, V value) {
final int osize = mSize;
final int hash;
int index;
if (key == null) {
hash = 0;
index = indexOfNull();
} else {
hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
index = indexOf(key, hash);
}
if (index >= 0) {
index = (index<<1) + 1;
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
index = ~index;
if (osize >= mHashes.length) {
final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
: (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
allocArrays(n);
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
if (mHashes.length > 0) {
if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0");
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
freeArrays(ohashes, oarray, osize);
}
if (index < osize) {
if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (osize-index)
+ " to " + (index+1));
System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);
System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
}
if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
if (osize != mSize || index >= mHashes.length) {
throw new ConcurrentModificationException();
}
}
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
mSize++;
return null;
}
插入操作分為如下步驟：
- 通過key和hash定位到該key在mHashes和mArray當(dāng)中的下標(biāo)卦方。因?yàn)閙Hashes中到hash值是升序存儲(chǔ)羊瘩，這里采用了二分法查找，因?yàn)榇嬖趆ash沖突盼砍，所以還得比較key是否相等尘吗，可以參照ArrayMap結(jié)構(gòu)圖。
- 如果找到下標(biāo)（index>=0）,則覆蓋原來到value浇坐，并返回該值
- 如果沒找到（index<0）睬捶，則～index為插入到期望下標(biāo)，此時(shí)如果mHashes已滿近刘，則申請(qǐng)擴(kuò)容擒贸，并釋放或者緩存原來的內(nèi)存。如果mHashes未滿觉渴，則使用System的arraycopy方法移動(dòng)數(shù)據(jù)介劫，以為即將插入的數(shù)據(jù)騰出空間。
-
對(duì)應(yīng)index上插入key和value案淋，并更新size
ArrayMap結(jié)構(gòu)圖
這里關(guān)注下擴(kuò)容細(xì)節(jié)座韵，主要三個(gè)方面，擴(kuò)容大小的計(jì)算踢京、擴(kuò)容內(nèi)存申請(qǐng)和老數(shù)據(jù)遷移回右，老內(nèi)存的處理；
final int n = osize >= (BASE_SIZE2) ? (osize+(osize>>1))
: (osize >= BASE_SIZE ? (BASE_SIZE2) : BASE_SIZE);
擴(kuò)容大小的計(jì)算根據(jù)當(dāng)前不同的size處理不一樣：
- 如果osize>=8:則新的size為osize的3/2
- 如果osize<8 && osize >= 4：則新size為8
- 如果osize<4:則新size為4
擴(kuò)若內(nèi)存的申請(qǐng)使用allocArrays方法漱挚，該方法我們分析過翔烁，會(huì)優(yōu)先嘗試使用緩存，不存在緩存才申請(qǐng)對(duì)應(yīng)內(nèi)存旨涝，需要注意的是該方法會(huì)給mHashes和mArray重新賦值蹬屹，而老數(shù)據(jù)的遷移則使用了System.arraycopy進(jìn)行數(shù)據(jù)的拷貝。
而老內(nèi)存的釋放白华，則調(diào)用了freeArrays方法：
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");
}
}
}
}
freeArrays方法是主要做的事情就是回收老內(nèi)存慨默，當(dāng)老數(shù)據(jù)的長(zhǎng)度滿足緩存的條件（長(zhǎng)度為4或者8）時(shí)，且當(dāng)前緩存?zhèn)€數(shù)還未滿（10）弧腥，則將老數(shù)組中元素置為空厦取，并將老數(shù)組緩存到對(duì)應(yīng)的緩存中，注意這里是頭部插入管搪，也就是最后插入的緩存虾攻，會(huì)最先被使用铡买。
刪除元素
刪除元素最后會(huì)調(diào)用到remove方法：
public V removeAt(int index) {
final Object old = mArray[(index << 1) + 1];
final int osize = mSize;
final int nsize;
if (osize <= 1) {
freeArrays(mHashes, mArray, osize);
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
nsize = 0;
} else {
nsize = osize - 1;
if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
// Shrunk enough to reduce size of arrays. We don't allow it to
// shrink smaller than (BASE_SIZE*2) to avoid flapping between
// that and BASE_SIZE.
final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
allocArrays(n);
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
if (index > 0) {
System.arraycopy(ohashes, 0, mHashes, 0, index);
System.arraycopy(oarray, 0, mArray, 0, index << 1);
}
if (index < nsize) {
System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index);
System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
(nsize - index) << 1);
}
} else {
if (index < nsize) {
System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index);
System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
(nsize - index) << 1);
}
mArray[nsize << 1] = null;
mArray[(nsize << 1) + 1] = null;
}
}
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
mSize = nsize;
return (V)old;
}
刪除操作接收一個(gè)index，表示對(duì)應(yīng)hash在mHashes數(shù)組中的下標(biāo)霎箍，在remove方法中奇钞，首先通過(index << 1) + 1定位到對(duì)應(yīng)的object數(shù)組下標(biāo)，找到對(duì)應(yīng)的value漂坏。接著判斷是否只有一個(gè)元素景埃，是則直接給mHashes和mArray賦值為EmptyArray，并釋放內(nèi)存顶别。如果不是只有一個(gè)元素谷徙，則進(jìn)行下列操作：
- 若當(dāng)前容量大于8，且當(dāng)前元素個(gè)數(shù)小于容量的三分之一驯绎，則觸發(fā)內(nèi)存收縮操作蒂胞。收縮后的容量計(jì)算方式為：
final int n = osize > (BASE_SIZE2) ? (osize + (osize>>1)) : (BASE_SIZE2);
- 若不滿足內(nèi)存收縮條件，則直接調(diào)用System.arraycopy拷貝原數(shù)組中元素条篷，覆蓋index對(duì)應(yīng)的值骗随，并置空nsize對(duì)應(yīng)的值，更新mSize赴叹；
