部落格

一、概述

　　HashMap，基於哈希結構的Map接口的一個實現，無序，允許null鍵值對，線程不安全的。可以使用集合工具類Collections中的synchronizedMap方法，去創建一個線程安全的集合map。

　　在jdk1.7中，HashMap主要是基於 數組+鏈表 的結構實現的。鏈表的存在主要是解決 hash 衝突而存在的。插入數據的時候，計算key的hash值，取得存儲的數組下標，如果衝突已有元素，則會在衝突地址上生成個鏈表，再通過key的比較，鏈表是否已存在，存在則覆蓋，不存在則鏈表上添加。這種方式，如果存在大量衝突的時候，會導致鏈表過長，那麼直接導致的就是犧牲了查詢和添加的效率。所以在jdk1.8版本之後，使用的就是 數組 + 鏈表 + 紅黑樹，當鏈表長度超過 8（實際加上初始的節點，整個有效長度是 9） 的時候，轉為紅黑樹存儲。

　　本文中內容，主要基於jdk1.7版本，單線程環境下使用的HahsMap沒有啥問題，但是當在多線程下使用的時候，則可能會出現併發異常，具體表象是CPU會直線上升100%。下面是主要介紹相關的存取以及為什麼會出現線程安全性問題。

二、結構

　　HashMap默認初始化size=16的哈希數組，然後通過計算待存儲的key的hash值，去計算得到哈希數組的下標值，然後放入鏈表中（新增節點或更新）。鏈表的存在即是解決hash衝突的。

三、源碼實現分析

　　1、存儲具體數據的table數組：

　　　　Entry為HashMap中的靜態內部類，其具體結構如下圖

　　　　key、value屬性就是存儲鍵值對的，next則是指向鏈表的下一個元素節點。

     2、 默認初始化方法：

　　  默認構造方法，不對table進行初始化new（真正初始化動作放在put中，後面會看到），只是設置參數的默認值，hashmap長度和table長度初始化成DEFAULT_INITIAL_CAPACITY（16），加載因子loadFactor默認DEFAULT_LOAD_FACTOR（0.75f，至於為什麼是0.75，這個可以參見 ）。

　　  加載因子：默認情況下，16*0.75=12，也就是在存儲第13個元素的時候，就會進行擴容（jdk1.7的threshold真正計算放在第一次初始化中，後面會再提及）。此元素的設置，直接影響到的是key的hash衝突問題。

　　3、put方法

 public V put(K key, V value) {
　　　   if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

　　3.1、EMPTY_TABLE是HashMap中的一個靜態的空的Entry數組，table也是HashMap的一個屬性，默認就是EMPTY_TABLE（這兩句可參見上面源碼），table就是我們真正數據存儲使用的。
　　3.2、前面提及，無參構造的時候，並未真正完成對HashMap的初始化new操作，而僅僅只是設置幾個常量，所以在第一次put數據的時候，table是空的。則會進入下面的初始化table方法中。

if (table == EMPTY_TABLE) {
    inflateTable(threshold);
}

private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);

    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); //計算加載因子，默認情況下結果為12
    table = new Entry[capacity];  //真正的初始化table數組
    initHashSeedAsNeeded(capacity);
}

　　3.3、key的null判斷

if (key == null)
    return putForNullKey(value);

private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

　　具體步驟解析：

　　　　1、key為null，取出table[0]的鏈表結構Enrty，如果取出的元素不為null，則對其進行循環遍歷，查找其中是否存在key為null的節點元素。

　　  　  2、如果存在key == null的節點，則使用新的value去更新節點的oldValue，並且將oldValue返回。

　　　　3、如果不存在key == null的元素，則執行新增元素addEntry方法：

　　　　　　（1）判斷是否需要擴容，size為當前數組table中，已存放的Entry鏈表個數，更直接點說，就是map.size()方法的返回值。threshold上面的真正初始化HashMap的時候已經提到，默認情況下，計算得到 threshold=12。若同時滿足　 (size >= threshold) && (null != table[bucketIndex]) ，則對map進行2倍的擴容，然後對key進行重新計算hash值和新的數組下標。

