- 課程目標

- 目前已經(jīng)講過的內(nèi)容

- 數(shù)據(jù)結(jié)構(gòu)

? ??

? ? memcache 本質(zhì)上來講就是一個超大的 hash table，而 MySQL 的 innodb 引擎使用的是 B+ tree，它們將 tuple 存儲在 B+ tree 的葉子節(jié)點上

? ??

? ? 臨時數(shù)據(jù)也可以用數(shù)據(jù)結(jié)構(gòu)來維護（就是緩存），比如在執(zhí)行一個查詢時，為了高效地計算某些東西，可以在運行時構(gòu)建一個數(shù)據(jù)結(jié)構(gòu)，放入所需數(shù)據(jù)，完成查詢的執(zhí)行，然后將這個臨時數(shù)據(jù)結(jié)構(gòu)丟棄掉

? ??

? ? 表索引（table index）也有對應(yīng)的數(shù)據(jù)結(jié)構(gòu)，即使用 tuple 中的 key 來構(gòu)建一個詞匯表，有些像書中的目錄，這樣就能很快地找到那個對應(yīng)的單個元素，也沒必要對整個數(shù)據(jù)庫進行循環(huán)掃描了

- 設(shè)計數(shù)據(jù)結(jié)構(gòu)? ??

? ??

? ? 1. 如何弄一個數(shù)據(jù)結(jié)構(gòu)，使得無須對該數(shù)據(jù)結(jié)構(gòu)進行大改或者每次要重新轉(zhuǎn)換整個數(shù)據(jù)結(jié)構(gòu)的情況下，支持快速讀寫

? ? 2. 該如何讓多個線程或者多個查詢?nèi)ピL問這個數(shù)據(jù)結(jié)構(gòu)，并且該數(shù)據(jù)結(jié)構(gòu)表示的數(shù)據(jù)不會再物理存儲層面出現(xiàn)問題，因為同時被線程修改的某個地址的數(shù)據(jù)會變成臟數(shù)據(jù)，從而讓它們訪問到某些無效的 page 或者是某些無效的內(nèi)存位置

? ??

? ? 這里最關(guān)心的應(yīng)該還是數(shù)據(jù)結(jié)構(gòu)的 物理完整性，而不是 邏輯完整性

? ??

- Hash 表? ??

? ??

? ? hash 表是一個抽象的數(shù)據(jù)類型，它可以提供無序的關(guān)聯(lián)數(shù)據(jù)的實現(xiàn)（unordered associative array implementation）的 API

? ??

? ? 注意，hash 函數(shù)并不會一直讓我們精確地找到我們想要找的東西，因為這會產(chǎn)生 hash 碰撞，但至少它能讓我們找到正確的位置，然后我們知道該如何在周圍找到我們想要的那個數(shù)據(jù)

? ??

? ? hash 表操作時間復(fù)雜度最壞的情況為什么是 O(n) 呢？這是因為 key 通過 hash 都碰撞到一起，放在一個數(shù)據(jù)/隊列/鏈表中了，所以這個時候就需要遍歷查找想要的那個 key

? ??

? ? 雖然 hash 表操作平均時間復(fù)雜度為 O(1)，但不同的 hash 函數(shù)執(zhí)行時間可能不一樣，有些快有些慢，在面對超大規(guī)模基數(shù)的數(shù)據(jù)查詢時，慢的 hash 函數(shù)會導(dǎo)致整個應(yīng)用需要付出大量的金錢，比如商業(yè)交易這一場景

? ??

? ? - 靜態(tài) Hash 表

? ??

? ? ? ??

? ? ? ? 一個最簡單的 hash 表如上圖所示，它其實就是一個巨大的數(shù)組，看起來就像是一大塊內(nèi)存

? ? ? ??

? ? ? ? 數(shù)組中每個 offset 位置都對應(yīng)了一個給定的元素

? ? ? ??

? ? ? ? 通過對 key 進行 hash，即將 key 與所有元素數(shù)量進行取模（如果該 key 對應(yīng)這個數(shù)組的下標），就會得到它對應(yīng)的 offset 值

? ? ? ??

? ? ? ??

? ? ? ? 但實際上 hash 表并不完全是這樣，hash 表需要保存的是一些指向這些原始的 key 所在位置的指針

