Sparsearrayソース分析

6353 ワード

SparseArayは、Android.utilパケットで提供されるクラスであり、オブジェクトに対する整数マッピングを確立するために、HashMapよりも性能が優れています.これは自動箱詰めを回避し、内部データ構造が追加のエンティティオブジェクトに依存しないためです.二分割検索を使ってキーを探すので、数が多い(数百以上)場合には不向きです.
    //           
    private static final Object DELETED = new Object();
    //      gc
    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 = EmptyArray.INT;
            mValues = EmptyArray.OBJECT;
        } else {
            mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
            mKeys = new int[mValues.length];
        }
        mSize = 0;
    }
構造関数デフォルトの容量は10です.
    /**
     * 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);
            }

            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            mSize++;
        }
    }
上は増です.ついでにContinerHelpers類のbinarySearch方法のコードを添付します.
    // 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
    }
これはかなり標準的な二分検索で実現されます.final int mid=(lo+hi)>>1,ここでは符号なしで右へ移動します>>オーバーフローを回避します.指定された値が見つからない場合は、loの逆の値を返します.負の値です.したがって、put方法では、検索が成功したかどうかは、戻り値が0以上であるかどうかを判定することができる.put方法を振り返ってみます.二点検索が成功すれば、直接に対応値を置換します.そうでなければ、iをビットごとに逆にして負の数ではないことを得て、対応する値が削除されたかどうかを見て、はい、対応するキーの値を置換します.そうでなければ、gcが必要であればgc、新しいキーの値を配列に挿入します.GroweingArayUtilsのinsert方法では、配列がいっぱいになったら、拡大容量は2倍になります.
    /**
     * 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();
        }

        mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
        mValues = GrowingArrayUtils.append(mValues, mSize, value);
        mSize++;
    }
増加のもう一つの方法.既存のキーよりも新しいキーが大きい場合は、二分検索なしで、直接末尾に挿入します.
    /**
     * Alias for {@link #delete(int)}.
     */
    public void remove(int key) {
        delete(key);
    }

    /**
     * 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;
            }
        }
    }
削除する.(同じ機能を無理やりに2つの方法の入り口に与えるのはちょっと気まずいです.)2つの検索が成功していて、対応値が削除されていない場合は、その値を削除して記録します.ここの削除は、すぐに配列要素を移動するのではなく、オブジェクトマークを削除し、同じキーを挿入するときに再使用するか、または後にgcが必要なときに配列を調整します.これは性能最適化を考慮した方法である.
    /**
     * 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];
        }
    }
調べます.二分検索を使います.
     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);
    }
gcメソッド.値配列を巡回して、削除されたオブジェクトを空にして、前へキーを移動します.
    /**
     * Returns the number of key-value mappings that this SparseArray
     * currently stores.
     */
    public int size() {
        if (mGarbage) {
            gc();
        }

        return mSize;
    }
gc前のmSizeは正確な記憶サイズではないので、sizeを取得するにはまずgcを行う必要があります.