本篇是入门教程，旨在短小精悍，简略介绍概要设计，面对源码时也知如何下手，深入理解细节请阅读源码。
HashMap
用得多，不解释。
SimpleArrayMap
关键代码
int[] mHashes;
Object[] mArray;
int mSize;
无父类，先看图。
ArrayMap
hash值按顺序装在二分排序数组中，其中hash1<hash2<hash3。
数组的index用于查找目标key对象和value对象。
有一个小知识点
~0 = -1;
~1 = -2;
ArrayMap
在SimpleArrayMap的基础上通过MapCollections增加Iterator。
SparseArray
关键代码
private int[] mKeys;
private Object[] mValues;
private int mSize;
无父类，看图
SparseArray
key是int型，按顺序装在二分排序数组中，其中k1<k2<k3<k。
一个key对应一个object。
SparseIntArray,SparseLongArray,SpaesrBooleanArray
与SparseArray类似， mValues数组换成简单类型，由此节省了三种对象(Entry,Key,Value)。
总结&对比
HashMap
- 包装类型的key和value
- 计算对象的哈希值
- 包含下一个Entry的指针
缺点
自动装拆箱的操作会对内存和GC有影响。
HashMapEntry是一层额外的封装
每次扩容时会重新排列（参考HashMap.transfer方法）
Hash算法不佳导致退化成链表
ArrayMap
API 19（Kitkat）中新增，低版本可以用Support库里的代替
- Object数组是自动装箱的（不包括hash数组）
- Object数组key和value是相邻的
- key的哈希值放在hash数组内
- 二分查找的时间复杂度是O(logN)
- hash数组的index * 2是对应Object数组的值
对比HashMap，并没有解决自动装箱问题，但对于大多数app而言，使用时间复杂度来赢取空间复杂度是值得的。
SparseArray
- values数组仍是自动装箱
- 二分查找的时间复杂度是O(logN)
- keys数组的index直接对应values数组
与HashMap对比，没了Entry和key对象，而且放弃了hash转而使用二分查找，对于扩容来说更轻量了。
总而言之，SparseArray和ArrayMap减少了对象的创建，对于集合数量比较少（千以下）的的性能提升有限，而且并不保证插入顺序。
网友评论