1.SparseArray（稀疏数组）
SparseArray是Android中特有的数据结构，标准的jdk里是没有这个类的。在Android内部用来替代HashMap
SparseArray占用内存空闲小，没有额外的Entry对象。一般几百以内的数据性能相对HashMap要好，大概提升0—50%的性能。
他的几个重要的特点：
①以键值对形式进行存储，基于二分查找，因此查找的时间复杂度为0(LogN);
②SparseArray中直接以int作为Key，避免了HashMap的装箱拆箱操作，性能更高，且int的存储开销远远小于Integer;（不支持任意类型的key，key只能是int类型）
③key总是有序的，不管经过多少次插入，key数组中key总是从小到大排列;（key不一定是连续的）
④采用了延迟删除的机制(针对数组的删除扩容开销大的问题的优化) ;
SparseArray适用于数据量不是很大，同时Key又是数字类型的场景。比如，存储某月中每天的某种数据，最多也只有31个，同时它的key也是数字（可以使用1-31，也可以使用时间戳）。再比如，你想要存储userid与用户数据的映射，就可以使用这个来存储。
2.SparseArray重要属性
public class SparseArray
private static final Object DELETED = new Object();
private boolean mGarbage = false;
private int[] mKeys;
private Object[] mValues;
private int mSize;
……
}
SparseArray中的元素较少，下面具体介绍：
①DELETED ：static final 的一个静态Object实例，当一个键值对被remove后，会在对应key的value下放置该对象，标记该元素已经被删除（延迟删除）
②mGarbage ：当值为true时，标志数据结构中有元素被删除，可以触发gc对无效数据进行回收（此时才真正删除）
③mKeys数组： 用于存放Key的数组，通过int[] 进行存储，与HashMap相比减少了装箱拆箱的操作，同时一个int只占4字节。一个重要特点，mKeys的元素是升序排列的，也是基于此，才能使用二分查找
④mValues数组：用于存放与Key对应的Value，通过数组的position 进行映射；如果存放的是int型等，可以用SparseIntArray ，存放的Values也是int数组，性能更高
⑤mSize：mSize的大小等于数组中mValues的值为非DELETED的元素个数
mKeys和mValues读写时采用的下标是一一对应的。
下面通过一个例子体会一下mSize和mKeys、mValues的对应关系：
SparseArray
sparseArray.put(0,null);
sparseArray.put(1,"android");
sparseArray.put(3,1);
sparseArray.put(35,new Boolean(true));
sparseArray.put(2,new String("java"));
sparseArray.put(18,new Object());
sparseArray.put(0,"hello world");
int size = sparseArray.size();
for(int i = 0; i log.d(TAG,"i = " + i+ " ;value = " + SparseArray.get(sparseArray.keyAt(i))); } 例子中new了一个SparseArray，注意声明时只能指定value的类型，而key是固定为int的。然后再往里面添加key和value。注意key为0的情况插入了两次。 然后通过debug可以看到在内存中SparseArray是如何存储的，如下图可以看出key和value的大小都是11，而且keys的值是按从小到大排序的： mGarbage=false mSize=6 mKeys:{int[11]} mValues:{Object[11]} 0=0 0="hello world" 1=1 1="android" 2=2 2="java" 3=3 3={Integer} 1 4=18 4={Object} 5=35 5={Boolean}true 6=0 7=0 8=0 9=0 10=0 此时sparseArray.size()结果为6，mSize也为6。 当执行sparseArray.delete(18);删除key=18的数据后，mSize、mKeys、mValues变化如下： mSize=5 mKeys:{int[11]} mValues:{Object[11]} 0=0 0="hello world" 1=1 1="android" 2=2 2="java" 3=3 3={Integer} 1 4=35 4={Boolean}true 5=35 6=0 7=0 8=0 9=0 10=0 此时sparseArray.size()结果仍然为6，mSize已经变成5。 注意：mValues只显示了非空数据。 3.构造方法 public SparseArray() { this(10); } public SparseArray(int initialCapacity) { if(initialCapacity == 0) { mKeys = Empty array.INT; mValues = Empty array.OBJECT; } else { mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity); mKeys = new int[mValues.length]; } maize = 0; } 可以看出，SparseArray的默认容量是10。（HashMap默认容量为16） SparseArray并不像HashMap一样定义了最大容量是多少，最大可以达到Integer.MAX_VALUE，可能会报OOM。每次扩容时，如果当前容量小于5则扩容为8，否则扩容为原容量的2倍。 4.删除方法 删除是使用标记删除的方法，直接将目标位置的有效元素设置为一个DELETED标记对象。 public void delete(int key) { //查找对应key在数组中的下标，如果存在，返回下标；不存在，返回下标的取反 int i = ContainerHelpers.binarySearch(mKeys, mSize, key); //key存在于mKeys数组中，将元素删除，用DELETED替换原value，起标记作用 if (i >= 0) { if (mValues[i] != DELETED) { mValues[i] = DELETED; mGarbage = true; } } } public E removeReturnOld(int key) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { if (mValues[i] != DELETED) { final E old = (E) mValues[i]; mValues[i] = DELETED; mGarbage = true; return old; } } return null; } public void remove(int key) { delete(key); } 首先通过ContainerHelpers.binarySearch来进行查找对应的key，返回的 i 就是对应数组的下标。 下面看看该方法的实现原理： ContainerHelpers.binarySearch主要做的就是二分查找，并返回下标。 class ContainerHelpers { //第一个参数array为keys的数组，第二个为数组中元素个数（与keys的length不一定相等），第三个value为目标的key static int binarySearch(int[] array, int size, int value) { //当前下标——lo为二分查找的左边界 int lo = 0; //数组下标值的最大值——hi为二分查找的右边界 int hi = size - 1; //还没找到，继续查找 while (lo <= hi) { //左边界+右边界除以2，获取到mid 的index final int mid = (lo + hi) >>> 1; //获取中间元素 final int midVal = array[mid]; if (midVal < value) { // 目标key在右部分 ，即数组中间处的值比要找的值小，代表要找的值在数组的中后部分，所以当前下标取值为mid+1 lo = mid + 1; } else if (midVal > value) { // 目标key在左部分 ，即数组中间处的值比要找的值大，代表要找的值在数组的前中部分，所以当前下标取值为mid-1 hi = mid - 1; } else { //中间处的值与要找的值相等，直接返回key对应在array的下标 return mid; // value found } } //上述没找到匹配值的时候，lo最终变成了要添加元素的位置，此处取反会变成负数，负数表示没有找到，重写取反代表的就是要添加元素的位置。对lo取反！！！很重要 return ~lo; // value not present } 这部分代码很简单，重点就在于最后的return，可能往往二分查找没有找到都是返回-1，但是这里返回了~lo，取反导致下标小于0，用于判断没有找到。这个主要用在put方法中，稍后再讲。现在只要知道，该方法是通过二分查找返回了当前key对应于mKeys数组的下标，如果没有找到，就返回一个特殊的负数。 之后下一步，我们得到了下标i，如果非负数，就对其所对应的value进行替换成DELETED，用于标记该key已经被删除，同时，将garbage赋值true，代表数组中可能存在垃圾。 总结：remove方法主要做的就是这些，找到需要删除的key，并将对应的value用DELETED替换；但是key仍然存在于mKeys数组，因此删除是一个伪删除。这就是所谓的延迟删除机制。 接下来，我们就去put方法中切身体会一下延迟删除的作用和好处。 5.put方法 public void put(int key, E value) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); //要put的key已经存在，可能是remove后，value存放着DELETED，也可能是存放旧值，那么就直接替换value值 if (i >= 0) { mValues[i] = value; } else { // 要put的key不存在，则对i取反，因为i已经取过一次反，这里再次取反，则得到要put的key的在mKeys中的正确下标 i = ~i; //如果 i 小于数组长度，且mValues==DELETED(i对应的Key被延迟删除了) if (i < mSize && mValues[i] == DELETED) { //直接取代，实现真实删除原键值对 mKeys[i] = key; mValues[i] = value; return; } //数组中可能存在延迟删除元素且当前数组长度满，无法添加 if (mGarbage && mSize >= mKeys.length) { //真实删除，将所有延迟删除的元素从数组中清除 gc(); //清除后重新确定当前key在数组中的目标位置 Search again because indices may have changed. i = ~ContainerHelpers.binarySearch( mKeys, mSize, key); } //不存在垃圾或者当前数组仍然可以继续添加元素，不需要扩容，则将 i 之后的元素全部后移，数组中仍然存在被DELETED的垃圾key mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtils.insert( mValues, mSize, i, value); //新元素添加成功，潜在可用元素数量+1 mSize++; } } 通过put源码，可以总结如下： ①通过二分法找出key的下标，判断是否已经存在要添加的key，如果找到直接替换对应的value ②如果不存在要添加的key，且容量充足，则直接添加 ③如果不存在要添加的key，则分别对key和value的两个数组进行扩容并添加元素 透过put的操作可以得到的信息有： ①SparseArray是允许插入value为null的情况，因为key为int类型，所以不存在key为null的情况 ②SparseArray添加元素时key是确保有序的，是按key的大小进行排序的，因此它采用的二分法先找到对应key对应的下标 ③SparseArray默认每次扩容是原容量的2倍（特殊情况：如果当前容量小于5则扩容为8） 可以看到，put方法也调用了ContainerHelpers.binarySearch方法先进行查找，查找到大于0，则在数组中找到了对应的key，此时，直接将value进行替换即可。如果没有找到，返回的是~lo，那么，将i赋值~~lo,即i=lo，此时i就是需要插入的位置。 用个例子展示一下，如果我们查找Key=2： 此时，lo大于hi，退出循环，lo对应的下标为2，且是插入Key=2的理想位置；因此，这个lo取反，有两个重要的作用： ①代表没有找到对应的key ②对返回值重新取反后，得到的就是lo，就是应该插入的元素。此时将key下标为lo及之后的元素后移，再将当前元素插入该位置，就完成了一次有序插入。 此刻，我们找到了i，就是目标位置，如果没有设置延迟删除（DELETED）。那么由于数组的特点，我们需要将 i 序号之后的数组后移，这样就会产生一个较大的性能损耗。但是如果设置了延迟删除且mValue[i]上当前的元素恰巧为DELETED，那么此时我们可以用当前的key替换原来mKeys的key，且用当前value替换DELETED，这样就成功避免了一次数组的迁移操作。 但是事情不可能永远凑巧，如果，i上的元素并非恰好被删除呢？那么此时我们会判断mGarbage，如果为true那么我们执行一次gc(gc的作用就是，如果有DELETED对象存在，就重新整理一下数组，将DELETED对象都移除，数组中只保留有效数据即可)，将无效数据移除，再进行一次二分查找，然后将 i 之后的数据全部后移，将当前key插入；如果mGarbage为false，那么证明其中的数据全部存在，因此不需要gc，直接进行元素插入并将数组后移。 其中GrowingArrayUtils.insert主要做的就是调用System.arraycopy将数组后移，如果需要扩容则扩容。 public static int[] insert(int[] array, int currentSize, int index, int element) { assert currentSize <= array.length; if (currentSize + 1 <= array.length) { //如果当前数组容量充足，先将当前下标index往后移 System.arraycopy(array, index, array, index + 1, currentSize - index); //再将要添加的元素放到下标为index的地方 array[index] = element; return array; } //如果容量不足，先进行扩容，生成新的数组 int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize)); //将原数组中index个元素拷贝到新数组中 System.arraycopy(array, 0, newArray, 0, index); //将要添加的元素添加到index位置 newArray[index] = element; //将原数组中index+1之后的元素拷贝到新数组中 System.arraycopy(array, index, newArray, index + 1, array.length - index); return newArray; } public static int growSize(int currentSize) { //扩容计算规则，当前容量小于5返回8，否则返回2倍的容量 return currentSize <= 4 ? 8 : currentSize * 2; } 既然遇到了gc，那我们再进入gc方法看看SparseArray是如何gc回收数据的： private void gc() { // Log.e("SparseArray", "gc start with " + mSize); //n代表gc前数组的长度； int n = mSize; int o = 0; int[] keys = mKeys; Object[] values = mValues; for (int i = 0; i < n; i++) { Object val = values[i]; //遍历元素，如果value不为DELETED，则用前数据放在o上，o的序号表示当前的有效元素下标。每遇到一次DELETED，则i-o的大小+1； if (val != DELETED) { //之后遇到非DELETED数据，则将后续元素的key和value往前挪 if (i != o) { keys[o] = keys[i]; values[o] = val; values[i] = null; } o++; } } //此时无垃圾数据，o的序号表示mSize的大小 mGarbage = false; mSize = o; // Log.e("SparseArray", "gc end with " + mSize); } 它的内部逻辑很简单，就是从头到尾遍历value数组，把每一个不是DELETED的对象都重新放置一遍，覆盖掉前面的DELETED对象。 这里要注意一个非常非常重要的点： 可以看到在循环遍历中，我们做的是将数组前移。因此会存在一个问题，即gc后有效数组长度为o，但是此时，keys.length可能会大于o，那么此时，最后的keys.length-o 个数组元素中仍然存在着key和value且不会消失；但是，由于mSize等于o，此时并不会访问到最后的多个废弃元素。只有在mSize数组范围内的DELETED数据才被称为延迟删除元素，mSize范围外的不会被gc删除，只会被之后的put数组后移覆盖。 下面来一个例子说明一下gc的特点： 6.Get方法 public E get(int key) { return get(key, null); } @SuppressWarnings("unchecked") public E get(int key, E valueIfKeyNotFound) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i < 0 || mValues[i] == DELETED) { return valueIfKeyNotFound; } else { return (E) mValues[i]; } } 7.总结 ①SparseArray采用了延迟删除的机制，通过将删除KEY的Value设置DELETED，方便之后对该下标的存储进行复用； ②使用二分查找，时间复杂度为O(LogN)，如果没有查找到，那么取反返回左边界，再取反后，左边界即为应该插入的数组下标； ③如果无法直接插入，则根据mGarbage标识（是否有潜在延迟删除的无效数据），进行数据清除，再通过System.arraycopy进行数组后移，将目标元素插入二分查找左边界对应的下标； ④mSize 小于等于keys.length，小于的部分为空数据或者是gc后前移的数据的原数据（也是无效数据），因此二分查找的右边界以mSize为准；mSize包含了延迟删除后的元素个数； ⑤如果遇到频繁删除，不会触发gc机制，导致mSize 远大于有效数组长度，造成性能损耗; ⑥根据源码,可能触发gc操作的方法有(1、put；2、与index有关的所有操作，setValueAt()等；3、size()方法；) ⑦mGarbage为true不一定有无效元素，因为可能被删除的元素恰好被新添加的元素覆盖； 根据SparseArray的这些特点。我们能分析出其使用场景： key为整型； 不需要频繁的删除； 元素个数相对较少； 8.SparseArray与HashMap ①SparseArray采用的不是哈希算法；HashMap采用的是哈希算法 ②SparseArray采用的是两个一维数组分别用于存储键和值；HashMap采用的是一维数组+单向链表 ③SparseArray key只能是int类型；HashMap的key可以是任何类型 ④SparseArray key是有序存储（升序）；HashMap的key无序 ⑤SparseArray默认容量是10；HashMap默认容量是16 ⑥SparseArray内存使用要优于HashMap，因为SparseArray的key是int类型，而HashMap的key是Object，并且SparseArray中value的存储不像HashMap一样需要额外的一个实体类Node/Entey进行封装 ⑦SparseArray查找元素总体而言比HashMap要逊色，因为SparseArray查找是需要经过二分法的过程，而HashMap不存在冲突的情况下其key处的hash对应的下标就可以直接取到值 针对以上SparseArray与HashMap的比较，采用SparseArray还是HashMap，建议根据如下需求选取： ①如果对内存要求比较高，而对查询效率没什么大的要求，可以使用SparseArray ②数据在百级别的，SparseArray比HashMap更有优势 ③要求key是int类型的，使用SparseArray，因为HashMap会对int自动装箱变成Integer类型 ④要求key是有序且是升序的用SparseArray
