Swiss Table の実装に Deep Dive !
オープンアドレス法の方が、実装は複雑になるがキャッシュ効率が良い
上位 57 bit を Group、下位 7 bit を Slot 検索に使う
Go の Swiss Map に導入されている最適化 🚧 要素がたくさん入っている table をその table 単体で capacity を拡張したり、split することで
capacity が 2 倍になる = Group が 2 倍になる
t.grow 実行時には、Group 数を 2 倍にする
t.split 実行時には、
🚧 要素数が 8 個以下の時は directory pointer が(こちら省略)
iteration 中の map の変更に対する工夫
イテレーション順序は未定義
イテレーション中に要素を追加・削除しても、同じ要素が返されてはならない
Directory の数は 2 の倍数だが、Table の数はその限りではない
そのため、異なる Directory が同じ Table を指すことがある
イテレーション中に変更された要素は最新の値を返さなければならない
イテレーション中に削除された要素は返されてはならない
イテレーション中に追加された要素は返されても良い
...