【實(shí)習(xí)周記】ArrayMap源碼分析

一.概述

ArrayMap是Android專門針對(duì)內(nèi)存優(yōu)化而設(shè)計(jì)的，用于取代Java API中的HashMap數(shù)據(jù)結(jié)構(gòu)。
內(nèi)部通過兩個(gè)數(shù)組實(shí)現(xiàn)，存儲(chǔ)結(jié)構(gòu)如下

二.主要方法的源碼分析

1.重要字段

(1).private static final int BASE_SIZE = 4; // 容量增量的最小值
(2).private static final int CACHE_SIZE = 10; // 緩存數(shù)組的上限

(2).static Object[] mBaseCache; //用于緩存大小為4的ArrayMap
(3).static int mBaseCacheSize; // 記錄大小為4的ArrayMap的緩存數(shù)量
(4).static Object[] mTwiceBaseCache; //用于緩存大小為8的ArrayMap
(5).static int mTwiceBaseCacheSize; // 記錄大小為8的ArrayMap的緩存數(shù)量

(6).final boolean mIdentityHashCode; //默認(rèn)false
(7).int[] mHashes; //由key的hashcode所組成的數(shù)組
(8).Object[] mArray; //由key-value對(duì)所組成的數(shù)組，是mHashes大小的2倍
(9).int mSize; //成員變量的個(gè)數(shù)

2.構(gòu)造方法

