关于HashMap的知识请看这篇 优秀文章:http://tryenough.com/java-hashmap
SparseArray
有两个构造方法,一个默认构造方法,一个传入容量。
SparseArray sparseArray = new SparseArray<>(); SparseArray sparseArray = new SparseArray<>(capacity);
首先来看看如何创建一个 SparseArray
,而 SparseArray
只需要指定一个泛型表示value类型,而 key
的类型在 SparseArray
内部已经指定了为int类型
看看怎么往里面存放数据吧
sparseArray.put(int key,Student value);
put()
就跟 HashMap
的使用方法一样。
sparseArray.get(int key); sparseArray.get(int key,Student valueIfNotFound);
简介:
用int[]数组存放key,避免了HashMap中基本数据类型需要装箱的步骤,其次不使用额外的结构体(Entry),单个元素的存储成本下降。
要理解SparseArray 的实现原理,需要看代码:
SparseArray用两个数组来存放key和value:
private int[] mKeys; private Object[] mValues;
key的存放按照从小到大的顺序,这样就能保证使用二分查找,而SparseArray内部查找数据也就是使用的二分查找,这样查找的效率比较高。我们来看下put方法,就能大概理解SparseArray的原理了:
//参数是传进来的 int类型的key 和 范形的value public void put(int key, E value) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); //使用二分查找寻找key应该在的位置,具体实现请先看下面的讲解 if (i >= 0) { mValues[i] = value; //如果寻找到lo就直接覆盖value } else { i = ~i; if (i < mSize && mValues[i] == DELETED) { //如果没有找到,并且返回的数组索引对应的值是DELETED那就直接覆盖value mKeys[i] = key; mValues[i] = value; return; } if (mGarbage && mSize >= mKeys.length) { //如果当前数组已满,检查数组中是否有DELETED的值,然后将其删除gc的操作:可查看下面具体源码 gc(); // Search again because indices may have changed. i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); } //最后将数据插入到正确的位置 mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); mSize++; } }
二分查找
//这里传递过来的value是上面的key static int binarySearch(int[] array, int size, int value) { int lo = 0; int hi = size - 1; while (lo <= hi) { final int mid = (lo + hi) >>> 1; final int midVal = array[mid]; if (midVal < value) { lo = mid + 1; } else if (midVal > value) { hi = mid - 1; } else { return mid; // value 找到,直接返回key的索引 } } return ~lo; // 没有找到就直接返回最终lo的取反值,此时的lo值就正好是排好序的lo }
gc:
private void gc() { // Log.e("SparseArray", "gc start with " + mSize); int n = mSize; int o = 0; int[] keys = mKeys; Object[] values = mValues; for (int i = 0; i < n; i++) { Object val = values[i]; if (val != DELETED) { if (i != o) { keys[o] = keys[i]; values[o] = val; values[i] = null; } o++; } } mGarbage = false; mSize = o; // Log.e("SparseArray", "gc end with " + mSize); }
总结:
SparseArray的优点:
避免了基本数据类型的装箱操作
不需要额外的结构体,单个元素的存储成本更低
数据量小的情况下,随机访问的效率更高
SparseArray的缺点:
插入操作需要复制数组,增删效率降低
数据量巨大时,复制数组成本巨大,gc()成本也巨大
数据量巨大时,查询效率也会明显下降
ArrayMap是一个<key,value>映射的数据结构,它设计上更多的是考虑内存的优化,内部是使用两个数组进行数据存储,一个数组记录key的hash值,另外一个数组记录Value值,它和SparseArray一样,也会对key使用二分法进行从小到大排序,在添加、删除、查找数据的时候都是先使用二分查找法得到相应的index,然后通过index来进行添加、查找、删除等操作,所以,应用场景和SparseArray的一样,如果在数据量比较大的情况下,那么它的性能将退化至少50%。
总结:
假设数据量都在千级以内的情况下:
1、如果key的类型已经确定为int类型,那么使用SparseArray,因为它避免了自动装箱的过程,如果key为long类型,它还提供了一个LongSparseArray来确保key为long类型时的使用 2、如果key类型为其它的类型,则使用ArrayMap
热度: 12