Iceberg Hashing

Iceberg Hashingのフロントヤードは、1本の単純な配列ではなく、「連続した1ブロックを1つのバケットとし、その中に複数のスロット（部屋）とメタデータ（道標）を詰め込んだ、キャッシュ最適化型のバケット構造」をとっています。

① フロントヤード

データの90%以上は、ハッシュ値に基づいたフロントヤードのバケット（配列）に直接格納されます。ここに入ったデータは、メモリ上の位置が絶対に変わりません（Stable）。これにより、マルチスレッドや永続メモリでも安全かつ高速に動けます。

② バックヤード

確率的に、特定のバケットだけデータが集中して溢れてしまう（オーバーフロー）ことがあります。Iceberg Hashingは、この「溢れたごく一部のデータだけ」を格納する小さな別テーブルとして、クックーハッシュ（カッコーハッシュ）を組み込んでいます

仕組み

その配列の具体的な内部構造と、そこで動く超高速アルゴリズムの仕組みは以下の通りです。

1. フロントヤードの「配列構造」

フロントヤードは、メモリ上に連続して配置された「バケット（Bucket）」の配列です。1つのバケットは通常、CPUのキャッシュライン（64バイトなど）の倍数にぴったり収まるサイズで設計されています。 1つのバケットの中身は、さらに以下のように細分化されています。

【 1つのバケット（例：64バイト）の内部構造 】

メタデータ（数バイト）[フィンガープリント群] │ 複数のスロット（Slot 1 〜 Slot K)[Key 1, Value 1][Key 2, Value 2] ...

• スロット（Slots）: 実データ（キーと値のペア、またはそのポインタ）を格納する固定個数（例：1バケットあたり4個や8個）の部屋です。
• メタデータ領域（フィンガープリント）: 各スロットにデータが入っているかどうか、また入っているデータの「ハッシュ値の断片（1バイト程度の小さな値＝フィンガープリント）」を並べたビット列（メタデータ配列）です。

2. フロントヤードで動く「アルゴリズム」

データの検索や挿入の際、この構造を活かして「1回のキャッシュアクセス（メモリ読み込み）」と「CPUのビット演算（SIMD命令）」だけで処理を完結させるアルゴリズムが動いています。

データの検索アルゴリズム

1. バケットの特定: キーのハッシュ値から、一発で対象の「バケット番号」を計算し、そのバケット（64バイトのかたまり）をCPUキャッシュに読み込みます。
2. メタデータの超高速スキャン: バケット内の重いデータ（Key/Value）を1つずつ順番に見ていく（線形探索する）のではなく、先頭にある軽い「メタデータ領域」だけをCPUのSIMD命令（ベクトル演算）を使って一瞬（1クロック）で並列チェックします。
3. フィンガープリントの照合: 探しているキーのハッシュ断片と、メタデータに記録されている断片が一致するスロットがあるか確認します。

• 一致しなければ: そのバケットには「絶対にデータがない」と100%断定し、即座にバックヤードの検索へ切り替えます。
  • 一致すれば: そのスロットの実データだけをピンポイントで読み込んで、本物のキーかどうかを確認します。

データの挿入アルゴリズム

1. ハッシュ値からバケットを特定します。
2. バケット内のメタデータをビット演算でチェックし、「空いているスロット」を探します。
3. 空きがあれば、そのスロットにデータを格納し、メタデータ領域に対応するフィンガープリントを書き込みます。これ以降、このデータはメモリ上で一切移動しません（Stable）。
4. もしバケット内のすべてのスロットが完全に埋まっていた場合（＝オーバーフロー）、フロントヤード内での押し出しや再配置は行わず、アルゴリズムは即座にデータを「バックヤード（クックーハッシュ側）」へ丸投げします。

まとめ

なぜ「絶対に位置が変わらない（Stable）」と言えるのか？

ロビンフッドハッシュや通常の線形探索法では、「隣のバケット」や「さらにその隣」へデータがはみ出していくため、新入りが来ると玉突きで押し出されてしまいます。 しかしIceberg Hashingのフロントヤードは、「自分のバケットの決まったスロット（部屋）の中から絶対に外へ出ない。満部屋なら、自分ではなく後から来た新入りが裏庭（バックヤード）に行く」というアルゴリズムになっているため、一度配置されたデータのアドレスがリサイズ時まで1ミリも動かない（Stableな）性質を保証できるのです。