HashMap

之前寫了“Java集合TreeMap紅黑樹一生只愛一次”，說到底還是太年輕了，Map其實在排序中應(yīng)用比較少，一般追求的是速度，通過HashMap來獲取速度。hashmap 調(diào)用object hashcode方法用于返回對象的哈希碼，主要使用在哈希表中。

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable

HashMap繼承AbstractMap 本質(zhì)是key-value鍵值對，具有Map素有常用的方法put() get() remove()。

Cloneable意味著可以被克隆。
實現(xiàn)serializable接口的作用是就是可以把對象存到字節(jié)流,然后可以恢復(fù)。
當(dāng)我們給put()方法傳遞鍵和值時，我們先對鍵調(diào)用hashCode()方法，返回的hashCode用于找到bucket位置來儲存Entry對象。

get

hashmap常用的get方法，可以看到先hash話，然后獲取

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;if ((e = first.next) != null) {if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;
}

put

在Java 8中put這個方法的思路分為以下幾步：

1. 調(diào)用key的hashCode方法計算哈希值，并據(jù)此計算出數(shù)組下標(biāo)index
2. 如果發(fā)現(xiàn)當(dāng)前的桶數(shù)組為null，則調(diào)用resize()方法進行初始化
3. 如果沒有發(fā)生哈希碰撞，則直接放到對應(yīng)的桶中
4. 如果發(fā)生哈希碰撞，且節(jié)點已經(jīng)存在，就替換掉相應(yīng)的value
5. 如果發(fā)生哈希碰撞，且桶中存放的是樹狀結(jié)構(gòu)，則掛載到樹上
6. 如果碰撞后為鏈表，添加到鏈表尾，如果鏈表長度超過TREEIFY_THRESHOLD默認是8，則將鏈表轉(zhuǎn)換為樹結(jié)構(gòu)
7. 數(shù)據(jù)put完成后，如果HashMap的總數(shù)超過threshold就要resize

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

為什么非要使用紅黑樹呢？

這個選擇是綜合考慮的，既要put效率很高，同時也要get效率很高，紅黑樹就是其中一種。
二叉樹也ok，紅黑樹是一種自平衡的二叉查找樹
平衡二叉樹可以有效的減少二叉樹的深度，從而提高了查詢的效率
除了之外，紅黑樹還具備
節(jié)點是紅色或黑色；
根節(jié)點是黑色；
所有葉子都是黑色的空節(jié)點；
每個紅色節(jié)點必須有兩個黑色的子節(jié)點，也就是說從每個葉子到根的所有路徑上，不能有兩個連續(xù)的紅色節(jié)點；
從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑色節(jié)點
紅黑樹的優(yōu)勢在于它是一個平衡二叉查找樹，對于普通的二叉查找樹（非平衡二叉查找樹）在極端情況下可能會退化為鏈表的結(jié)構(gòu)，再進行元素的添加、刪除以及查詢時，它的時間復(fù)雜度就會退化為 O(n)
紅黑樹的高度近似 log2n，它的添加、刪除以及查詢數(shù)據(jù)的時間復(fù)雜度為 O(logn)
紅黑樹時間復(fù)雜度比鏈表、二叉樹小，這就是采用紅黑樹做hashMap底層原理，然后在treeMap里面就更經(jīng)典了。

jdk1.7之前底層數(shù)據(jù)結(jié)構(gòu)采用哈希+鏈表。但后來業(yè)務(wù)越來越追求速度，hash的目的是為了得到進行索引，有些hash沖突可能造成死循環(huán)，所以jdk1.8加上紅黑樹來解決明顯可以提高效率。
但是要分情況在數(shù)組長度大于64，同時鏈表長度大于8的情況下，鏈表將轉(zhuǎn)化為紅黑樹。當(dāng)數(shù)據(jù)的長度退化成6時，紅黑樹轉(zhuǎn)化為鏈表。數(shù)據(jù)長度沒有那么長，就沒必要采用紅黑樹，紅黑樹雖然提高了速度，但也提交了空間復(fù)雜度。數(shù)據(jù)長度大于8和數(shù)組長度大于64，采用紅黑樹。那為什么是6和8作為臨近值呢，其實這個值不要死記，是官網(wǎng)進行壓力測試的出來的結(jié)論。

為什么HashMap要擴容呢？

     數(shù)組是固定的，但集合是動態(tài)的，可以擴容。

當(dāng)hashmap越來越來多的元素塞進來之后，hashmap不得不擴容了，hashmap中元素個數(shù)超過160.75=12的時候，就把數(shù)組的大小擴展為216=32，即擴大一倍，然后重新計算每個元素在數(shù)組中的位置，而這是一個非常消耗性能的操作。
所以我們提前預(yù)測知道hashmap容量，再稍微設(shè)置大些，這樣可以減少性能的消耗的。
但是initialCapacity初始容量設(shè)置小了，會不會報錯呢？
不會的，但是hashmap會自動擴容，同樣也會走到上面過程，重新計算，消耗性能的操作。
提前預(yù)判，但是后來業(yè)務(wù)改變，需要那么大的容量，程序員應(yīng)該即使更改，要不然就和不設(shè)置沒有區(qū)別啦。

