最近发现一个针对HashMap的一个提示：

查了 一下资料，得知android推荐用SparseArray，她的效率更高。
原来在存储数据的时候，是采用了二分法方式。
看看源码做了什么? frameworks\base\core\java\android\util目录下

/* * Copyright (C) 2006 The Android Open Source Project * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * *      http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */package android.util;import com.android.internal.util.ArrayUtils;/** * SparseArrays map integers to Objects.  Unlike a normal array of Objects, * there can be gaps in the indices.  It is intended to be more memory efficient * than using a HashMap to map Integers to Objects, both because it avoids * auto-boxing keys and its data structure doesn't rely on an extra entry object * for each mapping. * * 
Note that this container keeps its mappings in an array data structure, * using a binary search to find keys.  The implementation is not intended to be appropriate for * data structures * that may contain large numbers of items.  It is generally slower than a traditional * HashMap, since lookups require a binary search and adds and removes require inserting * and deleting entries in the array.  For containers holding up to hundreds of items, * the performance difference is not significant, less than 50%.
 * * 
To help with performance, the container includes an optimization when removing * keys: instead of compacting its array immediately, it leaves the removed entry marked * as deleted.  The entry can then be re-used for the same key, or compacted later in * a single garbage collection step of all removed entries.  This garbage collection will * need to be performed at any time the array needs to be grown or the the map size or * entry values are retrieved.
 * * 
It is possible to iterate over the items in this container using * {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using * keyAt(int) with ascending values of the index will return the * keys in ascending order, or the values corresponding to the keys in ascending * order in the case of valueAt(int).
 */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 < 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 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 < 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}     *     * 
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();    }}

package android.util;class ContainerHelpers {    static final boolean[] EMPTY_BOOLEANS = new boolean[0];    static final int[] EMPTY_INTS = new int[0];    static final long[] EMPTY_LONGS = new long[0];    static final Object[] EMPTY_OBJECTS = new Object[0];    // This is Arrays.binarySearch(), but doesn't do any argument validation.    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    }    static int binarySearch(long[] array, int size, long value) {        int lo = 0;        int hi = size - 1;        while (lo <= hi) {            final int mid = (lo + hi) >>> 1;            final long 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    }}