SparseArraysソース分析

Android開発ではIntegerをkeyとするmapを使用する場合はSparseArraysを優先します.APIドキュメントには、SparseArraysを使用するとメモリをより効率的に使用できることが示されています.ソースコードを読むことで,SparseArraysの実装では自動箱詰めメカニズムを回避し,entryを捨ててkeyとvalueのマッチングを保存するのではなく,keyとvalueをそれぞれ2つの配列で保存することが分かる.しかし、有利には弊害があり、このような実現方式はHashMapの検索上の効率を放棄せざるを得ない.SparseArraysは2つの検索で検索を実現しているので、HashMapの検索速度には及ばない.
    またkeyもvalueも配列で保存されているため,別の問題が生じる.これが配列が増加したり削除したりするときに比較的効果的ではないことはよく知られているはずです.だからSparseArraysはこの問題を避けるために、私から見れば巧みなメカニズムを使っています.実装方法は,削除の際に配列の削除操作を直ちに実行するのではなく,削除するkey対のvalueをDELETED,宣言文をprivate static final Object DELETED=new Object()とする.同時に、クラスにはグローバル変数boolean mGarbage=falseがあります.delete操作またはremove操作を実行すると、変数はtrueに設定されます.クエリーや追加などの操作を行うと、mGarbageの値に基づいて本格的な削除操作が実行されます.これにより,配列の削除操作が頻繁に行われることが回避され,効率が大幅に向上する.
     最後に説明したいのは、SparseArraysが配列がいっぱいになった場合に自動的に容量を拡張し、メモリの使用の無駄を回避することです.次のコードに示します.

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