Android SparseArray 源码详解

在Android开发中如果使用key为Integer的HashMap,就会出现黄色警告,提示使用SparseArray,SparseArray具有比HashMap更高的内存使用效率,我们在前面的《Android
HashMap源码详解》中提到,HashMap的存储方式是数组加链表,今天要分析的SparseArray是使用纯数组的形式存储。我们先来看其中的一个构造方法

Android数据结构解析系列:
Android中的数据结构解析(一)ArrayList、LinkedList、Vector
Android中的数据结构解析(二)HashSet、LinkedHashSet、TreeSet
Android中的数据结构解析(三)HashMap、HashTable、TreeMap

HashMap是java里比较常用的一个集合类,我比较习惯用来缓存一些处理后的结果。最近在做一个Android项目,在代码中定义这样一个变量,实例化时,Eclipse却给出了一个
performance 警告。

public SparseArray(int initialCapacity) {  
    if (initialCapacity == 0) {  
        mKeys = ContainerHelpers.EMPTY_INTS;  
        mValues = ContainerHelpers.EMPTY_OBJECTS;  
    } else {  
        initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);  
        mKeys = new int[initialCapacity];  
        mValues = new Object[initialCapacity];  
    }  
    mSize = 0;  
}

HashMap是Java和Android开发中非常常用的数据结构,相信大多数人都对它非常熟悉。然而,作为一名Android开发,仅仅只知道使用HashMap是不够的。在很多情况下,HashMap对内存的消耗较大,从而影响移动设备的性能。因此,为了内存优化和性能提升,Android提供了用来替代HashMap的api:SparseArray和ArrayMap。

澳门新葡萄京官网首页 1

先给一个初始空间的大小,默认的是10,但是这个最终空间大小是由计算得到的最理想的大小,

SparseArray

 

public static int idealIntArraySize(int need) {  
    return idealByteArraySize(need * 4) / 4;  
}  

public static int idealByteArraySize(int need) {  
    for (int i = 4; i < 32; i++)  
        if (need <= (1 << i) - 12)  
            return (1 << i) - 12;  

    return need;  
}

先来看一下SparseArray的介绍:

意思就是说用SparseArray<E>来替代,以获取更好性能。老实说,对SparseArray并不熟悉,第一感觉应该是Android提供的一个类。按住Ctrl点击进入SparseArray的源码,果不其然,确定是Android提供的一个工具类。

这就是他所谓的理想大小,不过一直没看明白他为什么要这样计算。

/**
 * SparseArrays map integers to Objects.  Unlike a normal array of Objects,
 * there can be gaps in the indices.  It is intended to be more memory efficient
 * than using a HashMap to map Integers to Objects, both because it avoids
 * auto-boxing keys and its data structure doesn't rely on an extra entry object
 * for each mapping.
 */

澳门新葡萄京官网首页 2

我们先来看一下gc()这个方法

可以看到,SparseArray只能存储key为int类型的数据。所以,可以使用SparseArray<Object>来替代HashMap<Integer,
Object>。它在性能上优于HashMap的原因有两点:

单纯从字面上来理解,SparseArray指的是稀疏数组(Sparse
array)
,所谓稀疏数组就是数组中大部分的内容值都未被使用(或都为零),在数组中仅有少部分的空间使用。因此造成内存空间的浪费,为了节省内存空间,并且不影响数组中原有的内容值,我们可以采用一种压缩的方式来表示稀疏数组的内容。

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);  
}

1.避免了int转为Integer时的自动装箱
在上一节中讲过,HashMap是通过key值的hashCode方法来确定元素存放的位置的。所以,当key值是基本类型int时,会自动装箱成Integer对象。装箱过程中会创建对象,这个动作是很消耗内存的。而SparseArray避免了装箱的这个动作,从而提升了性能。

假设有一个9*7的数组,其内容如下:

这个方法很简单,就是把元素重新排放,如果之前有删除的,就把后面的挪到前面,删除之后就会标注为DELETED,我们主要看一下put(int
key, E value)方法

