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

  Use new SparseArray<String> (...) instead for better performance 

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();     }   } 

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

 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   }