SparseAray原理分析

概要
Googleは新しいデータ構造Sparsearrayを推奨します.
SparseAray類にはコメントがあります.

Sparsearys map integers to Objecs.Unike a normal array of Objecs,

there can be gaps in the indices.It is inted to be more memory efficient

than using a HashMap to map Integers to Object,both because it avoid

at-box ing keys and its data struct doesn't rely on an extra entry object

for each mapping.

この注釈の意味は、int配列を使用してkeyを保存することにより、HashMapにおける基本的なデータタイプが箱詰めされるステップを回避し、次に追加の構造体を使用せずに、単一の要素の保存コストが低下することを意味する.
作成方法

    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 = EmptyArray.INT;
            mValues = EmptyArray.OBJECT;
        } else {
            mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
            mKeys = new int[mValues.length];
        }
        mSize = 0;
    }

初期化SparseArayは単純に二つの配列を作成しただけで、一つはキーを保存するためのもので、一つは値を保存するためのものです.
put()

    /**
     * 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) {
        //          key         key，    
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        if (i >= 0) {
            //   i>=0          key，         
            mValues[i] = value;
        } else {
            //   ，     i   key       
            i = ~i;
            if (i < mSize && mValues[i] == DELETED) {
                //                ，          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);
            }

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

get()

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

get()のコードは比較的簡単で、二分割検索でkeyのインデックスを取得し、このインデックスでvalueを取得します.
remove()

    public void remove(int key) {
        delete(key);
    }

    public void delete(int key) {
        //    key   
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //     ，      value   DELETED
        if (i >= 0) {
            if (mValues[i] != DELETED) {
                mValues[i] = DELETED;
                //           
                mGarbage = true;
            }
        }
    }

締め括りをつける
利点:

は、基本的なデータタイプの箱詰め動作

を回避する.

は追加の構造体を必要とせず、単一の要素の保存コストは

より低い.

データ量が小さい場合、ランダムアクセスの効率が高い

.
短所:

挿入操作にはコピー配列が必要で、削除効率は

を低減する.

データ量が大きい場合、コピー配列のコストが大きく、gc()コストも大きいです.

データ量が大きいと、照会効率も著しく低下します.
Googleはまた、他の類似のデータ構造、SparseIntAray、SparseBooleanAray、SparseLongAray、ArayMapなどを提供しています.
参考:SparseArayの使用と実現原理