? ? ? ??

? ? ? ??

? ? ? ? 對于這種 hash 表而言，存在的問題是什么呢？

? ? ? ??

? ? ? ? 1. 需要提前知道 hash 表中元素的數(shù)量

? ? ? ? 2. key 與 key 之間沒有碰撞（collision）

? ? ? ??

? ? ? ? 碰撞 指的是，對 key 進行 hash 后的結(jié)果指向了同一個 slot

? ? ? ??

? ? ? ??

? ? ? ? 完美 hash 函數(shù)（perfect hash function）是一種存在于研究文獻中的一種理論上的東西，因為在實際工作中，如果 key1 != key2，那么有可能 hash(key1) = hash(key2)。實際上能實現(xiàn)所謂完美 hash 函數(shù)的方式是通過另一張 hash 表將一個 key 映射到另一個 hash value 上（這種方式真的很蠢，因為速度會很慢），比如 Java 中的 concurrentHashmap，第一次 hash 是為了分區(qū)，第二次 hash 是為了確定具體位置，但也不能保證完美

? ? ? ??

? ? 那么該如何在擯棄上述兩個假設(shè)的前題下實現(xiàn)一個 hash 表呢？? ??

? ??

? ??

? ? 要實現(xiàn)一個 hash 表，它的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是由 2 部分組成

? ??

? ? 1. hash 函數(shù)

? ? ? ? 該函數(shù)將任意的 key 映射到一個較小范圍的 integer value 上，同時該函數(shù)會生成一個 32/64 bit 的唯一 hash 值（也可能不唯一）

? ? ? ??

? ? ? ? hash 函數(shù)的速度和碰撞率之間要做取舍

? ? 2. hashing scheme

? ? ? ? 即當(dāng)在 hash 表中遇上 hash 碰撞時，用 hashing scheme 來處理這種問題，hashing scheme 是一種機制或者說步驟

? ? ? ??

? ? ? ? 同樣的，這個也需要在內(nèi)存和計算（速度）之間做取舍，即時間換空間，空間換時間。

? ??

? ? - Hash 函數(shù)

? ??

? ? ? ??

? ? ? ? hash 函數(shù)就是一個速度很快的函數(shù)，將任意的 byte array 或者任意的 key 傳入函數(shù)，它就會返回一個 32/64 bit 的 integer? ??

? ? ? ??

? ? ? ? 比如一些著名的 hash 函數(shù)，比如 SHA-256/MD5

? ? ? ??

? ? ? ? 實際上 SHA-256 是不可逆的加密 hash 函數(shù)，它是一種使用了 公鑰/私鑰 的東西

? ? ? ??

? ? ? ? 對于 MD5 來說，可以將任意的 key 傳入它的 hash 函數(shù)，然后返回一個 32 bit 的唯一 hash 值，它本來應(yīng)該是不可逆的，但現(xiàn)在因為有人破解了它，所以可逆

? ? ? ??

? ? ? ? 在數(shù)據(jù)庫系統(tǒng)中，如果要做 hash 表，那么我們對它的加密性并不在意，所以也不會去用 SHA-256（用這個加密速度也超慢）

? ? ? ??

? ? ? ? MD5 是一種單向散列（one-way hash），可以將它作為構(gòu)建 hash 表的 hash 函數(shù)，但沒必要因為它還是非常慢。同時它也是不安全的，因為可以通過彩虹表對它進行破解

? ? ? ??

? ? ? ? 一些 hash 函數(shù)圖

? ? ? ??

? ? ? ??

? ? ? ? - CRC-64 是 1975 年被發(fā)明出來的，它的碰撞率雖然合理，但是速度非常非常慢

? ? ? ? - MurmurHash，從數(shù)據(jù)庫層面來講，它的誕生開啟了現(xiàn)代 hash 函數(shù)的時代。它在 2008 年誕生，是開源的。G 家在 2010 年早期采用了 MurmurHash，并對其做了改進，使得長度更短的 key 可以獲得更快的速度，然后 G 家就發(fā)布了 CityHash。2014 年時他們由基于這個做了改進，然后發(fā)布了 FarmHash，它的碰撞率比 CityHash 更低

