Android SparseArray与HashMap与ArrayMap的性能差别

google官方推荐，当使用HashMap时，Key值为整数类型时，建议使用SparseArray的效率更高

下面我们来见识一下SparseArray、HashMap、ArrayMap的性能区别，首先我们先看一下google官方推荐的SparseArray，SparseArray是Android的API，JDK中没有的该类。

SparseArray的源码分析：

当我们在Android中使用HashMap时，我们会看到编译器会弹如下提示：

Android SparseArray与HashMap与ArrayMap的性能差别_第1张图片

大概意思就是建议我们使用SparseArray来代替HashMap

SparseArray源码：（直接在代码中讲解）

public class SparseArray<E> implements Cloneable {      //用于删除元素的时候使用，当删除某个元素，我们需要将int-values中的values赋值为DELETED    private static final Object DELETED = new Object();      //判断此时是否需要垃圾回收（也就是数据是否需要重新整理，将数组中mValues值为DELETED的int-values从数组中删除掉）    private boolean mGarbage = false;      //存储索引集合.    private int[] mKeys;      //存储对象集合.    private Object[] mValues;      //存储的键值对总数.    private int mSize;      /**      * 创建默认大小为10     * Creates a new SparseArray containing no mappings.      */      public SparseArray() {          this(10);      }      /**      * 初始化键值对     * Creates a new SparseArray containing no mappings that will not      * require any additional memory allocation to store the specified      * number of mappings.  If you supply an initial capacity of 0, the      * sparse array will be initialized with a light-weight representation      * not requiring any additional array allocations.      */      public SparseArray(int initialCapacity) {          //如果传入的值是0，则键值对都是empty，否则按照传入的值申请最初的数组大小        if (initialCapacity == 0) {              mKeys = ContainerHelpers.EMPTY_INTS;              mValues = ContainerHelpers.EMPTY_OBJECTS;          } else {              initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);              mKeys = new int[initialCapacity];              mValues = new Object[initialCapacity];          }          //键值对的总个数为0        mSize = 0;      }      //深拷贝，创建新的空间存储这些键值对    @Override      @SuppressWarnings("unchecked")      public SparseArray clone() {          SparseArray clone = null;          try {              clone = (SparseArray) super.clone();              clone.mKeys = mKeys.clone();              clone.mValues = mValues.clone();          } catch (CloneNotSupportedException cnse) {              /* ignore */          }          return clone;      }      //通过键获取值    /**      * Gets the Object mapped from the specified key, or null      * if no such mapping has been made.      */      public E get(int key) {          return get(key, null);      }      //通过键获取值，如果没有则返回valueIfKeyNotFound    /**      * Gets the Object mapped from the specified key, or the specified Object      * if no such mapping has been made.      */      @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];          }      }      //删除第key个位置的数    /**      * Removes the mapping from the specified key, if there was any.      */      public void delete(int key) {          //二分查找        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);          if (i >= 0) {              //确定删除的数，将其置为DELETED，然后将垃圾回收置为true            if (mValues[i] != DELETED) {                  mValues[i] = DELETED;                  mGarbage = true;              }          }      }      /**      * Alias for {@link #delete(int)}.      */      public void remove(int key) {          delete(key);      }      /**      * Removes the mapping at the specified index.      */      public void removeAt(int index) {          if (mValues[index] != DELETED) {              mValues[index] = DELETED;              mGarbage = true;          }      }      /**      * Remove a range of mappings as a batch.      *      * @param index Index to begin at      * @param size Number of mappings to remove      */      public void removeAtRange(int index, int size) {          final int end = Math.min(mSize, index + size);          for (int i = index; i < end; i++) {              removeAt(i);          }      }      //垃圾回收方法    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) {                      //最开始我被这儿给绕了一道                    //Java中的除基本类型以外的数据使用“=”都是引用(如果没有重写的话)                    //所以这儿可以通过这种方式改变对象数组的值                    keys[o] = keys[i];                      values[o] = val;                      values[i] = null;                  }                  o++;              }          }          mGarbage = false;          mSize = o;          // Log.e("SparseArray", "gc end with " + mSize);      }      //向键值对中放值    /**      * 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) {              mValues[i] = value;          } else {              i = ~i;              //如果这个键值插入的地方已经被删除了，我们可以直接给他赋值，否则查询出的位置的元素没有被删除            if (i < mSize && mValues[i] == DELETED) {                  mKeys[i] = key;                  mValues[i] = value;                  return;              }              //判断数组的大小是否大于等于数组初始化的大小，如果大并且其中有垃圾则调用垃圾回收方法            if (mGarbage && mSize >= mKeys.length) {                  gc();                  //再次二分查找，取出键值在数组的位置                // Search again because indices may have changed.                  i = -ContainerHelpers.binarySearch(mKeys, mSize, key);              }              //如果数组的大小依旧大于等于初始化的大小，则申请一段mSize+1大小的数组            if (mSize >= mKeys.length) {                  int n = ArrayUtils.idealIntArraySize(mSize + 1);                  int[] nkeys = new int[n];                  Object[] nvalues = new Object[n];                  //表示将数组mKeys从0开始复制到数组nkeys从0开始，复制的长度为mKeys的长度                // 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            if (mSize - i != 0) {                  // Log.e("SparseArray", "move " + (mSize - i));                  //将数组mKeys从i开始复制到mKeys从i+1开始，复制的长度为数组的长度减去当前插入的位置                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++;          }      }      /**      * Returns the number of key-value mappings that this SparseArray      * currently stores.      */       //返回数据的大小    public int size() {          if (mGarbage) {              gc();          }          return mSize;      }      /**      * Given an index in the range 0...size()-1, returns      * the key from the indexth key-value mapping that this      * SparseArray stores.      *      * The keys corresponding to indices in ascending order are guaranteed to      * be in ascending order, e.g., keyAt(0) will return the      * smallest key and keyAt(size()-1) will return the largest      * key.
      */       //返回当前第index个值的键是多少    public int keyAt(int index) {          if (mGarbage) {              gc();          }          return mKeys[index];      }      /**      * Given an index in the range 0...size()-1, returns      * the value from the indexth key-value mapping that this      * SparseArray stores.      *      * The values corresponding to indices in ascending order are guaranteed      * to be associated with keys in ascending order, e.g.,      * valueAt(0) will return the value associated with the      * smallest key and valueAt(size()-1) will return the value      * associated with the largest key.
      */       //返回当前index位置的值是多少    @SuppressWarnings("unchecked")      public E valueAt(int index) {          if (mGarbage) {              gc();          }          return (E) mValues[index];      }      /**      * Given an index in the range 0...size()-1, sets a new      * value for the indexth key-value mapping that this      * SparseArray stores.      */       //给index位置的值设置为value    public void setValueAt(int index, E value) {          if (mGarbage) {              gc();          }          mValues[index] = value;      }      /**      * Returns the index for which {@link #keyAt} would return the      * specified key, or a negative number if the specified      * key is not mapped.      */       //返回键为key的位置    public int indexOfKey(int key) {          if (mGarbage) {              gc();          }          return ContainerHelpers.binarySearch(mKeys, mSize, key);      }      /**      * Returns an index for which {@link #valueAt} would return the      * specified key, or a negative number if no keys map to the      * specified value.      * Beware that this is a linear search, unlike lookups by key,      * and that multiple keys can map to the same value and this will      * find only one of them.      * 
Note also that unlike most collections' {@code indexOf} methods,      * this method compares values using {@code ==} rather than {@code equals}.      */       //返回值为value的位置    public int indexOfValue(E value) {          if (mGarbage) {              gc();          }          for (int i = 0; i < mSize; i++)              if (mValues[i] == value)                  return i;          return -1;      }      /**      * Removes all key-value mappings from this SparseArray.      */       //清除当前键值对    public void clear() {          int n = mSize;          Object[] values = mValues;          for (int i = 0; i < n; i++) {              values[i] = null;          }          mSize = 0;          mGarbage = false;      }      /**      * 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;      }      /**      * {@inheritDoc}      *      * This implementation composes a string by iterating over its mappings. If      * this map contains itself as a value, the string "(this Map)"      * will appear in its place.      */       //返回键值对    @Override      public String toString() {          if (size() <= 0) {              return "{}";          }          StringBuilder buffer = new StringBuilder(mSize * 28);          buffer.append('{');          for (int i=0; iif (i > 0) {                  buffer.append(", ");              }              int key = keyAt(i);              buffer.append(key);              buffer.append('=');              Object value = valueAt(i);              if (value != this) {                  buffer.append(value);              } else {                  buffer.append("(this Map)");              }          }          buffer.append('}');          return buffer.toString();      }  }

SparseArry结构图解：

Android SparseArray与HashMap与ArrayMap的性能差别_第2张图片

SparseArray只能存储当键为int的键值对，通过源码我们可以看到这儿键是int而不是Integer，所以SparseArray提高效率的方式是去箱的操作，因为键是int型数据，所以就不需要hash值的方式来存储数据，插入和查询都是通过二分查找的方式进行，插入数据时可能会存在大量的数据搬移。但是它避免了装箱，所以这时就要看数据量的大小来对比时间的快慢，如果数据少，即使数据搬移也不会很多，所以效率上SparseArray比HashMap要好，空间上装箱过后的Integer要比int占的空间要大，所以空间效率上SparseArray要比HashMap好！

HashMap结构图解：

Android SparseArray与HashMap与ArrayMap的性能差别_第3张图片

HashMap的数据结构：

static class HashMapEntry implements Entry {        //键    final K key;        //值    V value;     //键生成的hash值    final int hash;       //如果Hash值一样，则它下一个键值对     HashMapEntry next;}

从数据结构中我们可以看出首先对key值求Hash值，如果该Hash值在Hash数组中不存在，则添加进去，如果存在，则跟着Hash值的链表在尾部添加上这个键值对，在时间效率方面，使用Hash算法，插入和查找的操作都很快，每个数组后面一般不会存在很长的链表，所以不考虑空间利用率，HashMap的效率是非常高的

ArrayMap的结构图解

Android SparseArray与HashMap与ArrayMap的性能差别_第4张图片

当插入时，根据key的hashcode()方法得到hash值，计算出在mArrays的index位置，然后利用二分查找找到对应的位置进行插入，当出现哈希冲突时，会在index的相邻位置插入。
空间角度考虑，ArrayMap每存储一条信息，需要保存一个hash值，一个key值，一个value值。对比下HashMap 粗略的看，只是减少了一个指向下一个entity的指针。
时间效率上看，插入和查找的时候因为都用的二分法，查找的时候应该是没有hash查找快，插入的时候呢，如果顺序插入的话效率肯定高，但如果是随机插入，肯定会涉及到大量的数组搬移，数据量大，肯定不行，再想一下，如果是不凑巧，每次插入的hash值都比上一次的小，那就得次次搬移，效率一下就扛不住了的感脚。

参考资料：

HashMap，ArrayMap，SparseArray源码分析及性能对比
Android内存优化（使用SparseArray和ArrayMap代替HashMap）
Android 之Map容器替换 SparseArray，ArrayMap，ArraySet
Android学习笔记之性能优化SparseArray
SparseArray 的使用及实现原理
SparseArray源码解析
Android SparseArray源码分析

参考资料：

更多相关文章

随机推荐