526互联

Android创造的ArrayMap和SparseArray

发布时间 2023-08-20 15:31:23作者: joannae

ArrayMap和SparseArray，都是采取时间换取空间的方式来提高手机App的运行效率。

1.在数据量小的时候一般认为1000以下，当你的key为int的时候，使用 SparseArray 确实是一个很不错的选择，内存大概能节省30%，相比用HashMap，因为它key值不需要装箱，所以时间性能平均来看也优于HashMap，建议使用！

2.ArrayMap相对于SparseArray，特点就是key值类型不受限，任何情况下都可以取代HashMap，但是ArrayMap的内存节省并不明显，也就在10%左右，时间性能却是最差的，当然了，1000以内的数据量也无所谓了。

ArrayMap

  • 两个数组来存储；key的hash数据，key-value组成的数组；
  • 通过index来映射，2倍位置为key， 2倍位置+1 为value；
  • mHashes数据，是从小到大有序存储的
  • key是可以为null，null是hash值为0。不为空时，和mIdentityHashCode有关，仅可以在构造器中设置，默认为false 
    hashcode = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode()
  • 应用场景：
    1. item数量小于1000，尤其是插入数据和删除数据不频繁的情况。
    2. Map中包含子Map对
  • 初始化
    • 大小为0时，赋值空数组
    • 大小为4个，优先从mBaseCache（容量大小为8）找有效数组
    • 大小为8，优先从mTwiceBaseCache（容量大小为16）找有效数组
  • 扩容：调用下面两个方法时，可能会扩容 
    public void ensureCapacity(int minimumCapacity)
public V put(K key, V value)

    数组的移动System.arraycopy方法处理，如果容器大小增加了，则废弃的数组；废弃的数组，进行回收，如果存储容量大小为4或者8，会放入缓存中

  • 索引查找 
    1. 进行二分查找，先查找到一个hash相等的位置；
2. 根据查找的位置，若相等则返回查找位置
3. 依据hash值相等，往后查找，若key相等，则返回，hash不等则结束；这时位置跟随hash相等而向后移动
4. 依据hash值相等，往后查找，若key相等，则返回，hash不等则结束
5. 没有找到，返回前面四步处理后的位置，并取非操作，返回负数值
  • 删除数据时，可能会进行容量缩减

 

SparseArray

  • 为稀疏数据准备的；
  • 也是两个数组，存储数组索引的key，存储数据value，通过相等索引来映射；
  • mKeys是从小到大有序存储的
  • key值只能为int 类型，value值为Object类型
  • 应用场景：数据量不大，最好在千级以内
  • 与ArrayMap的区别
    1. list集合
    2. 没有缓存机制
    3. 扩容大小不同；如果小于等于4，变为8，否则2倍扩容
    4. 排序以key排序（ArrayMap是以key的hash排序），数据只存储int类型的value值，key为稀疏数组的索引；
    5. 位置查找时，直接进行二分查找，找到即为插入位置
    6. 删除数据时，对容量大小不做处理