Go1.24で進化したmap型について理解する
map の割り当て・読み取りのどちらでも Directory → Table → Group → Slot の順序で Key-Value を特定する
Table の特定
key から計算したハッシュと Directory の長さに応じた値で AND 演算した結果のビットパターンで特定
これにより、リハッシュ(スロットの再配置)を 1 つの Table に軽減できる
CPU 負荷の軽減・メモリ効率の改善
Group の特定
初回時
key のハッシュから上位 57bit(H1)を取得
初回の offset は H1 とグループ数に応じた値を AND 演算した結果からグループを選定
2 回目以降
前回の offset に Group の探索回数を加算
1 の結果に Table の長さに応じた値で AND 演算した結果からグループを選定
Quadratic probing により、オープンアドレス法で発生する クラスタリング の発生が抑制可能に Slot の特定
key のハッシュ値の下位 7bit(H2)を取得
結果から対象のスロット候補を選定
これにより、8スロットを一括で検証できるため、パフォーマンスが改善された
参考