前言
手執(zhí)煙花以謀生 心懷詩(shī)意以謀愛(ài)
不論我是否去記錄，在往昔與未來(lái)的無(wú)限歲月中，仍會(huì)有人奮起，有人沉淪，有人成為英雄，有人扮演小丑，有人挺身而出，有人迷惘沉淪。但你只需——“在繁華中自律，在落魄中自愈，在謀生的路上不拋棄良知，在謀愛(ài)的路上不丟失最嚴(yán)，這次我站在風(fēng)中，任你大霧四起。”
HashMap的設(shè)計(jì)原理
1. HashMap設(shè)計(jì)思路：- Map是一種以鍵值對(duì)存儲(chǔ)數(shù)據(jù)的容器，而 HashMap 則是借助了鍵值 Key 的 hashcode 值來(lái)組織存儲(chǔ)，使得可以非常快速和高效地地根據(jù)鍵值 key 進(jìn)行數(shù)據(jù)的存取。
- 對(duì)于鍵值對(duì)，HashMap 內(nèi)部會(huì)將其封裝成一個(gè)對(duì)應(yīng)的 Entry 對(duì)象，即 Entry 對(duì)象是鍵值對(duì)的組織形式；
- 對(duì)于每個(gè)對(duì)象而言，JVM 都會(huì)為其生成一個(gè) hashcode 值。HashMap 在存儲(chǔ)鍵值對(duì) Entry 的時(shí)候，會(huì)根據(jù) Key 的 hashcode 值，以某種映射關(guān)系，決定應(yīng)當(dāng)將這對(duì)鍵值對(duì) Entry 存儲(chǔ)在 HashMap 中的什么位置上；
- 當(dāng)通過(guò) Key 值取數(shù)據(jù)的時(shí)候，然后根據(jù) Key 值的 hashcode 和 內(nèi)部映射條件，直接定位到 Key 對(duì)應(yīng)的 Value 值存放在什么位置，可以非常高效地將 Value 值取出。
HashMap 的哈希函數(shù)設(shè)計(jì)
hash 函數(shù)是先拿到 key 的 hashcode，是一個(gè)32位的 int 值，然后讓 hashcode 的高16位和低16位進(jìn)行異或操 作
也叫擾動(dòng)函數(shù)，這么設(shè)計(jì)有二點(diǎn)原因
- 一定要盡可能降低 hash 碰撞，越分散越好；
- 算法一定要盡可能高效，因?yàn)檫@是高頻操作, 因此采用位運(yùn)算；
什么是Hash？
Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長(zhǎng)度的 `輸入`，通過(guò)散列算法變換成固定長(zhǎng)度的 `輸出`，該輸出就是散列值。ok，這樣的定義可能比較抽象。咱們結(jié)合上面提到的方案二的例子一句一句解釋。? HashMap 的數(shù)據(jù)結(jié)構(gòu)（JDK 1.8）
本文說(shuō)的是 JDK1.8 版本的，內(nèi)部使用數(shù)組 + 鏈表紅黑樹(shù)
JDK1.8 對(duì) HashMap 主要做了哪些優(yōu)化呢？
- 數(shù)組 + 鏈表改成了數(shù)組 + 鏈表或紅黑樹(shù)；
- 鏈表的插入方式從頭插法改成了尾插法，簡(jiǎn)單說(shuō)就是插入時(shí)，如果數(shù)組位置上已經(jīng)有元素，1.7 將新元 素放到數(shù)組中，原始節(jié)點(diǎn)作為新節(jié)點(diǎn)的后繼節(jié)點(diǎn)，1.8 遍歷鏈表，將元素放置到鏈表的最后；
- 擴(kuò)容的時(shí)候 1.7 需要對(duì)原數(shù)組中的元素進(jìn)行重新 hash 定位在新數(shù)組的位置，1.8 采用更簡(jiǎn)單的判斷邏 輯，位置不變或索引 + 舊容量大小；
- 在插入時(shí)，1.7 先判斷是否需要擴(kuò)容，再插入，1.8 先進(jìn)行插入，插入完成再判斷是否需要擴(kuò)容；
?為什么要做這幾點(diǎn)優(yōu)化
- 防止發(fā)生 hash 沖突，鏈表長(zhǎng)度過(guò)長(zhǎng)，將時(shí)間復(fù)雜度由 O(n) 降為 O(logn) ;
- 因?yàn)?1.7 頭插法擴(kuò)容時(shí)，頭插法會(huì)使鏈表發(fā)生反轉(zhuǎn)，多線程環(huán)境下會(huì)產(chǎn)生環(huán)； A 線程在插入節(jié)點(diǎn) B，B 線程也在插入，遇到容量不夠開(kāi)始擴(kuò)容，重新 hash，放置元素，采用頭插法， 后遍歷到的 B 節(jié)點(diǎn)放入了頭部，這樣形成了環(huán)，如下圖所示：
1.7 的擴(kuò)容調(diào)用 transfer 代碼，如下所示：
void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {while(null != e) {Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);} int i = indexFor(e.hash, newCapacity);e.next = newTable[i]; //A線程如果執(zhí)行到這一行掛起，B線程開(kāi)始進(jìn)行擴(kuò)容newTable[i] = e;e = next;}}} - 擴(kuò)容的時(shí)候?yàn)槭裁?1.8 不用重新 hash 就可以直接定位原節(jié)點(diǎn)在新數(shù)據(jù)的位置 這是由于擴(kuò)容是擴(kuò)大為原數(shù)組大小的 2 倍，用于計(jì)算數(shù)組位置的掩碼僅僅只是高位多了一個(gè) 1，怎么理 解呢？ 擴(kuò)容前長(zhǎng)度為 16，用于計(jì)算 (n-1) & hash 的二進(jìn)制 n-1 為 0000 1111，擴(kuò)容為 32 后的二進(jìn)制就高位多 了 1，為 0001 1111。 因?yàn)槭?& 運(yùn)算，1 和任何數(shù) & 都是她本身，那就分二種情況，如下圖：原數(shù)據(jù) hashcode 高位第 4 位為 0 和高位為 1 的情況； 第四位高位為 0，重新 hash 數(shù)值不變，第四位為 1，重新 hash 數(shù)值比原來(lái)大 16（舊數(shù)組的容量）
