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

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

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; 
   
    /** 
     * 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 clone() { 
      SparseArray clOne= null; 
      try { 
        clOne= (SparseArray) 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 null 
     * 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 = 0) { 
        mValues[i] = value; 
      } else { 
        i = ~i; 
   
        if (i = 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 0...size()-1, returns 
     * the key from the indexth key-value mapping that this 
     * SparseArray stores. 
     * 
     * 
The keys corresponding to indices in ascending order are guaranteed to 
     * be in ascending order, e.g., keyAt(0) will return the 
     * smallest key and keyAt(size()-1) will return the largest 
     * key.
 
     */ 
    public int keyAt(int index) { 
      if (mGarbage) { 
        gc(); 
      } 
   
      return mKeys[index]; 
    } 
   
    /** 
     * Given an index in the range 0...size()-1, returns 
     * the value from the indexth key-value mapping that this 
     * SparseArray stores. 
     * 
     * 
The values corresponding to indices in ascending order are guaranteed 
     * to be associated with keys in ascending order, e.g., 
     * valueAt(0) will return the value associated with the 
     * smallest key and valueAt(size()-1) will return the value 
     * associated with the largest key.
 
     */ 
    @SuppressWarnings("unchecked") 
    public E valueAt(int index) { 
      if (mGarbage) { 
        gc(); 
      } 
   
      return (E) mValues[index]; 
    } 
   
    /** 
     * Given an index in the range 0...size()-1, sets a new 
     * value for the indexth 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. 
     * 
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. 
     * 
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 = 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} 
     * 
     * 
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 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(); 
    } 
  } 

 /** 
   * 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; 
  } 

  /** 
   * 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 = 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 null 
   * 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]; 
    } 
  } 

 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) { 
        hi = mid - 1; 
      } else { 
        return mid; // value found 
      } 
    } 
    return ~lo; // value not present 
  }