Building an efficient hash table in Java

1) SwissTable プロジェクト ― 基本的な説明

SwissTable は、Google の研究から生まれたオープンアドレッシング型ハッシュテーブルの設計で、新しい C++ ハッシュテーブルとして発表され（後に Abseil に組み込まれました）。
基本構造は従来と同じで、

hash(key)

ここでのひねりは、メタデータ（小さな「制御バイト」）と実際のキー/値ストレージを分離し、制御バイトだけでほぼすべてのコストのかかるキー比較を回避する点にあります。
冷たいキャッシュ状態のキー配列（ポインタが多い）は触らずに、まず密度が高くキャッシュフレンドリーな制御バイト配列をスキャンします。
これは小さなブルームフィルターと似ており、「ここに候補があるかもしれない」という低コストの判定を先に行う仕組みです。

探査を高速化するため、SwissTable はハッシュを 2 部分に分割します。

h1

h2

検索時にはまず

(h1, h2)

h1

h2

探査コストが低いので、SwissTable は高負荷率（約 87.5 % = 7/8）でもパフォーマンス崩壊に陥りにくく、メモリ効率も向上します。
結果として、キャッシュミスやキー比較回数が減るだけでなく、オーバーフローバケットなどの副構造を少なくできる設計となっています。

2) SwissTable が複数言語で「デフォルト感覚」になるまで

世代を超える設計といえば、それがライブラリのトリックから標準ライブラリへ登場する瞬間です。

• Rust – Rust 1.36.0 以降、

  std::collections::HashMap

  は SwissTable ベースの

  hashbrown

  実装に切り替わりました。
  二次プロービングと SIMD ラックアップを使用しており、精神的・技術的には SwissTable にほぼ沿っています。

• Go – Go 1.24 で Swiss Table デザインに基づく新しいビルトインマップ実装が導入されました。
  マイクロベンチマークでは Go 1.23 より最大 60 % 高速、全体アプリケーションベンチでは約 1.5 % の CPU 時間改善を報告しています。

この時点で SwissTable は「C++ のクールなトリック」ではなく、現代のベースラインになっていました。
Rust が採用し、Go が ship した…なら Java も同じ設計に挑戦すべきだと直感的に思えました。
最新 CPU と強力 JIT、Vector API の到来で、技術的不可能性ではなく「やらなければならない」という itch が芽生えたのです。

3) SwissTable の秘密兵器と Java Vector API

SwissTable の高速さは、比較を広く（ワイドに）行うことから来ています。
複数の制御バイトを一度にチェックし、ブランチを減らす SIMD ワークロードです。
これは「1 バイトずつループして分岐する」スカラーコードよりもはるかに効率的です。

Java でこれを実装するには、以前は auto‑vectorization に頼ったり、

Unsafe

Java 25 の Vector API はまだ incubating ですが、

jdk.incubator.vector

設計の核は次の通りです：

1. 制御配列（コンパクト）＋別々のキー/値ストレージ

2. h1

   で初期グループを選択、

   h2

   はそのグループ内の制御バイトに格納される小さなフィンガープリント
3. 探索は 2 段階パイプライン：
   • ベクトルスキャンで

     h2

     と一致するビットを探す
   • 一致したインデックスで実際のキー比較を行う

挿入も同じスキャンを再利用し、既存キーが無い場合は最初に見つかった空スロットへ格納します。

Java ならではのレイアウト課題

• C++ ではキー/値を密にパックできますが、Java ではオブジェクト参照の配列になるためキーアクセス自体がキャッシュミスを招く可能性があります。
  そのため「キーはできるだけ遅れてタッチし、必要なときには最小限にする」設計が重要です。

• 削除は tombstone（削除済みだが空ではない）マーカーを用います。
  ただし tombstone が蓄積するとパフォーマンス低下につながるため、クリーンアップ戦略も必要です。

