java集合初探（一）：HashMap.
一、概述
HashMap可能是我們最經常用的Map介面的實現了。話不多說，我們先看看HashMap類的注釋：
基於哈希表的Map介面實現。
這個實現提供了所有可選的映射操作，並允許空值和空鍵。（HashMap類與Hashtable大致相當，只是它是不同步的，並且允許為null）
這個類對映射的順序不做任何保證；特別是，它不保證順序將隨著時間的推移保持不變。
這個實現為基本操作（get和put）提供了恆定的時間性能，假設hash函數在bucket中適當地分散了元素。集合視圖上的迭代所需的時間與HashMap實例的「容量」（bucket的數量）加上其大小（鍵值映射的數量）成比例。因此，如果迭代性能很重要，那麼不要將初始容量設置得太高（或者負載係數太低），這一點非常重要。
HashMap的實例有兩個影響其性能的參數：初始容量和負載因子。capacity是哈希表中的bucket數，初始容量就是創建哈希表時的容量。載入因子是一個度量哈希表在容量自動增加之前可以達到的完整程度。當哈希表中的條目數超過載入因子與當前容量的乘積時，哈希表將重新哈希（即重建內部數據結構），使哈希表的存儲桶數大約為原來的兩倍。
一般來說，默認的負載係數（.75）在時間和空間成本之間提供了很好的折衷。較高的值會減少空間開銷，但會增加查找開銷（反映在HashMap類的大多數操作中，包括get和put）。在設置初始容量時，應考慮地圖中的預期條目數及其荷載係數，以盡量減少再灰化操作的次數。如果初始容量大於最大入口數除以負載係數，則不會發生再吹灰操作。
如果要在一個HashMap實例中存儲許多映射，那麼以足夠大的容量創建它將使映射的存儲效率更高，而不是讓它根據需要執行自動重新快取以增加表。請注意，使用具有相同hashCode（）的多個鍵肯定會降低任何哈希表的性能。為了改善影響，當鍵是可比較的時，這個類可以使用鍵之間的比較順序來幫助打破聯繫。
請注意，此實現不是同步的。如果多個執行緒同時訪問一個哈希映射，並且至少有一個執行緒在結構上修改了該映射，則它必須在外部同步。（結構修改是指添加或刪除一個或多個映射的任何操作；僅更改與實例已包含的鍵相關聯的值不是結構修改。）這通常是通過對自然封裝映射的對象進行同步來完成的。如果不存在這樣的對象，則應該使用集合.synchronizedMap方法。最好在創建時執行此操作，以防止意外的不同步訪問映射：
Map m = Collections.synchronizedMap(new HashMap(...));注意，迭代器的fail-fast行為不能得到保證，因為一般來說，在存在不同步的並發修改時，不可能做出任何明確保證。Fail fast迭代器在盡最大努力的基礎上拋出ConcurrentModificationException。因此，編寫一個依賴這個異常來保證其正確性的程式是錯誤的：迭代器的fail-fast行為應該只用於檢測bug。
以下是HashMap的類關係：
HashMap實現了Map介面，並繼承 AbstractMap 抽象類，其中 Map 介面定義了鍵值映射規則。和 AbstractCollection抽象類在 Collection 族的作用類似， AbstractMap 抽象類提供了 Map 介面的骨幹實現，以最大限度地減少實現Map介面所需的工作。
對於HashMap，我們關注六個問題：
- HashMap的數據結構（實現結構，什麼情況變紅黑樹，樹化和鏈化的閾值）
- HashMap構造函數（四個構造函數）
- HashMap的put（哈希、異或與或運算獲取下標，為什麼初始容量是2的n次方）
- HashMap的get（為什麼重寫equals方法需同時重寫hashCode方法）
- HashMap的擴容（JDK8為什麼不需要重哈希）
- HashMap為什麼是執行緒不安全的？（1.7死循環，1.8數據覆蓋）
二、HashMap的數據結構
1.底層實現
既然HashMap叫這個名字，那他的實現必然是基於哈希表的，關於哈希表我在數據結構與演算法（十）：哈希表已有介紹。簡而言之，哈希表就是一種結合數組與鏈表的一種數據結構，藉助哈希演算法快速獲取元素下標以實現高效查找。
關於HashMap的底層的數據結構，我們需要了解兩個成員變數以及一個內部類：
transient Node<K,V>[] table;：桶容器Node<K,V>：entrySet使用的，基於Map.Entry<K,V>介面實現的節點類，也就是同容器中的鏈表
畫圖描述一下就是：
我們知道哈希表解決哈希衝突的方式有開放地址法和分離鏈表法，這裡很明顯使用的是分離鏈表法，也就是俗稱的拉鏈法。
當我們存儲一個鍵值對的時候，會通過哈希演算法獲得key對應的哈希值，通過哈希值去找到在桶中要存放的位置的下標，而有時候不同的key會計算出相同的哈希值，也就是哈希碰撞，那麼節點就會接在第一個節點的身後形成一條鏈表。當查找的時候先通過key計算得到哈希值找到鏈表，然後再遍歷鏈表找到key，因此如果哈希碰撞嚴重，會導致鏈表變的很長，會影響到查找效率。
按這角度思考，如果桶數組很大，那麼同樣的哈希演算法能得到的位置就更多，換句話說就是發生哈希碰撞的概率就越小，但是過大的桶數組又會浪費空間，所以就後面提到的擴容演算法來動態的調整容量。
2.什麼時候轉為紅黑樹？為什麼？
另外，我們知道在JDK7中HashMap底層實現只是數組+鏈表，而到了JDK8就變成了數組+鏈表+紅黑樹。
紅黑樹是一種複雜的樹結構，這裡我們簡單的理解為一種具有二叉排序樹性質和一定平衡二叉樹性質（不要求絕對平衡以避免頻繁旋轉）的二叉樹。
我們知道發生哈希碰撞的節點會在桶中形成鏈表，而當鏈表上的元素超過8個的時候就會轉變成紅黑樹。這是因為同樣深度的情況下，樹可以儲存比鏈表更多的元素，並且同時能保證良好的插入刪除和查找效率。當元素小於6個的時候又會轉回鏈表。
那麼為什麼會選擇8和6這兩個數字呢？
-
效率問題：
紅黑樹的平均查找長度是lg(n)，而鏈表是n/2。按這個計算，lg(8)=3，6/2=3 -> lg(4)=2， 4/2=2，我們可以看見當越小於8的時候紅黑樹和鏈表查找效率就越差不多，加上轉化為紅黑樹還需要消耗額外的時間和空間的情況下，所以不如直接用鏈表。
-
防止頻繁的轉換：
8和6之間隔了一個7，如果轉換為樹和轉換為鏈表的閾值是直接相鄰，那麼很可能出現頻繁在樹和鏈表的結構件轉換的現象。
三、HashMap的構造函數
我們先來看看有關HashMap構建中可能涉及的成員變數：
-
transient int size：實際存儲的key-value鍵值對的個數； -
int threshold：要調整大小的下一個大小值。一般是容量 * 負載係數，但是構造函數執行後大小等於初始化容量，只有第一次添加元素後才會初始化；
-
final float loadFactor：負載因子，代表了table的填充度有多少，默認是0.75。載入因子存在的原因，還是因為減緩哈希衝突，如果初始桶為16，等到滿16個元素才擴容，某些桶里可能就有不止一個元素了。 所以載入因子默認為0.75，也就是說大小為16的HashMap，到了第13個元素，就會擴容成32；
-
transient int modCount：HashMap被改變的次數。由於HashMap非執行緒安全，在對HashMap進行迭代時， 如果期間其他執行緒的參與導致HashMap的結構發生變化了（比如put，remove等操作）， 需要拋出異常ConcurrentModificationException
1.有初始容量和負載因子的構造方法
構造一個具有指定初始容量和負載因子的空HashMap。
這裡提到的負載因子，負載因子衡量的是一個散列表的空間的使用程度。
public HashMap(int initialCapacity, float loadFactor) {
//初始容量必須大於0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量不能大於最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//初始化載入因子
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
這裡調用的tableSizeFor()方法是個位運算，他的作用是：
對於給定的目標容量，返回2的冪
換而言之，初始化容量必須是2的n次方，這個地方與HashMap如何向集合高效添加元素的需求是直接相關的。
具體的分析可以參考：HashMap源碼註解 之 靜態工具方法hash()、tableSizeFor()（四）。
接著我們可以看到初始容量處理後直接給了threshold，不直接使用initialCapacity而是這樣做的原因是一開始的時候map的底層容器table尚未初始化，這個操作被放到了第一次put上，所以當我們第一次添加元素的時候，才會根據指定的初始大小去初始化容器。
2.只有初始容量的構造方法
構造一個具有指定初始容量和默認負載因子（0.75）的空HashMap。
public HashMap(int initialCapacity) {
//直接調用 HashMap(int initialCapacity, float loadFactor)構造方法
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
3.無參構造方法
構造一個具有指定初始容量（16）和默認負載因子（0.75）的空HashMap。
public HashMap() {
//全部使用默認值
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
4、有一個Map類型的參數的構造方法
使用與指定Map相同的映射構造一個新的HashMap。使用默認的負載因子（0.75）和足以將映射保存在指定Map中的初始容量創建HashMap。
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
這裡調用了putMapEntries()方法，我們待會再細說，現在先簡單里理解為根據一個已經存在的Map集合去創建一個新Map集合，有點類似於Arrays.copyOf()方法。
四、HashMap的put
我們從上文可以知道，當構造函數執行完畢以後，並沒有真正的開闢HashMap的數據存儲空間，而是等到第一次put的時候才會為table分配空間。
1.put操作的實現
HashMap中有一個put()方法：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
它的注釋是這樣描述的：
將指定值與該映射中的指定鍵相關聯。如果該映射先前包含該鍵的映射，則將替換舊值。
簡單的來說，就是兩個功能：
- 將值與建關聯
- 如果新值對應的鍵已有舊值，則替換舊值
我們可以看到，實際上這個方法通過hash（）和putVal() 兩個方法來實現。
2.計算桶容器下標
桶容器下標通過三個步驟來計算：獲取哈希值，異或運算混合高低位得到新哈希，新哈希和長度與運算獲取下標。
我們看看hash()方法的源碼：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這裡的hashCode()方法是一個Native方法，原理是將對象的記憶體地址轉為一個整數以獲取對象哈希值。
這一個方法先調用了一個 key.hashCode()方法獲取了key的哈希值，然後將哈希值與哈希值的高16位做異或運算。
而在下面的putVal()方法中，又通過類似下面三行程式碼進行取模：
//n為新桶數組長度
n = (tab = resize()).length;
//進行與運算取模
(n - 1) & hash
從網上看到一張很形象的圖：
我們來理解一下：
-
我們先看與運算取模。一方面位與運算運算快；另一方面由於長度必然是2的冪，所以轉二進位有效位必然全是1，與運算的時候可以充分散列表。
-
異或運算混合高低位：為了將哈希值的高位和低位混合，以增加隨機性。
比如數組table的長度比較小的時候（比如圖中的長度就只有4），也能保證考慮到哈希值的高低位都參與計算中。
為了更明確的說明長度取2的冪有助於充分散列避免哈希碰撞，這裡舉個特別明顯的例子：
當HashMap的容量是16時，它的二進位是10000，(n-1)的二進位是01111，與hash值得計算結果如下：
上面四種情況我們可以看出，不同的hash值，和(n-1)進行位運算後，能夠得出不同的值，使得添加的元素能夠均勻分布在集合中不同的位置上，避免hash碰撞。
下面就來看一下HashMap的容量不是2的n次冪的情況，當容量為10時，二進位為01010，(n-1)的二進位是01001，向裡面添加同樣的元素，結果為：
可以看出，有三個不同的元素進過&運算得出了同樣的結果（01001），嚴重的hash碰撞了。
3.將元素加入桶數組
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判斷鍵值對數組table[i]是否為空或為null，否則執行resize()進行擴容
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);
//插入後鏈表長度大於8就轉換成紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(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 key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果超過最大容量就擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
五、HashMap的get
1.get操作的實現
我們看看get()方法的注釋和源碼：
返回指定鍵所映射到的值；如果此映射不包含鍵的映射關係，則返回null。更正式地講，如果此映射包含從鍵k到值v的映射，使得（key == null？k == null：key.equals（k）），則此方法返回v；否則，返回v。否則返回null。 （最多可以有一個這樣的映射。）返回值null不一定表示該映射不包含該鍵的映射；它的返回值為0。映射也可能將鍵顯式映射為null。 containsKey操作可用於區分這兩種情況。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
我們可以看到實際上調用了getNode()方法：
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//確保table不為空，並且計算得到的下標對應table的位置上有節點
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//判斷第一個節點是不是要找的key
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;
}
2.為什麼重寫equals還要重寫hashcode？
首先，不被原本的的hashCode和equals是這樣的
- hashCode值是根據記憶體地址換算出來的一個值
- equals方法是判斷兩個對象記憶體地址是否相等
我們回顧一下上文，可以看到無論put()還是get()都會有類似這樣的語句：
p.hash == hash && (key != null && key.equals(k))
當我們試圖添加或者找到一個key的時候，方法會去判斷哈希值是否相等和值是否相等，都相等的時候才會判斷這個key就是要獲取的key。也就是說，嚴格意義上，一個HashMap里是不允許出現相同的key的。
當我們使用對象作為key的時候，根據原本的hashCode和equals仍然能保證key的唯一性。但是當我們重寫了equals方法而不重寫hashCode()方法時，可能出現值相等但是因為地址不相等導致哈希值不同，最後導致出現兩個相同的key的情況。
我們舉個例子：
我們現在有一個類：
/**
* @Author：CreateSequence
* @Date：2020-08-14 16:15
* @Description：Student類，重寫了equals方法
*/
public class Student {
String name;
Integer age;
/**
* 重寫了equals方法
* @param obj
* @return
*/
@Override
public boolean equals(Object obj) {
Student student = (Student) obj;
return (this.name == student.name) && (this.age == student.age);
}
public Student(String name, Integer age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
然後我們試試看：
public static void main( String[] args ) {
HashMap<Student,Integer> map = new HashMap(16);
Student student1 = new Student("小明", 21);
map.put(student1, 1);
Student student2 = new Student("小明", 21);
System.out.println("這個key已經存在了嗎？"+map.containsKey(student2));
System.out.println(map.get(student2));
}
//輸出結果
這個key已經存在了嗎？false
null
可以看到，因為hashCode()得到的值不同，在map中他們被當成了不同的key。
而當我們重寫了Student類的hashCode()方法以後：
@Override
public int hashCode() {
return age;
}
執行結果就變成：
這個key已經存在了嗎？true
1
可見重寫equals還要重寫hashcode的必要性。
參考：
六、HashMap的擴容
1.resize操作的實現
話不多說，我們直接源碼
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//舊桶容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//要擴容的大小
int oldThr = threshold;
int newCap, newThr = 0;
//如果桶已經配初始化過了
if (oldCap > 0) {
//如果擴容到極限大小，就不再繼續擴容了
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//否則就擴容到原來的兩倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//如果未初始化，並且指定了初始容量，則初始容量即為第一次擴容的目標大小
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//否則使用默認初始容量，並且根據默認初始容量和載入因子計算得到下次擴容大小
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//重新下一次計算擴容大小
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//將舊容器複製到新容器中
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//把每一個桶移動到新桶中
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//判斷是否為紅黑樹
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//否則就遍歷鏈表
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//哈希值與原長度進行與運算，如果多出來那一位是0，就保持原下標
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//如果多出來那一位是1，就移動到（原下標+原長度）對應的新位置
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//放回新桶的原位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//放回新位置
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
2.為什麼JDK8不需要重哈希了？
我們知道，如果桶數組擴容了，那麼數組長度也就變了，那麼put和get的時候根據長度與哈希進行與運算的時候計算出來的下標就不一樣。在JDK7擴容移動舊容器的數據的時候，會進行重哈希獲得新索引，而在JDK8進行了優化。
因為桶數組長度總是2的冪，所以擴容以後翻倍，轉換為二進位的時候就會比原來多一位，如果我們假設桶數組為n，則有：
n = 16 -> 10000; (n-1) - > 1111;
n = 32 -> 100000; (n-1) - > 11111;
n = 64 -> 1000000; (n-1) - > 111111;
n = 128 -> 10000000; (n-1) - > 1111111;
我們舉例子驗證一下，如下圖：
（a）是n=16時，key1與key2跟（n-1）與運算得到的二進位下標；（b）是擴容後n=32時，key1與key2跟（n-1）與運算得到的二進位下標。
我們可以看到key2進了一位，多出來這一位相當於多了10000，轉為十進位就是在原基礎上加16，也就是加上了原桶數組的長度，反映到程式碼里，就是 newTab[j + oldCap] = hiHead;這一句程式碼；
現在在看看key1，我們看到key1的索引並沒有移動，因為key多出來的那一位是0，所以與運算後還是0，最後得到的下標跟原來的一樣。
所以我們可以總結一下：
- 哈希值與原長度（注意是n不是n-1）進行與運算，判斷多出來的那一位是0還是1
- 如果是0就留在原來的位置
- 如果是1就移動到（原下標 + 原長度）對應下標的新位置
這樣做的好處除了不需要重新計算哈希值以外；由於哈希值多處來的一位數可能是0也可能是1，這樣就讓原本在同一條鏈表的上元素有可能可以在擴容後移動到新位置，有效緩解了哈希碰撞。
七、HashMap執行緒不安全
我們知道HashMap是執行緒不安全的，執行緒安全的Map集合是ConcurrentHashMap。事實上，HashMap的執行緒不安全在JDK7和JDK8表現不同：
- 在JDK7因為resize過程使用了頭插法，導致多執行緒環境下可能會產生死循環，數據覆蓋和數據丟失等問題
- JDK8解決了死循環問題，但是在擴後的添加中仍然會在多執行緒環境下出現數據覆蓋的問題
1.JDK7頭插法導致死循環
在JDK7中，錯誤出現在擴容方法transfer中，其程式碼如下：
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
//遍歷鏈表，當前節點為e
while(null != e) {
//獲取當前節點的下一個節點next
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;
e = next;
}
}
}
從程式碼中我們可以看到，擴容後重新計算了元素的下標，並採用頭插法將表元素移插到新鏈表上。
舉個例子：
假設執行緒A執行緒B同時對下圖集合擴容：
1.A先執行，在newTable[i] = e前時間片耗盡被掛起，此時e = 1，e.next = null，next = 2
2.執行緒B執行數組擴容，擴容完以後對於執行緒A就是現在這樣，此時next.next = 1，e.next = null，next = 2：
3.接著執行緒B掛起，執行緒A繼續執行 newTable[i] = e以後的程式碼，執行完畢後e = 2，next = 2，e.next = 1：
4.執行緒A接著下一次循環，由於e.next = 1，於是next = 1，頭插法把2插入newTable[i]中，執行完畢以後e = 1，next = e.next = null：
5.執行緒A執行最後一次循環，此時由於e.next = newTable[i]，所以e.next = 2，然後接著 newTable[i] = e ，也就是說1又被插回newTable[i]的位置：
這個時候最危險的事情發生了：e = 1，e.next =2 ，e.next.next = 1，說明2和1已經形成了一個環形鏈表：
在此之後會無線循環1和2的頭插，造成死循環。
2.JDK8數據覆蓋
DK7中也有這個問題。
我們知道put()方法在插入時會對插入位置進行非空判斷，如果兩個執行緒都判斷同一個位置為空，那麼先執行插入的數據就會被後一個覆蓋。
