本文準(zhǔn)備從以下幾個方面去講解HashMap：
1）HashMap源碼詳細(xì)分析
2）HashMap為什么是線程不安全的竞穷？
3）HashMap和HashTable的區(qū)別
4）1.7和1.8的HashMap實現(xiàn)區(qū)別總結(jié)
HashMap源碼分析
一贯吓、構(gòu)造函數(shù)
讓我們先從構(gòu)造函數(shù)說起，HashMap有四個構(gòu)造方法弓柱，別慌
1.1 HashMap()
// 1.無參構(gòu)造方法沟堡、
// 構(gòu)造一個空的HashMap疮鲫，初始容量為16，負(fù)載因子為0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
無參構(gòu)造方法就沒什么好說的了弦叶。
1.2 HashMap(int initialCapacity)
// 2.構(gòu)造一個初始容量為initialCapacity，負(fù)載因子為0.75的空的HashMap妇多，
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
HashMap(int initialCapacity) 這個構(gòu)造方法調(diào)用了1.3中的構(gòu)造方法伤哺。
1.3 HashMap(int initialCapacity, float loadFactor)
// 3.構(gòu)造一個空的初始容量為initialCapacity，負(fù)載因子為loadFactor的HashMap
public HashMap(int initialCapacity, float loadFactor) {
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);
}
//最大容量
//static final int MAXIMUM_CAPACITY = 1 << 30;
當(dāng)指定的初始容量< 0時拋出IllegalArgumentException異常者祖，當(dāng)指定的初始容量> MAXIMUM_CAPACITY時立莉，就讓初始容量 = MAXIMUM_CAPACITY。當(dāng)負(fù)載因子小于0或者不是數(shù)字時七问，拋出IllegalArgumentException異常蜓耻。
設(shè)定threshold。 這個threshold = capacity * load factor 械巡。當(dāng)HashMap的size到了threshold時刹淌，就要進(jìn)行resize，也就是擴(kuò)容讥耗。
tableSizeFor()的主要功能是返回一個比給定整數(shù)大且最接近的2的冪次方整數(shù)有勾，如給定10，返回2的4次方16.
我們進(jìn)入tableSizeFor(int cap)的源碼中看看：
//Returns a power of two size for the given target capacity.
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
note： HashMap要求容量必須是2的冪古程。
首先蔼卡，int n = cap -1是為了防止cap已經(jīng)是2的冪時，執(zhí)行完后面的幾條無符號右移操作之后挣磨，返回的capacity是這個cap的2倍雇逞，因為cap已經(jīng)是2的冪了，就已經(jīng)滿足條件了茁裙。 如果不懂可以往下看完幾個無符號移位后再回來看塘砸。（建議自己在紙上畫一下）
- 如果n這時為0了（經(jīng)過了cap-1之后），則經(jīng)過后面的幾次無符號右移依然是0呜达，最后返回的capacity是1（最后有個n+1的操作）谣蠢。這里只討論n不等于0的情況。
以16位為例查近，假設(shè)開始時 n 為 0000 1xxx xxxx xxxx （x代表不關(guān)心0還是1）
-
第一次右移
n |= n >>> 1;由于n不等于0眉踱，則n的二進(jìn)制表示中總會有一bit為1，這時考慮最高位的1霜威。通過無符號右移1位谈喳，則將最高位的1右移了1位，再做或操作戈泼，使得n的二進(jìn)制表示中與最高位的1緊鄰的右邊一位也為1婿禽，如0000 11xx xxxx xxxx 赏僧。
-
第二次右移
n |= n >>> 2;注意，這個n已經(jīng)經(jīng)過了
n |= n >>> 1;操作扭倾。此時n為0000 11xx xxxx xxxx 淀零，則n無符號右移兩位，會將最高位兩個連續(xù)的1右移兩位膛壹，然后再與原來的n做或操作驾中，這樣n的二進(jìn)制表示的高位中會有4個連續(xù)的1。如0000 1111 xxxx xxxx 模聋。 -
第三次右移
n |= n >>> 4;這次把已經(jīng)有的高位中的連續(xù)的4個1肩民，右移4位，再做或操作链方，這樣n的二進(jìn)制表示的高位中會有8個連續(xù)的1持痰。如0000 1111 1111 xxxx 。
第祟蚀。工窍。。暂题，你還忍心讓我繼續(xù)推么移剪？相信聰明的你已經(jīng)想出來了，容量最大也就是32位的正數(shù)薪者，所以最后一次 n |= n >>> 16; 可以保證最高位后面的全部置為1纵苛。當(dāng)然如果是32個1的話，此時超出了MAXIMUM_CAPACITY 言津，所以取值到 MAXIMUM_CAPACITY 攻人。
從https://blog.csdn.net/huzhigenlaohu/article/details/51802457這篇博客中找了張示例圖：
注意，得到的這個capacity卻被賦值給了threshold悬槽。 這里我和這篇博客的博主開始的想法一樣怀吻，認(rèn)為應(yīng)該這么寫：this.threshold = tableSizeFor(initialCapacity) * this.loadFactor; 因為這樣子才符合threshold的定義：threshold = capacity * load factor 。但是初婆，請注意蓬坡，在構(gòu)造方法中，并沒有對table這個成員變量進(jìn)行初始化磅叛，table的初始化被推遲到了put方法中屑咳，在put方法中會對threshold重新計算 。
我說一下我在理解這個tableSizeFor函數(shù)中間遇到的坑吧弊琴，我在想如果n=-1時的情況兆龙，因為初始容量可以傳進(jìn)來0。我將n= -1 和下面幾條運算一起新寫了個測試程序敲董，發(fā)現(xiàn)輸出都是 -1紫皇。 這是因為計算機(jī)中數(shù)字是由補(bǔ)碼存儲的慰安，-1的補(bǔ)碼是 0xffffffff。所以無符號右移之后再進(jìn)行或運算之后還是 -1聪铺。 那我想如果就無符號右移呢化焕？ 比如-1>>>10。聽我娓娓道來铃剔，32個1無符號右移10位后锣杂，高10位為0，低22位為1番宁，此時這個數(shù)變成了正數(shù)，由于正數(shù)的補(bǔ)碼和原碼相同赖阻，所以就變成了0x3FFFFF即10進(jìn)制的4194303蝶押。真刺激。
好開森火欧，這個構(gòu)造方法我們算是拿下了棋电。怎么樣，我猜你現(xiàn)在一定很激動苇侵，Hey赶盔，old Fe，這才剛開始榆浓。接下來看最后一個構(gòu)造方法伙判。
1.4 HashMap(Map<? extends K, ? extends V> m)
// 4. 構(gòu)造一個和指定Map有相同mappings的HashMap蛹锰，初始容量能充足的容下指定的Map,負(fù)載因子為0.75
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
套路，直接看 putMapEntries(m,false) 。源碼如下：
/**
* 將m的所有元素存入本HashMap實例中
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//得到 m 中元素的個數(shù)
int s = m.size();
//當(dāng) m 中有元素時弟胀，則需將map中元素放入本HashMap實例。
if (s > 0) {
// 判斷table是否已經(jīng)初始化邢疙，如果未初始化庇勃，則先初始化一些變量。（table初始化是在put時）
if (table == null) { // pre-size
// 根據(jù)待插入的map 的 size 計算要創(chuàng)建的 HashMap 的容量脊阴。
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 把要創(chuàng)建的 HashMap 的容量存在 threshold 中
if (t > threshold)
threshold = tableSizeFor(t);
}
// 如果table初始化過握侧，因為別的函數(shù)也會調(diào)用它，所以有可能HashMap已經(jīng)被初始化過了嘿期。
// 判斷待插入的 map 的 size,若 size 大于 threshold品擎，則先進(jìn)行 resize()，進(jìn)行擴(kuò)容
else if (s > threshold)
resize();
//然后就開始遍歷 帶插入的 map 秽五，將每一個 <Key ,Value> 插入到本HashMap實例孽查。
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
// put(K,V)也是調(diào)用 putVal 函數(shù)進(jìn)行元素的插入
putVal(hash(key), key, value, false, evict);
}
}
}
介紹putVal方法前，說一下HashMap的幾個重要的成員變量：
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
//實際存儲key坦喘，value的數(shù)組盲再，只不過key西设，value被封裝成Node了
transient Node<K,V>[] table;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
//因為 tableSizeFor(int) 返回值給了threshold
int threshold;
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
其實就是哈希表。HashMap使用鏈表法避免哈希沖突（相同hash值）答朋，當(dāng)鏈表長度大于TREEIFY_THRESHOLD（默認(rèn)為8）時贷揽，將鏈表轉(zhuǎn)換為紅黑樹，當(dāng)然小于UNTREEIFY_THRESHOLD（默認(rèn)為6）時梦碗，又會轉(zhuǎn)回鏈表以達(dá)到性能均衡禽绪。 我們看一張HashMap的數(shù)據(jù)結(jié)構(gòu)（數(shù)組+鏈表+紅黑樹 ）就更能理解table了：
再回到putMapEntries函數(shù)中，如果table為null洪规，那么這時就設(shè)置合適的threshold印屁，如果不為空并且指定的map的size>threshold，那么就resize()斩例。然后把指定的map的所有Key雄人，Value，通過putVal添加到我們創(chuàng)建的新的map中念赶。
putVal中傳入了個hash(key)础钠，那我們就先來看看hash(key):
/**
* key 的 hash值的計算是通過hashCode()的高16位異或低16位實現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)
* 主要是從速度、功效叉谜、質(zhì)量來考慮的旗吁，這么做可以在數(shù)組table的length比較小的時候
* 也能保證考慮到高低Bit都參與到Hash的計算中，同時不會有太大的開銷
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
異或運算：(h = key.hashCode()) ^ (h >>> 16)
原 來 的 hashCode : 1111 1111 1111 1111 0100 1100 0000 1010
移位后的hashCode: 0000 0000 0000 0000 1111 1111 1111 1111
進(jìn)行異或運算 結(jié)果：1111 1111 1111 1111 1011 0011 1111 0101
這樣做的好處是停局，可以將hashcode高位和低位的值進(jìn)行混合做異或運算很钓，而且混合后，低位的信息中加入了高位的信息董栽，這樣高位的信息被變相的保留了下來履怯。摻雜的元素多了，那么生成的hash值的隨機(jī)性會增大裆泳。
剛才我們漏掉了resize()和putVal() 兩個函數(shù)叹洲，現(xiàn)在我們按順序分析一波：
首先resize() ,先看一下哪些函數(shù)調(diào)用了resize()，從而在整體上有個概念：
接下來上源碼：
final Node<K,V>[] resize() {
// 保存當(dāng)前table
Node<K,V>[] oldTab = table;
// 保存當(dāng)前table的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 保存當(dāng)前閾值
int oldThr = threshold;
// 初始化新的table容量和閾值
int newCap, newThr = 0;
/*
1. resize（）函數(shù)在size > threshold時被調(diào)用工禾。oldCap大于 0 代表原來的 table 表非空运提，
oldCap 為原表的大小，oldThr（threshold） 為 oldCap × load_factor
*/
if (oldCap > 0) {
// 若舊table容量已超過最大容量闻葵，更新閾值為Integer.MAX_VALUE（最大整形值）民泵，這樣以后就不會自動擴(kuò)容了。
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
}
/*
2. resize（）函數(shù)在table為空被調(diào)用。oldCap 小于等于 0 且 oldThr 大于0，代表用戶創(chuàng)建了一個 HashMap鳞尔，但是使用的構(gòu)造函數(shù)為
HashMap(int initialCapacity, float loadFactor) 或 HashMap(int initialCapacity)
或 HashMap(Map<? extends K, ? extends V> m)嬉橙，導(dǎo)致 oldTab 為 null，oldCap 為0寥假， oldThr 為用戶指定的 HashMap的初始容量市框。
*/
else if (oldThr > 0) // initial capacity was placed in threshold
//當(dāng)table沒初始化時，threshold持有初始容量糕韧。還記得threshold = tableSizeFor(t)么;
newCap = oldThr;
/*
3. resize（）函數(shù)在table為空被調(diào)用枫振。oldCap 小于等于 0 且 oldThr 等于0，用戶調(diào)用 HashMap()構(gòu)造函數(shù)創(chuàng)建的 HashMap萤彩，所有值均采用默認(rèn)值粪滤，oldTab（Table）表為空，oldCap為0雀扶，oldThr等于0额衙，
*/
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 新閾值為0
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"})
// 初始化table
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把 oldTab 中的節(jié)點 reHash 到 newTab 中去
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 若節(jié)點是單個節(jié)點，直接在 newTab 中進(jìn)行重定位
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 若節(jié)點是 TreeNode 節(jié)點怕吴，要進(jìn)行 紅黑樹的 rehash 操作
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 若是鏈表，進(jìn)行鏈表的 rehash 操作
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 將同一桶中的元素根據(jù)(e.hash & oldCap)是否為0進(jìn)行分割（代碼后有圖解县踢，可以回過頭再來看）转绷，分成兩個不同的鏈表，完成rehash
do {
next = e.next;
// 根據(jù)算法 e.hash & oldCap 判斷節(jié)點位置rehash 后是否發(fā)生改變
//最高位==0硼啤，這是索引不變的鏈表议经。
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//最高位==1 （這是索引發(fā)生改變的鏈表）
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) { // 原bucket位置的尾指針不為空(即還有node)
loTail.next = null; // 鏈表最后得有個null
newTab[j] = loHead; // 鏈表頭指針放在新桶的相同下標(biāo)(j)處
}
if (hiTail != null) {
hiTail.next = null;
// rehash 后節(jié)點新的位置一定為原來基礎(chǔ)上加上 oldCap，具體解釋看下圖
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
}
引自美團(tuán)點評技術(shù)博客谴返。我們使用的是2次冪的擴(kuò)展(指長度擴(kuò)為原來2倍)煞肾，所以，元素的位置要么是在原位置嗓袱，要么是在原位置再移動2次冪的位置籍救。看下圖可以明白這句話的意思渠抹，n為table的長度蝙昙，圖（a）表示擴(kuò)容前的key1和key2兩種key確定索引位置的示例，圖（b）表示擴(kuò)容后key1和key2兩種key確定索引位置的示例梧却，其中hash1是key1對應(yīng)的哈希與高位運算結(jié)果奇颠。
元素在重新計算hash之后，因為n變?yōu)?倍放航，那么n-1的mask范圍在高位多1bit(紅色)烈拒，因此新的index就會發(fā)生這樣的變化：
因此，我們在擴(kuò)充HashMap的時候，只需要看看原來的hash值新增的那個bit是1還是0就好了荆几，是0的話索引沒變吓妆，是1的話索引變成“原索引+oldCap”，可以看看下圖為16擴(kuò)充為32的resize示意圖 ：
什么時候擴(kuò)容：通過HashMap源碼可以看到是在put操作時伴郁，即向容器中添加元素時耿战，判斷當(dāng)前容器中元素的個數(shù)是否達(dá)到閾值（當(dāng)前數(shù)組長度乘以加載因子的值）的時候，就要自動擴(kuò)容了焊傅。
擴(kuò)容(resize)：其實就是重新計算容量剂陡；而這個擴(kuò)容是計算出所需容器的大小之后重新定義一個新的容器，將原來容器中的元素放入其中狐胎。
resize()告一段落鸭栖，接下來看 putVal() 。
上源碼：
//實現(xiàn)put和相關(guān)方法握巢。
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為空或者長度為0晕鹊，則resize()
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//確定插入table的位置，算法是(n - 1) & hash暴浦，在n為2的冪時溅话，相當(dāng)于取摸操作。
////找到key值對應(yīng)的槽并且是第一個歌焦，直接加入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//在table的i位置發(fā)生碰撞飞几，有兩種情況，1独撇、key值是一樣的屑墨，替換value值，
//2纷铣、key值不一樣的有兩種處理方式：2.1卵史、存儲在i位置的鏈表；2.2搜立、存儲在紅黑樹中
else {
Node<K,V> e; K k;
//第一個node的hash值即為要加入元素的hash
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//2.2
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//2.1
else {
//不是TreeNode,即為鏈表,遍歷鏈表
for (int binCount = 0; ; ++binCount) {
///鏈表的尾端也沒有找到key值相同的節(jié)點以躯，則生成一個新的Node,
//并且判斷鏈表的節(jié)點個數(shù)是不是到達(dá)轉(zhuǎn)換成紅黑樹的上界達(dá)到，則轉(zhuǎn)換成紅黑樹啄踊。
if ((e = p.next) == null) {
// 創(chuàng)建鏈表節(jié)點并插入尾部
p.next = newNode(hash, key, value, null);
////超過了鏈表的設(shè)置長度8就轉(zhuǎn)換成紅黑樹
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;
}
}
//如果e不為空就替換舊的oldValue值
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;
}
注：hash 沖突發(fā)生的幾種情況：
1.兩節(jié)點key 值相同（hash值一定相同）寸潦，導(dǎo)致沖突；
2.兩節(jié)點key 值不同社痛，由于 hash 函數(shù)的局限性導(dǎo)致hash 值相同见转，沖突；
3.兩節(jié)點key 值不同蒜哀，hash 值不同斩箫，但 hash 值對數(shù)組長度取模后相同吏砂，沖突；
相比put方法乘客，get方法就比較簡單狐血，這里就不說了。
1.7和1.8的HashMap的不同點
（1）JDK1.7用的是頭插法易核，而JDK1.8及之后使用的都是尾插法匈织，那么為什么要這樣做呢？因為JDK1.7是用單鏈表進(jìn)行的縱向延伸牡直，當(dāng)采用頭插法就是能夠提高插入的效率缀匕，但是也會容易出現(xiàn)逆序且環(huán)形鏈表死循環(huán)問題。但是在JDK1.8之后是因為加入了紅黑樹使用尾插法碰逸，能夠避免出現(xiàn)逆序且鏈表死循環(huán)的問題乡小。
（2）擴(kuò)容后數(shù)據(jù)存儲位置的計算方式也不一樣：
- 在JDK1.7的時候是直接用hash值和需要擴(kuò)容的二進(jìn)制數(shù)進(jìn)行&（這里就是為什么擴(kuò)容的時候為啥一定必須是2的多少次冪的原因所在，因為如果只有2的n次冪的情況時最后一位二進(jìn)制數(shù)才一定是1饵史，這樣能最大程度減少hash碰撞）（hash值 & length-1） 满钟。
- 而在JDK1.8的時候直接用了JDK1.7的時候計算的規(guī)律，也就是擴(kuò)容前的原始位置+擴(kuò)容的大小值=JDK1.8的計算方式胳喷，而不再是JDK1.7的那種異或的方法湃番。但是這種方式就相當(dāng)于只需要判斷Hash值的新增參與運算的位是0還是1就直接迅速計算出了擴(kuò)容后的儲存方式。
（3）JDK1.7的時候使用的是數(shù)組+ 單鏈表的數(shù)據(jù)結(jié)構(gòu)吭露。但是在JDK1.8及之后時吠撮，使用的是數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)（當(dāng)鏈表的深度達(dá)到8的時候，也就是默認(rèn)閾值奴饮，就會自動擴(kuò)容把鏈表轉(zhuǎn)成紅黑樹的數(shù)據(jù)結(jié)構(gòu)來把時間復(fù)雜度從O（N）變成O（logN）提高了效率）。
HashMap為什么是線程不安全的择浊？
HashMap 在并發(fā)時可能出現(xiàn)的問題主要是兩方面：
- put的時候?qū)е碌亩嗑€程數(shù)據(jù)不一致
比如有兩個線程A和B戴卜，首先A希望插入一個key-value對到HashMap中，首先計算記錄所要落到的 hash桶的索引坐標(biāo)琢岩，然后獲取到該桶里面的鏈表頭結(jié)點投剥，此時線程A的時間片用完了，而此時線程B被調(diào)度得以執(zhí)行担孔，和線程A一樣執(zhí)行江锨，只不過線程B成功將記錄插到了桶里面，假設(shè)線程A插入的記錄計算出來的 hash桶索引和線程B要插入的記錄計算出來的 hash桶索引是一樣的糕篇，那么當(dāng)線程B成功插入之后啄育，線程A再次被調(diào)度運行時，它依然持有過期的鏈表頭但是它對此一無所知拌消，以至于它認(rèn)為它應(yīng)該這樣做挑豌，如此一來就覆蓋了線程B插入的記錄，這樣線程B插入的記錄就憑空消失了，造成了數(shù)據(jù)不一致的行為氓英。 - resize而引起死循環(huán)
這種情況發(fā)生在HashMap自動擴(kuò)容時侯勉，當(dāng)2個線程同時檢測到元素個數(shù)超過 數(shù)組大小 × 負(fù)載因子。此時2個線程會在put()方法中調(diào)用了resize()铝阐，兩個線程同時修改一個鏈表結(jié)構(gòu)會產(chǎn)生一個循環(huán)鏈表（JDK1.7中址貌，會出現(xiàn)resize前后元素順序倒置的情況）。接下來再想通過get()獲取某一個元素徘键，就會出現(xiàn)死循環(huán)练对。
HashMap和HashTable的區(qū)別
HashMap和Hashtable都實現(xiàn)了Map接口，但決定用哪一個之前先要弄清楚它們之間的分別啊鸭。主要的區(qū)別有：線程安全性锹淌，同步(synchronization)，以及速度赠制。
- HashMap幾乎可以等價于Hashtable赂摆，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受為null的鍵值(key)和值(value)钟些，而Hashtable則不行)烟号。
- HashMap是非synchronized，而Hashtable是synchronized政恍，這意味著Hashtable是線程安全的汪拥，多個線程可以共享一個Hashtable；而如果沒有正確的同步的話篙耗，多個線程是不能共享HashMap的迫筑。Java 5提供了ConcurrentHashMap，它是HashTable的替代宗弯，比HashTable的擴(kuò)展性更好脯燃。
- 另一個區(qū)別是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的蒙保。所以當(dāng)有其它線程改變了HashMap的結(jié)構(gòu)（增加或者移除元素）辕棚，將會拋出ConcurrentModificationException，但迭代器本身的remove()方法移除元素則不會拋出ConcurrentModificationException異常邓厕。但這并不是一個一定發(fā)生的行為逝嚎，要看JVM。這條同樣也是Enumeration和Iterator的區(qū)別详恼。
- 由于Hashtable是線程安全的也是synchronized补君，所以在單線程環(huán)境下它比HashMap要慢。如果你不需要同步昧互，只需要單一線程赚哗，那么使用HashMap性能要好過Hashtable她紫。
- HashMap不能保證隨著時間的推移Map中的元素次序是不變的。
需要注意的重要術(shù)語：
sychronized意味著在一次僅有一個線程能夠更改Hashtable屿储。就是說任何線程要更新Hashtable時要首先獲得同步鎖贿讹，其它線程要等到同步鎖被釋放之后才能再次獲得同步鎖更新Hashtable。
Fail-safe和iterator迭代器相關(guān)够掠。如果某個集合對象創(chuàng)建了Iterator或者ListIterator民褂，然后其它的線程試圖“結(jié)構(gòu)上”更改集合對象，將會拋出ConcurrentModificationException異常疯潭。但其它線程可以通過set()方法更改集合對象是允許的赊堪，因為這并沒有從“結(jié)構(gòu)上”更改集合。但是假如已經(jīng)從結(jié)構(gòu)上進(jìn)行了更改竖哩，再調(diào)用set()方法哭廉，將會拋出IllegalArgumentException異常。
結(jié)構(gòu)上的更改指的是刪除或者插入一個元素相叁，這樣會影響到map的結(jié)構(gòu)遵绰。
HashMap可以通過下面的語句進(jìn)行同步：
Map m = Collections.synchronizeMap(hashMap);
文末福利：
Java與大數(shù)據(jù)良心資源分享
本文授權(quán)后端技術(shù)精選公眾號獨家發(fā)布
