Java高并發(fā) -- 并發(fā)擴(kuò)展

主要是學(xué)習(xí)慕課網(wǎng)實(shí)戰(zhàn)視頻《Java并發(fā)編程入門(mén)與高并發(fā)面試》的筆記

死鎖

死鎖是指兩個(gè)或兩個(gè)以上的事務(wù)在執(zhí)行過(guò)程中，因爭(zhēng)奪鎖資源而造成的一種互相等待的現(xiàn)象，若無(wú)外力作用兩個(gè)事務(wù)都無(wú)法推進(jìn)，這樣就產(chǎn)生了死鎖。死鎖的四個(gè)必要條件：

• 互斥條件：即任何時(shí)刻，一個(gè)資源只能被一個(gè)進(jìn)程使用。其他進(jìn)程必須等待。
• 請(qǐng)求和保持條件：即當(dāng)資源請(qǐng)求者在請(qǐng)求其他的資源的同時(shí)保持對(duì)原有資源的占有且不釋放。
• 不剝奪條件：資源請(qǐng)求者不能強(qiáng)制從資源占有者手中奪取資源，資源只能由資源占有者主動(dòng)釋放。
• 環(huán)路等待條件：比如A占有B在等待的資源（B等待A釋放），B占有A在等待的資源（A等待B釋放）。多個(gè)進(jìn)程循環(huán)等待著相鄰進(jìn)程占用著的資源。

是指兩個(gè)或兩個(gè)以上的線程在執(zhí)行過(guò)程中，互相占用著對(duì)方想要的資源但都不釋放，造成了互相等待，結(jié)果線程都無(wú)法向前推進(jìn)。

死鎖的檢測(cè)：可以采用等待圖（wait-for gragh）。采用深度優(yōu)先搜索的算法實(shí)現(xiàn)，如果圖中有環(huán)路就說(shuō)明存在死鎖。

解決死鎖：

• 破環(huán)鎖的四個(gè)必要條件之一，可以預(yù)防死鎖。
• 加鎖順序保持一致。不同的加鎖順序很可能導(dǎo)致死鎖，比如哲學(xué)家問(wèn)題：A先申請(qǐng)筷子1在申請(qǐng)筷子2，而B(niǎo)先申請(qǐng)筷子2在申請(qǐng)筷子1，最后誰(shuí)也得不到一雙筷子（同時(shí)擁有筷子1和筷子2）
• 撤消或掛起進(jìn)程，剝奪資源。終止參與死鎖的進(jìn)程，收回它們占有的資源，從而解除死鎖。

舉個(gè)簡(jiǎn)單的例子

public class DeadLock implements Runnable {

    public static Object fork1 = new Object();
    public static Object fork2 = new Object();

    private String name;
    private Object tool;

    public DeadLock(Object o) {
        this.tool = o;
        if (tool == fork1) {
            this.name = "哲學(xué)家A";
        }
        if (tool == fork2) {
            this.name = "哲學(xué)家B";
        }
    }

