
Iceberg Hashingのフロントヤードは、1本の単純な配列ではなく、「連続した1ブロックを1つのバケットとし、その中に複数のスロット(部屋)とメタデータ(道標)を詰め込んだ、キャッシュ最適化型のバケット構造」をとっています。
データの90%以上は、ハッシュ値に基づいたフロントヤードのバケット(配列)に直接格納されます。ここに入ったデータは、メモリ上の位置が絶対に変わりません(Stable)。これにより、マルチスレッドや永続メモリでも安全かつ高速に動けます。
確率的に、特定のバケットだけデータが集中して溢れてしまう(オーバーフロー)ことがあります。Iceberg Hashingは、この「溢れたごく一部のデータだけ」を格納する小さな別テーブルとして、クックーハッシュ(カッコーハッシュ)を組み込んでいます
その配列の具体的な内部構造と、そこで動く超高速アルゴリズムの仕組みは以下の通りです。
フロントヤードは、メモリ上に連続して配置された「バケット(Bucket)」の配列です。1つのバケットは通常、CPUのキャッシュライン(64バイトなど)の倍数にぴったり収まるサイズで設計されています。 1つのバケットの中身は、さらに以下のように細分化されています。
【 1つのバケット(例:64バイト)の内部構造 】
メタデータ(数バイト)[フィンガープリント群] │ 複数のスロット(Slot 1 〜 Slot K)[Key 1, Value 1][Key 2, Value 2] ...
データの検索や挿入の際、この構造を活かして「1回のキャッシュアクセス(メモリ読み込み)」と「CPUのビット演算(SIMD命令)」だけで処理を完結させるアルゴリズムが動いています。
なぜ「絶対に位置が変わらない(Stable)」と言えるのか?
ロビンフッドハッシュや通常の線形探索法では、「隣のバケット」や「さらにその隣」へデータがはみ出していくため、新入りが来ると玉突きで押し出されてしまいます。 しかしIceberg Hashingのフロントヤードは、「自分のバケットの決まったスロット(部屋)の中から絶対に外へ出ない。満部屋なら、自分ではなく後から来た新入りが裏庭(バックヤード)に行く」というアルゴリズムになっているため、一度配置されたデータのアドレスがリサイズ時まで1ミリも動かない(Stableな)性質を保証できるのです。