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

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

  Use new SparseArray (...) instead for better performance 

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

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

public class SparseArray implements Cloneable { 
    private static final Object DELETED = new Object(); 
    private boolean mGarbage = false; 
   
    private int[] mKeys; 
    private Object[] mValues; 
    private int mSize; 
   
     
    public SparseArray() { 
      this(10); 
    } 
   
     
    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 clone() { 
      SparseArray clone = null; 
      try { 
 clone = (SparseArray) super.clone(); 
 clone.mKeys = mKeys.clone(); 
 clone.mValues = mValues.clone(); 
      } catch (CloneNotSupportedException cnse) { 
  
      } 
      return clone; 
    } 
   
     
    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]; 
      } 
    } 
   
     
    public void delete(int key) { 
      int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 
   
      if (i >= 0) { 
 if (mValues[i] != DELETED) { 
   mValues[i] = DELETED; 
   mGarbage = true; 
 } 
      } 
    } 
   
     
    public void remove(int key) { 
      delete(key); 
    } 
   
     
    public void removeAt(int index) { 
      if (mValues[index] != DELETED) { 
 mValues[index] = DELETED; 
 mGarbage = true; 
      } 
    } 
   
     
    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); 
    } 
   
     
    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++; 
      } 
    } 
   
     
    public int size() { 
      if (mGarbage) { 
 gc(); 
      } 
   
      return mSize; 
    } 
   
     
    public int keyAt(int index) { 
      if (mGarbage) { 
 gc(); 
      } 
   
      return mKeys[index]; 
    } 
   
     
    @SuppressWarnings("unchecked") 
    public E valueAt(int index) { 
      if (mGarbage) { 
 gc(); 
      } 
   
      return (E) mValues[index]; 
    } 
   
     
    public void setValueAt(int index, E value) { 
      if (mGarbage) { 
 gc(); 
      } 
   
      mValues[index] = value; 
    } 
   
     
    public int indexOfKey(int key) { 
      if (mGarbage) { 
 gc(); 
      } 
   
      return ContainerHelpers.binarySearch(mKeys, mSize, key); 
    } 
   
     
    public int indexOfValue(E value) { 
      if (mGarbage) { 
 gc(); 
      } 
   
      for (int i = 0; i < mSize; i++) 
 if (mValues[i] == value) 
   return i; 
   
      return -1; 
    } 
   
     
    public void clear() { 
      int n = mSize; 
      Object[] values = mValues; 
   
      for (int i = 0; i < n; i++) { 
 values[i] = null; 
      } 
   
      mSize = 0; 
      mGarbage = false; 
    } 
   
     
    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; 
    } 
   
     
    @Override 
    public String toString() { 
      if (size() <= 0) { 
 return "{}"; 
      } 
   
      StringBuilder buffer = new StringBuilder(mSize * 28); 
      buffer.append('{'); 
      for (int i=0; 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的构造函数：

  
  public SparseArray() { 
    this(10); 
  } 
   
   
  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。

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

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

再看查数据的方法：

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

可以看到，在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更好一些。