SAKA'S BLOG

SparseArray的简单分析

发表于

SparseArray是谷歌为安卓专门推出的一种数据结构，它没有自动装箱机制，在特定情况下比HashMap的效率要高。当然这些只是官方的说法，这篇文章主要探讨一下这种数据结构的实现，至于效率问题不做研究。

简要介绍

SparseArray底层采用两个相同容量的数组实现，key和value，其中key必须是int型，value则是指定的泛型，这样也就解释了为什么没有自动装箱，因为key数组就是int数组。

构造方法有两种，指定初始容量和不指定初始容量，后者默认初始容量是10.

它提供了与map类似的一些接口：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//获取key所对应的value值
public E get(int key);
//获取key所对应的value值，假如key未找到，则返回指定的值
public E get(int key,E valueIfKeyNotFound)；
//删除key所对应的value
public void delete(int key);
public void remove(int key);
//删除指定索引位置的value值，index的取值范围是0...size-1
public void removeAt(int index);
//删除从指定索引开始（包含它）的后面size个元素
public void removeAtRange(int index,int size);
//加入一个元素
public void put(int key,E value);
public void clear()
public void append(int key,E value);
/**
*   从下边开始所有的方法都会引发重排序
**/
//当前的容量
public int size();
//指定索引的key的值
public int keyAt(int index);
//指定索引的value的值
public E valueAt(int index);
//为指定的索引位置设定value
public void setValueAt(int index,E value);
//指定key的索引位置
public void indexOfKey(int key);
//指定vaule的索引位置
public void indexOfValue(E value);

结构分析

首先介绍一下二分查找法，这种查找必须针对于已经按递增/递减顺序排序好的数组，这是一种快速的查找方式，时间复杂度是log2n。
给一张简单的示意图：

二分查找

在SparseArray中使用的二分查找代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
static int binarySearch(int[] arrray,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;
        }
    }
    return ~lo;
}

这是一个典型的二分查找方法，先取数组中值，比较指定的value是在左还是右，然后再取所在区间的中值，再比较，直到找出对应的值。这里要注意一下这个返回值，假如找到的话会直接返回对应的索引位置，假如未找到的话，则会返回要查找的值的最近接位置的左值，并对他取反。注意这里的巧妙，对这个index正值取反后将会是一个负值，再次取反后将会护院，可以用来在这个位置来插入元素以保持排序。

SparseArray采用的是两个数组来分别保存key和value，采用数组的好处就是可以快速查找元素。在对元素操作时，必须同时增加和删除在key数组和value数组中的元素。因为所有的key都是int型，在插入元素时会自动为key排序，找到key的索引，然后找到value中去插入这个元素。

## 删除

SparseArray的删除操作并不是立即删除，而是采用的标记法。也就是当你执行delete、remove、removeAt、removeAtRange的时候，并不会立即清除指定的元素，而是将指定元素位置的value设置为DELTED标记，这样当下次执行可以引发重排序(上边提到的方法)的操作时，会首先将标记为DELETED的value和key清除，清除是一个耗时操作，需要便利所有元素来移动内存中的位置，简单看一下源码：

```java
private void gc(){
    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!=DELTED){
            if(i!=o){
                keys[o]=keys[i];
                values[o]=val;
                values[i]=null;
            }
            o++;
        }
    }
}

采用标记法的好处就是假如下一次操作不需要触发重排序，则会省略一个遍历循环，比如下面要讲的插入操作。

插入

插入过程也是一个巧妙的过程，有效的利用了在二分查找中返回的最接近查找的值的索引位置的反码，并利用它来在这个位置插入心得元素。

简单的看一下插入的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public void put(int key,E value){
    int i=ContainerHelpers.binarySearch(mKeys,mSize,key);

    if(i>=0){
        mValues[i]=value;
    }else{
        i=~i;

        if(i<mSize&&mValues[i]==DELETED){
            mKeys[i]=key;
            mValues[i]=value;
            return;
        }

        if(mGarbage&& mSzie >=mKyes.length){
            gc();
            i=~ContainerHelpers.binarySearch(mKeys,mSizem,key);
        }

        mKeys=GrowingArrayUtils.insert(mKeys,mSize,i,kye);
        mValues=GrowingArrayUtils.insert(mValues,mSize,i,value);
        mSize++;
    }
}

简单说一下方法中的第一行代码是查找key的索引，2、3行便是假如找到了，就直接替换这个key上的vlaue值，假如未找到，则执行插入操作。这里插入也两种方式：

  1. 要做插入位置已经被标记为删除了，则直接替换原有的值
  2. 要插入位置未标记删除删除，则直接插入，容量不够时自动扩容

讲到这里基本就明白了SparseArray的结构形式，它和HashMap是完全不同的两种结构。这里稍微将一下hashmap的原理，1.7版本的HaspMap底层采用数组和链表形式，每个Entry构成一个链表，这些链表再组成数组，这样做的好处是可以解决hash碰撞，并能根据hash码快速查找桶的位置。但是HashMap必须使用泛型来作为key，所以会遇到自动装箱的问题，在不可避免的情况下，使用final类可以稍微提高效率。这也就是SparseArray宣传的要比HashMap快的原因，但是后者的应用范围更广一些。

除了SparseArray以外，安卓还提供了一些特定类型的数据结构，SparseBooleanArray，SaprseIntArray和SparseLongArray，这三个类用于存储boolean、int和long类型，理论上是比SparseArray要快一些，因为它的value省去了自动装箱，使用的基本类型数组。

最后分享一个我自己正在维护的基于编译期注解实现时间轴效果的控件：

只需要添加一些注解就可以生成adapter,目前还在雏形，需要平衡易用性与复杂度的关系。

github:https://github.com/rangaofei/TimeLine