Go1.24で進化したmap型について理解する
https://gocon.jp/2025/talks/959061/
v1.24 から map 型の内部実装が Swiss Table を用いるように変わった
map の割り当て・読み取りのどちらでも Directory → Table → Group → Slot の順序で Key-Value を特定する
Table の特定
key から計算したハッシュと Directory の長さに応じた値で AND 演算した結果のビットパターンで特定
Extendible hasing を採用
これにより、リハッシュ(スロットの再配置)を 1 つの Table に軽減できる
CPU 負荷の軽減・メモリ効率の改善
Group の特定
初回時
key のハッシュから上位 57bit(H1)を取得
初回の offset は H1 とグループ数に応じた値を AND 演算した結果からグループを選定
2 回目以降
前回の offset に Group の探索回数を加算
1 の結果に Table の長さに応じた値で AND 演算した結果からグループを選定
オープンアドレス法 + Quadratic probing を採用
Quadratic probing により、オープンアドレス法で発生する クラスタリング の発生が抑制可能に
Slot の特定
key のハッシュ値の下位 7bit(H2)を取得
H2 を拡張した値と Control word をビット演算
結果から対象のスロット候補を選定
これにより、8スロットを一括で検証できるため、パフォーマンスが改善された
参考
https://go.dev/blog/swisstable
https://abseil.io/about/design/swisstables
https://go.dev/ref/mod
#Go #Go_Conference_2025