Ricky.L的随笔
0%

Android集合类-ArrayMap原理

发表于 更新于 分类于 Disqus：

ArrayMap、SparseArray、HashMap的区别？

  • 数据结构

    • 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更有全面。

总结：

  • HashMap的查找和插入时间复杂度为O(1)的代价是牺牲大量的内存来实现的。
  • 而SparseArray和ArrayMap性能略逊于HashMap，但更节省内存。
  • SparseArray的key是int类型，ArrayMap的key是任意类型。
  • SparseArray删除元素是延迟删除，减少数组拷贝的频次。
  • ArrayMap有对容量4和8的缓存机制，避免频繁的内存分配和垃圾回收。

Android中的小数据量的哈希表，Google推荐数据量小于1000使用ArrayMap，大于1000使用HashMap。

为什么ArrayMap数据量大了性能不如HashMap？数据量小了性能比HashMap好？

ArrayMap中的 mHashs 数组以升序的方式保存了所有的 hash code，在查找数据时则通过二分查找 hash code 所对应的 index。这也是它的 get() 比 HashMap 慢的根据原因所在。

插入、删除需要移动数组的元素，数据多了的话，速度也相对较慢，数据少了影响较小。

ArrayMap底层存储结构是怎样的？

  • mHashes是一个记录所有key的hashcode值组成的数组，是从小到大的排序方式；
  • mArray是一个记录着key-value键值对所组成的数组，是mHashes大小的2倍；

为什么mArray的大小是mHahses的2倍？

因为mArray存储了key和value，所以需要2倍于mHashes的容量。

mHashes 在 index 处存储了 key 的 hash code，而 mArray 则在 hash code 的 index<<1 处存储 key，在 index<<1 + 1 处存储 value。简单点说就是偶数处存储 key，相邻奇数处存储 value。

多个key的hashCode发生冲突时是怎么存储数据的？

HashMap用的是拉链法把同一个hashCode元素放在一个桶中

ArrayMap用的是开放定址法之线性探测法

相同的hashCode存储在mHashes数组中相邻的位置，把原来数组中该位置之后的元素全部后移一位

例子：

index == 0 时 和 index == 1时的 hash code 是一样的，说明 key1 与 key2 的 hash code 是一样的，也就是存在 hash 冲突了。那么，如上，这里的解决办法就是 hash code 存储了 2 份，而 key-value 分别存储一份。

ArrayMap.indexOf(key, hash)原理?

源码的注释已经说的很明白

  1. 在mHashes中二分查找hash的索引
  2. 如果mHashes中没找到hash，说明不存在这个元素，返回二分查找得出的应该插入的位置，以保障mHashes存储的hash保持升序
  3. 如果mHashes中找到了hash，有两种情况：找到元素了 或 存在哈希冲突，这一点通过mArray存储的key和方法传入的key是否相等来判断，如果相等说明找到元素了，不相等则没有找到，没有找到要返回待插入的位置
  4. 由于相同的hash在mHashes中存储在相邻的位置，如果mHashes中找到了hash，但是mArray中存储的key不相等，则往右往左分别寻找相同hash对应的mArray中的key是否相等

ArrayMap.put(key, value)原理?

  1. 求key的hashCode
  2. 通过indexOf(key, hash)计算新的hash应该插入mHashes数组中什么位置
  3. 如果index > 0 说明之前这个key已经存了值，替换为新的value就结束put流程
  4. index < 0 说明mHashes里不存在这个hash，index为待插入的位置
  5. 如果容量不够了，就申请新的数组，容量为之前的1.5倍，把旧数组的值全部拷贝到新的数组
  6. index后面的元素全部后移一位，给index的位置腾出空间
  7. 存储hash到mHashes[index]，存储key、value到mArray的index * 2和index * 2 + 1的位置

为什么通过key求得index后要左移1位？

因为这个index是mHashes的索引，mHashes数组长度是mArray数组长度的一半，索引乘以2，就是作为mArray的索引

ArrayMap.remove()原理？

一般情况下删除一个数据，只需要将 index 后面的数据都往 index 方向移一位，然后删除末位数即可。

如果再满足缩容的条件就进行缩容，条件是mHashs长度大于 2 * BASE_SIZE 且 实际元素个数小于mHashs长度的1/3，就把容量压缩为实际元素大小的1.5倍

为什么是1.5倍，这样保证不会频繁的创建数组，也不会浪费太多的空间，平衡了性能

mHashes里存的hashcode为什么要升序？

因为要二分查找获取插入位置。

为什么mHashes中查找元素要二分查找？不能用HashMap的索引定位法吗？

HashMap是怎么计算索引位置的？

HashMap是直接用数组大小与key的hashCode做与操作得到数组索引。

为什么ArrayMap不按照HashMap计算索引的方式来做呢？

因为扩容后会重新hash，让元素分布的更均匀以较少哈希冲突，重新hash过程比较耗时，实现起来也比较复杂。

数据量小的情况下，用二分查找足够应付。

ArrayMap为什么要设计一个缓存机制？

很多场景可能起初都是数据很少，为了减少频繁地创建和回收数组，特意设计了两个缓存池，分别缓存大小为4和8的ArrayMap对象，这两个长度的Map根据统计信息应该用的很多。

ArrayMap缓存机制实现原理？

freeArrays(hashes, array, size) 会把hashes数组和array数组用链表的形式存储下来，头结点用mBaseCache、mTwiceBaseCache存储，分别表示数组长度为4和8的缓存

freeArrays()触发时机:

  • 当执行removeAt()移除最后一个元素的情况
  • 当执行clear()清理的情况
  • 当执行ensureCapacity()在当前容量小于预期容量的情况下, 先执行allocArrays,再执行freeArrays
  • 当执行put()在容量满的情况下, 先执行allocArrays, 再执行freeArrays

当allocArrays分配内存时，如果所需要分配的大小等于4或者8，且相对应的缓冲池不为空，则会从相应缓存池中取出缓存的mArray和mHashes。

这里需要注意的是只有大小为4或者8的内存分配才有可能从缓存池取数据，因为freeArrays过程放入缓存池的大小只有4或8，对于其他大小的内存分配则需要创建新的数组。

优化小技巧，对于分配数据不超过8的对象的情况下，一定要创建4或者8大小，否则浪费了缓存机制。比如ArrayMap[7]就是不友好的写法，建议写成ArrayMap[8]。

两个缓存池大小上限为10个。

扩容的条件？

mSize是实际存储的元素的个数

当mSize大于或等于mHashes数组长度时需要扩容，新容量的规则如下：

  • 当map个数满足条件 osize<4时，则扩容后的大小为4；
  • 当map个数满足条件 4<= osize < 8时，则扩容后的大小为8；
  • 当map个数满足条件 osize>=8时，则扩容后的大小为原来的1.5倍；

缩容的条件？

当数组内存的大小大于8，且已存储数据的个数mSize小于数组空间大小的1/3的情况下，需要收紧数据的内容容量，分配新的数组，老的内存靠虚拟机自动回收。

  • 如果mSize<=8，则设置新大小为8；
  • 如果mSize> 8，则设置新大小为mSize的1.5倍。

也就是说在数据较大的情况下，当内存使用量不足1/3的情况下，内存数组会收紧50%

参考资料