    @Override
    public void run() {
        if (tool == fork1) {
            synchronized (fork1) {
                try {
                    System.out.println(name+"拿到了一個(gè)叉子");
                    Thread.sleep(500);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                synchronized (fork2) {
                    System.out.println(name+"拿到兩個(gè)叉子了");
                }
            }
        }

        if (tool == fork2) {
            synchronized (fork2) {
                try {
                    System.out.println(name+"拿到了一個(gè)叉子");
                    Thread.sleep(500);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                synchronized (fork1) {
                    System.out.println(name+"拿到兩個(gè)叉子了");
                }
            }
        }
    }

    public static void main(String[] args) {
        DeadLock a = new DeadLock(fork1);
        DeadLock b = new DeadLock(fork2);

        Thread t1 = new Thread(a);
        Thread t2 = new Thread(b);
        t1.start();
        t2.start();

    }
}

運(yùn)行上面這段程序，會(huì)輸出

哲學(xué)家B拿到了一個(gè)叉子
哲學(xué)家A拿到了一個(gè)叉子

然后程序就進(jìn)入了死循環(huán)，因?yàn)檎軐W(xué)家A在等B手里的叉子，哲學(xué)家B也在等A手上的叉子，但是他倆誰(shuí)都不肯釋放。

HashMap和ConcurrentHshMap

HashMap

HashMap的底層使用數(shù)組+鏈表/紅黑樹(shù)實(shí)現(xiàn)。

transient Node<K,V>[] table;這表示HashMap是Node數(shù)組構(gòu)成，其中Node類的實(shí)現(xiàn)如下，可以看出這其實(shí)就是個(gè)鏈表，鏈表的每個(gè)結(jié)點(diǎn)是一個(gè)<K,V>映射。

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

HashMap的每個(gè)下標(biāo)都存放了一條鏈表。

常量/變量定義

/* 常量定義 */

// 初始容量為16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 負(fù)載因子，當(dāng)鍵值對(duì)個(gè)數(shù)達(dá)到DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR會(huì)觸發(fā)resize擴(kuò)容 
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 當(dāng)鏈表長(zhǎng)度大于8，且數(shù)組長(zhǎng)度大于MIN_TREEIFY_CAPACITY，就會(huì)轉(zhuǎn)為紅黑樹(shù)
static final int TREEIFY_THRESHOLD = 8;
// 當(dāng)resize時(shí)候發(fā)現(xiàn)鏈表長(zhǎng)度小于6時(shí)，從紅黑樹(shù)退化為鏈表
static final int UNTREEIFY_THRESHOLD = 6;
// 在要將鏈表轉(zhuǎn)為紅黑樹(shù)之前，再進(jìn)行一次判斷，若數(shù)組容量小于該值，則用resize擴(kuò)容，放棄轉(zhuǎn)為紅黑樹(shù)
// 主要是為了在建立Map的初期，放置過(guò)多鍵值對(duì)進(jìn)入同一個(gè)數(shù)組下標(biāo)中，而導(dǎo)致不必要的鏈表->紅黑樹(shù)的轉(zhuǎn)化，此時(shí)擴(kuò)容即可，可有效減少?zèng)_突
static final int MIN_TREEIFY_CAPACITY = 64;

/* 變量定義 */

// 鍵值對(duì)的個(gè)數(shù)
transient int size;
// 鍵值對(duì)的個(gè)數(shù)大于該值時(shí)候，會(huì)觸發(fā)擴(kuò)容
int threshold;
// 非線程安全的集合類中幾乎都有這個(gè)變量的影子，每次結(jié)構(gòu)被修改都會(huì)更新該值，表示被修改的次數(shù)
transient int modCount;

關(guān)于modCount的作用見(jiàn)這篇blog

在一個(gè)迭代器初始的時(shí)候會(huì)賦予它調(diào)用這個(gè)迭代器的對(duì)象的modCount，如果在迭代器遍歷的過(guò)程中，一旦發(fā)現(xiàn)這個(gè)對(duì)象的modCount和迭代器中存儲(chǔ)的modCount不一樣那就拋異常。
Fail-Fast機(jī)制：java.util.HashMap不是線程安全的，因此如果在使用迭代器的過(guò)程中有其他線程修改了map，那么將拋出ConcurrentModificationException，這就是所謂fail-fast策略。這一策略在源碼中的實(shí)現(xiàn)是通過(guò)modCount域，modCount顧名思義就是修改次數(shù)，對(duì)HashMap內(nèi)容的修改都將增加這個(gè)值，那么在迭代器初始化過(guò)程中會(huì)將這個(gè)值賦給迭代器的expectedModCount。在迭代過(guò)程中，判斷modCount跟expectedModCount是否相等，如果不相等就表示已經(jīng)有其他線程修改了Map。

注意初始容量和擴(kuò)容后的容量都必須是2的次冪，為什么呢?

hash方法

先看散列方法

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

HashMap的散列方法如上，其實(shí)就是將hash值的高16位和低16位異或，我們將馬上看到hash在與n - 1相與的時(shí)候，高位的信息也被考慮了，能使碰撞的概率減小，散列得更均勻。

在JDK 8中，HashMap的putVal方法中有這么一句

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

關(guān)鍵就是這句(n - 1) & hash，這行代碼是把待插入的結(jié)點(diǎn)散列到數(shù)組中某個(gè)下標(biāo)中，其中hash就是通過(guò)上面的方法的得到的，為待插入Node的key的hash值，n是table的容量即table.length，2的次冪用二進(jìn)制表示的話，只有最高位為1，其余為都是0。減去1，剛好就反了過(guò)來(lái)。比如16的二進(jìn)制表示為10000，減去1后的二進(jìn)制表示為01111，除了最高位其余各位都是1，保證了在相與時(shí)，可以使得散列值分布得更均勻（因?yàn)槿绻澄粸?比如1011，那么結(jié)點(diǎn)永遠(yuǎn)不會(huì)被散列到1111這個(gè)位置），且當(dāng)n為2的次冪時(shí)候有(n - 1) & hash == hash % n, 舉個(gè)例子，比如hash等于6時(shí)候，01111和00110相與就是00110，hash等于16時(shí)，相與就等于0了，多舉幾個(gè)例子便可以驗(yàn)證這一結(jié)論。最后來(lái)回答為什么HashMap的容量要始終保持2的次冪

