Android ArrayMap源代码分析
分析源码之前先来介绍一下ArrayMap的存储结构，ArrayMap数据的存储不同于HashMap和SparseArray。
Java提供了HashMap，但是HashMap对于手机端而言，对空间的利用太大，所以Android提供了SparseArray和ArrayMap。二者都是基于二分查找，所以数据量大的时候，最坏效率会比HashMap慢很多。因此建议数量在千以内比较合适。
一、SparseArray
SparseArray对应的key只能是int类型，它不会对key进行装箱操作。它使用了两个数组，一个保存key，一个保存value。
SparseArray使用二分查找来找到key对应的插入位置。所以要保证mKeys数组有序。
remove的时候不会立刻重新清理删除掉的数据，而是将对一个的数据标记为DELETE(一个Object对象)。在必要的环节调用gc清理标记为DELETE的空间。
二、ArrayMap
重点介绍一下ArrayMap。
首先从ArrayMap的四个数组说起。mHashes，用于保存key对应的hashCode；mArray，用于保存键值对（key，value），其结构为[key1,value1,key2,value2,key3,value3,......]；mBaseCache，缓存，如果ArrayMap的数据量从4，增加到8，用该数组保存之前使用的mHashes和mArray，这样如果数据量再变回4的时候，可以再次使用之前的数组，不需要再次申请空间，这样节省了一定的时间；mTwiceBaseCache，与mBaseCache对应，不过触发的条件是数据量从8增长到12。
上面提到的数据量有8增长到12，为什么不是16？这也算是ArrayMap的一个优化的点，它不是每次增长1倍，而是使用了如下方法（mSize+(mSize>>1)），即每次增加1/2。
有了上面的说明，读懂代码就容易多了。
1、很多地方用到的indexOf
这里使用了二分查找来查找对应的index
intindexOf(Objectkey,inthash){
finalintN=mSize;
//Importantfastcase:ifnothingisinhere,nothingtolookfor.
//数组为空，直接返回
if(N==0){
return~0;
}
//二分查找，不细说了
intindex=ContainerHelpers.binarySearch(mHashes,N,hash);
//Ifthehashcodewasn'tfound,thenwehavenoentryforthiskey.
//没找到hashCode，返回index，一个负数
if(index<0){
returnindex;
}
//Ifthekeyatthereturnedindexmatches,that'swhatwewant.
//对比key值，相同则返回index
if(key.equals(mArray[index<<1])){
returnindex;
}
//Searchforamatchingkeyaftertheindex.
//如果返回的index对应的key值，与传入的key值不等，则可能对应的key在index后面
intend;
for(end=index+1;end<N&&mHashes[end]==hash;end++){
if(key.equals(mArray[end<<1]))returnend;
}
//Searchforamatchingkeybeforetheindex.
//接上句，后面没有，那一定在前面。
for(inti=index-1;i>=0&&mHashes[i]==hash;i--){
if(key.equals(mArray[i<<1]))returni;
}
//Keynotfound--returnnegativevalueindicatingwherea
//newentryforthiskeyshouldgo.Weusetheendofthe
//hashchaintoreducethenumberofarrayentriesthatwill
//needtobecopiedwheninserting.
//毛都没找到，那肯定是没有了，返回个负数
return~end;
}
2、看一下put方法
publicVput(Kkey,Vvalue){
finalinthash;
intindex;
//key是空，则通过indexOfNull查找对应的index；如果不为空，通过indexOf查找对应的index
if(key==null){
hash=0;
index=indexOfNull();
}else{
hash=key.hashCode();
index=indexOf(key,hash);
}
//index大于或等于0，一定是之前put过相同的key，直接替换对应的value。因为mArray中不只保存了value，还保存了key。
//其结构为[key1,value1,key2,value2,key3,value3,......]
//所以，需要将index乘2对应key，index乘2再加1对应value
if(index>=0){
index=(index<<1)+1;
finalVold=(V)mArray[index];
mArray[index]=value;
returnold;
}
//取正数
index=~index;
//mSize的大小，即已经保存的数据量与mHashes的长度相同了，需要扩容啦
if(mSize>=mHashes.length){
//扩容后的大小，有以下几个档位，BASE_SIZE（4），BASE_SIZE的2倍（8），mSize+(mSize>>1)（比之前的数据量扩容1/2）
finalintn=mSize>=(BASE_SIZE*2)?(mSize+(mSize>>1))
:(mSize>=BASE_SIZE?(BASE_SIZE*2):BASE_SIZE);
if(DEBUG)Log.d(TAG,"put:growfrom"+mHashes.length+"to"+n);
finalint[]ohashes=mHashes;
finalObject[]oarray=mArray;
//扩容方法的实现
allocArrays(n);
//扩容后，需要把原来的数据拷贝到新数组中
if(mHashes.length>0){
if(DEBUG)Log.d(TAG,"put:copy0-"+mSize+"to0");
System.arraycopy(ohashes,0,mHashes,0,ohashes.length);
System.arraycopy(oarray,0,mArray,0,oarray.length);
}
//看看被废弃的数组是否还有利用价值
//如果被废弃的数组的数据量为4或8，说明可能利用价值，以后用到的时候可以直接用。
//如果被废弃的数据量太大，扔了算了，要不太占内存。如果浪费内存了，还费这么大劲，加了类干啥。
freeArrays(ohashes,oarray,mSize);
}
//这次put的key对应的hashcode排序没有排在最后（index没有指示到数组结尾），因此需要移动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);
}
//把数据保存到数组中。看到了吧，key和value都在mArray中；hashCode放到mHashes
mHashes[index]=hash;
mArray[index<<1]=key;
mArray[(index<<1)+1]=value;
mSize++;
returnnull;
}
3、remove方法
remove方法在某种条件下，会重新分配内存，保证分配给ArrayMap的内存在合理区间，减少对内存的占用。但是从这里也可以看出，Android使用的是用时间换空间的方式。无论从任何角度，频繁的分配回收内存一定会耗费时间的。
remove最终使用的是removeAt方法，此处只说明removeAt
/**
*Removethekey/valuemappingatthegivenindex.
*@paramindexThedesiredindex,mustbebetween0and{@link#size()}-1.
*@returnReturnsthevaluethatwasstoredatthisindex.
*/
publicVremoveAt(intindex){
finalObjectold=mArray[(index<<1)+1];
//如果数据量小于等于1，说明删除该元素后，没有数组为空，清空两个数组。
if(mSize<=1){
//Nowempty.
if(DEBUG)Log.d(TAG,"remove:shrinkfrom"+mHashes.length+"to0");
//put中已有说明
freeArrays(mHashes,mArray,mSize);
mHashes=EmptyArray.INT;
mArray=EmptyArray.OBJECT;
mSize=0;
}else{
//如果当初申请的数组最大容纳数据个数大于BASE_SIZE的2倍（8），并且现在存储的数据量只用了申请数量的1/3，
//则需要重新分配空间，已减少对内存的占用
if(mHashes.length>(BASE_SIZE*2)&&mSize<mHashes.length/3){
//Shrunkenoughtoreducesizeofarrays.Wedon'tallowitto
//shrinksmallerthan(BASE_SIZE*2)toavoidflappingbetween
//thatandBASE_SIZE.
//新数组的大小
finalintn=mSize>(BASE_SIZE*2)?(mSize+(mSize>>1)):(BASE_SIZE*2);
if(DEBUG)Log.d(TAG,"remove:shrinkfrom"+mHashes.length+"to"+n);
finalint[]ohashes=mHashes;
finalObject[]oarray=mArray;
allocArrays(n);
mSize--;
//index之前的数据拷贝到新数组中
if(index>0){
if(DEBUG)Log.d(TAG,"remove:copyfrom0-"+index+"to0");
System.arraycopy(ohashes,0,mHashes,0,index);
System.arraycopy(oarray,0,mArray,0,index<<1);
}
//将index之后的数据拷贝到新数组中，和（index>0）的分支结合，就将index位置的数据删除了
if(index<mSize){
if(DEBUG)Log.d(TAG,"remove:copyfrom"+(index+1)+"-"+mSize
+"to"+index);
System.arraycopy(ohashes,index+1,mHashes,index,mSize-index);
System.arraycopy(oarray,(index+1)<<1,mArray,index<<1,
(mSize-index)<<1);
}
}else{
mSize--;
//将index后的数据向前移位
if(index<mSize){
if(DEBUG)Log.d(TAG,"remove:move"+(index+1)+"-"+mSize
+"to"+index);
System.arraycopy(mHashes,index+1,mHashes,index,mSize-index);
System.arraycopy(mArray,(index+1)<<1,mArray,index<<1,
(mSize-index)<<1);
}
//移位后最后一个数据清空
mArray[mSize<<1]=null;
mArray[(mSize<<1)+1]=null;
}
}
return(V)old;
}
4、freeArrays
put中有说明，这里就不进行概述了，直接上代码，印证上面的说法。
privatestaticvoidfreeArrays(finalint[]hashes,finalObject[]array,finalintsize){
//已经废弃的数组个数为BASE_SIZE的2倍（8），则用mTwiceBaseCache保存废弃的数组；
//如果个数为BASE_SIZE（4），则用mBaseCache保存废弃的数组
if(hashes.length==(BASE_SIZE*2)){
synchronized(ArrayMap.class){
if(mTwiceBaseCacheSize<CACHE_SIZE){
//array为刚刚废弃的数组，mTwiceBaseCache如果有内容，则放入array[0]位置，
//在allocArrays中会从array[0]取出，放回mTwiceBaseCache
array[0]=mTwiceBaseCache;
//array[1]存放hash数组。因为array中每个元素都是Object对象，所以每个元素都可以存放数组
array[1]=hashes;
//清除index为2和之后的数据
for(inti=(size<<1)-1;i>=2;i--){
array[i]=null;
}
mTwiceBaseCache=array;
mTwiceBaseCacheSize++;
if(DEBUG)Log.d(TAG,"Storing2xcache"+array
+"nowhave"+mTwiceBaseCacheSize+"entries");
}
}
}elseif(hashes.length==BASE_SIZE){
synchronized(ArrayMap.class){
if(mBaseCacheSize<CACHE_SIZE){
//代码的注释可以参考上面，不重复说明了
array[0]=mBaseCache;
array[1]=hashes;
for(inti=(size<<1)-1;i>=2;i--){
array[i]=null;
}
mBaseCache=array;
mBaseCacheSize++;
if(DEBUG)Log.d(TAG,"Storing1xcache"+array
+"nowhave"+mBaseCacheSize+"entries");
}
}
}
}
5、allocArrays
算了，感觉没啥好说的，看懂了freeArrays，allocArrays自然就理解了。
总体来说，通过新数组的个数产生3个分支，个数为BASE_SIZE（4），从mBaseCache取之前废弃的数组；BASE_SIZE的2倍（8），从mTwiceBaseCache取之前废弃的数组；其他，之前废弃的数组没有存储，因为太耗费内存，这种情况下，重新分配内存。
6、clear和erase
clear清空数组，如果再向数组中添加元素，需要重新申请空间；erase清除数组中的数组，空间还在。
7、get
主要的逻辑都在indexOf中了，剩下的代码不需要分析了，看了的都说懂（窃笑）。
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！