? ? ? ? - Meta 的 XXHash 的速度更快，碰撞率最低（這里指的是 XXHash 3）

? ? ? ??

? ? ? ? 2 張 hash 函數(shù)的 benchmark 圖

? ? ? ??

? ? ? ??

? ? ? ? 從上圖可以看到，當(dāng) key 的大小為 32 byte 和 64 byte 時，F(xiàn)armHash、CityHash、XXHash3 都出現(xiàn)了非常漂亮的尖峰，這是因為它們進行計算處理的 key 都剛好填滿單個 Cache Line（CPU 和主存之間數(shù)據(jù)傳輸?shù)淖钚挝唬?。?dāng)從內(nèi)存中讀取一次數(shù)據(jù)時，將 64 byte 大小的 key 放入 Cache 中，這樣就可以一次性操作所有從該緩存中找到的數(shù)據(jù)，即一次操作一整個 Cache line 中的數(shù)據(jù)。當(dāng) key 的大小超過 64 byte 后，CityHash 和 FarmHash 就會切換到另一種不同的算法上，導(dǎo)致速度上會有些不同

? ? ? ??

? ? ? ? 所以在數(shù)據(jù)庫系統(tǒng)中，盡可能多地去使用 XXHash3

? ??

? ? - 靜態(tài) Hashing Schemes

? ??

? ? ? ??

? ? ? ? 注意，此處討論的內(nèi)容跟所使用的 hash 函數(shù)沒有關(guān)系，所有的 hashing scheme 的工作方式都是一樣的，因為這是做完 hash 計算，跳轉(zhuǎn)到某個位置時才做的

? ? ? ??

? ? ? ? Cuckoo 和 Robin Hood Hashing 都是基于 Linear Probe Hashing 做的改進版

? ? ? ??

? ? ? ? 注意這些都是 靜態(tài) Hashing Schemes，意味著在分配內(nèi)存時，一開始就得知道要保存的 key 的數(shù)量，在某些情況下，可以猜出這個 hash 取模的基數(shù)有多大（key % n，n 就是這個基數(shù)）。在進行查詢處理或者使用 hash 表進行 join 操作時，需要知道在 hash 表中大概要對多少個 key 進行 hash，然后就可以進行內(nèi)存分配了

? ? ? ??

? ? ? ? 如果 hash 表容量快滿了，就必須對其進行擴容，基本上是擴展到原來的 2 倍。即將第一個 hash 表中所有的 key 復(fù)制到第二個 hash 表上，但這樣做代價非常高（所有元素重新打散并 hash 存儲，代價很高）

? ? ? ??

? ? ? ? 理想情況下，如果大概知道 hash 表的容量上限是多少，也就沒必要去做擴容的操作了

? ? ? ??

? ? ? ? 1. Linear Probe Hashing

? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? Linear Probe Hashing 有時也叫 Open Addressing，即開地址法，它就是一個大型的 slot 表，通過 hash 函數(shù)來跳轉(zhuǎn)到該表中的某個 offset 值上，或者是在該表中添加一些 slot

? ? ? ? ? ??

? ? ? ? ? ? Python 的 Dictionary 背后的數(shù)據(jù)結(jié)構(gòu)其實就是 hash 表，它就是一個使用了 Linear Probe Hashing 的 hash 表

? ? ? ? ? ??

? ? ? ? ? ? 如何解決 hash 碰撞？如果在進行 hash 計算所得到的 slot 位置上已經(jīng)有數(shù)據(jù)在上面，那么就挨著這條數(shù)據(jù)往下掃描，直到遇到下一個能插入數(shù)據(jù)的空 slot 為止（空的 slot 指沒有找到 key 對應(yīng)的 value）

? ? ? ? ? ??

? ? ? ? ? ? 一個例子

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? slot 上會保留原始的 key/value 對，原始的 key 會有所保留的原因是，當(dāng)要開始查找時，如果有多個 entry（key/value 對），那么就必須在 slot 上往下掃描，我們需要知道在該 slot 中存放的 key 是不是我們想要的那個，畢竟也沒法保證根據(jù) hash 計算得到的 slot 表中的位置就是我們想要的那個準確位置

? ? ? ? ? ??

