HashMap的原理
HashMap作為各種語言的核心數(shù)據(jù)結(jié)構(gòu)之一，應(yīng)用非常廣泛，其實(shí)現(xiàn)如下：
鏈接：https://www.cnblogs.com/chengxiao/p/6059914.html
HashMap的缺點(diǎn)：
- HashMap頻繁擴(kuò)容效率低；
- HashMap非線程安全；
- 高度依賴hash算法，可能導(dǎo)致鏈表過長( jdk1.8后使用紅黑樹替代了鏈表)，或則頻繁擴(kuò)容(擴(kuò)容依賴碰撞)；
- HashMap內(nèi)存占用過大；
so，HashMap雖然性能卓越，但是有很多缺點(diǎn)，是不是我們?cè)谝恍﹫鼍跋?數(shù)據(jù)量較少，例如 < 1000)情況下，可以用其他數(shù)據(jù)結(jié)構(gòu)來替代？
SparseArray
SparseArray(稀疏數(shù)組).他是Android內(nèi)部特有的api,標(biāo)準(zhǔn)的jdk是沒有這個(gè)類的.在Android內(nèi)部用來替代HashMap<Integer,E>這種形式,使用SparseArray更加節(jié)省內(nèi)存空間的使用,SparseArray也是以key和value對(duì)數(shù)據(jù)進(jìn)行保存的.使用的時(shí)候只需要指定value的類型即可.并且key不需要封裝成對(duì)象類型.
根據(jù)親測(cè),SparseArray存儲(chǔ)數(shù)據(jù)占用的內(nèi)存空間確實(shí)比HashMap要小一些.一會(huì)放出測(cè)試的數(shù)據(jù)在進(jìn)行分析。我們首先看一下二者的結(jié)構(gòu)特性.
-
SparseArray 結(jié)構(gòu)圖
默認(rèn)容器大小10
1541755523(1).png -
HashMap 結(jié)構(gòu)圖
詳見：HashMap介紹 - Sparse在內(nèi)存中維護(hù)兩個(gè)數(shù)組，一個(gè)Key(int)，一個(gè)數(shù)組Value；
在插入時(shí),首先通過二分法查找位置，如果找到且當(dāng)前位置為DELETED狀態(tài)時(shí)，直接替換，其他情況分段copy(根據(jù)當(dāng)前Size決定是否擴(kuò)容)，因此SparseArray的效率是不如HashMap的
/**
* 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);
}
if (mSize >= mKeys.length) {
int n = ArrayUtils.idealIntArraySize(mSize + 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;
}
if (mSize - i != 0) {
// Log.e("SparseArray", "move " + (mSize - i));
System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
}
mKeys[i] = key;
mValues[i] = value;
mSize++;
}
}
delete操作
/**
* 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;
}
}
}
SparseArray內(nèi)部維護(hù)了一套整理機(jī)制，在特殊情況下會(huì)觸發(fā)（獲取Size時(shí)，插入時(shí)等）
/**
* Returns the number of key-value mappings that this SparseArray
* currently stores.
*/
public int size() {
if (mGarbage) {
gc();
}
return mSize;
}
/**
* Given an index in the range <code>0...size()-1</code>, returns
* the key from the <code>index</code>th key-value mapping that this
* SparseArray stores.
*
* <p>The keys corresponding to indices in ascending order are guaranteed to
* be in ascending order, e.g., <code>keyAt(0)</code> will return the
* smallest key and <code>keyAt(size()-1)</code> will return the largest
* key.</p>
*/
public int keyAt(int index) {
if (mGarbage) {
gc();
}
return mKeys[index];
}
SparseArray的gc并不是垃圾回收機(jī)制(java GC)，Sparse的gc完成的工作是內(nèi)存整理，對(duì)于標(biāo)記為DELETED狀態(tài)的元素刪除掉，并整理內(nèi)存，實(shí)現(xiàn)如下：
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);
}
擴(kuò)容算法：
public static int idealByteArraySize(int need) {
for (int i = 4; i < 32; i++)
if (need <= (1 << i) - 12)
return (1 << i) - 12;
return need;
}
- 總結(jié)
HaspMap速度更優(yōu)，但是在內(nèi)存占用比較大，默認(rèn)16，擴(kuò)充系數(shù)0.75，每次擴(kuò)充2倍。在移動(dòng)端，數(shù)據(jù)量比較少的情況下(1000以下)，HaspMap的優(yōu)勢(shì)不太明顯，但是內(nèi)存占用比較大。因此Android針對(duì)于移動(dòng)端采用了SparseArray(key必須是Int)和ArrayMap等輕量級(jí)的數(shù)據(jù)結(jié)構(gòu)。
