Android随笔-ArrayMap

ArrayMap 是 Android 系统android.util 包专门设计用于替代 HashMap 的内存优化型数据结构由 Google 工程师 Dianne Hackborn 于 2013 年引入 Android 源码。它的核心思想是用时间换空间——牺牲部分查找性能换取更小的内存占用。一、设计背景HashMap 在移动端的痛点HashMap 的查找和插入时间复杂度为 O(1)但代价是牺牲大量内存HashMap 的内存开销说明Entry 对象每个键值对封装为NodeK,V含key、value、hash、next四个字段哈希表数组默认容量 16负载因子 0.75大量空闲槽位链表/红黑树冲突时额外分配节点对象自动装箱int等基础类型 key 需装箱为Integer扩容开销容量翻倍2 倍触发全量 rehash临时内存翻倍在 Android 这种内存敏感的移动设备上当数据量不大几百个以内时HashMap 的内存浪费非常可观。二、ArrayMap 的核心数据结构ArrayMap 用两个数组替代了 HashMap 的数组链表红黑树结构publicfinalclassArrayMapK,VimplementsMapK,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*21索引关系key 存放在 mArray[index 1]value 存放在 mArray[(index 1) 1]三、核心方法源码级解析1. 查找indexOf(key, hash)ArrayMap 的所有操作都基于二分查找时间复杂度 O(log n)intindexOf(Objectkey,inthash){// 1. 在 mHashes 中二分查找 hash 的位置finalintindexbinarySearch(mHashes,0,mSize,hash);if(index0){// 没找到返回待插入位置取反return~index;}// 2. hash 找到了但可能是哈希冲突需验证 key 是否相等if(key.equals(mArray[index1])){returnindex;// 真正找到}// 3. 哈希冲突相同 hash 的 key 在相邻位置前后扫描for(intiindex-1;i0mHashes[i]hash;i--){if(key.equals(mArray[i1]))returni;}for(intiindex1;imSizemHashes[i]hash;i){if(key.equals(mArray[i1]))returni;}// 4. 没找到返回冲突链末尾的插入位置return~end;}2. 插入put(key, value)publicVput(Kkey,Vvalue){finalintosizemSize;finalinthash;intindex;if(keynull){hash0;indexindexOfNull();// 专门处理 null key}else{hashmIdentityHashCode?System.identityHashCode(key):key.hashCode();indexindexOf(key,hash);}if(index0){// key 已存在覆盖 valueindex(index1)1;finalVold(V)mArray[index];mArray[index]value;returnold;}index~index;// 转换为实际插入位置// 容量检查与扩容if(osizemHashes.length){finalintnosize(BASE_SIZE*2)?(osize(osize1))// 8 时按 1.5 倍扩容:(osizeBASE_SIZE?(BASE_SIZE*2):BASE_SIZE);// ... 申请新数组System.arraycopy 迁移数据}// index 后面的元素后移腾出位置if(indexosize){System.arraycopy(mHashes,index,mHashes,index1,osize-index);System.arraycopy(mArray,index1,mArray,(index1)1,(mSize-index)1);}// 插入新数据mHashes[index]hash;mArray[index1]key;mArray[(index1)1]value;mSize;returnnull;}3. 删除remove(key)publicVremove(Objectkey){intindexindexOfKey(key);if(index0){returnremoveAt(index);}returnnull;}publicVremoveAt(intindex){finalObjectoldmArray[(index1)1];if(mSize1){// 只剩一个元素直接清空并缓存数组freeArrays(mHashes,mArray,mSize);mHashesEmptyArray.INT;mArrayEmptyArray.OBJECT;mSize0;}else{// 触发收缩判断if(mHashes.length(BASE_SIZE*2)mSizemHashes.length/3){// 内存利用率低收缩数组shrinkArrays();}else{// 普通删除前移覆盖System.arraycopy(mHashes,index1,mHashes,index,mSize-index-1);System.arraycopy(mArray,(index1)1,mArray,index1,(mSize-index-1)1);mArray[(mSize-1)1]null;mArray[((mSize-1)1)1]null;}mSize--;}return(V)old;}四、扩容与收缩机制扩容策略当前容量扩容方式 4扩容到 4 (BASE_SIZE)4 ~ 7扩容到 8 (BASE_SIZE * 2) 8按1.5 倍扩容 (osize (osize 1))对比 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_SIZE10;// 缓存上限销毁时通过 freeArrays() 将数组放入缓存创建时通过 allocArrays() 优先从缓存复用。五、与 HashMap、SparseArray 的对比特性HashMapArrayMapSparseArray内存占用高Entry 对象 哈希表 链表/树低双数组无额外对象极低无装箱int[] Object[]查找复杂度O(1) 平均O(log n) 二分查找O(log n) 二分查找插入/删除快链表/树操作慢需数组移动元素慢延迟删除标记 DELETED扩容倍数2 倍1.5 倍2 倍Key 类型任意 Object任意 Objectint 类型避免自动装箱适用数据量 1000 1000推荐 1000推荐线程安全否否否典型场景大数据量通用 MapBundle底层、小数据缓存ViewID 映射、资源 ID 缓存六、使用建议✅推荐使用 ArrayMap 的场景数据量较小 1000最好在几百以内内存敏感场景如 Bundle 底层Android 源码中 Bundle 内部使用 ArrayMap频繁创建/销毁 Map 对象缓存复用机制减少 GCKey 为非 int 类型String、Object 等❌不推荐使用的场景5.数据量 1000性能退化明显至少 50%6.高频增删操作数组移动开销大7.Key 为 int 类型优先使用 SparseArray避免 int→Integer 自动装箱 替代建议**// 不推荐HashMapInteger,ObjectmapnewHashMap();// 推荐避免自动装箱SparseArrayObjectarraynewSparseArray();// 推荐String key小数据量ArrayMapString,ObjectarrayMapnewArrayMap();**七、总结ArrayMap 两个有序数组 二分查找 1.5 倍扩容 缓存复用。它用 O(log n) 的查找代价换来了比 HashMap 更小的内存 footprint是 Android 源码中 Bundle、Intent 等高频组件的底层实现选择。