企业官网建设流程全解析

ArrayMap 是 Android 系统（android.util 包）专门设计用于替代 HashMap 的内存优化型数据结构，由 Google 工程师 Dianne Hackborn 于 2013 年引入 Android 源码。它的核心思想是用时间换空间——牺牲部分查找性能，换取更小的内存占用。

一、设计背景：HashMap 在移动端的痛点

HashMap 的查找和插入时间复杂度为 O(1)，但代价是牺牲大量内存：

在 Android 这种内存敏感的移动设备上，当数据量不大（几百个以内）时，HashMap 的内存浪费非常可观。

二、ArrayMap 的核心数据结构

ArrayMap 用两个数组替代了 HashMap 的"数组+链表+红黑树"结构：

publicfinalclassArrayMap<K,V>implementsMap<K,V>{int[]mHashes;// 存储 key 的 hashCode，按升序排列Object[]mArray;// 交替存储 key 和 value，长度为 mHashes 的 2 倍intmSize;// 当前键值对数量}

存储映射关系

mHashes 数组: [10, 25, 38, 52, 67] ← 有序的 hashCode ↓ ↓ ↓ ↓ ↓ mArray 数组: [k0, v0, k1, v1, k2, v2, k3, v3, k4, v4] ↑ ↑ ↑ ↑ ↑ index*2 index*2+1

索引关系：

• key 存放在 mArray[index << 1]
• value 存放在 mArray[(index << 1) + 1]

三、核心方法源码级解析

1. 查找：indexOf(key, hash)

ArrayMap 的所有操作都基于二分查找，时间复杂度 O(log n)：

intindexOf(Objectkey,inthash){// 1. 在 mHashes 中二分查找 hash 的位置finalintindex=binarySearch(mHashes,0,mSize,hash);if(index<0){// 没找到，返回待插入位置（取反）return~index;}// 2. hash 找到了，但可能是哈希冲突，需验证 key 是否相等if(key.equals(mArray[index<<1])){returnindex;// 真正找到}// 3. 哈希冲突：相同 hash 的 key 在相邻位置，前后扫描for(inti=index-1;i>=0&&mHashes[i]==hash;i--){if(key.equals(mArray[i<<1]))returni;}for(inti=index+1;i<mSize&&mHashes[i]==hash;i++){if(key.equals(mArray[i<<1]))returni;}// 4. 没找到，返回冲突链末尾的插入位置return~end;}

2. 插入：put(key, value)

publicVput(Kkey,Vvalue){finalintosize=mSize;finalinthash;intindex;if(key==null){hash=0;index=indexOfNull();// 专门处理 null key}else{hash=mIdentityHashCode?System.identityHashCode(key):key.hashCode();index=indexOf(key,hash);}if(index>=0){// key 已存在，覆盖 valueindex=(index<<1)+1;finalVold=(V)mArray[index];mArray[index]=value;returnold;}index=~index;// 转换为实际插入位置// 容量检查与扩容if(osize>=mHashes.length){finalintn=osize>=(BASE_SIZE*2)?(osize+(osize>>1))// >= 8 时按 1.5 倍扩容:(osize>=BASE_SIZE?(BASE_SIZE*2):BASE_SIZE);// ... 申请新数组，System.arraycopy 迁移数据}// index 后面的元素后移，腾出位置if(index<osize){System.arraycopy(mHashes,index,mHashes,index+1,osize-index);System.arraycopy(mArray,index<<1,mArray,(index+1)<<1,(mSize-index)<<1);}// 插入新数据mHashes[index]=hash;mArray[index<<1]=key;mArray[(index<<1)+1]=value;mSize++;returnnull;}

3. 删除：remove(key)

publicVremove(Objectkey){intindex=indexOfKey(key);if(index>=0){returnremoveAt(index);}returnnull;}publicVremoveAt(intindex){finalObjectold=mArray[(index<<1)+1];if(mSize<=1){// 只剩一个元素，直接清空并缓存数组freeArrays(mHashes,mArray,mSize);mHashes=EmptyArray.INT;mArray=EmptyArray.OBJECT;mSize=0;}else{// 触发收缩判断if(mHashes.length>(BASE_SIZE*2)&&mSize<mHashes.length/3){// 内存利用率低，收缩数组shrinkArrays();}else{// 普通删除：前移覆盖System.arraycopy(mHashes,index+1,mHashes,index,mSize-index-1);System.arraycopy(mArray,(index+1)<<1,mArray,index<<1,(mSize-index-1)<<1);mArray[(mSize-1)<<1]=null;mArray[((mSize-1)<<1)+1]=null;}mSize--;}return(V)old;}

四、扩容与收缩机制

扩容策略

对比 HashMap 的 2 倍扩容，ArrayMap 的 1.5 倍更节省内存。
收缩策略
当 size <= mHashes.length / 3 时触发收缩：

• size > 8：收缩为 size 的 1.5 倍
• size <= 8：收缩为 8（避免在 BASE_SIZE 和 2*BASE_SIZE 之间频繁扩缩）

缓存复用机制
ArrayMap 维护了两个全局缓存池，减少 GC 压力：

staticObject[]mBaseCache;// 缓存容量为 4 的 ArrayMapstaticintmBaseCacheSize;staticObject[]mTwiceBaseCache;// 缓存容量为 8 的 ArrayMapstaticintmTwiceBaseCacheSize;staticfinalintCACHE_SIZE=10;// 缓存上限

销毁时通过 freeArrays() 将数组放入缓存，创建时通过 allocArrays() 优先从缓存复用。

五、与 HashMap、SparseArray 的对比

六、使用建议

✅推荐使用 ArrayMap 的场景

1. 数据量较小（< 1000，最好在几百以内）
2. 内存敏感场景：如 Bundle 底层（Android 源码中 Bundle 内部使用 ArrayMap）
3. 频繁创建/销毁 Map 对象：缓存复用机制减少 GC
4. Key 为非 int 类型：String、Object 等

❌不推荐使用的场景
5.数据量 > 1000：性能退化明显（至少 50%）
6.高频增删操作：数组移动开销大
7.Key 为 int 类型：优先使用 SparseArray（避免 int→Integer 自动装箱）

💡 替代建议

**// 不推荐HashMap<Integer,Object>map=newHashMap<>();// 推荐（避免自动装箱）SparseArray<Object>array=newSparseArray<>();// 推荐（String key，小数据量）ArrayMap<String,Object>arrayMap=newArrayMap<>();**

七、总结

ArrayMap = 两个有序数组 + 二分查找 + 1.5 倍扩容 + 缓存复用。它用 O(log n) 的查找代价，换来了比 HashMap 更小的内存 footprint，是 Android 源码中 Bundle、Intent 等高频组件的底层实现选择。