2.避免了额外的Entry对象
HashMap的底层实现是数组+链表的数据结构。HashMap的每一条数据都会用一个Entry对象进行记录:

 

 /** 
   * Adds a mapping from the specified key to the specified value, 
   * replacing the previous mapping from the specified key if there 
   * was one. 
   */  
  public void put(int key, E value) {  
//通过二分法查找  
      int i = ContainerHelpers.binarySearch(mKeys, mSize, key);  

      if (i >= 0) {  
    //如果找到,说明这个key是存在的,替换就行了。  
          mValues[i] = value;  
      } else {  
    //如果没找到就取反,binarySearch方法没找到返回的是大于key所在下标的取反,在这里再取反  
    //返回的正好是大于key所在下标的值  
          i = ~i;  
    //首先说明一点,是有的key值存放的时候都是排序好的,如果当前存放的key大于数组中最大的key  
    //那么这时的i肯定是大于mSize的,在这里i小于mSize说明这里的key是小于mKeys[]中的最大值的,  
    //如果mValue[i]被删除了,就把当前的key和value放入其中,在这里举个例子,比如下面的数组  
    //{1,3,7,9,13,16,22}如果key为7通过二分法查找得到的i为2,如果key为8则得到的i为-4,通过取反  
    //为3,在下标为3的位置如果被删除了就用当前的值替换掉  
          if (i < mSize && mValues[i] == DELETED) {  
              mKeys[i] = key;  
              mValues[i] = value;  
              return;  
          }  
    //如果当前下标为i的没有被删除,就会执行下面的代码。如果对数据进行了操作,就是mGarbage为true,  
    //并且当前的数据已经满了就调用gc(),然后再重新查找,因为gc之后数据的位置可能会有变化,所以要  
    //必须重新查找  
          if (mGarbage && mSize >= mKeys.length) {  
              gc();  

              // Search again because indices may have changed.  
              i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);  
          }  
    //当目前空间满了以后需要重新计算最理想的数组大小,然后再对数组进行扩容。  
          if (mSize >= mKeys.length) {  
              int n = ArrayUtils.idealIntArraySize(mSize + 1);  

              int[] nkeys = new int[n];  
              Object[] nvalues = new Object[n];  

              // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);  
              System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);  
              System.arraycopy(mValues, 0, nvalues, 0, mValues.length);  

              mKeys = nkeys;  
              mValues = nvalues;  
          }  
    //这里的i有可能是上面重新查找的i,根据上面的二分法查找如果等于mSize,说明当前的key比mKeys中的任何  
    //值都要大,肯定要按顺序放在mKeys数组中最大值的后面,如果不等于,说明当前的key应该放到mKeys数组中  
    //间下标为i的位置,需要对当前大于key的值向后移一位。  
          if (mSize - i != 0) {  
              // Log.e("SparseArray", "move " + (mSize - i));  
              System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);  
              System.arraycopy(mValues, i, mValues, i + 1, mSize - i);  
          }  
    //存放数据  
          mKeys[i] = key;  
          mValues[i] = value;  
          mSize++;  
      }  
  }
