> # map的底層 - 哈希表（hash table），又稱散列表，它通過建立鍵`key`與值`value`之間的映射，實現高效的元素查詢 - 查找元素，添加元素，刪除元素 O(n)時間 - `hmap` 是 `map` 結構的頭部，用于存儲 `map` 的元數據 - `bmap` 是實際存儲 `map` 鍵值對的結構。它表示一個存儲桶（bucket） >### hmap ``` type hmap struct { count int // 活躍的鍵值對數量 == map 的大小。必須是第一個字段（由 len() 內置函數使用）。 flags uint8 // 標志位，用于存儲與 map 狀態相關的標志信息。 B uint8 // 存儲桶的數量的對數（log_2），可以容納最多 loadFactor * 2^B 個元素。 noverflow uint16 // 近似的溢出存儲桶的數量；有關詳細信息，請參見 incrnoverflow。 hash0 uint32 // 哈希種子，用于哈希函數的初始值。 buckets unsafe.Pointer // 指向存儲桶數組的指針，數組大小為 2^B。如果 count == 0，則可能為 nil。 oldbuckets unsafe.Pointer // 指向先前存儲桶數組的指針，其大小為當前的一半，僅在增長時為非 nil。 nevacuate uintptr // 遷移進度計數器（小于此值的存儲桶已遷移到新的存儲桶數組）。 extra *mapextra // 可選字段，包含一些額外的字段。 } ``` * **count**：記錄 `map` 中當前存儲的鍵值對的數量（活躍單元數），也是 `len()` 內置函數的依據。 * **flags**： 存儲與 `map` 狀態相關的標志信息。例如，用于記錄 `map` 是否正在增長等狀態。 * **B**：表示存儲桶數量的對數（log\_2），存儲桶數量為 `2^B`。它決定了 `map` 可以存儲的最大鍵值對數量。 * **noverflow**： 記錄溢出存儲桶的數量（大致），在發生哈希沖突時，多個鍵值對可能會被分配到同一個存儲桶，因此可能會產生溢出存儲桶。 * **hash0**：哈希種子，用于哈希函數。通過引入種子，使得 `map` 的哈希分布更隨機，以減少沖突。 * **buckets**： 指向當前存儲桶數組的指針，數組的大小為 `2^B`。如果 `map` 為空（count == 0），該字段可能為 `nil`。 * **oldbuckets**： 在 `map` 進行擴容時，指向先前存儲桶數組的指針，舊數組的大小是新數組的一半。在擴容過程中，這個指針會被用來遷移舊的鍵值對。 * **nevacuate**： 在擴容過程中，記錄了遷移進度的計數器。小于此值的存儲桶已經被遷移到新的存儲桶數組。 * **extra**：可選字段，用于存儲一些額外的數據，比如保存小 `map` 結構體的溢出數據或指向垃圾回收器的指針。 > bmap ``` type bmap struct { // tophash 通常包含此存儲桶中每個鍵的哈希值的最高字節。 // 如果 tophash[0] < minTopHash，則 tophash[0] 是存儲桶搬遷狀態。 tophash [bucketCnt]uint8 // 接下來是 bucketCnt 個鍵和 bucketCnt 個元素。 // 注意：將所有鍵一起打包然后將所有元素一起打包使代碼稍微復雜一些， // 比如交替存儲 key/elem/key/elem/...，但是這樣可以消除填充， // 填充可能需要，例如 map[int64]int8。 // 緊跟在這些之后的是溢出指針。 } ```  > # key的定位 - key 根據當前初始話的hash種子進行哈希計算得到哈希值， hash后幾位確定桶的位置， 前幾位作為tophash - 當兩個不同的 key 落在同一個桶中，也就是發生了哈希沖突。沖突的解決手段是用鏈表法：在 bucket 中，從前往后找到第一個空位。這樣，在查找某個 key 時，先找到對應的桶，再去遍歷 bucket 中的 key。如果在 bucket 中沒找到，并且 overflow 不為空，還要繼續去 overflow bucket 中尋找，直到找到或是所有的 key 槽位都找遍了，包括所有的 overflow bucket。 - 鏈式地址解決哈希沖突： 每個桶存儲一個鏈表包含所有沖突的元素 > # 擴容 - 擴容的時候不是馬上全部遷移， 而是會有標記狀態， 每次遷移一部分 > # 相關閱讀 - [go map底層實現](https://www.cnblogs.com/ybf-yyj/p/12763015.html) - [go map深度解析](https://www.jianshu.com/p/0a777dc7f7ae) - [golang map合并\_數據結構和算法(Golang實現)](https://blog.csdn.net/weixin_39688451/article/details/110236131) - [Hello算法](https://www.hello-algo.com/chapter_hashing/hash_map)