SparseArray原始碼來自：android-25/java/util/SparseArray
ArrayMap原始碼來自：25.3.1/support-compat-25.3.1/android/android.support.v4.util.ArrayMap
一、SparseArray實作原始碼學習
SparseArray采用時間換取空間的方式來提高手機App的運行效率，這也是其與HashMap的區別；HashMap通過空間換取時間，查找迅速；HashMap中當table陣列中內容達到總容量0.75時，則擴展為當前容量的兩倍，關于HashMap可查看HashMap實作原理學習)
- SparseArray的key為int，value為Object，
- 在Android中，資料長度小于千時，用于替換HashMap
- 相比與HashMap，其采用 時間換空間 的方式，使用更少的記憶體來提高手機APP的運行效率(HashMap中當table陣列中內容達到總容量0.75時，則擴展為當前容量的兩倍，關于HashMap可查看HashMap實作原理學習)
下邊對其原始碼進行簡單學習，
1、構造方法
// 構造方法
public SparseArray() {
this(10);
}
// 構造方法
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {
// key value各自為一個陣列，默認長度為10
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
mSize = 0;
}
ps：
SparseArray構造方法中，創建了兩個陣列mKeys、mValues分別存放int與Object，其默認長度為10
2、 put(int key, E value)
public void put(int key, E value) {
// 二分查找,key在mKeys串列中對應的index
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
// 如果找到，則直接賦值
if (i >= 0) {
mValues[i] = value;
}
// 找不到
else {
// binarySearch方法中，找不到時，i取了其非，這里再次取非，則非非則正
i = ~i;
// 如果該位置的資料正好被洗掉,則賦值
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
// 如果有資料被洗掉了，則gc
if (mGarbage && mSize >= mKeys.length) {
gc();
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
// 插入資料，增長mKeys與mValues串列
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
ps：
- 因為key為int,不存在hash沖突
- mKeys為有序串列，通過二分查找，找到要插入的key對應的index (這里相對于查找hash表應該算是費時間吧，但節省了記憶體，所以是 時間換取了空間)
- 通過二分查找到的index，將Value插入到mValues陣列的對應位置
3、get(int key)
// 通過key查找對應的value
public E get(int key) {
return get(key, null);
}
// 通過key查找對應的value
public E get(int key, E valueIfKeyNotFound) {
// mKeys陣列中采用二分查找，找到key對應的index
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
// 沒有找到，則回傳空
if (i < 0 || mValues[i] == DELETED) {
return valueIfKeyNotFound;
} else {
// 找到則回傳對應的value
return (E) mValues[i];
}
}
ps：
每次呼叫get，則需經過一次mKeys陣列的二分查找，因此mKeys陣列越大則二分查找的時間就越長，因此SparseArray在大量資料，千以上時，會效率較低
3、ContainerHelpers.binarySearch(mKeys, mSize, key)二分查找
// array為有序陣列
// size陣列中內容長度
// value要查找的值
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];
// 如果中間元素小于要查找元素，則midIndex賦值給 lo
if (midVal < value) {
lo = mid + 1;
}
// 如果中間元素大于要查找元素，則midIndex賦值給 hi
else if (midVal > value) {
hi = mid - 1;
}
// 找到則回傳
else {
return mid; // value found
}
}
// 找不到,則lo 取非
return ~lo; // value not present
}
二、android.support.v4.util.ArrayMap
ArrayMap和SparseArray有點類似；其中含有兩個陣列，一個是mHashes（key的hash值陣列，為一個有序陣列），另一個陣列存盤的是key和value，其中key和value是成對出現的，key存盤在陣列的偶數位上，value存盤在陣列的奇數位上，
1、構造方法
public SimpleArrayMap() {
// key的hash值陣列，為一個有序陣列
mHashes = ContainerHelpers.EMPTY_INTS;
// key 與 value陣列
mArray = ContainerHelpers.EMPTY_OBJECTS;
mSize = 0;
}
ps：
構造方法中初始化了兩個陣列mHashes、mArray，其中mHashes為key的Hash值對應的陣列
2、put(K key, V value)
public V put(K key, V value) {
// key 對應的hash值
final int hash;
// hash對應的mHashes串列的index
int index;
// key為空，hash為0
if (key == null) {
hash = 0;
index = indexOfNull();
}
//
else {
// 計算key的hashcode
hash = key.hashCode();
// 查找key對應mHashes中的index,大于0則找到了，否則為未找到
// 這里涉及到hash沖突,如果hash沖突，則在index的相鄰位置插入資料
index = indexOf(key, hash);
}
// 找到key對應mHashes中的index
if (index >= 0) {
// 取出基數位置原有的Value
index = (index<<1) + 1;
final V old = (V)mArray[index];
// 將新資料放到基數index位置
mArray[index] = value;
return old;
}
// indexOf中取了反，這里反反則正
index = ~index;
// 如果滿了就擴容
if (mSize >= mHashes.length) {
final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
: (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
// 擴容
allocArrays(n);
// 把原來的資料拷貝到擴容后的陣列中
if (mHashes.length > 0) {
if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
freeArrays(ohashes, oarray, mSize);
}
// 根據上面的二分法查找，如果index小于mSize，說明新的資料是插入到陣列之間index位置，插入之前需要把后面的移位
if (index < mSize) {
if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index)
+ " to " + (index+1));
System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);
System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
}
// 保存資料
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
mSize++;
return null;
}
// 根據key 與key的hash，查找key對應的index
int indexOf(Object key, int hash) {
final int N = mSize;
// Important fast case: if nothing is in here, nothing to look for.
if (N == 0) {
return ~0;
}
// 二分查找mHashes有序陣列，查找hash對應的index
int index = ContainerHelpers.binarySearch(mHashes, N, hash);
// 沒有找到
if (index < 0) {
return index;
}
// 偶數位為對應的key，則找到了
if (key.equals(mArray[index<<1])) {
return index;
}
// index之后查找
// 這里涉及到hash沖突,如果hash沖突，則在index的相鄰位置插入資料
// Search for a matching key after the index.
int end;
for (end = index + 1; end < N && mHashes[end] == hash; end++) {
if (key.equals(mArray[end << 1])) return end;
}
// index之前查找
// Search for a matching key before the index.
for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
if (key.equals(mArray[i << 1])) return i;
}
// 沒有找到
return ~end;
}
========== THE END ==========
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/28324.html
標籤：Android
上一篇：[譯]facebook Android平臺上動態串列的記憶體優化(Memory optimization for feeds on Android)