? ? ? ? ? ? 比如對 C 進行 hash，但此時 C 落在了之前 A 的位置

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 所以此時就直接跳到 A 的下一個位置，然后把 entry（這里指 key/value 對） 插入到那個位置上

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 比如插入 E 也是一樣的

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 那么假設(shè)要刪除 C，應(yīng)該怎么做呢？

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 先對 C 進行 hash，hash 完后，找到的是 A 所在的位置，但這并不是要刪除的那個數(shù)據(jù)，于是繼續(xù)往下掃描，找到了 C，直接移除

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 但是這里會有一個問題

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 如果去查找 D，那么它會發(fā)現(xiàn) C 的位置是一個空 slot，那么它就認為它的查找已經(jīng)完成了，即便這個 D 所對應(yīng)的數(shù)據(jù)是在下面的

? ? ? ? ? ??

? ? ? ? ? ? 所以有兩種方式來做移除

? ? ? ? ? ??

? ? ? ? ? ? 1. tombstone

? ? ? ? ? ? ? ? 即在原來 C 的位置上放一個這個標記，表示這里沒有一個 logic entry 了，但從物理上來講，這個 slot 是被占用了

? ? ? ? ? ??

? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? 當(dāng)查找 D 時，會落到這個有 tombstone 標記的 slot 上面

? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? 然后雖然這個 slot 中沒有數(shù)據(jù)，但它確實不是空 slot，所以直接跳到下一個

? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? 但，這就浪費了空間。這需要后續(xù)清理掉，并用上 fill factor（填充因子）

? ? ? ? ? ? 2. data movement

? ? ? ? ? ? ? ? 就是做數(shù)據(jù)移動，看到有空數(shù)據(jù)往上移動

? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? 但要記住這個 slot 表是 環(huán)形 的

? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? 技術(shù)上來講，B 應(yīng)該是在 F 后面的，雖然物理上不是，如果像上圖中那樣，將 B 移動到箭頭所指向的位置，可能會導(dǎo)致某些錯誤發(fā)生

? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? 因為 B 原來 hash 的位置是在上面，如果移動到下面的位置，在查找 B 時，會看到那里啥都沒有

? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? 所以大部分情況下都會去使用 tombstone，數(shù)據(jù)移動這種方式實際上很復(fù)雜

? ? ? ? ? ??

? ? ? ? ? ? 在實戰(zhàn)中，一般使用 n 或者 2n 作為 slot 的數(shù)量，n 為要放入 key 的數(shù)量

? ? ? ? ? ??

? ? ? ? 2. Robin Hood Hashing

? ? ? ??

? ? ? ? ? ? 在了解這個之前，得先了解 Non-Unique Keys，即非唯一 Key，因為在實際的數(shù)據(jù)集中，沒辦法假設(shè)所有的 Key 都是唯一的，所以需要在 hash 表中對它們進行處理，有 2 種方法可以做到

? ? ? ? ? ??

? ? ? ? ? ? 第 1 種方法是，維護一個單獨的鏈表，上面保存了所有的值。即在 hash 表中的 key 會指向?qū)儆谠?key 的單獨鏈表，該鏈表上所保存的 value 對應(yīng)的都是同一個 key

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 第 2 種方法是，保存冗余的 key，這也是最常見的。即在 slot 數(shù)組中不斷地復(fù)制這個 key

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 在實戰(zhàn)中，第 2 種方法用的多

? ? ? ? ? ??

? ? ? ? ? ? Bobin Hood Hashing 是在 1985 年提出的，出自當(dāng)時一篇無人問津的 paper，然后過去 10 年，它在 Hacker News 上出現(xiàn)過幾次。而 Bobin Hood（羅賓漢）是一個英國的民間傳說，講述的是一個劫富濟貧的俠盜的故事。那么 Bobin Hood Hashing 做的事情也是類似的，就是會讓那些 "poor" key 從 "rich" key 身上偷取 slot

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? Number of Positions（距離數(shù)）表示的是你所在的位置與你第一次進行 hash 所計算出的位置之間的距離差。

? ? ? ? ? ??

? ? ? ? ? ? 距離數(shù)越大，越 "poor"，反之越 "rich"

? ? ? ? ? ??

