SpareArray

1.SpareArrayと普通のHanshMapの違いは何ですか?
SpareArrayは、整数とオブジェクトのマッピングテーブルで、整数とオブジェクトのマッピングの場合、HashMapよりも効率的です.整数キーを使用すると自動梱包プロセスが省略され、各キーと値の関係も追加のentityオブジェクトには使用されません.spareArryは2つの配列で実現されるマッピング関係です.

    private int[] mKeys;
    private Object[] mValues;

データ構造は配列を使用してマッピング関係を確立します.二分検索を使用して各valueを探します.大量のデータ構造を格納するのに適していません.従来のhashMapよりも遅く、データの追加と削除には二分検索が必要です.小規模なデータではパフォーマンスが優れています.

342    private static int binarySearch(int[] a, int start, int len, int key) {
343        int high = start + len, low = start - 1, guess;
344
345        while (high - low > 1) {
346            guess = (high + low) / 2;
347
348            if (a[guess] < key)
349                low = guess;
350            else
351                high = guess;
352        }
353
354        if (high == start + len)
355            return ~(start + len);
356        else if (a[high] == key)
357            return high;
358        else
359            return ~high;
360    }

 
パフォーマンスを向上させるために、データを削除する際に、すぐにデータを削除するのではなく、データを削除状態としてマークし、後で再利用しやすくし、ゴミ回収時に削除したエントリを圧縮します.ごみ回収は、データの拡張とspareArrayサイズの取得時に実行されます.

90    public void delete(int key) {
91        int i = binarySearch(mKeys, 0, mSize, key);
92
93        if (i >= 0) {
94            if (mValues[i] != DELETED) {
95                mValues[i] = DELETED;
96                mGarbage = true;
97            }
98        }
99    }

108    private void gc() {
109        // Log.e("SparseArray", "gc start with " + mSize);
110
111        int n = mSize;
112        int o = 0;
113        int[] keys = mKeys;
114        Object[] values = mValues;
115
116        for (int i = 0; i < n; i++) {
117            Object val = values[i];
118
119            if (val != DELETED) {
120                if (i != o) {
121                    keys[o] = keys[i];
122                    values[o] = val;
123                }
124
125                o++;
126            }
127        }
128
129        mGarbage = false;
130        mSize = o;
131
132        // Log.e("SparseArray", "gc end with " + mSize);
133    }
191    public int size() {
192        if (mGarbage) {
193            gc();
194        }
195
196        return mSize;
197    }

SpareArrayの軽量レベルで効率的なデータ構造で、主にintタイプをキーとするキー値ペアを保存するために使用されています.データ量が少ない場合よりも効率的です.HashMapとは少し違う点があります
-SpareArray内部では配列を使用してキー値ペアを保存し、キーは整数である必要があります.HashMapはentityを使用してキー値ペアを保存し、配列にチェーンテーブルを付けた(赤と黒の木)方式でentityを保存します.キーと値のタイプには必要ありません.
-SpareArrayはデータを挿入・削除する際に二分検索方式でデータを検索し、時間が複雑でO(logn)と読み、hashMapの検索時間の複雑さは理想的にはO(1)であり、
-SpareArrayは削除操作を最適化し、データを削除すると、データは削除状態としてマークされ、メモリは回収されず、拡張や新規データの場合にのみメモリが回収されます.