HashMap痢法、HashTable、ConcurrentHashMap

a.線程安全問題
HashMap是線程不安全的，多線程環(huán)境下可能會導致死循環(huán)（HashMap擴容時）锄列，key可以為null；
在jdk1.7中惯悠，HashMap底層是通過“數(shù)組 + 鏈表”的實現(xiàn)方式邻邮，put使用頭插法（多線程情況下擴容時可能會出現(xiàn)鏈表環(huán)）；
在jdk1.8中克婶，HashMap底層是通過“數(shù)組+鏈表+紅黑樹”的方式筒严，當鏈表節(jié)點較少時（<=8），使用鏈表鸠补，當鏈表節(jié)點較多時（>8且size()>64萝风，當size小于64的時候會執(zhí)行擴容）轉(zhuǎn)為紅黑樹，put使用尾插法紫岩。
數(shù)據(jù)不一致：
當多個線程同時想hashMap中put數(shù)據(jù)時规惰，當出現(xiàn)一個以上的線程put的數(shù)據(jù)的坐標一致時，可能會導致一個線程的數(shù)據(jù)修改被覆蓋泉蝌，導致數(shù)據(jù)不一致歇万。原理如同數(shù)據(jù)庫的事務，數(shù)據(jù)被覆蓋勋陪。
死循環(huán)：
在HasMap擴容時贪磺，多線程的擴容會導致在rehash鏈表的時候，有可能會導致死循環(huán)诅愚。

HashMap的put方法
1.首先 Put 方法接收到 key 和 value 時寒锚，會先利用 key 進行哈希算法得到這個 key 對應的值Hash。
2．再通過這個哈希值與數(shù)組長度-1進行與操作得到一個數(shù)組下標
3.．再判斷數(shù)組下標位置是不是空著违孝，如果空著刹前，則直接把 key 和 value 封裝為一個 Node 對象并存入此數(shù)組位置。
4．如果此下標位置上非空雌桑，表示此位置上存在 Node 對象喇喉，那么則判斷該 Node 對象是不是一個紅黑樹節(jié)點，如果是則將 key 和 value 封裝為一個紅黑樹節(jié)點并添加到紅黑樹中去校坑，在這個過程中會判斷紅黑樹中是否存在當前 key 拣技，如果存在則更新value千诬。
5．如果此位置上的 Node 對象是鏈表節(jié)點，則將 key 和 value 封裝為一個鏈表 Node 并插入到鏈表中去膏斤。
6．插入到鏈表中后徐绑，會判斷鏈表的節(jié)點個數(shù)是不是超過了8個，如果超過則把當前位置的鏈表轉(zhuǎn)化為紅黑樹掸绞。
7．插入鏈表使用的是尾插法泵三，所以需要遍歷鏈表，而在這個過程中也會去判斷 key 是否存在衔掸，如果存在則更新 value烫幕。

b.實現(xiàn)原理
HashTable與HashMap實現(xiàn)原理是一樣的，但是HashTable的get和put方法都是synchronized操作敞映，不允許key和value為null较曼，因此HashTable的性能是比較差的。
總結：

c.ConcurrentHashMap
ConcurrentHashMap避免了HashTable對全局加鎖改成了局部加鎖操作振愿，這樣就極大地提高了并發(fā)環(huán)境下的操作速度捷犹。
在jdk1.7中，ConcurrentHashMap采用了“數(shù)組 + Segment + 分段鎖”的方式實現(xiàn)冕末，其中每個Segment內(nèi)部是一個Entry數(shù)組萍歉，數(shù)組中的每個元素又是一個鏈表，ConcurrentHashMap在每個Segment上加鎖档桃，這樣當一個線程占用鎖訪問其中一個段數(shù)據(jù)的時候枪孩，其他段的數(shù)據(jù)也能被其他線程訪問，能夠?qū)崿F(xiàn)真正的并發(fā)訪問藻肄，實現(xiàn)了粗粒度的分段鎖蔑舞。

ConcurrentHashMap內(nèi)部結構圖.jpg

