TL;DR
- Swiss Table は、オープンアドレス法で実装されたキャッシュ効率のよいハッシュテーブルである。
- Go の Swiss Map は、Extendible hashing で容量を拡張し、イテレーション中の変更にも決まった振る舞いを保証する。
内容
Swiss Table
Swiss Table は、チェイン法ではなくオープンアドレス法で実装されたハッシュテーブルである。オープンアドレス法は実装が複雑になるが、キャッシュ効率がよい。ハッシュ値の上位 57 ビットをグループの検索に、下位 7 ビットをスロットの検索に使う。
Go の Swiss Map の最適化
Go の Swiss Map は、Extendible hashing で容量を拡張する。要素がたくさん入ったテーブルは、そのテーブル単体で容量を拡張したり、分割したりする。容量が 2 倍になると、グループの数も 2 倍になる。t.grow はグループの数を 2 倍にし、t.split はテーブルを分割する。
イテレーション中の変更
Go の map のイテレーションには、次の決まりがある。
- イテレーション順序は未定義
- イテレーション中に要素を追加・削除しても、同じ要素が返されてはならない
- イテレーション中に変更された要素は最新の値を返さなければならない
- イテレーション中に削除された要素は返されてはならない
- イテレーション中に追加された要素は返されても良い
Directory の数は 2 の倍数だが、Table の数はそうとは限らない。そのため、異なる Directory が同じ Table を指すことがあり、同じ要素を二度返さないための工夫が要る。
キーワード
- Go
- Swiss Table
- ハッシュテーブル
- オープンアドレス法
- Extendible hashing