深入分析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更好一些。