? ? ? ? ? ? 基本思路是，對整個 hash 表進行平衡，嘗試讓每個 key 都盡可能靠近它原本所在的位置。即對所有的 key 來講，在全局狀態(tài)下盡可能快地找到它們，而不是針對于某一個。

? ? ? ? ? ??

? ? ? ? ? ? 一個例子

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 在插入數(shù)據(jù) A 時，可以記錄下數(shù)據(jù) A 實際所在的位置與第一次 hash 計算出的原始位置所差的跳轉(zhuǎn)次數(shù)

? ? ? ? ? ??

? ? ? ? ? ? 第一次插入 A 時，跳轉(zhuǎn)次數(shù)為 0，所以是 A | val[0]，對于 B 也是一樣

? ? ? ? ? ??

? ? ? ? ? ? C 要插入時，本來要插 A 的位置，但因為 A 的位置不是空的，所以它插入到 A 的下一位

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 所以是 C | val[1]，因為 C 當(dāng)前所在的位置距離它第一次通過 hash 所得出的位置相差 1 個單位

? ? ? ? ? ??

? ? ? ? ? ? 對于 D 來說也是一樣的

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 而對于 E

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 因為 E 需要跳轉(zhuǎn) 2 次才能達到 D 跳轉(zhuǎn)一次的位置（D 跳轉(zhuǎn)一次就到它原本第一次 hash 計算出來的位置了），E[2] > D[1]，所以 E 比 D 要更 "poor"，所以 E 就要去 偷 D 所在的 slot 的位置，并插入其中

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 那么現(xiàn)在就只能將 D 插入到 E 的下面了，并將 D | val[1]，更新為 D | val[2]

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 而 F 就是放到 D 下面

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 這種方法會使得寫入或者插入的代價更高，因為這種方式進行了多次寫入的操作，而 Linear Probe Hashing 只需要一次寫入

? ? ? ? ? ??

? ? ? ? ? ? 但是在該算法下，需要對更多的條件進行檢查，看看能否將一個放到另一個的位置上，只要有一次條件誤判，就會付出巨大的代價。更多的寫入操作帶來更多的緩存無效。所以在實戰(zhàn)中，還是優(yōu)先使用 Linear Probe Hashing，它依然是最快的方法

? ? ? ? ? ??

? ? ? ? 3. Cuckoo Hashing

? ??

? ? ? ? ? ??

? ? ? ? ? ? 思路是，使用多個 hash 表，然后要做的是該判斷往哪個 hash 表中插入 key，即哪個 hash 表能提供一個空余的 slot

? ? ? ? ? ??

? ? ? ? ? ? 在 Cuckoo Hashing 中，查找和刪除的時間復(fù)雜度始終是 O(1)，這意味著當(dāng)進行查找時，始終都會跳到 hash 表上，準確地找到那個數(shù)據(jù)

? ? ? ? ? ??

? ? ? ? ? ? 但插入操作的代價可能更高，因為要判斷是在 hash 表 1 中還是 hash 表 2 中進行存儲等操作

? ? ? ? ? ??

? ? ? ? ? ? 例子

? ? ? ? ? ??

? ? ? ? ? ? 注意大多數(shù)人在使用 Cuckoo Hashing 時，通常都只使用 2 個 hash 表

? ? ? ? ? ??

? ? ? ? ? ? 對于 Cuckoo Hashing 中的每個 hash 表來說，必須為 hash 函數(shù)提供一個單獨的 hash seed，拿到 key 之后，對它 hash 2 次（這里對同一個 key，給 hash 函數(shù)不同的 seed，那么就會生成不同的 hash 值）

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 這個時候要插入 B 了

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 但是在 hash 表 1 中，對應(yīng)的位置已經(jīng)有 A 了，這個時候就選擇 hash 表 2 插入

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 這個時候插入 C

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 但現(xiàn)在 hash1(C) 和 hash2(C) 的位置都被 A 和 B 占了，這個時候該怎么辦呢？

? ? ? ? ? ??

