散列表

定義：
通過(guò)散列函數(shù)把元素的鍵值映射為下標(biāo)特纤，然后將數(shù)據(jù)存儲(chǔ)在數(shù)組中對(duì)應(yīng)下標(biāo)的位置岁疼。當(dāng)我們按照鍵值查詢?cè)貢r(shí)，我們用同樣的散列函數(shù)双饥，將鍵值轉(zhuǎn)化數(shù)組下標(biāo)媒抠，從對(duì)應(yīng)的數(shù)組下標(biāo)的位置取數(shù)據(jù)。

裝載因子：
散列表的裝載因子=填入表中的元素個(gè)數(shù)/散列表的長(zhǎng)度咏花。
裝載因子越大趴生，說(shuō)明空閑位置越少，沖突越多昏翰，散列表的性能會(huì)下降苍匆。

散列沖突解決方案

1. 開(kāi)放尋址法
   線性探測(cè)
   插入過(guò)程：
   如果某個(gè)數(shù)據(jù)經(jīng)過(guò)散列函數(shù)散列之后，存儲(chǔ)位置已經(jīng)被占用了棚菊，我們就從當(dāng)前位置開(kāi)始浸踩，依次往后查找，看是否有空閑位置统求，直到找到為止检碗。
   查找過(guò)程：
   我們通過(guò)散列函數(shù)求出要查找元素的鍵值對(duì)應(yīng)的散列值，然后比較數(shù)組中下標(biāo)為散列值的元素和要查找的元素码邻。如果相等折剃，則說(shuō)明就是我們要找的元素；否則就順序往后依次查找像屋。如果遍歷到數(shù)組中的空閑位置怕犁，還沒(méi)有找到，就說(shuō)明要查找的元素并沒(méi)有在散列表中。
   刪除過(guò)程：
   將刪除的元素奏甫，特殊標(biāo)記為deleted戈轿。當(dāng)線性探測(cè)查找的時(shí)候，遇到標(biāo)記為deleted的空間阵子，并不是停下來(lái)思杯，而是繼續(xù)往下探測(cè)。
   適用條件：
   當(dāng)數(shù)據(jù)量比較小挠进、裝載因子小的時(shí)候智蝠，適合采用開(kāi)放尋址法。
   ThreadLocalMap使用開(kāi)放尋址法解決散列沖突奈梳。

2. 鏈表法
   在散列表中，每個(gè)桶會(huì)對(duì)應(yīng)一條鏈表解虱，所有散列值相同的元素都會(huì)放到相同槽位對(duì)應(yīng)的鏈表中攘须。
   內(nèi)存的利用率比開(kāi)放尋址法要高，對(duì)大裝載因子的容忍度更高殴泰。
   比較適合存儲(chǔ)大對(duì)象于宙、大數(shù)據(jù)量的散列表，而且悍汛，比起開(kāi)放尋址法捞魁，它更加靈活，支持更多的優(yōu)化策略离咐，比如用紅黑樹(shù)代替鏈表谱俭。

如何設(shè)計(jì)散列表

1. 散列函數(shù)
   散列函數(shù)的設(shè)計(jì)不能太復(fù)雜。會(huì)消耗很多計(jì)算時(shí)間宵蛀，也就間接地影響到散列表的性能昆著。
   散列函數(shù)生成的值要盡可能隨機(jī)并且均勻分布，這樣才能避免或者最小化散列沖突术陶，而且即便出現(xiàn)沖突凑懂，散列到每個(gè)槽里的數(shù)據(jù)也會(huì)比較平均，不會(huì)出現(xiàn)某個(gè)槽內(nèi)數(shù)據(jù)特別多的情況梧宫。

2. 解決負(fù)載因子過(guò)大問(wèn)題
   擴(kuò)容接谨，數(shù)組長(zhǎng)度擴(kuò)大為之前2倍，負(fù)載因子原先是0.8也會(huì)減到0.4塘匣。
   散列表的大小變了脓豪，數(shù)據(jù)的存儲(chǔ)位置也變了，所以需要通過(guò)散列函數(shù)重新計(jì)算每個(gè)數(shù)據(jù)的存儲(chǔ)位置馆铁。

