知其是以然-HashMapMap常用MapHashMapConcurrentHash

Map

1. 定義：給定一個鍵和一個值，你可以将該值存儲在一個Map對象. 之後，你可以通過鍵來通路對應的值

常用Map

	簡介	優缺
HashMap	散列桶(數組+連結清單[+紅黑樹])	O(1)~O(lgN)，周遊效率不高
HashTable	synchronized+數組+連結清單
LinkedHashMap	HashMap+雙向連結清單	插入或查找順序排序
TreeMap	紅黑樹	key順序排序
ConcurrentHashMap	線程安全的HashMap

graph TD
A[Map]
B1[HashMap]
B2[HashTable]
B3[TreeMap]
C11[LinkedHashMap]
A-->B1
A-->B2
A-->B3
B1-->C11           

HashMap工作原理

put

1. 求Hash值，計算下标
2. 如果沒有碰撞，放入桶中
3. 如果碰撞，以連結清單方式連結到後面
4. [1.8+]如果連結清單長度超過門檻值(8)，就把連結清單轉化為紅黑樹，連結清單長度低于門檻值(6)，就轉回連結清單。
5. 如果節點已經存在，就替換舊值。
6. 如果桶滿了[容量(16)*加載因子(0.75)],就resize（擴容2倍，重排）

get

2. 調用keys.equals()方法找到連結清單(紅黑樹)中正确的節點

resize

1. 将數組擴大兩倍
2. 重新計算每個元素在數組的位置
3. 1.7- 采用隊頭插入，避免尾部周遊，并可以将最近資料放在連結清單表頭，提高熱點資料查詢效率。
4. 1.8+ 采用隊尾插入周遊，并增加tail指針，避免了死鎖，也避免了尾部周遊，提高了效率。

HashMap深入思考

HashMap hash函數的實作為什麼不用簡單的‘%’進行取模運算

1. 模運算消耗較大(除法，浮點數，十進制轉二進制等多種原因)。
2. hashMap計算模具體本質:

hash  = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
index = (length - 1) & hash
三次位運算即可得出結果，效率較高。           

減少碰撞方案

1. 擾動函數減少碰撞，即盡可能不同對象盡可能傳回不同的hashcode，減少調用equal方法次數。
2. 使用final對象，并采取合适的equals和hashCode方法，減少碰撞發生。
3. hashMap沒有采用的一種解決方案：開放定址法

JDK1.8+ 為什麼采取紅黑樹(RBT)解決連結清單過深問題而不用其它樹結構如二叉查找樹(BST)、平衡二叉樹(AVL)等。

1. BST時間複雜度為n，RBT和AVL為log2N。
2. 在插入操作時，AVL可以保證最多僅需三次旋轉就平衡，AVL插入次數不可預知。

多線程情況下hashMap在resize時為什麼會可能出現死循環。

1.7會發生死循環原因:

void transfer(Entry newTable) {
    Entry[] srv = table;
    int newCapacity = newTale.length;
    for (int j = 0; j < table.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            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);
        }
    }
}           

采用隊頭插入方式，避免了尾部周遊，但當多線程同時操作情況下，可能會産生環形連結清單(因為在隊頭插入過程中，會将尾部節點指針指向頭部，如果此時通知執行resize操作，即有可能形成環形連結清單，然後再get操作的時候形成循環死鍊)

連結

A->B

在頭部後面的節點正常來說不會再次從頭部插入，但特殊情況下，線程1操作A，線程2以更快速度操作完B->A。 此時，1線程執行，将A放入到連結清單頭部，并指向B，形成環形連結清單。

hashMap其它設計方案

開放定址法：在雜湊演算法得到一個存儲位址之後，如果發生沖突，不是在原處建立一個連結清單而是按照一定規則尋找周圍可用的位址進行插入。

1. 根據開放定址法，我們可以使用三個數組即可實作Map，其中，used表示對應的位址是否被使用，即：

keys[], values[], used[]           

1. 分析1步驟，其實used[] 數組是沒有必要的，我們可以使用keys=0代表空節點，keys=1代表删除節點的方案取消used[],對于實際keys為0/1的資料單獨建立一個合作哨兵對象（sentinel object）即可。這樣，map被簡化為

keys[]，values[]           

1. 分析2步驟，通常我們的map不會超過Integer.MAX，那麼對于部分特殊的Map(例如：Int2IntMaps),我們可以将key和value存儲在同一個long中，key存儲在低32位，value存儲在高32位，這樣map被我們進一步簡化：

keyValues[]           

1. 繼續分析2步驟，單獨建立的哨兵對象會增加複雜度，那麼可以在初始化階段随機選擇一個int，作為标記，當插入該随機值的資料時，可以傳回map中不存在的其它随機值即可。

ps:具體實作可參考：FastUtil、Goldman Sachs Collections、HPPC、Koloboke、Trove

1.7版本

Segment分段鎖

原理是将原來兩層的map結構(數組+連結清單)變為三層結構(Segment數組 + HashEntry數組 + 連結清單)，在hashEntry層加鎖，就可以實作最大Segment.length的并發度。

size操作

先嘗試将所有的Segment元素中的count相加，這樣執行兩次，然後将兩次的結果對比，如果兩次結果相等則直接傳回；而如果兩次結果不同，則再将所有Segment加鎖，然後再執行統計得到對應的size值。

1.8版本

放棄分段鎖，采用CAS保證資料準确，

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                    Node<K,V> c, Node<K,V> v) {
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}