Android-S parseAray

SparseAray
Android APIでは、GoogleはHashMapに代わるデータ構造を提供しています.このデータ構造はSparsearyです.
まず、HashMapを振り返ってみると、HashMapは配列＋一方向チェーンからなる容器で、デフォルトサイズは16で、putのたびにindexを計算して配列に入れるという問題は、メモリ内の配列要素が連続ではなく、ハッシュであるため、メモリが無駄になってしまうということです.
Sparsearrayはこの問題を解決するために生まれました.
 
まず、Sparsearrayのメンバー変数を見てみます.

public class SparseArray implements Cloneable {
    private static final Object DELETED = new Object();
    private boolean mGarbage = false;

    private int[] mKeys;       //     key
    private Object[] mValues;  //     value
    private int mSize;         //    

SparseArayには、2つの配列があり、1つの配列はkeyを保存し、1つはvalueを保存します.
更にSparsearrayの構造関数を見てください.

    public SparseArray() {
        this(10);    //      ，     10
    }

    public SparseArray(int initialCapacity) {
        if (initialCapacity == 0) {
            mKeys = EmptyArray.INT;
            mValues = EmptyArray.OBJECT;
        } else {
            //         ，  value
            mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
            mKeys = new int[mValues.length];    //  value，       key  
        }
        mSize = 0;
    }

 
私達はputの方法を見てみます.

    public void put(int key, E value) {
        //      ，     index
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i >= 0) {
            //      ，       value
            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。
                gc();

                // Search again because indices may have changed.
                //     index
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }

            //    
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            mSize++;
        }
    }

getの方法を見てください

    public E get(int key, E valueIfKeyNotFound) {
        //    index
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        //     key      ，      valueIfKeyNotFound
        if (i < 0 || mValues[i] == DELETED) {
            return valueIfKeyNotFound;
        } else {
            //       
            return (E) mValues[i];
        }
    }

deleteの方法を見てください.

    public void delete(int key) {
        //      index
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i >= 0) {
            if (mValues[i] != DELETED) {
                //      ，  GC
                mValues[i] = DELETED;
                mGarbage = true;
            }
        }
    }

 まとめ:
Sparsearrayは2つの配列からなるキーの値が容器に対して、keyのデータタイプはintしかないので、毎回2点検索でkeyを探しています.