我們一直知道HashMap是非線程安全的，HashTable是線程安全的，可這是為什么呢？先聊聊HashMap吧，想要了解它為什么是非線程安全的，我們得從它的原理著手。

jdk7中的HashMap

HashMap底層維護(hù)一個(gè)數(shù)組，數(shù)組中的每一項(xiàng)都是Entry

transient Entry<K,V>[] table;

我們向HashMap放置的對(duì)象實(shí)際上是放置在Entry數(shù)組中

而Map中的key、value則以Entry的形式存放在數(shù)組中

private static class Entry<K,V> implements Map.Entry<K,V> {    final int hash;    final K key;
    V value;    Entry<K,V> next;

而這個(gè)Entry應(yīng)該放在數(shù)組的哪一個(gè)位置上（這個(gè)位置通常稱為位桶或者h(yuǎn)ash桶，即hash值相同的Entry會(huì)放在同一位置，用鏈表相連），是通過(guò)key的hashCode來(lái)計(jì)算的。

iOS培訓(xùn),Swift培訓(xùn),蘋果開(kāi)發(fā)培訓(xùn),移動(dòng)開(kāi)發(fā)培訓(xùn)

當(dāng)兩個(gè)key通過(guò)hashcode計(jì)算是相同的時(shí)候，就會(huì)發(fā)生hash沖突，HashMap解決hash沖突的辦法是使用鏈表。

簡(jiǎn)而言之就是，如果該位置沒(méi)有對(duì)象，則將對(duì)象直接放到數(shù)組中，如果該位置有對(duì)象，順著存在此對(duì)象的鏈找（Map中不允許存在相同的key和value），如果不存在相同的，第一種情況：如果該鏈表擴(kuò)容了，則把對(duì)象放入到數(shù)組中，原先存放在數(shù)組中的數(shù)據(jù)放置該對(duì)象的后面。第二種情況：如果該鏈表沒(méi)有擴(kuò)容，則直接放到鏈表的最后。如果存在相同的，則進(jìn)行替換。

當(dāng)HashMap中的元素越來(lái)越多的時(shí)候，hash沖突的幾率也就越來(lái)越高，因?yàn)閿?shù)組的長(zhǎng)度是固定的。所以為了提高查詢的效率，就要對(duì)HashMap的數(shù)組進(jìn)行擴(kuò)容，而在HashMap數(shù)組擴(kuò)容之后，最消耗性能的點(diǎn)就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計(jì)算其在新數(shù)組中的位置，并放進(jìn)去，這就是resize。

值得注意的是，HashMap中key和value都允許有null值存在，不過(guò)只允許一個(gè)null的key，可以有多個(gè)null值的value。

jdk8中的HashMap

在JDK1.7的部分就只有鏈表結(jié)構(gòu)，但是由于鏈表過(guò)長(zhǎng)的時(shí)候查找元素時(shí)間較長(zhǎng)，在JDK1.8的時(shí)候加入了紅黑樹(shù)，當(dāng)鏈表超過(guò)一定長(zhǎng)度之后，鏈表就會(huì)轉(zhuǎn)換成紅黑樹(shù)，便于查找和插入，在最壞的情況下，鏈表的時(shí)間復(fù)雜度是O(n),紅黑樹(shù)是O(logn),這樣會(huì)提高HashMap的效率。
iOS培訓(xùn),Swift培訓(xùn),蘋果開(kāi)發(fā)培訓(xùn),移動(dòng)開(kāi)發(fā)培訓(xùn)

在jdk8中，當(dāng)同一個(gè)hash值得節(jié)點(diǎn)數(shù)大于8的時(shí)候，將不再以鏈表的形式存儲(chǔ)了，而是會(huì)調(diào)整成一顆紅黑樹(shù)。

static final int TREEIFY_THRESHOLD = 8;

從JDK1.8開(kāi)始，HashMap的元素是以Node形式存在，主要結(jié)構(gòu)如下：

 static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;    final K key;
    V value;
    Node<K,V> next;

JDK中Entry的名字變成了Node，原因是和紅黑樹(shù)的實(shí)現(xiàn)TreeNode相關(guān)聯(lián)。

可以看一下jdk8中的put方法，跟jdk7相比還是做了很大的改變。

    public V put(K key, V value) {    return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;    //如果當(dāng)前map中無(wú)數(shù)據(jù)，執(zhí)行resize方法。并且返回n
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;    //如果要插入的鍵值對(duì)要存放的這個(gè)位置剛好沒(méi)有元素，那么把他封裝成Node對(duì)象，放在這個(gè)位置上就可以了
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);    else {
        Node<K,V> e; K k;        //如果這個(gè)元素的key與要插入的一樣，那么就替換一下
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;         //如果當(dāng)前節(jié)點(diǎn)是TreeNode類型的數(shù)據(jù)，存儲(chǔ)的鏈表已經(jīng)變?yōu)榧t黑樹(shù)了，執(zhí)行putTreeVal方法去存入
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);         //還是鏈表狀態(tài)
        else {            for (int binCount = 0; ; ++binCount) {                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);                    //判斷是否要轉(zhuǎn)成紅黑樹(shù)
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
                        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;    //判斷閥值，決定是否擴(kuò)容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);    return null;
}

