最近在安卓群里看到了一個哥們面試被問Android特有的容器灭贷，當時我反問了一下自己這個問題就懵逼了简软，感覺做了3年的假安卓。后來才發(fā)現(xiàn)原來ArrayMap和SparseArray是安卓中特有的伙狐，雖然接觸過氓奈，但關(guān)注的確實比較少，正好借這個機會總結(jié)一下蜓肆。
本文會按以下順序探討問題颜凯，盡量不長篇大論討論源碼，關(guān)于這方面寫的好的文章網(wǎng)上也很多仗扬，努力做到從宏觀上關(guān)注整體設計思想和各自優(yōu)缺點
![]()
image
Hash表
定義:Hash表/散列表是根據(jù)關(guān)鍵碼值而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)症概，它通過關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度早芭。這個映射函數(shù)叫散列函數(shù)彼城，存放記錄的數(shù)組叫做散列表。
上面的定義說人話就是退个，在關(guān)鍵字（key）和表中的存儲位置建立一個函數(shù)關(guān)系精肃，這個函數(shù)叫做散列函數(shù)/哈希函數(shù)。這種映射轉(zhuǎn)換通常是一種壓縮映射帜乞，因為散列值的空間通常小于輸入的空間司抱，不同的輸入可能會散列出相同的結(jié)果。這種情況稱之為哈希沖突黎烈。所以兩個對象的HashCode有可能相同习柠，當兩個對象的內(nèi)容(eqauls)不同。
散列表解決沖突的方式：
- 開放地址法
- 再散列函數(shù)法
- 鏈地址法
- 公共溢出區(qū)法
讓我們從以下幾點關(guān)注HashMap
- 存儲結(jié)構(gòu)
- 哈希函數(shù)
- 哈希沖突
- 擴容
那讓我們通過HashMap源碼（Java 7的源碼）照棋，看看HashMap是如何解決上面幾個問題的资溃？還是從put方法開始一探究竟
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);//table為空則初始化
}
if (key == null)
return putForNullKey(value);
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);//散列函數(shù)-step1
int i = indexFor(hash, table.length);//散列函數(shù)-step2
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
HashMap的初始化和數(shù)據(jù)結(jié)構(gòu)
table就是散列表，看一下table的實現(xiàn)HashMapEntry<K,V>[]烈炭。每個數(shù)組中存儲著一個鏈表溶锭，所以HashMap的存儲結(jié)構(gòu)就是數(shù)組+鏈表。在存儲數(shù)據(jù)的時候如果table為空符隙，則初始化趴捅。
/**
* Inflates the table.
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
// Android-changed: Replace usage of Math.min() here because this method is
// called from the <clinit> of runtime, at which point the native libraries
// needed by Float.* might not be loaded.
float thresholdFloat = capacity * loadFactor;
if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
thresholdFloat = MAXIMUM_CAPACITY + 1;
}
threshold = (int) thresholdFloat;
table = new HashMapEntry[capacity];
}
roundUpToPowerOf2是為了確保容量為2的n次方垫毙，并且是離number值最近的一個2的n次方。
Integer.highestOneBit(number)取出這個值最高位拱绑，且把其余位置0综芥。Integer.bitCount(number) > 1判斷number是否為2的n次方，如果是bitCount必然為1猎拨，不是則再乘2返回膀藐。
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
int rounded = number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (rounded = Integer.highestOneBit(number)) != 0
? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
: 1;
return rounded;
}
那么這里就需要注意了，如果在創(chuàng)建HashMap對象的時候調(diào)用無參構(gòu)造方法红省，創(chuàng)建的數(shù)組長度為4额各。當存儲內(nèi)容超過75%就會觸發(fā)擴容。所以通常會推薦吧恃，盡量預估容器需要的容量臊泰，調(diào)用有參構(gòu)造方法。同時因為加載因子的作用蚜枢，初始長度應為 n / loadFactor （n為預估的長度）
哈希函數(shù)
這兩行便是HashMap的散列函數(shù)缸逃，先計算Key的哈希值，在保證這個哈希值不會超過數(shù)組的長度厂抽。
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
這里利用了與2的n次方求余可以利用與運算計算的特性需频，同時初始化、擴容的時候又保證了數(shù)組的長度為2的n次方筷凤。
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
碰撞函數(shù)
計算出數(shù)據(jù)該存在在散列表的哪個位置昭殉，接下來就該存入數(shù)據(jù)了。在HashMap中藐守，通過鏈地址法來解決碰撞問題挪丢，也就是說，每個數(shù)組中存放的都是一個鏈表卢厂。
看一下最基礎(chǔ)的兩種線性存儲結(jié)構(gòu)乾蓬，HashMap正是集合了這兩種線性存儲結(jié)構(gòu)設計出的容器。
| 數(shù)據(jù)結(jié)構(gòu) | 優(yōu)缺點 |
|---|---|
| 順序表 | 尋址容易慎恒，但插入刪除開銷大 |
| 鏈表 | 尋址困難任内，但插入刪除開銷小 |
擴容
當增加結(jié)點的時候，會判斷當前散列表的長度融柬，如果容量已經(jīng)超過75%（默認的增長因子為0.75）死嗦。則會進行擴容，新的散列表長度是原先兩倍粒氧。因為涉及到鏈表的拷貝越除，非常消耗性能，這也是為什么建議預估使用容量，調(diào)用有參構(gòu)造方法的原因摘盆。
/**
* Transfers all entries from current table to newTable.
*/
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
for (HashMapEntry<K,V> e : table) {
while(null != e) {
HashMapEntry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
HashMap的版本變化
Java 8中翼雀，HashMap最重要的變化是存儲結(jié)構(gòu)的變化。由以前的數(shù)組+鏈表變成了數(shù)組+鏈表/紅黑樹骡澈，當沖突結(jié)點達到7個或7個以上的時候锅纺，會把鏈表轉(zhuǎn)換為紅黑樹掷空，然后進行存儲肋殴。同時由于紅黑樹比鏈表的性能更好，即使沖突了查找的時間復雜度為O(logN)坦弟，所以哈希函數(shù)也做了簡化护锤。
如果跟面試官聊到了版本變化，你又恰好說出了紅黑樹酿傍，恐怕順口被問一句紅黑樹性質(zhì)也不是什么奇怪的事情把烙懦？
那么紅黑樹有什么性質(zhì)？
1）每個結(jié)點要么是紅的赤炒，要么是黑的氯析。
2）根結(jié)點是黑的。
3）每個葉結(jié)點莺褒，即空結(jié)點（NIL）是黑的掩缓。
4）如果一個結(jié)點是紅的，那么它的倆個兒子都是黑的遵岩。
5）對每個結(jié)點你辣，從該結(jié)點到其子孫結(jié)點的所有路徑上包含相同數(shù)目的黑結(jié)點。
SparseArray解析
數(shù)據(jù)結(jié)構(gòu)
SparseArray通過數(shù)組+數(shù)組的方式存儲數(shù)據(jù)尘执，不需要開辟內(nèi)存空間來額外存儲外部映射舍哄，提高了內(nèi)存效率。通過二分查找來找對象誊锭，執(zhí)行效率相對于HashMap要慢一點表悬。
public class SparseArray<E> implements Cloneable {
private int[] mKeys;
private Object[] mValues;
//...
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++;
}
}
}
核心就是二分查找
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
}
ArrayMap解析
ArrayMap中不再存儲結(jié)點，維護了兩個數(shù)組丧靡，mHashes存放每一項的HashCode签孔，mArray存放鍵值對。需要注意的一點是窘行，ArrayMap沒有實現(xiàn)Serializable接口饥追，而HashMap實現(xiàn)了這個接口。
public final class ArrayMap<K, V> implements Map<K, V> {
int[] mHashes;//key的hashcode值
Object[] mArray;//key value數(shù)組
@Override
public V put(K key, V value) {
final int hash;
int index;
if (key == null) {
hash = 0;
index = indexOfNull();
} else {
hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
index = indexOf(key, hash);
}
if (index >= 0) {
index = (index<<1) + 1;
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
index = ~index;
if (mSize >= mHashes.length) {
final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
: (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);
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);
}
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;
}
}
關(guān)于如何優(yōu)化HashMap的一點思考
這個問題印象中也有人面試被問到過罐盔，當時我的第一反應是使用的時候盡量估算容量但绕，避免擴容產(chǎn)生的開銷。接著思考的方向是如何提高哈希計算的效率或者提高判斷的效率，苦思冥想依然沒有結(jié)果捏顺，也沒有同行給出答案六孵。這次重新總結(jié)3種容器，又想到了這個問題幅骄，同時對這個題目也有了新的思考劫窒，當然依然沒有找到答案。
(每個容器設計出來必然有所取舍拆座，如果改善缺點的同時保留優(yōu)點主巍，那必然是優(yōu)化。如果為了改善缺點卻摒棄了某些優(yōu)點挪凑，那恐怕就不能稱之為優(yōu)化了孕索。如果拋棄HashMap本身的設計特點，造一個更牛逼的容器躏碳，且不說我恐怕沒這個造輪子的本事搞旭，這也不能叫做優(yōu)化HashMap了吧)
那么HashMap該如何優(yōu)化？其實我最初考慮的有些狹隘了菇绵，優(yōu)化完全可以從幾個方面入手
- 更友好的接口肄渗，使用起來更便捷
- 更高的效率
- 更少的空間
- 更簡潔的代碼
- 線程安全
- (你一定還能想到更多)
如果還是沒有頭緒，那么為以上的切入點加上定語再思考一下咬最？
- 特定場景更高的效率
- 特定場景更少的空間
- (你一定還能想到更多)
這樣一看是不是更有思路了翎嫡，ArrayMap和SparseArray就是設計出來在部分場景中取代HashMap，那這些場景是不是正是HashMap可以優(yōu)化的點呢丹诀？
所以這道題在我看來應該回答的是钝的，哪些場景下可以用其他容器取代HashMap提高效率？
