版權聲明：本文為小斑馬學習總結文章饭望，技術來源于韋東山著作，轉載請注明出處！
最近無意中發(fā)現(xiàn)有很多對Map尤其是HashMap的線程安全性的話題討論打肝，在我的理解中，對HashMap的理解中也就知道它是線程不安全的挪捕，以及HashMap的底層算法采用了鏈地址法來解決哈希沖突的知識粗梭，但是對其線程安全性的認知有限，故寫這篇博客的目的就是讓和我一樣對這塊內容不熟悉的小伙伴有一個對级零。

一断医、哈希表

這里先說一下哈希表的定義：哈希表是一種根據(jù)關鍵碼去尋找值的數(shù)據(jù)映射結構，該結構通過把關鍵碼映射的位置去尋找存放值的地方奏纪，說起來可能感覺有點復雜鉴嗤，我想我舉個例子你就會明白了，最典型的的例子就是字典序调，大家估計小學的時候也用過不少新華字典吧醉锅，如果我想要獲取“按”字詳細信息，我肯定會去根據(jù)拼音an去查找 拼音索引（當然也可以是偏旁索引）发绢，我們首先去查an在字典的位置硬耍，查了一下得到“安”，結果如下朴摊。這過程就是鍵碼映射默垄，在公式里面，就是通過key去查找f(key)甚纲。其中口锭，按就是關鍵字（key），f（）就是字典索引，也就是哈希函數(shù)鹃操，查到的頁碼4就是哈希值韭寸。

二、哈希沖突

但是問題又來了荆隘，我們要查的是“按”恩伺，而不是“安，但是他們的拼音都是一樣的椰拒。也就是通過關鍵字按和關鍵字安可以映射到一樣的字典頁碼4的位置晶渠，這就是哈希沖突（也叫哈希碰撞），在公式上表達就是key1≠key2燃观，但f(key1)=f(key2)褒脯。沖突會給查找?guī)砺闊阆胂肜禄伲惚緛聿檎业氖恰鞍础狈ǎ菂s找到“安”字，你又得向后翻一兩頁脊框，在計算機里面也是一樣道理的颁督。
但哈希沖突是無可避免的，為什么這么說呢浇雹，因為你如果要完全避開這種情況沉御，你只能每個字典去新開一個頁，然后每個字在索引里面都有對應的頁碼箫爷，這就可以避免沖突嚷节。但是會導致空間增大（每個字都有一頁）。
既然無法避免虎锚，就只能盡量減少沖突帶來的損失硫痰，而一個好的哈希函數(shù)需要有以下特點：

• 1.盡量使關鍵字對應的記錄均勻分配在哈希表里面（比如說某廠商賣30棟房子，均勻劃分ABC3個區(qū)域窜护，如果你劃分A區(qū)域1個房子效斑，B區(qū)域1個房子，C區(qū)域28個房子柱徙，有人來查找C區(qū)域的某個房子最壞的情況就是要找28次）缓屠。

• 2.關鍵字極小的變化可以引起哈希值極大的變化。

比較好的哈希函數(shù)是time33算法护侮。PHP的數(shù)組就是把這個作為哈希函數(shù)敌完。
核心的算法就是如下：

unsigned long hash(const char* key){
unsigned long hash=0;
for(int i=0;i<strlen(key);i++){
    hash = hash*33+str[i];
}  
return hash;
}

三、哈希沖突解決辦法

如果遇到?jīng)_突羊初，哈希表一般是怎么解決的呢滨溉？具體方法有很多什湘，百度也會有一堆，最常用的就是開發(fā)定址法和鏈地址法晦攒。
1.開發(fā)定址法
如果遇到?jīng)_突的時候怎么辦呢闽撤？就找hash表剩下空余的空間，找到空余的空間然后插入脯颜。就像你去商店買東西哟旗，發(fā)現(xiàn)東西賣光了，怎么辦呢栋操？找下一家有東西賣的商家買唄闸餐。

由于我沒有深入試驗過，所以貼上在書上的解釋：

四、HashMap底層實現(xiàn)

