golang map 實作原理

在學習 Golang 的過程中，map 是我們常用的一種資料結構，可以用來儲存 key-value 對。但是，你是否想過 map 的實作原理是什麼呢？在本文中，我們將探究 Golang 中 map 的實作原理。

map 實作原理簡介

map 其實是一個雜湊表，它的實作原理就是雜湊演算法。哈希表是一種根據關鍵字直接存取記憶體儲存位置的資料結構，也就是說，它提供了一種將關鍵字映射到記憶體位址的方法。在哈希表中，關鍵字被稱為“鍵”，透過雜湊函數計算得到的記憶體位址稱為“桶”，桶儲存了鍵值對。

在Golang 中，map 是透過在桶記憶體區域儲存鍵值對實現的，每個桶都有一個頭部結構體，用於描述桶的狀態，這個頭部結構體稱為“ bucket」。

bucket 資料結構

先來看看bucket 的資料結構：

type bmap struct {
    tophash [bucketCnt]uint8
    // data 的类型在 map 被分配空间的时候由 map 的 key 和 value 类型决定
    // 如果 key 类型和 value 类型都是未知类型，那么 data 的类型是 byte
    // 因为 byte 可以用于存储任何类型，也就是说 data 可以存储任何类型的 key 和 value
    // 在存储 key 和 value 的时候，需要将 key 和 value 转换成 uintptr，然后再转换成 byte 存储到 data 中
    // 读取 key 和 value 的时候反向操作即可
    // 因此，map 中的 key 和 value 一般都是需要转换成 uintptr 类型的
    // 这里我们可以简单地理解为 data 存储了键值对的二进制数据
    // 第一个 bucket 中如果存不下某个 key-value，还需要在第二个 bucket 中存储
    // 所以，data 的长度可以为 1 或 2
    // 当 data 的长度为 1 或 2 时，存储的键值对的个数分别为 1 或 2
    // 因此，bucket 中最多只能存储 8 个键值对
    // 否则，就需要将键值对存储在 overflow 中
    // overflow 是一个指向单链表头部的指针数组
    // 如果某个桶存储的键值对数量超过了 8，那么就将多余的键值对存储到 overflow 中
    // overflow 中的第一个 bucket 中也是能够存储 8 个键值对的，如果第一个 bucket 中存不下的话
    // 那么还需要在第二个 bucket 中继续存储
    // 所以，overflow 数组的长度也可以为 1 或 2
    // 当 overflow 数组长度为 1 或 2 时，最多存储 8 个键值对的 overflow
    // 当 overflow 数组长度为 3 时，最多存储 24 个键值对的 overflow
    // 也就是说，如果 map 中存储的键值对数量很多的话，那么可能会有很多个 overflow 桶
    // 而 overflow 数组是动态分配的，因此它的长度是不定的，只有在运行时才能确定
    data unsafe.Pointer
    // overflow 是一个指针数组，用于存储除当前桶以外的其它桶
    // 如果某个桶的键值对数量超过了 8，那么它会将多余的键值对存储到 overflow 中
    // overflow 数组中的每个元素都是一个 bucket 指针
    // 这些 bucket 指针构成了一个链表，也就是所谓的 overflow 链表
    overflow *[]*bmap
    // 这里存储的是这个 bucket 当前存储的键值对的个数
    count int16
    // flags 存储了 bucket 的标志
    // 一个 bucket 可能会有如下三种状态：
    // 1. empty，表示这个 bucket 没有存储任何键值对
    // 2. iterator，表示这个 bucket 正在被访问，不能再被其它操作使用
    // 3. deleted，表示这个 bucket 存储的键值对已经被删除了
    // 注意，该标志位只有在 GC 达到一定阈值后才会被置为 true，而且并不是立即删除键值对，而是在下一次 GC 的时候才会内存回收
    flags uint8
    // Bmap 的类型标记
    // Bmap 用来标识存储于上文中 data 指针中的数据类型
    // 如果 data 中存储的是 int，那么 Bmap 的值为 hmap.BmapInt
    // 如果 data 中存储的是 string，那么 Bmap 的值为 hmap.BmapString
    // 如果 data 中存储的是 interface{}，那么 Bmap 的值为 hmap.BmapInterface
    // 如果 data 中存储其他类型，那么 Bmap 的值为 hmap.BmapOther
    BmapType uint16
    // 与该 bucket 相关联的 key 的类型
    tophash0 uint8
}

從上面的定義中，我們可以看到，bucket 儲存了以下資訊：

• tophash：用於快速篩選出不匹配的key；
• data：儲存鍵值對的資料；
• overflow：儲存overflow 鍊錶的指標陣列；
• count：儲存了目前bucket 中儲存的鍵值對的個數，最多為8；
• flags：儲存了bucket 的一些狀態資訊；
• BmapType：存儲了data 中儲存資料的型別；
• tophash0：與該bucket 相關聯的key 的型別。

實作原理

由於map 儲存的資料是鍵值對，而且鍵值對的key 值是不可重複的並且能夠進行比較大小操作，我們可以採用哈希函數將key 值轉換為唯一的雜湊值，然後將雜湊值作為key 值對應的索引，將value 值儲存在該索引上。

在Golang 中，每個map 都有一個哈希表，這個哈希表實際上就是一段連續的儲存空間，可以儲存若干個桶（bucket），每個桶都是一個bucket 類型的結構體。

那麼雜湊表的大小是如何決定的呢？它是在 map 創建時動態分配記憶體而來的，首次分配空間時候使用的預設大小為 8 個桶。如果第一次增加元素的時候，桶的數量不夠，則雜湊表的大小會擴容，並重新計算每個元素在雜湊表中的索引位置。

在 Golang 中，雜湊函數的作用主要是將 key 值雜湊化，使其更方便的定位到雜湊表中的一個桶，從而加速查找 key 值對應的 value 值。在 Golang 中，雜湊函數的實作採用了 MurmurHash3 演算法。

由於雜湊函數是將 key 對應到整數，因此不同的 key 值可能會對應到相同的索引。這種情況被稱為哈希衝突。當出現雜湊衝突時，Golang 採用鍊錶法來解決，將相同索引上的鍵值對儲存在該索引的鍊錶中，這些鍵值對就稱為 overflow。

總結

Golang 的 map 實作原理主要依賴雜湊表和雜湊函數。哈希函數用於散列化 key 值，將其映射到哈希表中的一個桶，從而加速查找 value 值的操作。雜湊表由若干個桶組成，每個桶由一個 bucket 類型的結構體表示，儲存了鍵值對的資訊。當哈希表中的相同索引位置上存在多個鍵值對時，採用鍊錶法儲存 overflow。 Golang 中的 map 其實就是一個動態哈希表，可以動態地調整哈希表的大小。在使用 map 時，需要注意避免哈希衝突和包含無法比較大小的類型作為 key。

以上是golang map 實作原理的詳細內容。更多資訊請關注PHP中文網其他相關文章！