? ? ? ? ? ? 答案是隨機選一個，這里選的是 hash 表 2，然后移除掉 B，插入 C

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 那么 B 怎么辦呢？重新 hash 一下 B，搶走 A 的 slot

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 那么 A 怎么辦呢？重新 hash 一下 A，把 A 放到 hash 表 2 中的一個空 slot 的地方

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 但這個方式存在 遞歸碰撞，即有可能在碰到最后一個元素后，又碰到最初的那個元素去了，這種情況下，需要擴容（臥槽，這 tm 擴容。。。）

? ? ? ? ? ??

? ? - 動態(tài) Hash 表? ??

? ??

? ? ? ??

? ? ? ? 動態(tài) hash 表能夠在無須重建整個東西的情況下，根據(jù)需要調(diào)整大小，比如 chained hash table，這是最常用的一種動態(tài) hash 表

? ? ? ??

? ? ? ? 1. Chained Hash 表

? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 也叫 chained hashing/bucket hash table，里面主要維護了一個包含了 bucket 的鏈表，通過將具有相同 hash key 的所有元素放入相同的 bucket 來解決沖突，也就是在 bucket list 末尾追加，所以每個 bucket chain 都可以永遠擴容下去

? ? ? ? ? ??

? ? ? ? ? ? 所以要查找的話，也只能循環(huán)掃描了

? ? ? ? ? ??

? ? ? ? ? ? 例子

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 可以將這些 bucket 當(dāng)作是 page

? ? ? ? ? ??

? ? ? ? 2. Extendible Hashing

? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 基于 chained hash 表的思想，但是不同于它的無限擴容，Extendible Hashing 要做是將鏈表逐步拆分

? ? ? ? ? ??

? ? ? ? ? ? 這里 "拆分" 的意思也跟 "重建" 差不多，也要進行一波擴容并重新 hash 的操作，但這里只是對 某個獨立的局部 進行操作

? ? ? ? ? ??

? ? ? ? ? ? 要拆分的只是那些要 overflow 的 chain，而不是整個 hash 表

? ? ? ? ? ??

? ? ? ? ? ? 拆分完那些 overflowed bucket 之后，在其對應(yīng)的 slot array 中，允許多個 slot 指向同一個 bucket chain

? ? ? ? ? ??

? ? ? ? ? ? 優(yōu)勢是，在移動數(shù)據(jù)時，只需要移動那些 overflowed 的 bucket 就行

? ? ? ? ? ??

? ? ? ? ? ? 例子

? ? ? ? ? ??

? ? ? ? ? ? 要有 1 個 全局 counter，它負責(zé) bit 的數(shù)量，即負責(zé)需要看幾個 bit 才能去找對應(yīng)的 bucket

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 而對于每個 bucket chain 或者每個 bucket，給它們一個局部的 counter，表示需要看幾個 bit 才能找到該位置

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 在這個例子中，第 1 個 bucket 中的局部 counter 的值是 1，表示只需要看 1 bit 就能定位到這個 bucket

? ? ? ? ? ??

? ? ? ? ? ? 這就是為啥你看那個藍色圈出來的 bit，看 00 和 01 時，它們倆都會映射到同一個 bucket，因為它們第 1 個 bit 都是 0，因為這個 bucket 存在 overflow 的情況，還沒有對它進行拆分

? ? ? ? ? ??

? ? ? ? ? ? 另外 2 個 bucket 擁有的分別是藍色圈出來的 10 和 11，因為它們的局部 counter 的值是 2，也就是說需要看 2 個 bit 才行

? ? ? ? ? ??

? ? ? ? ? ? 現(xiàn)在假設(shè)要查找 A? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 注意這里生成的 hash 是一堆 bit 序列

? ? ? ? ? ??

? ? ? ? ? ? 然后看下全局 counter，它會檢查這個 hash 函數(shù)生成的 bit 序列中的前多少位，以此來決定要跳轉(zhuǎn)到哪個 bucket

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 例子中全局 counter 的值是 2，那么只需要看這個 bit 序列的前 2 位，即 01，然后在 slot array 中查找

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 找到 01，跟著指針，就找到了對應(yīng)的那個 bucket

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 如果這個時候要插入 B

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 因為全局 counter 是 2，那么看 B 的前 2 位，是 10，跟著 slot array 中 10 指的位置，第 2 個 bucket 那兒有一個空余的位置，插入它即可

? ? ? ? ? ??

