1 哈希表

哈希表屬于編程中比較常見的數(shù)據(jù)結(jié)構(gòu)之一，基本上所有的語言都會(huì)實(shí)現(xiàn)數(shù)組和哈希表這兩種結(jié)構(gòu)，Hash table 的歷史是比較悠遠(yuǎn)的，我們?cè)诰幊虝r(shí)也是離不開的，這種數(shù)據(jù)結(jié)構(gòu)的作用其實(shí)很簡單，就是我們可以根據(jù)一個(gè) key 可以查找到對(duì)應(yīng)的 value，也就是說這種數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)的是鍵值對(duì)的“列表”。

1.1 原理

首先哈希表中第一個(gè)點(diǎn)就是哈希函數(shù)，也就是我們需要一個(gè)函數(shù)，根據(jù)我們的 key 計(jì)算出一個(gè)值，然后根據(jù)這個(gè)值可以直接找到對(duì)應(yīng)的 value。因?yàn)槲覀兊墓１淼囊粋€(gè)作用就是 O(1) 復(fù)雜度找到 key 對(duì)應(yīng)的 value。

完美的哈希函數(shù)是可以做到將任何一個(gè) key 值都可以計(jì)算出一個(gè)唯一且固定大小的值，不幸的是目前世界上還沒有這種完美的哈希函數(shù)。因此我們需要解決的另外一個(gè)問題就是哈希沖突的解決。

1.1.1 哈希沖突

假如我們有兩個(gè)不同的 key，通過哈希函數(shù)計(jì)算出的結(jié)果相同，那么我們是不能認(rèn)為這兩個(gè) key 在 map 中是相同的，也就是如果出現(xiàn)了這種情況，我們的 map 結(jié)構(gòu)是可以解決這個(gè)問題的。目前解決辦法有很多，這里只說三個(gè)比較常見的解決方案：

開放地址法(Open Addressing)：

• 寫入時(shí)：假如 key Alice 與 Bob 通過哈希函數(shù)計(jì)算出結(jié)果沖突。當(dāng) map 中已經(jīng)存在 key Alice，再寫入 key 為 Bob時(shí)，發(fā)現(xiàn)哈希結(jié)果對(duì)應(yīng)位置已經(jīng)存在 Alice，此時(shí)在 Alice 位置之后再尋找位置，一直找到為空的位置，將 Bob 寫入。
• 讀取時(shí)：此時(shí) map 中已存在 key Alice、Bob，且哈希結(jié)果相同，此時(shí)想查找 Bob 對(duì)應(yīng) value 時(shí)，先計(jì)算 Bob 哈希結(jié)果，再通過哈希結(jié)果在 map 中查找位置，此時(shí)由于和 Alice 哈希結(jié)果相同，并且 Alice 先于 Bob 存入 map，所以會(huì)直接找到 Alice 的位置，發(fā)現(xiàn) key 是 Alice 不是 Bob，接著在 Alice 位置后面查找，直到找到 key Bob 或者找到空。

再哈希法(Re-Hashing)：

• 設(shè)計(jì)多個(gè)哈希函數(shù)，假如 Alice 與 Bob 計(jì)算哈希結(jié)果相同，那么用另外一個(gè)哈希函數(shù)來計(jì)算 Bob 的哈希值，這種方式來解決哈希沖突。
• 鏈地址法(Separate Chaining)：
• 此方法將同一個(gè)哈希結(jié)果對(duì)應(yīng)的位置想象成一個(gè)桶，如果多個(gè) key 對(duì)應(yīng)哈希結(jié)果相同，那么都放到同一個(gè)桶中，并且桶中元素使用鏈表結(jié)構(gòu)存儲(chǔ)。
• 寫入時(shí)：Alice 于 Bob 哈希結(jié)果相同，此時(shí) map 已經(jīng)有 Alice，再寫入 Bob 時(shí)，發(fā)現(xiàn)對(duì)應(yīng)哈希結(jié)果位置已經(jīng)存在了 Alice，此時(shí)在當(dāng)前桶中的 Alice 后鏈接一個(gè) Bob，此時(shí)哈希結(jié)果對(duì)應(yīng)的桶就存在了兩個(gè)元素 Alice 與 Bob。
• 讀取時(shí)：讀取 Bob key 時(shí)，發(fā)現(xiàn)對(duì)應(yīng)哈希結(jié)果的桶中第一個(gè)元素是 Alice，此時(shí)在桶中按鏈表順序挨個(gè)查找，直到 key 相同或者空。
• 裝載因子：此方案存在一個(gè)問題，當(dāng)一個(gè)桶中元素過多時(shí)，其復(fù)雜度將增加，極端情況下就變成了鏈表。所以我們會(huì)限制在一個(gè)桶中元素的個(gè)數(shù)。這樣在一個(gè)桶中元素過多時(shí)，需要生成新的桶。
• 裝載因子 = 元素總量 / 桶總個(gè)數(shù)

