go.dev - Faster Go maps with Swiss Tablesを読んでいたら、オープンアドレスハッシュテーブルとスイステーブルについての説明があったので、調べてみた。
オープンアドレスハッシュテーブル（Open Addressing Hash Table） は、ハッシュ衝突（異なるキーが同じハッシュ値を持つ場合）を解決する代表的な手法であり、「オープンアドレス法（Open Addressing）」 とも呼ばれる。 チェイン法（衝突時にリストなどを用いる方法）とは異なり、衝突が発生した際には同じ配列（ハッシュテーブル）の別スロットへと探索を続けて格納する点が特徴である。
ハッシュ関数でインデックスを決定 キー ( k ) をハッシュ関数 ( h(k) ) に通し、テーブルのどのインデックスに格納するかを求める。
衝突が発生したら別の場所を探す もし指定されたインデックスがすでに使用されていた場合、次に空いているスロットを探し出し、そこにデータを格納する。
探索方法（プロービング）の例
スイステーブル（Swiss Table） は、Google が開発した 高性能なハッシュテーブル であり、C++の Abseil Library（absl::flat_hash_map） や Rust の hashbrown などで採用されている。オープンアドレス法をベースに、メモリ効率と高速性 を徹底的に追求した実装である。
SIMDを活用した高速探索 SIMD（Single Instruction, Multiple Data） によって一度に複数のバケットを並列にチェックする。これにより、衝突解決や検索時の比較をまとめて処理することができるため、通常のオープンアドレス法より高速に動作する。
バケットのグループ化（Bucket Grouping） スイステーブルは、複数のスロットをまとめたバケットグループという単位で管理する。たとえば一つのグループに 8 や 16 個のスロットを含める場合、一度にこれらを走査できるため、衝突解消や検索を効率よく行える。
Control Bytes（タグ）の使用 バケットグループごとにControl Bytes（あるいはControl Blockと呼ぶ場合もある）を用意し、各スロットが「使用中か」「削除済みか」といった状態やフルハッシュの一部（タグ）をまとめて保持する。 これにより、実際のキーを参照する前に一括して「マッチしそうなスロット」を絞り込むことができるため、高いキャッシュ効率と検索性能を実現できる。
トンボマーク方式による削除 削除時にはスロットを空にせず、トンボマーク（tombstone） を立てておく。再ハッシュやリサイズなどのタイミングで、トンボマークが付いたスロットをまとめて再配置・整理する。
キーをハッシュ化し、部分ハッシュ（タグ）を記録 キーからハッシュ値を取得し、その一部をタグとしてControl Bytesに格納する。
タグを用いたSIMD並列検索 バケットグループに対して、一度に複数スロットのタグをSIMD命令で比較し、候補を高速に絞り込む。
タグが一致したスロットのキーを照合 タグが一致したスロットを見つけたら、実際のキーを取り出して完全一致するか確認する。
衝突時は次のバケットグループへ 同一グループ内に空きがなかったりキーが一致しなかった場合、プロービングによって次のバケットグループをチェックする。
削除時はトンボマーク（tombstone）を付与 削除スロットを空にせず、トンボマークを付ける。後からリサイズや再配置する際に、これらの不要スロットを整理する。
bmf-san/road-to-algorithm-master/tree/master/data_structures/hash_tableを参照。
Clineの素振りを兼ねて書いたコードであるが、いくらかバグは残っているかも。
オープンアドレスハッシュテーブルは、余分なポインタ構造を必要としないためメモリ効率とキャッシュ効率に優れた手法である。しかし、負荷率が高まるにつれ探索回数が増えやすく、削除処理が複雑になるといった課題を抱えている。 一方、スイステーブル（Swiss Table） は、SIMD活用やバケットのグループ化、Control Bytes（タグ管理）といった工夫を重ねることで、オープンアドレス法の欠点をうまく補いながら高性能を実現している。Google の Abseil Library や Rust の hashbrown といった実装で採用されている。
関連書籍