ArrayMap

• 继承至Map的 key- value的数据集合
• 相比于HaspMap 它占用的内存较小，内存使用率更高，效率相对HaspMap要慢，尤其是大量数据的时候，因为内部使用二分查找
• 内部有两个数组，一个用于存储hash值， 一个用于存储数据object。二分查找是根据hash值的大小排序的，因此，下图中的mHashes必定是一个有序的数据。因此它在增删的时候，会重新排序，效率低。
  

二分查找和红黑树性能对比

• 二分查找
  用数组保存数据，保证有序。二分查找速度很快，但是仅限于查找。因为插入的时候要保证有序，所以要往后移动数据以便插入。查找复杂度O(logn),插入复杂度O(n)
• 红黑树
  无论数据量如何，插入删除时间复杂度都为O(logn)

SparseArray是什么？

• SparseArray稀疏数组，可以用来存储基本类型数据，避免数据的装箱拆箱，某些情况下性能更好。
• 几个同类
  1. SparseArray
     存储Object类型，put(int key, E value)
  2. SparseIntArray
     存储int类型，put(int key, int value)
  3. SparseLongArray
     存储long类型，put(int key, long value)
  4. SparseBooleanArray
     存储boolen类型，put(int key, boolean value)

SparseArray用法

• 添加数据
  put(int key, int value)
  append(int key, int value)
• 删除数据
  removeAt(int index) 根据索引删除
  delete(int key) 根据键删除
  索引和键不同。

    private fun test() {
        val intArray = SparseIntArray()
        intArray.put(1, 1)
        intArray.put(2, 2)
        intArray.put(3, 3)
        Log.d(TAG, "test: $intArray")
        intArray.delete(1)
        Log.d(TAG, "test: $intArray")
        intArray.removeAt(1)
        Log.d(TAG, "test: $intArray")
    }

D/MainActivity: test: {1=1, 2=2, 3=3}
D/MainActivity: test: {2=2, 3=3}
D/MainActivity: test: {2=2}

SparseArray特点

1. 可以存储基本类型，避免装箱开箱
2. 无需Hash
3. 根据key进行排序
4. 增加数据和查找数据基于二分查找
5. 延迟删除
   并不是在每次remove操作直接移动数组元素，而是用一个删除标记将对应key的value标记为已删除，并标记需要回收，等待下次添加、扩容等需要移动数组元素的地方统一操作，进一步提升性能
6. 某些场景下可以用SparseArray来代替HashMap<Integer, E>

参考资料

• SparseArray官方文档
• ArrayMap官方文档
• Android内存优化（使用SparseArray和ArrayMap代替HashMap）
• 查找算法之顺序、二分、二叉搜索树、红黑树 详细比较总结