在 Go 語言中，map 使用的是鏈地址法。

2 Go 中 map分析

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

map 的源碼位于 src/runtime/map.go 文件中，結(jié)構(gòu)如下：

type hmap struct { 
    count     int // 當(dāng)前 map 中元素?cái)?shù)量 
    flags     uint8 
    B         uint8  // 當(dāng)前 buckets 數(shù)量，2^B 等于 buckets 個(gè)數(shù) 
    noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details 
    hash0     uint32 // 哈希種子 
 
    buckets    unsafe.Pointer // buckets 數(shù)組指針 
    oldbuckets unsafe.Pointer // 擴(kuò)容時(shí)保存之前 buckets 數(shù)據(jù)。 
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated) 
 
    extra *mapextra // optional fields 
} 
 
// 每一個(gè) bucket 的結(jié)構(gòu)，即 hmap 中 buckets 指向的數(shù)據(jù)。 
type bmap struct { 
    tophash [bucketCnt]uint8 
} 
 
// 編譯期間重構(gòu)此結(jié)構(gòu) 
type bmap struct { 
    topbits  [8]uint8 
    keys     [8]keytype 
    values   [8]valuetype 
    pad      uintptr 
    overflow uintptr 
} 

關(guān)于 hmap 的結(jié)構(gòu)這里已經(jīng)將很多重要的字段列出來了，其中最重要的就是 buckets 這一部分，根據(jù)上面我們說過的鏈地址法可知，對(duì)同一類 key (哈希結(jié)果相同)放入相同的桶中。此時(shí)每一個(gè)桶還有另外一個(gè)字段 overflow，也就是當(dāng)前桶裝不下就會(huì)再創(chuàng)建新的桶。這就是 Go 中 map 的主要實(shí)現(xiàn)方法，更詳細(xì)的部分我們接下來一點(diǎn)一點(diǎn)聊。

2.2 源碼

map 的源碼位于 src/runtime/map.go 文件中。關(guān)于 map 的操作的具體實(shí)現(xiàn)在這里都可以找到：

• 創(chuàng)建 map：func makemap(t *maptype, hint int, h *hmap) *hmap
• 訪問某個(gè) key：
• 返回結(jié)果只包括 value：func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
• 返回結(jié)果包括 bool 結(jié)果：func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)
• 存入 key：func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
• 刪除 key：func mapdelete(t *maptype, h *hmap, key unsafe.Pointer)

本篇文章不會(huì)帶大家將源碼通讀一遍，但是會(huì)將其實(shí)現(xiàn)過程以圖或者文字形式分析出來，但是建議大家有時(shí)間可以根據(jù)本篇文章的內(nèi)容再去自己讀一遍源碼，如果我這里將所有源碼都解釋一遍，估計(jì)朋友們很快就又忘記了，還不如記住實(shí)現(xiàn)流程。所以本文更多的是講 map 每個(gè)操作的過程圖，以及其中的部分要點(diǎn)，而不是將源碼一行一行的解釋出來。

3. 圖解 map

3.1 創(chuàng)建map

我們已經(jīng)知道 map 的數(shù)據(jù)結(jié)構(gòu)，其實(shí) map 的初始化也無非就是填充各個(gè)字段而已：

• 第一個(gè)就是 hash0 字段，此處會(huì)隨機(jī)給一個(gè)種子，用在哈希函數(shù)計(jì)算時(shí)使用。關(guān)于哈希函數(shù)在運(yùn)行時(shí)，Go 會(huì)檢測 cpu 是否支持 aes，支持則使用 aes hash，否則使用 memhash。位于路徑：src/runtime/alg.go 下的 alginit() 函數(shù)。
• 根據(jù)參數(shù) hint計(jì)算需要的桶數(shù)。
• 根據(jù)桶的數(shù)量創(chuàng)建一個(gè)連續(xù)的空間來存儲(chǔ)桶的數(shù)據(jù)。

大體上就是這么一個(gè)過程，關(guān)于源碼中的一些檢查項(xiàng)這里就不多廢話了，并且源碼注釋也寫的很清楚了。

下面這個(gè)圖就是一個(gè) map 的主要相關(guān)存儲(chǔ)結(jié)構(gòu)：

map 主要結(jié)構(gòu)

3.2 定位 key

