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