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を行う必要があります.