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

この文書のステータス

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

概要

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

  1. “key”を指定する
  2. ハッシュ化して11111111
  3. マップ配列[11111111]
  4. バケット特定
  5. バケット(配列)の中でさらにハッシュあるいは値が一致するものを探す
  6. “value”を得る

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

// 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と書いてあるとおり、メモリ上で交互に配置されて余分なスペースが生まれるのを防ぐため。キーの型と、値の型が異なると隙間が生まれやすい

関連

  • 類推: KDOC 190: 『Rubyのしくみ Ruby Under a Microscope』。Rubyでも同様にハッシュ・バケットを使ってハッシュテーブルを実装している
  • 類推: このように、パフォーマンスを優先するためにハックしている箇所はあるか
  • 追加調査: バケット動作をより解像度高く調べる方法はあるか。動作させて試したい