HashMap 是開發(fā)中常用的經(jīng)典數(shù)據(jù)結(jié)構(gòu)，在查詢問題上效率極高。本文對 HashMap 的相關(guān)問題做一次總結(jié)。
JDK1.7中 HashMap 的底層結(jié)構(gòu)為數(shù)組 + 鏈表的形式。
我們知道，數(shù)組的查詢和修改速度很快，但是增加一個元素或者刪除一個元素就很慢，但是鏈表就反過來，鏈表是增加和刪除一個元素很快，查詢和修改就很慢。而 HashMap 將兩者結(jié)合起來，旨在提高查詢效率。那它的工作原理是什么呢？
簡單來說， HashMap 為 key : value 類型的數(shù)據(jù)結(jié)構(gòu)，我們存放數(shù)據(jù)（假定為(key, value))時，調(diào)用 put 方法， HashMap 會計算 key 的 hash 值，經(jīng)過某些操作計算出特定的數(shù)組索引，再將數(shù)據(jù)散列到索引處。這樣就完成一次數(shù)據(jù)的存儲。那鏈表在哪里使用呢？
當(dāng) put 方法在對不同的 key 進(jìn)行 hash 操作時，可能會計算出相同的 hash 值（這時候 hash 算法的設(shè)計就尤為重要了），如果數(shù)組的索引處已經(jīng)被相同 hash 值的數(shù)據(jù)占有了該怎么辦呢？這時候就要用到鏈表了。前面提到過，鏈表在查詢和修改數(shù)據(jù)的時候很慢，但是它在插入和刪除數(shù)據(jù)的時候卻很快，那么利用這個特性，我們將相同的 hash 值對應(yīng)的數(shù)據(jù)裝進(jìn)同一個桶（bucket）中，在這個桶中形成一個鏈表，將它們?nèi)兼溄釉谝黄穑@樣就可以解決相同 hash 值的問題了。
這樣一來，存放在 HashMap 中的數(shù)據(jù)就可以被高效查詢了，如果沖突很少的情況下，或者說理想情況下，其時間復(fù)雜度為 O(1) ，是不是非?？?？
但是問題呢，也出在這里，不然1.8為什么還要去優(yōu)化 HashMap 呢？
其實在日常開發(fā)中，理想情況基本上是不存在的。如果插入的數(shù)據(jù)沖突嚴(yán)重，那么桶里的鏈表會越來越長，這樣在查詢時的效率就會越來越低，時間復(fù)雜度為 O(n)（鏈表查詢的時間復(fù)雜度為 O(n) ）。
JDK1.8對HashMap的查詢效率進(jìn)行了大幅優(yōu)化，時間復(fù)雜度可已達(dá)到 O(logn) ，而在1.7中，這個值為 O(n) 。那么JDK到底怎么優(yōu)化了呢？
1.8中 HashMap 為鏈表長度設(shè)置了一個閾值，長度超過這個閾值的鏈表將會被轉(zhuǎn)換為紅黑樹。閱讀1.8的 HashMap 源碼，就可以從兩個核心方法 (get/put )看出 1.8 中對大鏈表做了優(yōu)化，修改為紅黑樹之后查詢效率直接提高到了 O(logn) 。
HashMap的遍歷方式
//method 1
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());
}
//method 2
Iterator<String> iterator = map.keySet().iterator();
while (iterator.hasNext()){
String key = iterator.next();
System.out.println("key=" + key + " value=" + map.get(key));
}
建議使用第一種方法遍歷 HashMap ，原因是每次遍歷都可以同時拿到 Map 中的 key 和 value ，效率較高；而第二種方法只能先拿到 key ，然后再通過 key 計算 value ，效率不及第一種方法。
分析一下method1這種遍歷方法：
Map接口提供了一個 entrySet() 的方法，這個方法將出現(xiàn)在 map 中的 mappings ，也就是 map 中所有的 Entry<K, V> 都存放在一個 Set 集合中，并最終返回這個Set集合。
我們?yōu)檫@個Set初始化一個泛型迭代器，迭代循環(huán) Set 中的 Entry<K, V> ，最終取得相應(yīng)的鍵值對。
經(jīng)過優(yōu)化的 HashMap 查詢效率的確是高了很多，但是 HashMap 原有的問題也都存在，比如在并發(fā)場景下使用時容易出現(xiàn)死循環(huán)。
final HashMap<String, String> map = new HashMap<String, String>();
for (int i = 0; i < 1000; i++) {
new Thread(new Runnable() {
@Override
public void run() {
map.put(UUID.randomUUID().toString(), "");
}
}).start();
}
但是為什么呢？簡單分析下。
HashMap 在擴容的時候會調(diào)用 resize() 方法，就是這里的并發(fā)操作容易在一個桶上形成環(huán)形鏈表；這樣當(dāng)獲取一個不存在的 key 時，計算出的 index 正好是環(huán)形鏈表的下標(biāo)就會出現(xiàn)死循環(huán)（其實鏈表此時成環(huán)）。
不過我覺得這不能算是Bug，因為HashMap本身就是非線程安全的，在單線程中使用它是沒有任何問題的。如果要在多線程中使用和HashMap相同的功能，ConcurrentHashMap了解一下？
