KDOC 438: Goのバケット構造体はフィールドがないが値を保持している

この文書のステータス

  • 作成
    • 2025-09-14 貴島
  • レビュー
    • 2025-09-16 貴島

概要

ハッシュテーブルは、キー値のハッシュをインデックスとした配列に格納して実装されている。要素を全部見る必要がない分早い。1つ1つの配列をバケットという。

  • “key” -> ハッシュ化して11111111 -> マップ配列[11111111] -> バケット特定 -> バケット(配列)の中でさらにハッシュあるいは値が一致するものを探す -> “value”

Goのmapのバケット構造体はこのように定義されている。 

https://github.com/golang/go/blob/988a20c8c5e2c9eb49f8749e5ee94ce3c964fe59/src/runtime/map_noswiss.go#L149-L160

// A bucket for a Go map.
type bmap struct {
	// tophash generally contains the top byte of the hash value
	// for each key in this bucket. If tophash[0] < minTopHash,
	// tophash[0] is a bucket evacuation state instead.
	tophash [abi.OldMapBucketCount]uint8
	// Followed by bucketCnt keys and then bucketCnt elems.
	// NOTE: packing all the keys together and then all the elems together makes the
	// code a bit more complicated than alternating key/elem/key/elem/... but it allows
	// us to eliminate padding which would be needed for, e.g., map[int64]int8.
	// Followed by an overflow pointer.
}
  • フィールドはないがデータを保持している
  • [key, key, key, …, value, value, value] とメモリ配置させるためにGo外で管理している
  • paddingと書いてあるとおり、メモリ上で交互に配置されて余分なスペースが生まれるのを防ぐため。キーの型と、値の型が異なると隙間が生まれやすい

関連

なし。