HashMap允許使用null作為key或者value外莲，并且HashMap不是線程安全的猪半，除了這兩點外，HashMap與Hashtable大致相同，下面是官方API對HashMap的描述：
Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.
如果有多個線程對Hash映射進行訪問办龄，那么至少有一個線程會對哈希映射進行結構的修改：結構上的修改是指添加或刪除一個或多個映射關系的任何操作烘绽；僅改變與實例已經(jīng)包含的鍵關聯(lián)的值不是結構上的修改。
那么很顯然俐填，當多個線程同時（嚴格來說不能稱為同時安接，因為CPU每次只能允許一個線程獲取資源，只不過時間上非常短英融，CPU運行速度很快盏檐，所以理解為同時）修改哈希映射，那么最終的哈希映射（就是哈希表）的最終結果是不能確定的驶悟，這只能看CPU心情了胡野。如果要解決這個問題，官方的參考方案是保持外部同步痕鳍，什么意思硫豆？看下面的代碼就知道了：

Map m = Collections.synchronizedMap(new HashMap(...));

但是不建議這么使用，因為當多個并發(fā)的非同步操作修改哈希表的時候笼呆，最終結果不可預測熊响，所以使用上面的方法創(chuàng)建HashMap的時候，當有多個線程并發(fā)訪問哈希表的情況下诗赌，會拋出異常汗茄，所以并發(fā)修改會失敗。比如下面這段代碼：