創(chuàng)建ArrayMap對(duì)象時(shí)可以指定ArrayMap的長度，默認(rèn)長度為0。

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 {//分配內(nèi)存allocArrays(capacity);}mSize = 0; }

(1).內(nèi)存分配

private void allocArrays(final int size) { if (size == (BASE_SIZE*2)) { //當(dāng)分配大小為8的對(duì)象，先查看緩存池synchronized (ArrayMap.class) { // 當(dāng)緩存池不為空時(shí)if (mTwiceBaseCache != null) { final Object[] array = mTwiceBaseCache; //從緩存池中取出mArraymArray = array; //將緩存池指向上一條緩存地址 mTwiceBaseCache = (Object[])array[0]; //從緩存中mHashesmHashes = (int[])array[1];//清空緩存 array[0] = array[1] = null;//緩存池大小減1mTwiceBaseCacheSize--; return;}}//當(dāng)分配大小為4的對(duì)象，原理同上} 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;}}}// 分配大小除了4和8之外的情況，則直接創(chuàng)建新的數(shù)組mHashes = new int[size];mArray = new Object[size<<1]; }

3.put方法

public V put(K key, V value) { //osize記錄當(dāng)前map大小final int osize = mSize; final int hash;int index;if (key == null) {hash = 0;index = indexOfNull();} else {//獲取hashCodehash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();//采用二分查找法，從mHashes數(shù)組中查找值等于hash的keyindex = indexOf(key, hash); }//若index大于零，說明在mHashes中key存在，所以用新的value覆蓋舊的valueif (index >= 0) {//index的2倍+1所對(duì)應(yīng)的元素存在相應(yīng)value的位置index = (index<<1) + 1; final V old = (V)mArray[index];mArray[index] = value;return old;}//當(dāng)index<0，說明是新的鍵值對(duì)，對(duì)index進(jìn)行加一取相反數(shù)作為新的鍵值對(duì)的位置 index = ~index; //當(dāng)mSize大于或等于mHashes數(shù)組長度時(shí)，需要擴(kuò)容if (osize >= mHashes.length) { final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1)): (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);final int[] ohashes = mHashes;final Object[] oarray = mArray;//進(jìn)行內(nèi)存分配allocArrays(n); //由于ArrayMap并非線程安全的類，不允許并行，如果擴(kuò)容過程其他線程 //mSize則拋出異常if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {throw new ConcurrentModificationException();}if (mHashes.length > 0) {//將原來老的數(shù)組拷貝到新分配的數(shù)組System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);System.arraycopy(oarray, 0, mArray, 0, oarray.length);}//釋放內(nèi)存freeArrays(ohashes, oarray, osize); }//當(dāng)需要插入的位置不在數(shù)組末尾時(shí)，需要將index位置后的數(shù)據(jù)通過拷貝往后移動(dòng)一位if (index < osize) {System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);//這里，index+1比index大1，但是<<1操作擴(kuò)大二倍后，就相差2了//所以不是從index<<1到(index+2)<<1System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);}if (CONCURRENT_MODIFICATION_EXCEPTIONS) {if (osize != mSize || index >= mHashes.length) {throw new ConcurrentModificationException();}}//將hash、key、value添加相應(yīng)數(shù)組的位置，數(shù)據(jù)個(gè)數(shù)mSize加1mHashes[index] = hash;mArray[index<<1] = key;mArray[(index<<1)+1] = value;mSize++; return null; }

(1).二分查找

indexOfNull和indexOf方法內(nèi)部主要通過binarySearch實(shí)現(xiàn)，并對(duì)返回值進(jìn)行了一些處理。

static int binarySearch(int[] array, int size, int value) {int lo = 0;int hi = size - 1;while (lo <= hi) {final int mid = (lo + hi) >>> 1;final int midVal = array[mid];if (midVal < value) {lo = mid + 1;} else if (midVal > value) {hi = mid - 1;} else {return mid; }}return ~lo; }

(2).內(nèi)存釋放

private static void freeArrays(final int[] hashes, final Object[] array, final int size) {//當(dāng)釋放的是大小為8的對(duì)象if (hashes.length == (BASE_SIZE*2)) { synchronized (ArrayMap.class) {// 當(dāng)大小為8的緩存池的數(shù)量小于10個(gè)，則將其放入緩存池if (mTwiceBaseCacheSize < CACHE_SIZE) { //array[0]指向原來的緩存池array[0] = mTwiceBaseCache; //array[1]存儲(chǔ)hash數(shù)組array[1] = hashes;//清空其他數(shù)據(jù)for (int i=(size<<1)-1; i>=2; i--) {array[i] = null; }//mTwiceBaseCache指向新加入緩存池的arraymTwiceBaseCache = array; //緩存池大小加1mTwiceBaseCacheSize++; }}//當(dāng)釋放的是大小為4的對(duì)象，原理同上} 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++;}}} }

4.get方法

public V get(Object key) {//根據(jù)key找到index，并返回相應(yīng)值final int index = indexOfKey(key);return index >= 0 ? (V)mArray[(index<<1)+1] : null; }

(1).indexOfKey

public int indexOfKey(Object key) {return key == null ? indexOfNull(): indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode()); }

可以看出indexOfKey內(nèi)部通過調(diào)用indexOfNull和indexOf實(shí)現(xiàn)，核心也是通過二分查找實(shí)現(xiàn)。

5.remove方法

public V remove(Object key) {final int index = indexOfKey(key);if (index >= 0) {return removeAt(index); }return null; }

remove內(nèi)部調(diào)用indexOfKey，把key轉(zhuǎn)換為index，最后委派給removeAt處理。

(1).removeAt

public V removeAt(int index) {final Object old = mArray[(index << 1) + 1];final int osize = mSize;final int nsize;//當(dāng)被移除的是ArrayMap的最后一個(gè)元素if (osize <= 1) { //釋放內(nèi)存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) {final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2);final int[] ohashes = mHashes;final Object[] oarray = mArray;allocArrays(n); //內(nèi)存收縮//禁止并發(fā)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) { //當(dāng)被移除的元素不是數(shù)組最末尾的元素時(shí)，則需要將后面的數(shù)組往前移動(dòng)System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index);System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,(nsize - index) << 1);}//再將最后一個(gè)位置設(shè)置為nullmArray[nsize << 1] = null;mArray[(nsize << 1) + 1] = null;}}if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {throw new ConcurrentModificationException();}mSize = nsize; //大小減1return (V)old; }

三.總結(jié)

1.緩存機(jī)制——內(nèi)存分配(allocArrays)和內(nèi)存釋放(freeArrays)

(1).allocArrays觸發(fā)時(shí)機(jī):

當(dāng)執(zhí)行ArrayMap的構(gòu)造函數(shù)的情況
當(dāng)執(zhí)行removeAt()在滿足容量收緊機(jī)制的情況
當(dāng)執(zhí)行ensureCapacity()在當(dāng)前容量小于預(yù)期容量的情況下, 先執(zhí)行allocArrays,再freeArrays
當(dāng)執(zhí)行put()在容量滿的情況下, 先執(zhí)行allocArrays, 再執(zhí)行freeArrays

(2).freeArrays()觸發(fā)時(shí)機(jī):

當(dāng)執(zhí)行removeAt()移除最后一個(gè)元素的情況
當(dāng)執(zhí)行clear()清理的情況
當(dāng)執(zhí)行ensureCapacity()在當(dāng)前容量小于預(yù)期容量的情況下, 先執(zhí)行allocArrays,再freeArrays
當(dāng)執(zhí)行put()在容量滿的情況下, 先執(zhí)行allocArrays, 再執(zhí)行freeArrays

2.擴(kuò)容機(jī)制——容量擴(kuò)張(put)和容量收縮(removeAt)

(1).容量擴(kuò)張：put

觸發(fā)：當(dāng)mSize大于或等于mHashes數(shù)組長度時(shí)擴(kuò)容
當(dāng)map個(gè)數(shù)滿足條件 osize<4時(shí)，則擴(kuò)容后的大小為4；
當(dāng)map個(gè)數(shù)滿足條件 4<= osize < 8時(shí)，則擴(kuò)容后的大小為8；
當(dāng)map個(gè)數(shù)滿足條件 osize>=8時(shí)，則擴(kuò)容后的大小為原來的1.5倍；
可見ArrayMap大小在不斷增加的過程，size的取值為4，8，12，18，27，40，60，……

(2).容量收縮：removeAt

觸發(fā)：當(dāng)數(shù)組內(nèi)存的大小大于8，且已存儲(chǔ)數(shù)據(jù)的個(gè)數(shù)mSize小于數(shù)組空間大小的1/3時(shí)，收縮
當(dāng)mSize<=8，則設(shè)置新大小為8；
當(dāng)mSize> 8，則設(shè)置新大小為mSize的1.5倍。
在數(shù)據(jù)較大的情況下，當(dāng)內(nèi)存使用量不足1/3的情況下，內(nèi)存數(shù)組會(huì)收緊50%。

總結(jié)

以上是生活随笔為你收集整理的【实习周记】ArrayMap源码分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。