? ? ? ? ? ? 如果這個時候要插入 C

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? C 目前要插入的位置是第 2 個 bucket，但是此時第 2 個 bucket 沒空間了，它變成 overflowed 的了，所以現(xiàn)在必須要對它進行拆分

? ? ? ? ? ??

? ? ? ? ? ? 怎么拆分呢？

? ? ? ? ? ??

? ? ? ? ? ? 先把全局 counter 增加到 3

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 然后將 slot array 擴容到原來的 2 倍，這樣就可以處理 3 bit 的情況了

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 注意，這個 slot array 的擴容操作代價很低，因為這只是一個指針數(shù)組，可以在上面用一個 latch 來保護它，調(diào)整完大小再將數(shù)據(jù)放回去，無須移動 bucket 中的數(shù)據(jù)

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 如上圖，對 bucket 進行重構(gòu)，將保存在這些單個 page 上的數(shù)據(jù)進行拆分，并根據(jù)局部 counter 中的值，將它們重新映射

? ? ? ? ? ??

? ? ? ? ? ? 現(xiàn)在再嘗試插入 C

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 3 個 bit，C 的 hash 結(jié)果的前 3 位是 101，找到 slot array 中 101 的位置，跟著它的指針，即能找到對應(yīng)位置插入

? ? ? ? ? ??

? ? ? ? ? ? 注意這里并沒有對全部的 bucket 進行拆分，而只是拆分了之前那個 overflowed 的 bucket，即之前的第 2 個

? ? ? ? ? ??

? ? ? ? ? ? 刪除操作其實就是將插入操作逆向執(zhí)行

? ? ? ? ? ??

? ? ? ? ? ? 每個 bucket 就是 page

? ? ? ? ? ??

? ? ? ? ? ? Buffer 池中可能存儲的是一張表下涉及的多個 page 的數(shù)據(jù)條目，也可能是多個表下的部分數(shù)據(jù)條目

? ? ? ? ? ??

? ? ? ? 3. Linear Hashing? ??

? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? Extendible Hashing 存在一個小問題，就是要拆分 overflowed bucket 時，需要將 slot array 擴容為原來的 2 倍大，在調(diào)整 slot array 的大小時，需要在上面使用一個 latch，這樣能保證直到重新分配完所有的數(shù)據(jù)為止，其他人不會對其進行讀寫

? ? ? ? ? ??

? ? ? ? ? ? 這會成為一個性能瓶頸，因為這個 hash 表同一時間可能會被多個人訪問

? ? ? ? ? ??

? ? ? ? ? ? Linear Hashing 的思路是，只需要去重新分配那些 overflowed bucket 即可，沒必要去用一個全局的 latch 來阻止所有人訪問這個 hash 表

? ? ? ? ? ??

? ? ? ? ? ? 那么如何做到呢？

? ? ? ? ? ??

? ? ? ? ? ? Linear Hashing 會去維護多個 hash 函數(shù)，這些 hash 函數(shù)的工作方式和之前講到的 Cuckoo Hashing 中相同，用不同的 seed 對給定的 key 生成不同的 hash 值，然后找到那個對應(yīng)的 bucket

? ? ? ? ? ??

? ? ? ? ? ? 這里需要維護一個新的東西，叫 split pointer，它會去跟蹤那個要進行 split 的 overflowed bucket

? ? ? ? ? ??

? ? ? ? ? ? 例子

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 初始狀態(tài)下，這個 split pointer 指向 slot array 的第 0 個

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 此處 hash 函數(shù)中的 n 即擁有的 entry 的數(shù)量

? ? ? ? ? ??

? ? ? ? ? ? 假設(shè)現(xiàn)在要去查找 key 為 6 的相關(guān)數(shù)據(jù)

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 6 % 4 = 2，那么在 slot array 中就是 2 所在的位置，順著其指針找，找到第 3 個 bucket，然后在 bucket 中順序查找比對 key，就找到了對應(yīng)的位置

? ? ? ? ? ??

