記憶體優化(使用SparseArray和ArrayMap代替HashMap)
支援原文:http://tryenough.com/java-sparseArray
HashMap
關於HashMap的知識請看這篇優秀文章:
SparseArray
SparseArray 的使用
支援原文:http://tryenough.com/java-sparseArray
建立
SparseArray
有兩個構造方法,一個預設構造方法,一個傳入容量。
SparseArray sparseArray = new SparseArray<>(); SparseArray sparseArray = new SparseArray<>(capacity);
首先來看看如何建立一個SparseArray
,而SparseArray
只需要指定一個泛型表示value型別,而key
的型別在SparseArray
內部已經指定了為int型別
put()
看看怎麼往裡面存放資料吧
sparseArray.put(int key,Student value);
put()
就跟HashMap
的使用方法一樣。
get()
sparseArray.get(int key); sparseArray.get(int key,Student valueIfNotFound);
SparseArray 實現原理
簡介:
用int[]陣列存放key,避免了HashMap中基本資料型別需要裝箱的步驟,其次不使用額外的結構體(Entry),單個元素的儲存成本下降。
要理解SparseArray 的實現原理,需要看程式碼:
SparseArray用兩個陣列來存放key和value:
private int[] mKeys; private Object[] mValues;
key的存放按照從小到大的順序,這樣就能保證使用二分查詢,而SparseArray內部查詢資料也就是使用的二分查詢,這樣查詢的效率比較高。我們來看下put方法,就能大概理解SparseArray的原理了:
支援原文:http://tryenough.com/java-sparseArray
//引數是傳進來的 int型別的key 和 範形的value public void put(int key, E value) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key);//使用二分查詢尋找key應該在的位置,具體實現請先看下面的講解 if (i >= 0) { mValues[i] = value;//如果尋找到lo就直接覆蓋value } else { i = ~i; if (i < mSize && mValues[i] == DELETED) { //如果沒有找到,並且返回的陣列索引對應的值是DELETED那就直接覆蓋value mKeys[i] = key; mValues[i] = value; return; } if (mGarbage && mSize >= mKeys.length) { //如果當前陣列已滿,檢查陣列中是否有DELETED的值,然後將其刪除gc的操作:可檢視下面具體原始碼 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++; } }
二分查詢
//這裡傳遞過來的value是上面的key 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 找到,直接返回key的索引 } } return ~lo;// 沒有找到就直接返回最終lo的取反值,此時的lo值就正好是排好序的lo }
gc:
支援原文:http://tryenough.com/java-sparseArray
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); }
總結:
SparseArray的優點:
避免了基本資料型別的裝箱操作
不需要額外的結構體,單個元素的儲存成本更低
資料量小的情況下,隨機訪問的效率更高
SparseArray的缺點:
插入操作需要複製陣列,增刪效率降低
資料量巨大時,複製陣列成本巨大,gc()成本也巨大
資料量巨大時,查詢效率也會明顯下降
ArrayMap的原理
ArrayMap是一個<key,value>對映的資料結構,它設計上更多的是考慮記憶體的優化,內部是使用兩個陣列進行資料儲存,一個數組記錄key的hash值,另外一個數組記錄Value值,它和SparseArray一樣,也會對key使用二分法進行從小到大排序,在新增、刪除、查詢資料的時候都是先使用二分查詢法得到相應的index,然後通過index來進行新增、查詢、刪除等操作,所以,應用場景和SparseArray的一樣,如果在資料量比較大的情況下,那麼它的效能將退化至少50%。
支援原文:http://tryenough.com/java-sparseArray
總結:
假設資料量都在千級以內的情況下:
1、如果key的型別已經確定為int型別,那麼使用SparseArray,因為它避免了自動裝箱的過程,如果key為long型別,它還提供了一個LongSparseArray來確保key為long型別時的使用
2、如果key型別為其它的型別,則使用ArrayMap