　　　　　　（2）創建新的節點原色createEntry方法，首先獲取table數組中下標為bucketIndex的鏈表的表頭元素，然後新建個Entry作為新的表頭，並且新表頭其中的next指向老的表頭數據。

　　3.4、key不為null的存儲　　
　　　　原理以及過程上通key==null的大體相同，只不過，key==null的時候，固定是獲取table[0]的鏈表進行操作，而在不為key ！= null的時候，下標位置是通過
  int hash = hash(key); int i = indexFor(hash, table.length); 計算得到的

  static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

　　很清晰的就能看明白，先計算key的hash，然後與當前table的長度進行相與，這樣計算得到待存放數據的下標。得到下標后，過程就與key==null一致了，遍歷是否存在，存在則更新並返回oldVlaue，不存在則新建Entry。

　　4、get方法

 public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

    如果key == null，則調用getForNullKey方法，遍歷table[0]處的鏈表。

private V getForNullKey() {
        if (size == 0) {
            return null;
        }
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

　　如果key ！= null，則調用getEntry，根據key計算得到在table數組中的下標，獲取鏈表Entry，然後遍歷查找元素，key相等，則返回該節點元素。

 final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

四、線程不安全分析

　　上述，主要淺析了下HashMap的存取過程，HashMap的線程安全性問題主要也就是在上述的擴容resize方法上，下面來看看在高併發下，擴容后，是如何引起100%問題的。

　　1、在進行新元素 put 的時候，這在上面中的3.3的代碼片段中可以查看，addEntry 添加新節點的時候，會計算是否需要擴容處理：(size >= threshold) && (null != table[bucketIndex]) 。

　　2、如果擴容的話，會接下來調用 resize 方法

 void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        //關鍵性代碼，構建新hashmap並將老的數據移動過來
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

　　3、其中，出現100%問題的關鍵就是上面的 transfer 方法，新建hashmap移動複製老數據

 1  void transfer(Entry[] newTable, boolean rehash) {
 2         int newCapacity = newTable.length;
 3         for (Entry<K,V> e : table) {
 4             // 遍歷老的HashMap，當遇到不為空的節點的是，進入移動方法
 5             while(null != e) {
 6                 // 首先創建個Entry節點 指向該節點所在鏈表的下一個節點數據
 7                 Entry<K,V> next = e.next;
 8                 if (rehash) {
 9                     e.hash = null == e.key ? 0 : hash(e.key);
10                 }
11 　　　           // 計算老的數據在新Hashmap中的下標位置
12                 int i = indexFor(e.hash, newCapacity);
13 　　　　　        // 將新HashMap中相應位置的元素，掛載到老數據的後面（不管有無數據）
14                 e.next = newTable[i];
15                 // 將新HashMap中相應位置指向上面已經成功掛載新數據的老數據
16 　　　　　        newTable[i] = e;
17 　　　　　        // 移動到鏈表節點中的下一個數據，繼續複製節點
18                 e = next;
19             }
20         }
21     }    

　　問題的關鍵就在上述的14、15行上，這兩行的動作，在高併發下可能就會造成循環鏈表，循環鏈表在等待下一個嘗試 get 獲取數據的時候，就悲劇了。下面舉例模擬說說這個過程：

　　（1）假設目前某個位置的鏈表存儲結構為 A -> B -> C，有兩個線程同時進行擴容操作

　　（2）線程1執行到第7行 Entry<K,V> next = e.next; 的時候被掛起了，此時，線程1的 e 指向 A ， next 指向的是 B

　　（3）線程2執行完成了整個的擴容過程，那麼此時的鏈表結構應該是變為了 C -> B -> A

　　（4）線程1喚醒繼續執行，而需要操作的鏈表實際就變成了了上述線程2完成后的 C ->B -> A，下面分為幾步去完成整個操作：

　　　　　 第一次循環：

　　　　　　　　（i）執行 e.next = newTable[i] ，將 A 的 next 指向線程1的新的HashMap，由於此時無數據，所以 e.next = null

　　　　　　　　（ii）執行 newTable[i] = e，將線程1的新的HashMap的第一個元素指向 A 

　　　　　　　　（iii）執行e = next，移動到鏈表中的下一個元素，也就是上面的（2）中的 線程掛起的時候的 B

　　　　　 第二次循環：

　　　　　　　　（i）執行 Entry<K,V> next = e.next，此時的 e 指向 B，next指向 A

　　　　　　　　（ii）執行 e.next = newTable[i] ，將 B 的 next 指向線程1的新的HashMap，由於此時有數據A，所以 e.next = A

　　　　　　　　（iii）執行 newTable[i] = e，將線程1的新的HashMap的第一個元素指向 B，此時線程1的新Hashmap鏈表結構為B -> A

　　　　　　　　（iiii）執行e = next，移動到鏈表中的下一個元素 A

　　　　　 第三次循環：

　　　　　　　　（i）執行 Entry<K,V> next = e.next，此時的 e 指向 A，next指向 null

　　　　　　　　（ii）執行 e.next = newTable[i] ，將 A 的 next 指向線程1的新的HashMap，由於此時有數據B，所以 e.next = B

　　　　　　　　（iii）執行 newTable[i] = e，將線程1的新的HashMap的第一個元素指向 A ，此時線程1的新Hashmap鏈表結構為 A -> B -> A

　　　　　　　　（iiii）執行e = next，移動到鏈表中的下一個元素，已移動到鏈表結尾，結束 while 循環，完成鏈表的轉移。

　　（5）上述過程中，很顯然的，最終的鏈表結構中，出現了 A -> B -> A 的循環結構。擴容完成了，剩下的等待的是get獲取的時候， getEntry 方法中 for循環e = e.next中就永遠出不來了。

　　注意：擴容過程中，newTable是每個擴容線程獨有的，共享的只是每個Entry節點數據，最終的擴容是會調用 table = newTable 賦值操作完成。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

※帶您來了解什麼是 USB CONNECTOR  ?

※自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象

※如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站，提高曝光率!!

※綠能、環保無空污,成為電動車最新代名詞，目前市場使用率逐漸普及化

※廣告預算用在刀口上，網站設計公司幫您達到更多曝光效益

前言  

       合格的web後端程序員，在開發之外，必須給IIS、Nginx、各種原生web服務器上配置Https，不然你就僅僅是個碼農，本博最近將專題記錄

• 如何為IIS，Nginx配置Https

• 如何申請適用於生產的免費SSL證書

本博客小試牛刀，先實操在Nginx for Docker上添加自簽名SSL證書

為啥先倒騰自簽名SSL證書，申請公網SSL證書需要公網可識別的域名或者公網IP；

如果有實際SSL證書， 按照本文替換即可。

手繪Https原理

長話短說：  目前常見的Http請求明文傳輸， 報文可被截取並篡改，請求可被偽造； 

因此基於常見HTTP（HTTP-TCP-IP）協議棧引入SSL/TSL（Transport Secure Layer） ，HTTPS在進行加密傳輸之前會進行一次握手，確定傳輸密鑰。

流程解讀：

① 傳輸密鑰是對稱密鑰，用於雙方對傳輸數據的加解密

② 怎麼在傳輸之前確立傳輸密鑰呢？ 針對普遍的多客戶端訪問受信web服務器的場景， 提出非對稱密鑰（公鑰存於客戶端，私鑰存於web服務器），雙方能互相加解密，說明中間數據（傳輸密鑰）沒被篡改。

③ 再拋出疑問，怎麼認定下發的公鑰是這個web服務器匹配的密鑰？怎麼確定這個公鑰下發過程沒被截取篡改？ 這就是追溯到握手階段的下發證書過程，瀏覽器內置的CA機構認定該證書是其有效下發，並通過簽名認定該證書沒被篡改，最終認定該 證書下發的公鑰是受信web服務器準確下發。

④ 如果面向面試記憶Https原理，恐怕有些難度，所以個人用一種 【雞生蛋還是蛋生雞】的方式向上追溯流程， 方便大家知其然更知其所以然。

前置準備

 >   CentOS機器上安裝Docker、 Docker-Compose

 >   常規操作構建 Nginx for Docker網站， 項目結構如下： 

ssl-docker-nginx
    ├── docker-compose.yml
    ├── nginx   
    │      └── nginx.conf
    └── site
           └── index.html

    該項目將會使用  nginx/nginx.conf、site/index.html替換Nginx鏡像默認配置文件和默認啟動頁，docker-compose.yml 如下：

version: '2'
services:
  server:
    image: nginx:latest
    volumes:
      - ./nginx/nginx.conf:/etc/nginx/nginx.conf
      - ./site:/usr/share/nginx/html
    ports:
    - "8080:80"

    docker-compose  up -d 啟動Nginx容器，還是那樣熟悉的味道： 【chrome默認將http連接認定為不安全】

添加SSL自簽名證書

很明顯： web服務器需要存儲證書（內置了公鑰）和私鑰

 ① 創建自簽名證書 （什麼叫自簽名，就是自己給自己頒發 SSL證書）

[nodotnet@gs-server-5809 ssl-docker-nginx]$ openssl req -newkey rsa:2048 -nodes -keyout nginx/my-site.com.key -x509 -days 365 –out nginx/my-site.com.crt

req是證書請求的子命令，-newkey rsa:2048 -keyout nginx/my-site.com.key表示生成私鑰(PKCS8格式)，

　　　　　　　　　　-nodes 表示私鑰不加密，

　　　　　　　　　　 -x509表示輸出證書，-days365 為有效期，此後根據提示輸入證書擁有者信息；

       之後會在nginx目錄下生產2個文件， 分別是私鑰、證書

 ② 將證書和密鑰掛載到Nginx Image， 修改docker-compose.yml

version: '2'
services:
  server:
    image: nginx:latest
    volumes:
      - ./nginx/nginx.conf:/etc/nginx/nginx.conf
      - ./site:/usr/share/nginx/html
      - ./nginx/my-site.com.crt:/etc/nginx/my-site.com.crt    #新行 - ./nginx/my-site.com.key:/etc/nginx/my-site.com.key    #新行
    ports:
    - "8080:80"
    - "443:443"        // 容器開啟HTTPS默認的443端口

 ③  修改nginx/nginx.conf，接受Https請求

events {
  worker_connections  4096;  ## Default: 1024
}

http {
    server {
        listen 80;
        root         /usr/share/nginx/html/;
    }

    server {      　　　　　　# 新Server接受來自443端口的Https請求
        listen              443 ssl;
        ssl_certificate     /etc/nginx/my-site.com.crt;
        ssl_certificate_key /etc/nginx/my-site.com.key;
        root        /usr/share/nginx/html;
    }
}

執行docker-compose down && docker-compose up -d 發起https://10.201.80.126:443請求，當前自簽名證書頒發機構不在瀏覽器內置的CA機構，所以該證書目前被瀏覽器認為是無效。

理論上將 該自簽名證書導出，之後在 【chrome瀏覽器】-【高級設置】-【管理證書】中導入該證書，即可讓 chrome接受自簽名SSL證書。

That‘s All,  Https作為以後web的主流配置，碼農進階資深必須掌握；後續會記錄Https & HSTS， 申請免費SSL證書，盡請關注。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※為什麼 USB CONNECTOR 是電子產業重要的元件?

※網頁設計一頭霧水??該從何著手呢? 找到專業技術的網頁設計公司，幫您輕鬆架站!

※想要讓你的商品成為最夯、最多人討論的話題?網頁設計公司讓你強力曝光

※想知道最厲害的台北網頁設計公司推薦、台中網頁設計公司推薦專業設計師”嚨底家”!!