以下基于 JDK1.7 分析。
如圖所示隶症，HashMap 底層是基于數(shù)組和鏈表實現(xiàn)的龙屉。其中有兩個重要的參數(shù)：
- 容量
- 負載因子
容量的默認大小是 16呐粘，負載因子是 0.75，當(dāng) HashMap 的 size > 16*0.75 時就會發(fā)生擴容(容量和負載因子都可以自由調(diào)整)转捕。
put 方法
首先會將傳入的 Key 做 hash 運算計算出 hashcode,然后根據(jù)數(shù)組長度取模計算出在數(shù)組中的 index 下標作岖。
由于在計算中位運算比取模運算效率高的多，所以 HashMap 規(guī)定數(shù)組的長度為 2^n 五芝。這樣用 2^n - 1 做位運算與取模效果一致痘儡，并且效率還要高出許多。
由于數(shù)組的長度有限枢步，所以難免會出現(xiàn)不同的 Key 通過運算得到的 index 相同沉删，這種情況可以利用鏈表來解決，HashMap 會在 table[index]處形成鏈表醉途，采用頭插法將數(shù)據(jù)插入到鏈表中矾瑰。
get 方法
get 和 put 類似，也是將傳入的 Key 計算出 index 隘擎，如果該位置上是一個鏈表就需要遍歷整個鏈表殴穴，通過 key.equals(k) 來找到對應(yīng)的元素。
遍歷方式
Iterator<Map.Entry<String, Integer>> entryIterator = map.entrySet().iterator();
while (entryIterator.hasNext()) {
Map.Entry<String, Integer> next = entryIterator.next();
System.out.println("key=" + next.getKey() + " value=" + next.getValue());
}
Iterator<String> iterator = map.keySet().iterator();
while (iterator.hasNext()){
String key = iterator.next();
System.out.println("key=" + key + " value=" + map.get(key));
}
map.forEach((key,value)->{
System.out.println("key=" + key + " value=" + value);
});
強烈建議使用第一種 EntrySet 進行遍歷嵌屎。
第一種可以把 key value 同時取出推正，第二種還得需要通過 key 取一次 value，效率較低, 第三種需要 JDK1.8 以上宝惰，通過外層遍歷 table植榕，內(nèi)層遍歷鏈表或紅黑樹。
notice
在并發(fā)環(huán)境下使用 HashMap 容易出現(xiàn)死循環(huán)尼夺。
并發(fā)場景發(fā)生擴容尊残，調(diào)用 resize() 方法里的 rehash() 時，容易出現(xiàn)環(huán)形鏈表淤堵。這樣當(dāng)獲取一個不存在的 key時寝衫，計算出的 index 正好是環(huán)形鏈表的下標時就會出現(xiàn)死循環(huán)。
所以 HashMap 只能在單線程中使用拐邪，并且盡量的預(yù)設(shè)容量慰毅，盡可能的減少擴容。
在 JDK1.8 中對 HashMap 進行了優(yōu)化： 當(dāng) hash 碰撞之后寫入鏈表的長度超過了閾值(默認為8)扎阶，鏈表將會轉(zhuǎn)換為紅黑樹汹胃。
假設(shè) hash 沖突非常嚴重婶芭，一個數(shù)組后面接了很長的鏈表，此時重新的時間復(fù)雜度就是 O(n) 着饥。
如果是紅黑樹犀农，時間復(fù)雜度就是 O(logn) 。
大大提高了查詢效率宰掉。