static class HashMapEntry<K, V> implements Entry<K, V> {
    final K key;
    V value;
    final int hash;
    HashMapEntry<K, V> next;

澳门新葡萄京官网首页 3

我们再来看一下上面提到的binarySearch(int[] array, int size, int
value)方法

除了key和value之外,还记录了hash值,和到下一个Entry对象的指针。而SparseArray只需要一个key数组和一个value数组存放数据(下面会讲到),不需要额外的Entry对象,从而节省了内存。

 

static int binarySearch(int[] array, int size, int value) {  
    int lo = 0;  
    int hi = size - 1;  

    while (lo <= hi) {  
        int mid = (lo + hi) >>> 1;  
        int midVal = array[mid];  

        if (midVal < value) {  
            lo = mid + 1;  
        } else if (midVal > value) {  
            hi = mid - 1;  
        } else {  
            return mid;  // value found  
        }  
    }  
    return ~lo;  // value not present  
}

接下来看一下SparseArray的具体实现和常用方法:

在此数组中,共有63个空间,但却只使用了5个元素,造成58个元素空间的浪费。以下我们就使用稀疏数组重新来定义这个数组:

这就是二分法查找,前提是数组必须是排序好的并且是升序排列,原理就是通过循环用当前的value和数组中间的值进行比较,如果小于就在前半部分查找,如果大于就在后半部分查找。最后如果找到就返回所在的下标,如果没有就返回一个负数。剩下的remove(int
key)方法和delete(int
key)方法都很简单,删除的时候只是把他的value置为DELETED就可以了,这里就不在介绍。下面我们再来介绍最后一个方法append(int
key, E value)

构造方法:

 

/** 
 * Puts a key/value pair into the array, optimizing for the case where 
 * the key is greater than all existing keys in the array. 
 */  
public void append(int key, E value) {  
    if (mSize != 0 && key <= mKeys[mSize - 1]) {  
        put(key, value);  
        return;  
    }  

    if (mGarbage && mSize >= mKeys.length) {  
        gc();  
    }  

    int pos = mSize;  
    if (pos >= mKeys.length) {  
        int n = ArrayUtils.idealIntArraySize(pos + 1);  

        int[] nkeys = new int[n];  
        Object[] nvalues = new Object[n];  

        // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);  
        System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);  
        System.arraycopy(mValues, 0, nvalues, 0, mValues.length);  

        mKeys = nkeys;  
        mValues = nvalues;  
    }  

    mKeys[pos] = key;  
    mValues[pos] = value;  
    mSize = pos + 1;  
}
    private int[] mKeys;
    private Object[] mValues;
    private int mSize;

    ……

    public SparseArray() {
        this(10);
    }

    public SparseArray(int initialCapacity) {
        if (initialCapacity == 0) {
            mKeys = EmptyArray.INT;
            mValues = EmptyArray.OBJECT;
        } else {
            mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
            mKeys = new int[mValues.length];
        }
        mSize = 0;
    }

澳门新葡萄京官网首页 4

通过上面的注释我们知道如果当前的key比mKeys中的任何一个都大时,使用这个方法比put方法效率更好一些,这个方法和put差不多,put方法的key可以是任何值,但append方法的key值更偏向于大于mKeys的最大值,如果小于就会调用put方法。

key和value分别存放在mKeys和mValues这两个数组中。调用无参构造方法时,默认初始化数组的长度为10。

澳门新葡萄京官网首页, 

再来看一下SparseArray中增删改查方法的实现:

其中在稀疏数组中第一部分所记录的是原数组的列数和行数以及元素使用的个数、第二部分所记录的是原数组中元素的位置和内容。经过压缩之后,原来需要声明大小为63的数组,而使用压缩后,只需要声明大小为6*3的数组,仅需18个存储空间。

    public void put(int key, E value) {
        //二分查找 key是否存在
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i >= 0) {
            //如果key存在则直接替换value
            mValues[i] = value;
        } else {
            //key不存在 对i取反(~)就是应该插入的位置
            i = ~i;

            //如果插入的位置刚好是被删除过的元素,则直接将删除掉的value替换为要插入的value
            if (i < mSize && mValues[i] == DELETED) {
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }

            //如果曾经删除过元素且没有进行过gc,进行一次gc操作
            if (mGarbage && mSize >= mKeys.length) {
                gc();

                // gc后数组下标可能会改变 所以重新查找一遍
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }

            //插入的操作
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            mSize++;
        }
    }

 

SparseArray存储的元素都是按元素的key值从小到大排列好的。put方法的第一行,先调用了ContainerHelpers.binarySearch(mKeys,
mSize, key)查找key是否存在。看一下这个方法的源码:

继续阅读SparseArray的源码,从构造方法我们可以看出,它和一般的List一样,可以预先设置容器大小,默认的大小是10:

    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 found
            }
        }
        return ~lo;  // value not present
    }

 

就是一个简单的二分查找算法,如果找到key就返回key的位置,如果找不到就返回key应该插入位置的取反。二分查找是SparseArray的核心算法,可以快速查找到key的位置。

[java] view
plaincopy

再回到put方法。在对key进行二分查找之后,如果key存在则直接替换掉相应的value,如果key不存在则在对应的位置插入key和value。

 

看到这里可能会有人迷糊了:中间那两个莫名其妙的if是干嘛的呢?好像删掉它们也不会有什么问题啊?这里就涉及到了SparseArray的一个巧妙的优化。我们知道,对数组进行插入和删除操作的代价是非常大的,例如在数组中间删除一个元素,那么这个元素后面的所有元素都要向前移动一个位置,如果删除操作多了,会极大的降低性能。

  1. public SparseArray() {  
  2.     this(10);  
  3. }  
  4.   
  5. public SparseArray(int initialCapacity) {  
  6.     initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);  
  7.   
  8.     mKeys = new int[initialCapacity];  
  9.     mValues = new Object[initialCapacity];  
  10.     mSize = 0;  
  11. }  

那么SparseArray的删除操作是怎么做的呢?来看一下delete方法:

再来看看它对数据的“增删改查”。

    private static final Object DELETED = new Object();

    ……

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

        if (i >= 0) {
            if (mValues[i] != DELETED) {
                mValues[i] = DELETED;
                mGarbage = true;
            }
        }
    }

它有两个方法可以添加键值对:

首先还是用二分查找找到要删除key在数组中的位置,查找到之后,并不立即删除这个元素,而是将相应的value标记为DELETED。这样如果之后有插入的key和这个删除掉的key相同时,直接替换掉value,这样就省去了一次删除和一次插入操作,提升了性能。在执行垃圾回收gc方法时,会一次性将所有标记为DELETED的元素全部删除,使原本要执行多次的删除操作减少到了一次:

 

    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 != DELETED) {
                if (i != o) {
                    keys[o] = keys[i];
                    values[o] = val;
                    values[i] = null;
                }

                o++;
            }
        }

        mGarbage = false;
        mSize = o;
    }

[java] view
plaincopy

看到这里,你应该不会再对put里那两个奇怪的if感到困惑了。再看一下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];
        }
    }
  1. public void put(int key, E value) {}  
  2. public void append(int key, E value){}  

很简单没有什么难点了

有四个方法可以执行删除操作:

要注意的一点是,由于SparseArray使用了二分查找,并且每次插入/删除等操作时都需要查找一次,所以在数据量大的时候,虽然节省了内存,但效率肯定是不如HashMap的。这时候的性能提升就很不明显了。

 

所以,使用SparseArray替换HashMap适合于以下两个条件:
1.key为int类型。(long类型也可以,使用LongSparseArray)
2.数据量不大。(千级左右)

[java] view
plaincopy

ArrayMap
相对于SparseArray,ArrayMap不限制key的类型,任何的HashMap都可以用ArrayMap替换。ArrayMap的内部存储方式依然是两个数组:

 

    int[] mHashes;
    Object[] mArray;
  1. public void delete(int key) {}  
  2. public void remove(int key) {} //直接调用的delete(int key)  
  3. public void removeAt(int index){}  
  4. public void clear(){}  

不过不同的是,ArrayMap的key和value全部存储在mArray数组中。存储形式可以表示为:[key1,
value1, key2, value2, key3, value3……]
那么mHashes数组中存储的自然就是每一个元素的hash值,查找元素时,先计算key转换过后的hash值,在mHashes数组中找到对应的hash值的位置,然后就可以在mArray数组中找到对应的key和value了。

修改数据起初以为只有setValueAt(int index, E
value)可以修改数据,但后来发现put(int key, E
value)也可以修改数据,我们查看put(int key, E
value)的源码可知,在put数据之前,会先查找要put的数据是否已经存在,如果存在就是修改,不存在就添加。