• リサイズは「全体再ハッシュ」がコスト高ですが、Go のテーブル分割や拡張可能ハッシュのように成長戦略を工夫すれば改善できます。

Vector API は「魔法ではなく最適化ツール」として扱い、ロード・比較・マスク・イテレーションという明確なループ構造で実装しました。

4) SwissMap において本当に重要だった要素

equals()

h1

h2

h2

ByteVector

h2

h1

制御バイト中心の検索ループ（簡略版）

protected int findIndex(Object key) {
    if (size == 0) return -1;
    int h = hash(key);
    int h1 = h1(h);
    byte h2 = h2(h);
    int nGroups = numGroups();
    int visitedGroups = 0;
    int mask = nGroups - 1;
    int g = h1 & mask; // 効率的な modulo
    for (;;) {
        int base = g * DEFAULT_GROUP_SIZE;
        ByteVector v = loadCtrlVector(base);
        long eqMask = v.eq(h2).toLong();
        while (eqMask != 0) {
            int bit = Long.numberOfTrailingZeros(eqMask);
            int idx = base + bit;
            if (Objects.equals(keys[idx], key)) { // 見つかった
                return idx;
            }
            eqMask &= eqMask - 1; // LSB をクリア
        }
        long emptyMask = v.eq(EMPTY).toLong(); // 同じベクトルを再利用
        if (emptyMask != 0) { // 空があれば確定ミス
            return -1;
        }
        if (++visitedGroups >= nGroups) {
            return -1; // 無限ループ防止（全 tombstone のケース）
        }
        g = (g + 1) & mask;
    }
}

5) ベンチマーク

以下は高負荷率でのプロービングとポインタ多いキーを重視した JMH 設定です。
実行環境：Windows 11 x64、Eclipse Temurin JDK 21.0.9、AMD Ryzen 5 5600（6C/12T）。

主な結果

• 高負荷率で SwissMap は他のオープンアドレッシングテーブルと競争力があり、JDK

  HashMap

  と同等かそれ以上のスループットを実現。
• メモリ使用量はフラットレイアウト（バケット／オーバーフロー無し）＋最大負荷率 0.875 により、小さいペイロードでは

  HashMap

  よりも 50 % 以上メモリ節約。

注意：Vector API はまだ incubating、テーブルは高負荷・参照キー向けに最適化されているため、プリミティブ専用マップや低負荷構成では結果が異なる可能性があります。

6) 簡単な備考

ベンチマークセクションで「SWAR‑style SwissTable」が突然登場するのは、後続調整で同じ制御バイトワークフローを SWAR（SIMD Within a Register）で実装し、Vector API を使わずに高速化したためです。
SWAR は「レジスタ内で SIMD」を意味し、64 ビット単位で複数の制御バイトを比較する手法です。
結果として同じ高速パスが、よりポータブルかつ JDK バージョンに依存せず実装できます。

この投稿は 3 本に分けるべき内容をまとめたもので、次回で SWAR の詳細（設計・実装）を公開予定です。ぜひご期待ください。

P.S. コードが欲しい方へ

この記事は HashSmith と呼ばれる JVM 向け高速メモリ効率のハッシュテーブル集を公表している試作プロジェクトの物語版です。
SwissMap（SwissTable 風、Vector API を用いた SIMD 探索）と SwissSet の両方が含まれています。
実験的で本番向けではありませんが、JMH ベンチマークやドキュメントを付属しているため、数値再現や実装詳細の検証が可能です。

ベンチマークを走らせたい、エッジケースを確認したい、あるいはより良い探査/リハッシュ戦略を提案したい場合はぜひ issue / PR をお寄せください。

P.P.S. 見逃せない講演

Google のエンジニア Matt Kulukundis らが CppCon で行った SwissTable に関するトークは非常に分かりやすく、設計の核心を掴める内容です。
ぜひご覧ください：https://www.youtube.com/watch?v=ZzQ0j3pRkJ4