為什么 HashMap 會發生數據覆蓋問題
本文轉載自微信公眾號「Java極客技術」，作者鴨血粉絲 。轉載本文請聯系Java極客技術公眾號。
阿粉今天就來談談這個，這個問題在 1.7 版本和 1.8 版本中都有，阿粉分別來說說
在說之前，咱們先要達成一個共識：HashMap 發生數據覆蓋的問題，是在多線程環境 & 擴容下產生的，接下來咱們具體來看
jdk 1.7
- void transfer(Entry[] newTable, boolean rehash) {
- int newCapacity = newTable.length;
- for (Entry<K,V> e : table) {
- while(null != e) {
- Entry<K,V> next = e.next;
- if (rehash) {
- e.hash = null == e.key ? 0 : hash(e.key);
- }
- int i = indexFor(e.hash, newCapacity);
- e.next = newTable[i];
- newTable[i] = e; // 線程 A 運行到這里時被掛起
- e = next;
- }
- }
- }
在擴容時，發生數據覆蓋問題主要核心就是上面的代碼，我們假設一下，剛開始時，結構是這樣的：
現在有兩個線程 A 和 B ，它們都要進行插入操作，首先 A 進行插入操作，經過 Hash 之后就得到了要落到的桶的索引坐標，運行到 newTable[i] = e; 這行代碼時， CPU 時間片用完了，此時線程 A 就停止運行被掛起，這個時候是這個樣子的：
線程 A 被掛起之后，線程 B 被調度得以運行，巧的是，線程 B 經過 Hash 之后得到的要落到的桶索引坐標和線程 A 一樣，此時線程 B 也進行插入操作，線程 B 因為時間片足夠用，所以就成功的將記錄插入到了桶里面：
線程 B 插入成功之后，根據 Java 內存模型，此時主內存中存放的值就是線程 B 運行之后的結果
接下來線程 A 被喚醒，繼續執行插入操作。對于 A 來說，前面的步驟都已經執行過了，所以就不需要再次運行，直接從 newTable[i] = e; 這行代碼開始往下繼續運行即可，線程 A 保存的環境是 e = 12 next = 6 e.next = newTable[i]; 即 newTable[3] = null; ，那么接下來執行 newTable[i] = e; & e = next 也就是 newTable[3] = 12 e = next = 6 執行完畢之后，大概就是這樣：
元素 15 就這么被覆蓋掉了
jdk 1.8
看完 1.7 之后，咱們再來看看 1.8 版本。數據覆蓋主要發生在 put 操作中，下面是 1.8 源碼(阿粉在這里截取了一小部分)：
- 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) // 如果沒有 hash 碰撞，則直接插入
- tab[i] = newNode(hash, key, value, null);
- }
在上面的代碼中，我們能夠看到，源碼只是判斷了 hash 是否有碰撞，如果沒有就不再做別的檢查進行插入操作
在多線程環境下，如果線程 1 檢查完了 hash 沒有碰撞，要進行插入時， CPU 時間片使用完畢，此時它被掛起，線程 2 開始跑，無巧不成書嘛，此時線程 2 經過 hash 之后得到的值和線程 1 的 hash 值一樣，線程 2 將值插入進去，線程 1 恢復運行，因為前面檢查了 hash 碰撞，此時插入時不再做任何檢查，直接將值插入
那么線程 2 插入的值就被覆蓋掉了
HashMap 之所以發生數據覆蓋的問題，最主要的原因在于它沒有加鎖，所以在多線程環境下會發生數據覆蓋問題
修正一個問題
在 面試官你能不能別問我 HashMap 了? 這篇文章中，阿粉說之所以是 8 轉為紅黑樹，和時間復雜度有關，后來經過一位小伙伴留言才發現阿粉的思路錯了，和泊松分布有關，這一點源碼中也有說明：
- Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution
- with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although
- with a large variance because of resizing granularity. Ignoring variance, the expected
- occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)).
- The first values are:
- 0: 0.60653066
- 1: 0.30326533
- 2: 0.07581633
- 3: 0.01263606
- 4: 0.00157952
- 5: 0.00015795
- 6: 0.00001316
- 7: 0.00000094
- 8: 0.00000006
- more: less than 1 in ten million
從源碼中可以看到，在負載因子 0.75 ( HashMap 默認)的情況下，單個 hash 槽內元素個數為 8 的概率為 0.00000006，是相當小的一個值了，因此將 7 作為一個分水嶺，等于 7 時不做轉換，大于等于 8 才轉紅黑樹，小于等于 6 才轉鏈表。
哈希攪動和高低 16 位有關系嗎?
有的小伙伴問阿粉，哈希攪動和高低 16 位有關系嗎?
阿粉不太清楚這個有關系是怎樣的一個有關系，但是 16 這個數字的選取，作者肯定也是經過考慮之后再決定的
哈希攪動主要發生在 resize() 這個方法中，我們可以看到源碼中的注釋：
- Initializes or doubles table size.
- If null, allocates in accord with initial capacity target held in field threshold.
- Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.
翻譯一下就是：在初始化或者增加表大小時，如果沒有指定，那么就按照初始容量來進行分配。如果指定了，由于使用的是 2 的冪，所以每個 bin 元素也必須保持相同的索引，或者在新表中以 2 的冪偏移
這樣看的話，好像和 16 位有點兒關系