3. 如何解決低效擴(kuò)容
   為了解決一次性擴(kuò)容耗時(shí)過(guò)多的情況跑揉，我們可以將擴(kuò)容操作穿插在插入操作的過(guò)程中，分批完成。當(dāng)裝載因子觸達(dá)閾值之后历谍，我們只申請(qǐng)新空間现拒，但并不將老的數(shù)據(jù)搬移到新散列表中。
   當(dāng)有新數(shù)據(jù)要插入時(shí)望侈，我們將新數(shù)據(jù)插入新散列表中印蔬，并且從老的散列表中拿出一個(gè)數(shù)據(jù)放入到新散列表。這樣沒(méi)有了集中的一次性數(shù)據(jù)搬移脱衙，插入操作就都變得很快了侥猬。
   查詢先從新散列表中查找，再?gòu)呐f散列表中查找捐韩。

HashMap

HashMap是一個(gè)利用哈希表原理來(lái)存儲(chǔ)元素的集合退唠。遇到?jīng)_突時(shí)，HashMap是采用的鏈表法來(lái)解決荤胁。
在JDK1.7中瞧预，HashMap是由數(shù)組+鏈表構(gòu)成的。在JDK1.8中仅政，HashMap是由數(shù)組+鏈表+紅黑樹(shù)構(gòu)成垢油。

HashMap初始化容量16，負(fù)載因子0.75圆丹。
鏈表長(zhǎng)度大于8會(huì)轉(zhuǎn)成紅黑樹(shù)滩愁，小于6，紅黑樹(shù)又會(huì)轉(zhuǎn)成鏈表辫封。
當(dāng)極端情況硝枉，所有數(shù)據(jù)都裝進(jìn)一個(gè)桶內(nèi)，使用查詢時(shí)間是O（n）倦微，使用紅黑樹(shù)查詢時(shí)間是O（logn）檀咙，在數(shù)據(jù)量較大且哈希碰撞較多時(shí)，能夠極大的增加檢索的效率璃诀。在數(shù)據(jù)量較小的情況下弧可，紅黑樹(shù)要維護(hù)平衡，比起鏈表來(lái)劣欢，性能上的優(yōu)勢(shì)并不明顯棕诵，空間成本比較高。
允許key和value都為null凿将。key重復(fù)會(huì)被覆蓋校套，value允許重復(fù)。
無(wú)序牧抵。

字段屬性

private static final long serialVersionUID = 362498820763181265L;
// 集合初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 16;
// 集合的最大容量
static final int MAXIMUM_CAPACITY = 1073741824;
// 默認(rèn)的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75F;
// 當(dāng)桶上的結(jié)點(diǎn)數(shù)大于這個(gè)值時(shí)會(huì)轉(zhuǎn)成紅黑樹(shù)
static final int TREEIFY_THRESHOLD = 8;
// 當(dāng)桶上的節(jié)點(diǎn)數(shù)小于這個(gè)值時(shí)會(huì)轉(zhuǎn)成鏈表
static final int UNTREEIFY_THRESHOLD = 6;
// 當(dāng)集合中的容量大于這個(gè)值時(shí)笛匙，表中的桶才能進(jìn)行樹(shù)形化侨把，否則桶內(nèi)元素太多時(shí)會(huì)擴(kuò)容，而不是樹(shù)形化          
// 為了避免進(jìn)行擴(kuò)容妹孙、樹(shù)形化選擇的沖突秋柄，這個(gè)值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
transient HashMap.Node<K, V>[] table;
transient Set<Entry<K, V>> entrySet;
// 記錄集合被修改的次數(shù)
transient int modCount;
// 當(dāng)前已占用數(shù)組長(zhǎng)度
int threshold;
// 散列表的加載因子
final float loadFactor;

Hash算法

這種做法可以使數(shù)組元素分布均勻，減少散列沖突蠢正。

