Go 1.24のマップ内部：Swiss Tablesがもたらす高速化の仕組み
How Swiss tables work in Go built-in map
Go 1.24で組み込みのマップ実装がSwiss Tablesベースに置き換えられました。本記事では、ランタイムでのマップの表現から、グループとコントロールバイトの役割、H1/H2ハッシュ分割、SIMDを用いた高速なキー検索、テーブルへの拡張までを、図解を交えて段階的に解説します。旧実装との違いや、削除時のトゥームストーン処理、分割グループレイアウトの実験的機能にも触れ、Goのマップがどのようにして高速化されたかを理解できます。
Goはキーをハッシュ化する際にマップごとのシードを使用するため、同じキーでもマップが異なればハッシュ値が変わり、格納場所も変わります。
- nasso_dev
Swissテーブルは、Googleのチューリッヒオフィスで働くエンジニアによって発明されたため、その名前が付けられました。同じくGoogle出身のプログラミング言語であるGoが、それを使っていなかったことに驚いています！Swissテーブルの開発に関する素晴らしい講演として、CppCon 2017でのMatt Kulukundis氏による「Designing a fast, efficient, cache-friendly hash table, step by step」を強くお勧めします。https://youtu.be/ncHmEUmJZf4