ConcurrentHashMap訪問一個數(shù)據(jù)時，需要兩次Hash操作嘹屯，第一次Hash定位到Segment攻询，第二次Hash定位到元素所在鏈表的頭部。因此這也是Segment方案的查詢性能比較慢的原因州弟。
在jdk1.8中钧栖，ConcurrentHashMap參考了JDK8 HashMap的實現(xiàn)，采用了“數(shù)組+鏈表+紅黑樹“”來實現(xiàn)婆翔。同時拋棄了Segment轉(zhuǎn)而采用的是Node桐经，每個node保存有key、value和key的Hash值浙滤，其中value和next都是用volatile修飾，保證并發(fā)可見气堕。
ConcurrentHashMap內(nèi)部大量采用CAS(compare and swap)操作纺腊，CAS 操作包含三個操作數(shù) —— 內(nèi)存位置（V）畔咧、預期原值（A）和新值(B)。如果內(nèi)存地址里面的值和A的值是一樣的揖膜，那么就將內(nèi)存里面的值更新成B誓沸。CAS是通過無限循環(huán)來獲取數(shù)據(jù)的，若果在第一輪循環(huán)中壹粟，a線程獲取地址里面的值被b線程修改了拜隧，那么a線程需要自旋，到下次循環(huán)才有可能機會執(zhí)行趁仙。
put加鎖位置
put的過程如下：
1.當存放數(shù)據(jù)的Node<K,V>[] table數(shù)組為null或者length=0的時候初始化table數(shù)組洪添；
2.當key的hash值對應的Node<K,V>[] table數(shù)組的坐標值為null的時候，使用CAS進行賦值雀费；
3.當Node<K,V>[] table數(shù)組正在擴容干奢，那么當前線程參與擴容，使用helpTransfer方法盏袄；
4.否則對key的hash值對應的Node<K,V>[] table數(shù)組的坐標對象進行synchronized加鎖忿峻，如果是鏈表，那么使用尾插法進行插入辕羽；如果是紅黑樹逛尚，則插入紅黑樹；

加鎖的位置是在Node<K,V>[] table數(shù)組中的節(jié)點刁愿，即不會加鎖到鏈表的非head節(jié)點绰寞，也不會加鎖的紅黑樹的非根節(jié)點。

擴容問題
jdk1.7的HashMap擴容
jdk1.8的HashMap擴容
jdk1.7的ConcurrentHashMap擴容
jdk1.8的ConcurrentHashMap擴容
ConcurrentHashMap擴容時酌毡，按照正常的邏輯所有的讀寫都要阻塞克握，但是大牛就是神一樣的存在，Doug lea（膜拜一下）對ConcurrentHashMap擴容做了優(yōu)化枷踏，具體思路是：在ConcurrentHashMap擴容時菩暗，如果有讀寫線程進來，那么可以讓這些讀寫線程參與到擴容中旭蠕，這樣加快了擴容停团，而且讀寫線程也不需要始終等待。

ConcurrentHashMap引入了ForwardingNode類掏熬，當線程發(fā)起擴容時佑稠，就會更改sizeCtl的值

    /**
     * Table initialization and resizing control.  When negative, the
     * table is being initialized or resized: -1 for initialization,
     * else -(1 + the number of active resizing threads).  Otherwise,
     * when table is null, holds the initial table size to use upon
     * creation, or 0 for default. After initialization, holds the
     * next element count value upon which to resize the table.
     */
    private transient volatile int sizeCtl;

對于擴容時的讀操作
如果當前節(jié)點有數(shù)據(jù)，還沒有遷移走旗芬，則可以直接讀舌胶，不影響；
如果當前節(jié)點已經(jīng)遷移走疮丛，那么都節(jié)點會設置成fwd節(jié)點幔嫂，此時讀線程會參與到擴容中辆它。

對于擴容時的寫或者刪除操作
如果當前節(jié)點已經(jīng)遷移走，那么都節(jié)點會設置成fwd節(jié)點履恩，此時讀線程會參與到擴容中锰茉；
如果當前節(jié)點有數(shù)據(jù)，還沒有遷移走切心，當前鏈表的頭結點會被鎖住飒筑，寫或者刪除操作會被阻塞，直到擴容完成绽昏。

總結如下：