HashMap的多線程不安全

個(gè)人覺(jué)得HashMap在并發(fā)時(shí)可能出現(xiàn)的問(wèn)題主要是兩方面,首先如果多個(gè)線程同時(shí)使用put方法添加元素，而且假設(shè)正好存在兩個(gè)put的key發(fā)生了碰撞(hash值一樣)，那么根據(jù)HashMap的實(shí)現(xiàn)，這兩個(gè)key會(huì)添加到數(shù)組的同一個(gè)位置，這樣最終就會(huì)發(fā)生其中一個(gè)線程的put的數(shù)據(jù)被覆蓋。第二就是如果多個(gè)線程同時(shí)檢測(cè)到元素個(gè)數(shù)超過(guò)數(shù)組大小*loadFactor，這樣就會(huì)發(fā)生多個(gè)線程同時(shí)對(duì)Node數(shù)組進(jìn)行擴(kuò)容，都在重新計(jì)算元素位置以及復(fù)制數(shù)據(jù)，但是最終只有一個(gè)線程擴(kuò)容后的數(shù)組會(huì)賦給表，也就是說(shuō)其他線程的都會(huì)丟失，并且各自線程put的數(shù)據(jù)也丟失。

對(duì)第二種不安全的情況進(jìn)行分析：HashMap的死循環(huán)

由于插入過(guò)程，新插入元素總是插入到頭部，源碼如下：

void transfer(Entry[] newTable)  {  
Entry[] src = table;  
int newCapacity = newTable.length;   
for (int j = 0; j < src.length; j++) {  
    Entry<K,V> e = src[j];  
    if (e != null) {  
        src[j] = null; 
        //這里在做插入的過(guò)程中，總是將新插入元素放在鏈表頭 
        do {  
            Entry<K,V> next = e.next;  
            int i = indexFor(e.hash, newCapacity);  
            e.next = newTable[i];  
            newTable[i] = e;  
            e = next;  
        } while (e != null);  
    }  
}  
}

解析代碼：

e=3Entry<K,V> next = e.next;  保存了3.next也就是7e.next = newTable[i];  表示3后面跟著的是null，newTable表示重新建立的一張表

newTable[i] = e; 表示在表的下標(biāo)的那個(gè)位置放的是e(也就是3)，也就說(shuō)下圖中的下標(biāo)為3的地方放了key=3這個(gè)對(duì)象

e=next；表示e=7了

第二次循環(huán)--

Entry<K,V> next = e.next;  保存了7.next也就是5e.next = newTable[i];   表示7.next=3了，說(shuō)明3放到7的尾巴上去了

newTable[i] = e;    表示下圖中的下標(biāo)為3的地方放了key=7這個(gè)對(duì)象

e=next；表示e=5了

又開(kāi)啟了再一次的循環(huán)。

iOS培訓(xùn),Swift培訓(xùn),蘋果開(kāi)發(fā)培訓(xùn),移動(dòng)開(kāi)發(fā)培訓(xùn)

為什么會(huì)發(fā)生死循環(huán)呢？

解析：多線程情況下，多個(gè)線程同時(shí)檢測(cè)到對(duì)數(shù)組進(jìn)行擴(kuò)容

當(dāng)線程1正好插入了3（e=3），并且保存了e.next(也就7)

CPU正好切到了線程2，并且完成了擴(kuò)容，如上圖所示。

之后我們對(duì)線程1繼續(xù)進(jìn)行操作，把7也插進(jìn)線程1中，可以看到如下所示：

iOS培訓(xùn),Swift培訓(xùn),蘋果開(kāi)發(fā)培訓(xùn),移動(dòng)開(kāi)發(fā)培訓(xùn)

但是由于受到線程2的影響，e=7,e.next=3,我們后面又得插入3了，然后插入3之后，因?yàn)?.next=7,所以我們又插入7，這樣就形成了死循環(huán)。

這個(gè)問(wèn)題在JDK1.8中得到了解決，它用了新的索引插入方式

Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;do {
next = e.next;//還是原索引位置if ((e.hash & oldCap) == 0) {    if (loTail == null)
        loHead = e;    else
        loTail.next = e;
    loTail = e;
}//原索引+ oldCap位置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;
}

由于擴(kuò)容是在原容量基礎(chǔ)上乘以2，那么hash碼校驗(yàn)的時(shí)候會(huì)比原來(lái)的多一位，那么只需要比較這個(gè)位置是0還是1即可，是1那么就在原索引位置向后位移原容量大小即可，是0就不動(dòng)。

iOS培訓(xùn),Swift培訓(xùn),蘋果開(kāi)發(fā)培訓(xùn),移動(dòng)開(kāi)發(fā)培訓(xùn)

HashTable

Hashtable是線程安全的，我們可以看看它的源碼

public synchronized V put(K key, V value) {
    // Make sure the value is not null    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.    Entry<?,?> tab[] = table;    int hash = key.hashCode();    int index = (hash & x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;            entry.value = value;            return old;
        }
    }

    addEntry(hash, key, value, index);    return null;
}

在主要的函數(shù)上都加了synchronize同步關(guān)鍵字，所有線程競(jìng)爭(zhēng)同一把鎖，所以線程安全。

http://www.cnblogs.com/lixuan1998/p/7202040.html