? ? ? ? ? ? 假設(shè)現(xiàn)在要插入 17

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 那么 17 % 4 就是 1，找到 slot array 中 1 所在的位置，順著其指針找，找到第 2 個 bucket，但在這個 bucket 中，沒有空余的 slot，那么怎么辦呢？創(chuàng)建一個 overflow bucket，在這個上面放 17 這個值

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 因為現(xiàn)在創(chuàng)建了一個 overflowed bucket，就相當(dāng)于觸發(fā)了一次 overflow，所以現(xiàn)在不管這個 split pointer 指向的是哪個 bucket，對應(yīng) bucket 現(xiàn)在都要進行一次拆分，比如圖中的第一個 bucket，哪怕這個 bucket 還可以存數(shù)據(jù)

? ? ? ? ? ??

? ? ? ? ? ? 拆分的工作方式是這樣的

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 在 slot array 的地方再增加一個 entry，也就是新增了一個格子 4。用一個新的 hash 函數(shù)，即 key % 2n，而這個 split pointer 會幫助我們跟蹤，該使用第 1 個還是第 2 個 hash 函數(shù)，它也會告訴我們，在 slot array 中，拆分 bucket 的距離有多遠

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 然后在 slot array 為 4 的位置，新增一個 bucket，把 20 放入這個新增的 bucket 中。

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 然后將這個 split pointer 下移一個單位

? ? ? ? ? ??

? ? ? ? ? ? 那么如果此時再想進行一次查找時，首先用第一個 hash 函數(shù)對其進行 hash

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 如果此時 hash 得到的結(jié)果所指向的位置時在 split pointer 所在的這條分界線之上，那么就知道正在查找的那個 bucket 已經(jīng)被拆分了

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 因此現(xiàn)在就應(yīng)該使用第 2 個 hash 函數(shù)來去找數(shù)據(jù)，因為數(shù)據(jù)肯定不在原來要拆分的那個 bucket 上

? ? ? ? ? ??

? ? ? ? ? ? 如果是查找 9 ，邏輯也是一樣的

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 9 % 4 = 1，因為在 1 所在 slot array 的那個位置 在 split pointer 分界線之下，所以它是沒有被拆分的，所以使用第一個 hash 函數(shù)是對的，那么就可以順著指針直接去找了

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 然而算法最糟糕的情況是，每個人都往同一個 bucket 中插入數(shù)據(jù)，這會導(dǎo)致它花了很長時間對 bucket 進行拆分，但使用一個具備低碰撞率的優(yōu)秀 hash 函數(shù)的話，可以解決這個問題

? ? ? ? ? ??

? ? ? ? ? ? 如果進行刪除操作，split pointer 會往回移動，不過如果要實現(xiàn)會相當(dāng)棘手

? ? ? ? ? ??

? ? ? ? ? ? 例子

? ? ? ? ? ??

? ? ? ? ? ? 假設(shè)現(xiàn)在要刪除 20

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 如果用第 1 個 hash，那么它算出來就是 0，但此處的位置是在 split pointer 的分界線之上，所以需要用第 2 個 hash

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 于是在 slot array 的 4 這個位置，delete 對應(yīng)的 bucket 里的 20

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 那么這個 bucket 就空了，如果要回收，就是反向操作

? ? ? ? ? ??

? ? ? ? ? ? 首先清掉這個空 bucket，并且清掉指針

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 然后將 split pointer 往回移動一個單位

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 現(xiàn)在，分界線消失了，第 2 個 hash 函數(shù)也沒了，內(nèi)存回收完畢

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? （這里 4 的消失，我認為也是隨著指針清空然后這個也被 remove 掉了）

? ? ? ? ? ??

? ? ? ? ? ? 如果回收完后 緊接著 是下面這種情況，在 overflowed bucket 中插入一個 21

? ? ? ? ? ??

? ? ? ? ? ??

? ? ? ? ? ? 就會觸發(fā) overflow（因為 slot array 的位置 1 對應(yīng)的 bucket 放不下，要放到其 overflow bucket 中），那么又要根據(jù)算法拆分 bucket

? ? ? ? ? ??

? ? ? ? ? ? 算法做了很多事情讓插入更快，但很難做到快速刪除

? ? ? ? ? ??

- 結(jié)論? ? ? ??

? ??

? ? hash 表沒辦法比較 key 的大小，所以不適合用于表索引的一些場景

? ??

? ? 相反，在創(chuàng)建索引時，最常用的就是 B+ Tree

? ??