Weekly 之 集合 专栏

这周的 weekly 是分享集合相关的知识，集合所涉及到的知识点就是数据结构、线程安全和性能相关。这次总结了个常见的集合思维导图：

这里面主要的知识点是 Java 集合中的 HashMap 与 Android 集合中 ArrayMap、SparseArray 的比较了，引用 Gityuan 的总结：

• 数据结构
  • 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 更有全面。