前言
昨晚想在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, eg, <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, eg, * <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更好一些。