static final int hash(Object key) {
    int h;
    // 算出來(lái)的hash值比較分散,減少了碰撞的可能性
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

key在數(shù)組中的位置公式：i = (table.length - 1) & hash;

hash值算出來(lái)骇笔，要計(jì)算當(dāng)前key在數(shù)組中的索引下標(biāo)位置時(shí)，可以采用取模的方式嚣崭，就是索引下標(biāo)位置 = hash 值 % 數(shù)組大小笨触，這樣做的好處，就是可以保證計(jì)算出來(lái)的索引下標(biāo)值可以均勻的分布在數(shù)組的各個(gè)索引位置上雹舀。但取模操作對(duì)于處理器的計(jì)算是比較慢的芦劣，數(shù)學(xué)上有個(gè)公式，當(dāng)b是2的冪次方時(shí)说榆，a % b = a &（b-1）持寄，所以此處索引位置的計(jì)算公式我們可以更換為： (n-1) & hash。

如何解決hash沖突

hash沖突指的是key值的hashcode計(jì)算相同娱俺，但key值不同的情況。

• 好的hash算法
• 到達(dá)閾值自動(dòng)擴(kuò)容
• hash沖突發(fā)生時(shí)废麻，采用鏈表來(lái)解決
• hash沖突嚴(yán)重時(shí)荠卷，鏈表自動(dòng)轉(zhuǎn)化成紅黑樹(shù)，提高遍歷速度

添加元素

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //數(shù)組為空烛愧，擴(kuò)容數(shù)組
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //如果當(dāng)前索引位置是空的油宜，直接生成新的節(jié)點(diǎn)在當(dāng)前索引位置上
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 如果key的hash和值都相等，直接把當(dāng)前下標(biāo)位置的Node值賦值給臨時(shí)變量
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 紅黑樹(shù) 
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 是個(gè)鏈表怜姿，把新節(jié)點(diǎn)放到鏈表的尾端
        else {
            for (int binCount = 0; ; ++binCount) {
                // 到了尾節(jié)點(diǎn)
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 當(dāng)鏈表的長(zhǎng)度大于等于 8 時(shí)慎冤，鏈表轉(zhuǎn)紅黑樹(shù)
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果存在跳出返回
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 說(shuō)明新節(jié)點(diǎn)的新增位置已經(jīng)找到了
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 記錄HashMap的數(shù)據(jù)結(jié)構(gòu)發(fā)生了變化
    ++modCount;
    //如果HashMap的實(shí)際大小大于擴(kuò)容的門(mén)檻，開(kāi)始擴(kuò)容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

1. 判斷鍵值對(duì)數(shù)組長(zhǎng)度是否是0沧卢，為0進(jìn)行擴(kuò)容蚁堤。
2. 根據(jù)鍵值key計(jì)算hash得到插入數(shù)據(jù)索引i，如果當(dāng)前索引位置是空的但狭，直接生成新的節(jié)點(diǎn)在當(dāng)前索引位置上披诗，轉(zhuǎn)向6。如果不為空立磁，轉(zhuǎn)向3呈队。
3. hash沖突，兩種解決方案：鏈表 or 紅黑樹(shù)唱歧。
4. 如果是鏈表宪摧，調(diào)用鏈表的新增方法粒竖。
5. 如果是紅黑樹(shù)，調(diào)用紅黑樹(shù)的新增方法几于。
6. 通過(guò)onlyIfAbsent變量判斷是否覆蓋對(duì)應(yīng)key的值蕊苗。
7. 判斷是否需要擴(kuò)容。

鏈表新增節(jié)點(diǎn)

循環(huán)鏈表孩革，將新元素追加隊(duì)尾岁歉。
當(dāng)鏈表長(zhǎng)度大于等于8，并且整個(gè)數(shù)組大小大于等于64時(shí)膝蜈，才會(huì)轉(zhuǎn)成紅黑樹(shù)锅移。注意當(dāng)數(shù)組大小小于64時(shí)，只會(huì)觸發(fā)擴(kuò)容饱搏，不會(huì)轉(zhuǎn)化成紅黑樹(shù)非剃。

紅黑樹(shù)新增節(jié)點(diǎn)

• 通過(guò)equals判斷新增的節(jié)點(diǎn)在紅黑樹(shù)上是不是已經(jīng)存在；
• 新增的節(jié)點(diǎn)如果已經(jīng)在紅黑樹(shù)上推沸，直接返回备绽；不在的話，判斷新增節(jié)點(diǎn)是在當(dāng)前節(jié)點(diǎn)的左邊還是右邊鬓催，左邊值小肺素，右邊值大；
• 自旋當(dāng)前節(jié)點(diǎn)宇驾，直到當(dāng)前節(jié)點(diǎn)的左邊或者右邊的節(jié)點(diǎn)為空時(shí)倍靡，停止自旋，當(dāng)前節(jié)點(diǎn)即為我們新增節(jié)點(diǎn)的父節(jié)點(diǎn)课舍；
• 把新增節(jié)點(diǎn)放到當(dāng)前節(jié)點(diǎn)的左邊或右邊為空的地方塌西，并于當(dāng)前節(jié)點(diǎn)建立父子節(jié)點(diǎn)關(guān)系；
• 進(jìn)行著色筝尾，旋轉(zhuǎn)捡需。

擴(kuò)容

擴(kuò)容時(shí)機(jī)：

1. 添加元素時(shí)發(fā)現(xiàn)數(shù)組為空，進(jìn)行初始化擴(kuò)容筹淫，默認(rèn)擴(kuò)容大小為 16;
2. 添加元素成功站辉，發(fā)現(xiàn)現(xiàn)有數(shù)組大小大于擴(kuò)容的門(mén)閥值時(shí)，進(jìn)行擴(kuò)容损姜，擴(kuò)容為老數(shù)組大小的2倍;
   每次擴(kuò)容時(shí)門(mén)閥值都會(huì)被重新計(jì)算庵寞，門(mén)閥值等于數(shù)組的大小 * 影響因子（0.75）。

1.7源碼：
新建一個(gè)擴(kuò)容數(shù)組薛匪，將數(shù)組元素轉(zhuǎn)移到新數(shù)組里面捐川，修改閾值。
轉(zhuǎn)移數(shù)組元素：
遍歷同桶數(shù)組中的每一個(gè)桶逸尖，遍歷桶的外接鏈表古沥。找到新表的桶位置瘸右。
舊桶數(shù)組中的某個(gè)桶的外掛單鏈表是通過(guò)頭插法插入新桶數(shù)組中的，并且原鏈表中的Entry結(jié)點(diǎn)并不一定仍然在新桶數(shù)組的同一鏈表岩齿。

1.8源碼：
為了性能在同一索引處發(fā)生哈希沖突到一定程度時(shí)鏈表結(jié)構(gòu)會(huì)轉(zhuǎn)換為紅黑數(shù)結(jié)構(gòu)存儲(chǔ)沖突元素太颤，故在擴(kuò)容時(shí)如果當(dāng)前索引中元素結(jié)構(gòu)是紅黑樹(shù)且元素個(gè)數(shù)小于鏈表還原閾值時(shí)就會(huì)把樹(shù)形結(jié)構(gòu)縮小或直接還原為鏈表結(jié)構(gòu)。

查找元素

通過(guò)key計(jì)算索引盹沈，找到桶位置龄章，先檢查第一個(gè)節(jié)點(diǎn)，如果是則返回乞封，如果不是做裙，則遍歷其后面的鏈表或者紅黑樹(shù)，找到返回肃晚，沒(méi)有找到返回null锚贱。

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                // 如果當(dāng)前節(jié)點(diǎn)hash等于key的hash，并且equals相等关串，當(dāng)前節(jié)點(diǎn)就是我們要找的節(jié)點(diǎn)
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

刪除元素

刪除元素首先是要找到桶的位置拧廊，然后如果是鏈表，則進(jìn)行鏈表遍歷晋修，找到需要?jiǎng)h除的元素后吧碾，進(jìn)行刪除；如果是紅黑樹(shù)墓卦，也是進(jìn)行樹(shù)的遍歷倦春，找到元素刪除后，進(jìn)行平衡調(diào)節(jié)趴拧，當(dāng)紅黑樹(shù)的節(jié)點(diǎn)數(shù)小于6時(shí)，會(huì)轉(zhuǎn)化成鏈表山叮。

參考
JDK1.8源碼(七)——java.util.HashMap 類
《極客時(shí)間-數(shù)據(jù)結(jié)構(gòu)與算法之美專欄》