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