深入分析Android系统中SparseArray的源码

前言
昨晚想在Android应用中增加一个int映射到String的字典表，使用HashMap实现的时候，Eclipse给出了一个警告，昨晚项目上线紧张，我直接给忽略了，今天看了一下具体的Eclipse提示如下：

  Use new SparseArray<String> (...) instead for better performance

这个警告的意思是使用SparseArray来替代，以获取更好的性能。

源码
因为SparseArray整体代码比较简单，先把源码展示出来，然后再分析为什么使用SparseArray会比使用HashMap有更好的性能。

public class SparseArray<E> implements Cloneable {
    private static final Object DELETED = new Object();
    private boolean mGarbage = false; 

    private int[] mKeys;
    private Object[] mValues;
    private int mSize; 

    /**
     * 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) {
      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;
    } 

    @Override
    @SuppressWarnings("unchecked")
    public SparseArray<E> clone() {
      SparseArray<E> clone = null;
      try {
        clone = (SparseArray<E>) 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 <code>null</code>
     * if no such mapping has been made.
     */
    public E get(int key) {
      return get(key, null);
    } 

    /**
     * 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];
      }
    } 

    /**
     * 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) {
        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) {
            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);
        } 

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

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

    /**
     * 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 <code>0...size()-1</code>, returns
     * the key from the <code>index</code>th key-value mapping that this
     * SparseArray stores.
     *
     * <p>The keys corresponding to indices in ascending order are guaranteed to
     * be in ascending order, e.g., <code>keyAt(0)</code> will return the
     * smallest key and <code>keyAt(size()-1)</code> will return the largest
     * key.</p>
     */
    public int keyAt(int index) {
      if (mGarbage) {
        gc();
      } 

      return mKeys[index];
    } 

    /**
     * Given an index in the range <code>0...size()-1</code>, returns
     * the value from the <code>index</code>th key-value mapping that this
     * SparseArray stores.
     *
     * <p>The values corresponding to indices in ascending order are guaranteed
     * to be associated with keys in ascending order, e.g.,
     * <code>valueAt(0)</code> will return the value associated with the
     * smallest key and <code>valueAt(size()-1)</code> will return the value
     * associated with the largest key.</p>
     */
    @SuppressWarnings("unchecked")
    public E valueAt(int index) {
      if (mGarbage) {
        gc();
      } 

      return (E) mValues[index];
    } 

    /**
     * Given an index in the range <code>0...size()-1</code>, sets a new
     * value for the <code>index</code>th key-value mapping that this
     * SparseArray stores.
     */
    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.
     */
    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.
     * <p>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.
     * <p>Note also that unlike most collections' {@code indexOf} methods,
     * this method compares values using {@code ==} rather than {@code equals}.
     */
    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}
     *
     * <p>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; i<mSize; i++) {
        if (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();
    }
  }

首先，看一下SparseArray的构造函数：

 /**
   * 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) {
    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;
  }

从构造方法可以看出，这里也是预先设置了容器的大小，默认大小为10。

再来看一下添加数据操作：

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

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

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

再看查数据的方法：

  /**
   * Gets the Object mapped from the specified key, or <code>null</code>
   * if no such mapping has been made.
   */
  public E get(int key) {
    return get(key, null);
  } 

  /**
   * 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];
    }
  }

可以看到，在put数据和get数据的过程中，都统一调用了一个二分查找算法，其实这也就是SparseArray能够提升效率的核心。

 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
  }

个人认为（lo + hi） >>> 1的方法有些怪异，直接用 lo + (hi - lo) / 2更好一些。