一個(gè) map 初始化后基本的結(jié)構(gòu)我們已經(jīng)知道了，接下來就是我們?cè)谶@個(gè)結(jié)構(gòu)中如何添加一個(gè) key 對(duì)應(yīng)的 value。

我們?cè)倏匆槐槊恳粋€(gè)桶的結(jié)構(gòu)：

type bmap struct { 
    topbits  [8]uint8 
    keys     [8]keytype 
    values   [8]valuetype 
    pad      uintptr 
    overflow uintptr 
} 

這里的 keys 與 values 字段就是存儲(chǔ) key 和 value 的真正內(nèi)存的地方，我們可以看到這里每個(gè)都是長度為8的數(shù)組，也就是說一個(gè)桶內(nèi)存了兩個(gè)數(shù)組，一個(gè)存的是 key 列表，另一個(gè)是 value 列表，并且每個(gè)數(shù)據(jù)的大小都是8。那么當(dāng)有第9個(gè)元素入桶時(shí)，我們就需要?jiǎng)?chuàng)建新的桶了，也就是 overflow 字段指向一個(gè)新的 bucket(bmap 結(jié)構(gòu))。

還有一個(gè)字段就是 topbits，也是一個(gè)長度為8的數(shù)組，其實(shí)看到這里我們應(yīng)該想到，這三個(gè)數(shù)組長度都相同應(yīng)該有對(duì)應(yīng)關(guān)系了，也就是說 topbits 數(shù)組中第一個(gè)元素是一個(gè)8位大小，我們稱之為 高8位，這是我們?cè)倩叵胍幌鹿：瘮?shù)，我們的哈希函數(shù)的結(jié)果取高8位，然后存入 topbits 數(shù)組，然后其在數(shù)組的索引我們稱之為i，那么我們就可以在 keys 和 values 數(shù)組的第i個(gè)位置存儲(chǔ)數(shù)據(jù)了。

上面是在已知一個(gè)桶中添加或者修改元素，那么我們?cè)撊绾尾檎疫@個(gè)桶呢?

我們知道在 hmap 中有 buckets 字段，其指向 []bmap 數(shù)組。那么我們就需要通過 key 找到對(duì)應(yīng)的 bmap 在 []bmap 中的位置。關(guān)于此處的計(jì)算大家感興趣的可以看一下源碼，這里就不詳細(xì)說每一個(gè)運(yùn)算符都是怎么運(yùn)算的，只說一下大致的流程：hmap 中有一個(gè) B 字段，根據(jù)字段 B 的值，以及 key 的 hash 值，計(jì)算出目標(biāo)桶在 []bmap 中的位置(其實(shí)就是取了 key 的哈希的后幾位作為數(shù)組的下標(biāo)即可)。

現(xiàn)在我們根據(jù)一個(gè) key 可以在 hmap 中的 buckets 字段找到對(duì)應(yīng)的 bmap 對(duì)象，同時(shí)在 bmap 中根據(jù) key 哈希的高八位找到其在 keys 與 values 數(shù)組中的位置。這里我們還沒有說如果有 overflow 的情況。其實(shí)不說想必大家也能猜到了，在我們定位到一個(gè) bmap 時(shí)，是不知道其一共有多少個(gè)溢出桶的：假設(shè)我們有桶 A，A 的 overflow 字段指向桶 B，B 的 overflow 指向桶 C，假設(shè)我們此時(shí)根據(jù) key 的哈希找到了桶 A，然后 for 循環(huán)遍歷桶中的 topbits 數(shù)組，如果某個(gè)高8位的哈希與我們想找的 key 的哈希的高8位相同，就去對(duì)應(yīng)位置的 keys 數(shù)組查找對(duì)應(yīng)的 key1，假如 key1 與我們的目標(biāo) key 相等，那么直接返回其對(duì)應(yīng) values 數(shù)組中的 value 即可。如果key1 與我們的目標(biāo) key 不相等，接著變量桶中其他元素。假設(shè)桶中所有元素遍歷后沒有找到相同的 key，那么此時(shí)就要到 A 桶的溢出桶 B 再去遍歷，如果 B 中依然找不到再去桶 C 中查找。此時(shí)大家可以思考一下如果是你，你會(huì)如何實(shí)現(xiàn)這部分代碼呢?你實(shí)現(xiàn)的和 Go 的源碼是否一樣呢?

當(dāng)我們知道了上面定位 key 的過程，對(duì)于 key 的增刪改查過程也就不多說了，因?yàn)楹诵牡奈覀円呀?jīng)掌握了，現(xiàn)在大家可以去看一下源碼了，這時(shí)大家看源碼必定事半功倍。