ArrayMap在性能上优于HashMap的原因有两点:

[java] view
plaincopy

1.和SparseArray一样,由于使用了两个数组存储数据,不再需要额外创建Entry对象,因此节省了内存空间。

 

2.扩容时,HashMap会重新new一个长度为2倍的容器返回。而ArrayMap则是调用System.arraycopy方法copy数据,减少了内存开销。

  1. public void put(int key, E value) {  
  2.     int i = binarySearch(mKeys, 0, mSize, key);  
  3.   
  4.     if (i >= 0) {  
  5.         mValues[i] = value;  
  6.     } else {  
  7.         i = ~i;  
  8.   
  9.         if (i < mSize && mValues[i] == DELETED) {  
  10.             mKeys[i] = key;  
  11.             mValues[i] = value;  
  12.             return;  
  13.         }  
  14.   
  15.         if (mGarbage && mSize >= mKeys.length) {  
  16.             gc();  
  17.   
  18.             // Search again because indices may have changed.  
  19.             i = ~binarySearch(mKeys, 0, mSize, key);  
  20.         }  
  21.         …………  

ArrayMap在mHashes数组中查找hash值时,同样用的是二分查找,所以在数据量较大时效率较低。因此ArrayMap一样适合于在数据量不大时使用。

 

总结
综上所述,在数据量在千级或千级以内时,使用SparseArray和ArrayMap可以减少内存的消耗,提升性能。其中,在key值为int或long型时,使用SparseArray(LongSparseArray);key值为其他对象时,使用ArrayMap。

 所以,修改数据实际也有两种方法:

[java] view
plaincopy

 

  1. public void put(int key, E value)  
  2. public void setValueAt(int index, E value)  

最后再来看看如何查找数据。有两个方法可以查询取值:

 

[java] view
plaincopy

 

  1. public E get(int key)  
  2. public E get(int key, E valueIfKeyNotFound)  

其中get(int key)也只是调用了 get(int key,E
valueIfKeyNotFound),最后一个从传参的变量名就能看出,传入的是找不到的时候返回的值.get(int
key)当找不到的时候,默认返回null。

查看第几个位置的键:

[java] view
plaincopy

 

  1. public int keyAt(int index)  

[java] view
plaincopy

 

  1.    

有一点需要注意的是,查看键所在位置,由于是采用二分法查找键的位置,所以找不到时返回小于0的数值,而不是返回-1。返回的负值是表示它在找不到时所在的位置。

查看第几个位置的值:

[java] view
plaincopy

 

  1. public E valueAt(int index)  

[java] view
plaincopy

 

  1.    

查看值所在位置,没有的话返回-1:

 

1 public int indexOfValue(E value)

最后,发现其核心就是折半查找函数(binarySearch),算法设计的很不错。

 

1 private static int binarySearch(int[] a,int start, int len, intkey) {
2     inthigh = start + len, low = start - 1, guess;
3  
4     while(high - low > 1) {
5         guess = (high + low) /2;
6  
7         if(a[guess] < key)
8             low = guess;
9         else
10             high = guess;
11     }
12  
13     if(high == start + len)
14         return~(start + len);
15     elseif (a[high] == key)
16         returnhigh;
17     else
18         return~high;
19 }

相应的也有SparseBooleanArray,用来取代HashMap<Integer,
Boolean>,SparseIntArray用来取代HashMap<Integer,
Integer>,大家有兴趣的可以研究。

总结:SparseArray是android里为<Interger,Object>这样的Hashmap而专门写的类,目的是提高效率,其核心是折半查找函数(binarySearch)。在Android中,当我们需要定义

 

1 HashMap<Integer, E> hashMap = new HashMap<Integer, E>();

时,我们可以使用如下的方式来取得更好的性能。

 

1 SparseArray<E> sparseArray = new SparseArray<E>();

发表评论

电子邮件地址不会被公开。 必填项已用*标注