Android SparseArray 源码详解

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

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

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。

先给一个初始空间的大小,默认的是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的介绍:

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

/**
 * 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.
 */

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

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

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避免了装箱的这个动作,从而提升了性能。

这个方法很简单,就是把元素重新排放,如果之前有删除的,就把后面的挪到前面,删除之后就会标注为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;

我们再来看一下上面提到的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的具体实现和常用方法:

这就是二分法查找,前提是数组必须是排序好的并且是升序排列,原理就是通过循环用当前的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;
    }

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

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

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

    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是否存在。看一下这个方法的源码:

    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的位置。