for (int i = 0; i < 20; i++) {
    collectionSynMap.put(i, String.valueOf(i));
}
Set<Entry<Integer,String>> keySets = collectionSynMap.entrySet();
Iterator<Entry<Integer, String>> keySetsIterator = keySets.iterator();
try {
    while(keySetsIterator.hasNext()){
        Entry<Integer,String> entrys = (Entry<Integer, String>) keySetsIterator.next();
        System.out.println(entrys.getValue());
        if(entrys.getValue().equals("1")){
            System.out.println(entrys.getValue());
            collectionSynMap.remove(1);
            //keySetsIterator.remove();
        }
    }
} catch (Exception e) {
    e.printStackTrace();

就會拋出ConcurrentModificationException異常铭若，因為在使用迭代器遍歷的時候修改映射結構洪碳，但是使用代碼中注釋的刪除是不會拋出異常的。
通過上面的分析叼屠，我們初步了解HashMap的非線程安全的原理瞳腌，下面從源碼的角度分析一下，為什么HashMap不是線程安全的：

public V put(K key, V value) {
   //這里省略了對重復鍵值的處理代碼
   modCount++;
   addEntry(hash, key, value, i);
   return null;
}

那么問題應該處在addEntry()上环鲤，下面來看看其源碼：

void addEntry(int hash, K key, V value, int bucketIndex) {
//如果達到Map的閾值纯趋，那么就擴大哈希表的容量
if ((size >= threshold) && (null != table[bucketIndex])) {
    //擴容
    resize(2 * table.length);
    hash = (null != key) ? hash(key) : 0;
    bucketIndex = indexFor(hash, table.length);
}
//創(chuàng)建Entry鍵值對，此處省略這部分代碼

假設有線程A和線程B都調用addEntry()方法冷离，線程A和B會得到當前哈希表位置的頭結點（就是上面鏈地址法的第一個元素）吵冒，并修改該位置的頭結點，如果是線程A先獲取頭結點西剥，那么B的操作就會覆蓋線程A的操作痹栖，所以會有問題。
下面再看看resize方法的源碼：

void resize(int newCapacity) {
//此處省略如果達到閾值擴容為原來兩倍的過程代碼
Entry[] newTable = new Entry[newCapacity];
//把當前的哈希表轉移到新的擴容后的哈希表中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);

所以如果有多個線程執(zhí)行put方法瞭空，并調用resize方法揪阿，那么就會出現(xiàn)多種情況疗我，在轉移的過程中丟失數(shù)據(jù)，或者擴容失敗南捂，都有可能吴裤，所以從源碼的角度分析這也是線程不安全的。
HashMap測試代碼

for (int i = 0; i < 40; i++) {
    hashMap.put(i, String.valueOf(i));
}
Set<Entry<Integer,String>> keySets = hashMap.entrySet();
final Iterator<Entry<Integer, String>> keySetsIterator = keySets.iterator();
Thread t3 = new Thread(){
public void run(){
    try {
        while(keySetsIterator.hasNext()){
            Entry<Integer,String> entrys = (Entry<Integer, String>) keySetsIterator.next();
            System.out.println(entrys.getValue());
            if(entrys.getValue().equals("1")){
                System.out.println(entrys.getValue());
                hashMap.remove(1);
            }
        }
    } catch (Exception e) {
        e.printStackTrace();
    }
}
};
Thread t4 = new Thread(){
public void run(){
    try {
        while(keySetsIterator.hasNext()){
            Entry<Integer,String> entrys = (Entry<Integer, String>) keySetsIterator.next();
            System.out.println(entrys.getValue());
            if(entrys.getValue().equals("1")){
                System.out.println(entrys.getValue());
                hashMap.remove(1);
            }
        }
    } catch (Exception e) {
        e.printStackTrace();
    }
}
};
t3.start();
t4.start();

這段代碼啟動了兩個線程并發(fā)修改HashMap的映射關系溺健，所以會拋出兩個ConcurrentModificationException異常麦牺，通過這段測試代碼在此證明了HashMap的非線程安全。
Hashtable的底層實現(xiàn)
在介紹HashMap提到Hashtable是線程安全的鞭缭，那么H啊時table是如何實現(xiàn)線程安全的呢剖膳？有了上面的介紹，我們直接從源碼中分析其線程安全性：

public synchronized V put(K key, V value) {
// 保證value值不為空岭辣，此處省略其代碼
// 保證key是不重復的吱晒，此處省略其代碼
//查過閾值則擴容，此處省略
// Creates the new entry.
Entry<K,V> e = tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
return null;

通過源碼可以很明顯看到其put方法使用synchronized關鍵字沦童，在線程中這是實現(xiàn)線程安全的一種方式仑濒，所以Hashtable是線程安全的。
Hashtable的測試案例
下面使用一段測試代碼驗證Hashtable的線程安全：

Thread t3 = new Thread(){
    public void run(){
        for (int i = 0; i < 20; i++) {
            hashTable.put(i, String.valueOf(i));
        }
    }
};
Thread t4 = new Thread(){
    public void run(){
        for (int i = 20; i < 40; i++) {
            hashTable.put(i, String.valueOf(i));
        }
    }
};
t3.start();
t4.start();
//放完數(shù)據(jù)后偷遗，從map中取出數(shù)據(jù)躏精，如果map是線程安全的，那么取出的entry應該和放進去的一一對應
for (int i = 0; i < 40; i++) {
    System.out.println(i + "=" + hashTable.get(i));

最后得到的輸出結果是這樣的：
CocurrentHashMap詳解
ConcurrentHashMap的測試案例
下面仍然通過一段測試程序驗證ConcurrentHashMap的線程安全：

Thread t5 = new Thread(){
    public void run(){
        for (int i = 0; i < 20; i++) {
            concurrentHashMap.put(i, String.valueOf(i));
        }
    }
};
Thread t6 = new Thread(){
    public void run(){
        for (int i = 20; i < 40; i++) {
            concurrentHashMap.put(i, String.valueOf(i));
        }
    }
};
t5.start();
t6.start();
for (int i = 0; i < 40; i++) {
    System.out.println(i + "=" + concurrentHashMap.get(i));

最后鹦肿，控制臺輸出的結果如下：
說了那么多，針對Map子類的安全性可以總結如下幾點：

• HashMap采用鏈地址法解決哈希沖突辅柴，多線程訪問哈希表的位置并修改映射關系的時候箩溃，后執(zhí)行的線程會覆蓋先執(zhí)行線程的修改，所以不是線程安全的
• Hashtable采用synchronized關鍵字解決了并發(fā)訪問的安全性問題但是效率較低.碌嘀。
• ConcurrentHashMap使用了線程鎖分段技術涣旨，每次訪問只允許一個線程修改哈希表的映射關系，所以是線程安全的