哈希 鏈表、紅黑樹 （來處理極端情況下的哈希碰撞）

數(shù)組+（鏈表或紅黑樹）Node類來存儲Key、Value

hashMap什么時候擴容？

注意，是在put的時候才會擴容，在容量超過四分之三的時候就會擴容

hashMap的key可以為空嗎

可以，Null值會作為key來存儲

key重復(fù)了，會被覆蓋嗎？

會的

HashMap擴容為什么總是2的次冪？

HashMap擴容主要是給數(shù)組擴容的，因為數(shù)組長度不可變，而鏈表是可變長度的。從HashMap的源碼中可以看到HashMap在擴容時選擇了位運算，向集合中添加元素時，會使用(n - 1) & hash的計算方法來得出該元素在集合中的位置。只有當(dāng)對應(yīng)位置的數(shù)據(jù)都為1時，運算結(jié)果也為1，當(dāng)HashMap的容量是2的n次冪時，(n-1)的2進制也就是1111111***111這樣形式的，這樣與添加元素的hash值進行位運算時，能夠充分的散列，使得添加的元素均勻分布在HashMap的每個位置上，減少hash碰撞

當(dāng)HashMap的容量是16時，它的二進制是10000，(n-1)的二進制是01111

JDk1.7HashMap擴容死循環(huán)問題

HashMap是一個線程不安全的容器，在最壞的情況下，所有元素都定位到同一個位置，形成一個長長的鏈表，這樣get一個值時，最壞情況需要遍歷所有節(jié)點，性能變成了O(n)。
JDK1.7中HashMap采用頭插法拉鏈表，所謂頭插法，即在每次都在鏈表頭部（即桶中）插入最后添加的數(shù)據(jù)。
死循環(huán)問題只會出現(xiàn)在多線程的情況下。

假設(shè)在原來的鏈表中，A節(jié)點指向了B節(jié)點。
在線程1進行擴容時，由于使用了頭插法，鏈表中B節(jié)點指向了A節(jié)點。
在線程2進行擴容時，由于使用了頭插法，鏈表中A節(jié)點又指向了B節(jié)點。
在線程n進行擴容時，
這就容易出現(xiàn)問題了。在并發(fā)擴容結(jié)束后，可能導(dǎo)致A節(jié)點指向了B節(jié)點，B節(jié)點指向了A節(jié)點，鏈表中便有了環(huán)

死循環(huán)解決方案：

1)、使用線程安全的ConcurrentHashMap替代HashMap，個人推薦使用此方案。

2)、使用線程安全的容器Hashtable替代，但它性能較低，不建議使用。

3)、使用synchronized或Lock加鎖之后，再進行操作，相當(dāng)于多線程排隊執(zhí)行，也會影響性能，不建議使用。

為了解決JDK1.7死循環(huán)問題，JDK1.8引入了紅黑樹
即在數(shù)組長度大于64，同時鏈表長度大于8的情況下，鏈表將轉(zhuǎn)化為紅黑樹。同時使用尾插法。當(dāng)數(shù)據(jù)的長度退化成6時，紅黑樹轉(zhuǎn)化為鏈表。

從JDK1.8開始，在HashMap里面定義了一個常量TREEIFY_THRESHOLD，默認為8。當(dāng)鏈表中的節(jié)點數(shù)量大于TREEIFY_THRESHOLD時，鏈表將會考慮改為紅黑樹
使用線程安全如Concurrenthashmap、HashTable

為什么線程不安全？

1、put的時候?qū)е碌亩嗑€程數(shù)據(jù)不一致。
這個問題比較好想象，比如有兩個線程A和B，首先A希望插入一個key-value對到HashMap中，首先計算記錄所要落到的桶的索引坐標(biāo)，然后獲取到該桶里面的鏈表頭結(jié)點，此時線程A的時間片用完了，而此時線程B被調(diào)度得以執(zhí)行，和線程A一樣執(zhí)行，只不過線程B成功將記錄插到了桶里面，假設(shè)線程A插入的記錄計算出來的桶索引和線程B要插入的記錄計算出來的桶索引是一樣的，那么當(dāng)線程B成功插入之后，線程A再次被調(diào)度運行時，它依然持有過期的鏈表頭但是它對此一無所知，以至于它認為它應(yīng)該這樣做，如此一來就覆蓋了線程B插入的記錄，這樣線程B插入的記錄就憑空消失了，造成了數(shù)據(jù)不一致的行為。

2、另外一個比較明顯的線程不安全的問題是HashMap的get操作可能因為resize而引起死循環(huán)（cpu100%）
HashMap的擴容機制就是重新申請一個容量是當(dāng)前的2倍的桶數(shù)組，然后將原先的記錄逐個重新映射到新的桶里面，然后將原先的桶逐個置為null使得引用失效。HashMap之所以線程不安全，就是resize這里出的問題。