ArrayMap是Android专门针对内存优化而设计的，用于取代Java API中的HashMap数据结构。为了更进一步优化key是int类型的Map，Android再次提供效率更高的数据结构SparseArray，可避免自动装箱过程。对于key为其他类型则可使用ArrayMap。HashMap的查找和插入时间复杂度为O(1)的代价是牺牲大量的内存来实现的，而SparseArray和ArrayMap性能略逊于HashMap，但更节省内存。
1.HashMap
JavaAPI提供的散列表，用来存储key-value对，内部的实现结构是一个数组和链表，提供了O（1）的查找和插入速度，但代价是大量内存。JDK1.8版本当链表长度超过8则转换为红黑树，让最坏情况的时间复杂度为O(logn)。当前实际键值对个数是否大于或等于阈值threshold（默认为0.75*capacity）即进行扩容，每次扩容是至少是当前大小的2倍，扩容的大小一定是2^n。
问题：HashMap容量或者扩容的大小为什么必须是2的幂?
n 是2的次幂，那么 n-1 通过 二进制表示就能确保永远都是尾端以连续1的形式表示（00001111，00000011）。因此在求mod运算决定放在数组哪个位置的时候，可以通过（n-1）&hash极大加快了运算速度。同理，在做扩容的时候，能确保node要不就是维持不变，要不就是在原本位置+oldCap的新位置上。
2.HashTable
HashTable是HashMap的线程安全版本，通过使用synchronized修饰方法的方式来实现多线程同步。因为Hashtable的同步会锁住整个数组，在高并发的情况下，性能会非常差。
问题：Synchronized容器和Concurrent容器有什么区别？
多线程安全的容器主要分为两种：Synchronized和Concurrent，虽然它们都是线程安全的，但是它们在性能方面差距比较大。Synchronized容器（同步容器）主要通过synchronized关键字来实现线程安全，在使用的时候会对所有的数据加锁。代价是严重降低了并发性，当多个线程竞争容器时，吞吐量会严重降低。于是引入了Concurrent容器（并发容器），Concurrent容器采用了更加智能的方案，该方案不是对整个数据加锁，而是采取了更加细粒度的锁机制，因此，在大并发量的情况下，拥有更高的效率。
3. ConcurrentHashMap
为了解决HashTable并发效率低问题，引入了Concurrent容器，采用分段锁的机制来提升并发能力。JDB1.8版本废弃了分段锁segment的机制，采用数组+链表+红黑树的数据结构，利用CAS+synchronized 来保证并发更新的安全。
3.ArrayMap
Android专门针对内存优化而设计的，用于取代Java API中的HashMap数据结构。
mHashes是一个记录所有key的hashcode值组成的数组，是从小到大的排序方式；mArray是一个记录着key-value键值对所组成的数组，是mHashes大小的2倍。
为了减少频繁地创建和回收Map对象，ArrayMap采用了两个大小为10的缓存队列来分别保存大小为4和8的Map对象,用于ArrayMap所在进程的全局缓存。为了节省内存有更加保守的内存扩张以及内存收缩策略。特别注意该缓存只会缓存大小为4或者为8的array，所以在使用ArrayMap的时候生成new一个ArrayMap要把大小设置为4或者8，用起缓存机制。假如设置为ArrayMap[7]那么就会重新分配内存，没有使用起缓存机制。扩容策略是1.5倍扩容，即4,8,12,18等等。缩紧策略是已存储数据的个数小于数组空间大小的1/3的情况下，内存数组会收紧50%。put方法插入数据时间复杂度为O(logN)，因为要做二分查找找到对应的index，此外还有个消耗是需要在插入位置把数组往后拷贝腾挪出位置来。
4.SparseArray
为了更进一步优化key是int类型的Map，Android再次提供效率更高的数据结构SparseArray，可避免自动装箱过程。SparseArray对应的key只能是int类型，它不会对key进行装箱操作。它使用了两个数组，一个保存key，一个保存value。 从内存使用上来说，SparseArray不需要保存key所对应的哈希值，所以比ArrayMap还能再节省1/3的内存。 延迟回收，当执行delete()或者removeAt()删除数据的操作，只是将相应位置的数据标记为DELETE，并设置mGarbage=true，而不会直接执行数据拷贝移动的操作。
5.总结
数据结构：ArrayMap和SparseArray采用的都是两个数组，Android专门针对内存优化而设计的，HashMap采用的是数据+链表+红黑树
内存优化：ArrayMap比HashMap更节省内存，综合性能方面在数据量不大的情况下，推荐使用ArrayMap。Hash需要创建一个额外对象来保存每一个放入map的entry，且容量的利用率比ArrayMap低，整体更消耗内存。SparseArray比ArrayMap节省1/3的内存，但SparseArray只能用于key为int类型的Map，所以int类型的Map数据推荐使用SparseArray。
性能方面：ArrayMap查找时间复杂度O(logN)，ArrayMap增加、删除操作需要移动成员，速度相比较慢，对于个数小于1000的情况下，性能基本没有明显差异。HashMap查找、修改的时间复杂度为O(1)，SparseArray适合频繁删除和插入来回执行的场景，性能比较好。
缓存机制：ArrayMap针对容量为4和8的对象进行缓存，可避免频繁创建对象而分配内存与GC操作，这两个缓存池大小的上限为10个，防止缓存池无限增大，HashMap没有缓存机制。SparseArray并没有缓存，但有延迟回收机制（删除时只是标记下，并不挪到数组），提供删除效率，同时减少数组成员来回拷贝的次数。
扩容机制：ArrayMap是在容量满的时机触发容量扩大至原来的1.5倍，在容量不足1/3时触发内存收缩至原来的0.5倍，更节省的内存扩容机制。HashMap是在容量的0.75倍时触发容量扩大至原来的2倍，且没有内存收缩机制。HashMap扩容过程有hash重建，相对耗时。所以能大致知道数据量，可指定创建指定容量的对象，能减少性能浪费。
并发问题：ArrayMap是非线程安全的类，大量方法中通过对mSize判断是否发生并发，来决定抛出异常。但没有覆盖到所有并发场景，比如大小没有改变而成员内容改变的情况就没有覆盖。HashMap是在每次增加、删除、清空操作的过程将modCount加1，在关键方法内进入时记录当前mCount，执行完核心逻辑后，再检测mCount是否被其他线程修改，来决定抛出异常。这一点的处理比ArrayMap更有全面。ConcurrentModificationException这种异常机制只是为了提醒开发者不要多线程并发操作，千万不要并发操作ArrayMap和HashMap。