• 使散列值分布均勻
• 位運(yùn)算的效率比取余的效率高

注意table.length是數(shù)組的容量，而transient int size表示存入Map中的鍵值對(duì)數(shù)。

int threshold表示臨界值，當(dāng)鍵值對(duì)的個(gè)數(shù)大于臨界值，就會(huì)擴(kuò)容。threshold的更新是由下面的方法完成的。

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;
}

該方法返回大于等于cap的最小的二次冪數(shù)值。比如cap為16，就返回16，cap為17就返回32。

put方法

put方法主要由putVal方法實(shí)現(xiàn)：

• 如果沒(méi)有產(chǎn)生hash沖突，直接在數(shù)組tab[i = (n - 1) & hash]處新建一個(gè)結(jié)點(diǎn)；
• 否則，發(fā)生了hash沖突，此時(shí)key如果和頭結(jié)點(diǎn)的key相同，找到要更新的結(jié)點(diǎn)，直接跳到最后去更新值
• 否則，如果數(shù)組下標(biāo)中的類型是TreeNode，就插入到紅黑樹(shù)中
• 如果只是普通的鏈表，就在鏈表中查找，找到key相同的結(jié)點(diǎn)就跳出，到最后去更新值；到鏈表尾也沒(méi)有找到就在尾部插入一個(gè)新結(jié)點(diǎn)。接著判斷此時(shí)鏈表長(zhǎng)度若大于8的話，還需要將鏈表轉(zhuǎn)為紅黑樹(shù)（注意在要將鏈表轉(zhuǎn)為紅黑樹(shù)之前，再進(jìn)行一次判斷，若數(shù)組容量小于64，則用resize擴(kuò)容，放棄轉(zhuǎn)為紅黑樹(shù)）

get方法

get方法由getNode方法實(shí)現(xiàn)：

• 如果在數(shù)組下標(biāo)的鏈表頭就找到key相同的，那么返回鏈表頭的值
• 否則如果數(shù)組下標(biāo)處的類型是TreeNode，就在紅黑樹(shù)中查找
• 否則就是在普通鏈表中查找了
• 都找不到就返回null

remove方法的流程大致和get方法類似。

HashMap的擴(kuò)容，resize()過(guò)程？

newCap = oldCap << 1

resize方法中有這么一句，說(shuō)明是擴(kuò)容后數(shù)組大小是原數(shù)組的兩倍。

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;
                    // 如果數(shù)組中只有一個(gè)元素，即只有一個(gè)頭結(jié)點(diǎn)，重新哈希到新數(shù)組的某個(gè)下標(biāo)
                    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
                        // 數(shù)組下標(biāo)處的鏈表長(zhǎng)度大于1，非紅黑樹(shù)的情況
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            // oldCap是2的次冪，最高位是1，其余為是0，哈希值和其相與，根據(jù)哈希值的最高位是1還是0，鏈表被拆分成兩條，哈希值最高位是0分到loHead。
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            // 哈希值最高位是1分到hiHead
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            // loHead掛到新數(shù)組[原下標(biāo)]處；
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            // hiHead掛到新數(shù)組中[原下標(biāo)+oldCap]處
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;

舉個(gè)例子，比如oldCap是16，二進(jìn)制表示是10000，hash值的后五位和oldCap相與，因?yàn)閛ldCap的最高位（從右往左數(shù)的第5位）是1其余位是0，因此hash值的該位是0的所有元素被分到一條鏈表，掛到新數(shù)組中原下標(biāo)處，hash值該位為1的被分到另外一條鏈表，掛到新數(shù)組中原下標(biāo)+oldCap處。舉個(gè)例子：桶0中的元素其hash值后五位是0XXXX的就被分到桶0種，其hash值后五位是1XXXX就被分到桶4中。

ConcurrentHashMap

JDK 7中使用的是分段鎖，內(nèi)部分成了16個(gè)Segment即分段，每個(gè)分段可以看作是一個(gè)小型的HashMap，每次put只會(huì)鎖定一個(gè)分段，降低了鎖的粒度：

• 首先根據(jù)key計(jì)算出一個(gè)hash值，找到對(duì)應(yīng)的Segment
• 調(diào)用Segment的lock方法（Segment繼承了重入鎖），鎖住該段內(nèi)的數(shù)據(jù)，所以并沒(méi)有鎖住ConcurrentHashMap的全部數(shù)據(jù)
• 根據(jù)key計(jì)算出hash值，找到Segment中數(shù)組中對(duì)應(yīng)下標(biāo)的鏈表，并將該數(shù)據(jù)放置到該鏈表中
• 判斷當(dāng)前Segment包含元素的數(shù)量大于閾值，則Segment進(jìn)行擴(kuò)容（Segment的個(gè)數(shù)是不能擴(kuò)容的，但是單個(gè)Segment里面的數(shù)組是可以擴(kuò)容的）

多線程put的時(shí)候，只要被加入的鍵值不屬于 同一個(gè)分段，就可以做到真正的并行put。對(duì)不同的Segment則無(wú)需考慮線程同步，對(duì)于同一個(gè)Segment的操作才需考慮。

JDK 8中使用了CAS+synchronized保證線程安全，也采取了數(shù)組+鏈表/紅黑樹(shù)的結(jié)構(gòu)。

put時(shí)使用synchronized鎖住了桶中鏈表的頭結(jié)點(diǎn)。

數(shù)組的擴(kuò)容，被問(wèn)到了我在看吧.....我只知道多個(gè)線程可以協(xié)助數(shù)據(jù)的遷移。

有這么一個(gè)問(wèn)題，ConcurrentHashMap，有三個(gè)線程，A先put觸發(fā)了擴(kuò)容，擴(kuò)容時(shí)間很長(zhǎng)，此時(shí)B也put會(huì)怎么樣？此時(shí)C調(diào)用get方法會(huì)怎么樣？C讀取到的元素是舊桶中的元素還是新桶中的

A先觸發(fā)擴(kuò)容，ConcurrentHashMap遷移是在鎖定舊桶的前提下進(jìn)行遷移的，并沒(méi)有去鎖定新桶。

• 在某個(gè)桶的遷移過(guò)程中，別的線程想要對(duì)該桶進(jìn)行put操作怎么辦？一旦某個(gè)桶在遷移過(guò)程中了，必然要獲取該桶的鎖，所以其他線程的put操作要被阻塞。因此B被阻塞。
• 某個(gè)桶已經(jīng)遷移完成（其他桶還未完成），別的線程想要對(duì)該桶進(jìn)行put操作怎么辦？該線程會(huì)首先檢查是否還有未分配的遷移任務(wù)，如果有則先去執(zhí)行遷移任務(wù)，如果沒(méi)有即全部任務(wù)已經(jīng)分發(fā)出去了，那么此時(shí)該線程可以直接對(duì)新的桶進(jìn)行插入操作（映射到的新桶必然已經(jīng)完成了遷移，所以可以放心執(zhí)行操作）

ConcurrentHashMap的get操作沒(méi)有加鎖，所以可以讀取到值，不過(guò)是舊桶中的值。

if (finishing) {
    nextTable = null;
    table = nextTab;
    sizeCtl = (n << 1) - (n >>> 1);
    return;
}

從table = nextTable可以看出，當(dāng)所有數(shù)據(jù)遷移完成時(shí)，才將用nextTab新數(shù)組去覆蓋舊數(shù)組table。所以在A擴(kuò)容過(guò)程中，C讀取到的是舊數(shù)組中的元素。

擴(kuò)容

• 垂直擴(kuò)容（垂直擴(kuò)展）：提升單機(jī)處理能力（提高硬盤(pán)、內(nèi)存、CPU）
• 水平擴(kuò)容（水平擴(kuò)展）：增加系統(tǒng)成員數(shù)（增加服務(wù)器個(gè)數(shù)）