My favourite small hash table

私はハッシュテーブルの設計と実装、特に線形探索（linear probing）を採用したロビン・フッド方式（Robin Hood）で、表サイズが2 のべき乗になるケースに興味があります。以下ではコアアイデアを実践的に見ていきます。

---

前提条件

1. キーは 32‑bit 整数の均一乱数です。
2. 値も 32‑bit 整数です。
3. キー

   0

   が存在する場合、その値は必ず非ゼロです。
4. テーブルは 32 GiB を超えません。

この前提条件を満たせば、キー／バリューのペアは 64‑bit 単語に収まります：下位 32 ビットがキー、上位 32 ビットが値です。
(3) が保証する「

key == 0 && value == 0

」という実際のエントリーは存在しないため、64‑bit 値

0

を空スロットとして利用できます。

---

テーブル構造

struct hash_table_t {
    uint64_t *slots;   // スロット配列
    uint32_t mask;     // (length-1) ＝ 2^n - 1（長さは 2 のべき乗）
    uint32_t count;    // 占有スロット数
};

mask

を使うことで

index = key & mask

が得られます。
ロードファクタを 100 % 未満に保つために、

count < length

を保証し、

count

は 32 ビットで十分です。

---

探索（Lookup）

キーがランダムなため、キー

K

の「自然位置」は単純に

(K & mask)

です。
そのスロットが占有されていれば、線形探索を続けます：

(K+1)&mask

,

(K+2)&mask

…。

ロビン・フッドのルール は次のようになります。
任意のスロット

S

が保存されたキーの連鎖に含まれる場合、

Score(S.index, S.key) ≥ Score(S.index, K)

ここで

Score(index, key) = (index - key) & mask

です。

探索時には、自然位置からの距離

d

を保持します。
空スロットに到達したか、あるいは現在のスコアが

d

より小さいスロットを見つけた場合、そのキーは存在しません。

uint64_t table_lookup(hash_table_t *table, uint32_t key) {
    uint32_t mask  = table->mask;
    uint64_t *slots = table->slots;

    for (uint32_t d = 0; ; ++d) {
        uint32_t idx  = (key + d) & mask;
        uint64_t slot = slots[idx];

        if (slot == 0)
            return 0;                           // 存在しない

        if (key == (uint32_t)slot)
            return (slot >> 32) | (slot << 32); // 存在、値を取得（回転）

        if (((idx - (uint32_t)slot) & mask) < d)
            return 0;                           // キーはここにあり得ない
    }
}

x86‑64 や arm64 上ではこのコードは非常に軽量です。

slots[idx]

はアドレス生成命令一つ、下位 32 ビットの比較はネイティブ、32 ビット回転も1 命令で済みます。
riscv64 では

Zba/Zbb

拡張に依存しますが、なければスロットレイアウトを書き換える必要があります。

---

挿入（Insertion）

挿入は同じ探索パターンをたどります。キーが既に存在すれば上書きし古い値を返します。
現在の距離より小さいスコアを持つスロットに到達したら、そのスロットへ交換し、置換されたペアを再挿入（

table_reinsert

）します。

uint64_t table_set(hash_table_t *table, uint32_t key, uint32_t val) {
    uint32_t mask  = table->mask;
    uint64_t *slots = table->slots;
    uint64_t kv   = key + ((uint64_t)val << 32);

    for (uint32_t d = 0; ; ++d) {
        uint32_t idx  = ((uint32_t)kv + d) & mask;
        uint64_t slot = slots[idx];

        if (slot == 0) {                     // 空 – 挿入
            slots[idx] = kv;
            break;
        }

        if ((uint32_t)kv == (uint32_t)slot) { // 既存キー
            slots[idx] = kv;
            return (slot >> 32) | (slot << 32);
        }

        uint32_t d2 = (idx - (uint32_t)slot) & mask;
        if (d2 < d) {                        // 交換して置換ペアを再挿入
            slots[idx] = kv;
            table_reinsert(slots, mask, slot, d2);
            break;
        }
    }

    /* 75 % 超過時にリサイズ */
    if (++table->count * 4ull >= mask * 3ull)
        table_rehash(table);

    return 0;
}

table_reinsert

は軽量ヘルパーで、空スロットが見つかるまで探索を続けます。カウントは更新しません。

void table_reinsert(uint64_t *slots, uint32_t mask,
                    uint64_t kv, uint32_t d) {
    for (;; ++d) {
        uint32_t idx  = ((uint32_t)kv + d) & mask;
        uint64_t slot = slots[idx];

        if (slot == 0) {                     // 空 – 完了
            slots[idx] = kv;
            break;
        }

        uint32_t d2 = (idx - (uint32_t)slot) & mask;
        if (d2 < d) {                        // 交換して続行
            slots[idx] = kv;
            kv = slot;
            d  = d2;
        }
    }
}

table_rehash

はテーブルサイズを倍にし（新マスクは

old_mask*2+1

）、すべてのエントリーを再挿入します。

---

削除（Removal）

ロビン・フッドスコアを利用しているため、墓碑（tombstone）は不要です。
キーを削除するときは、その後ろにあるスロットを左へシフトし続け、空スロットまたはスコア

0

のスロットが出るまで繰り返します。これで連鎖の性質が保たれます。

uint64_t table_remove(hash_table_t *table, uint32_t key) {
    uint32_t mask  = table->mask;
    uint64_t *slots = table->slots;

    for (uint32_t d = 0; ; ++d) {
        uint32_t idx  = (key + d) & mask;
        uint64_t slot = slots[idx];

        if (slot == 0)
            return 0;                           // 存在しない

        if (key == (uint32_t)slot) {             // 見つかった
            uint32_t nxt = (idx + 1) & mask;
            --table->count;

            while (slots[nxt] && ((slots[nxt] ^ nxt) & mask)) {
                slots[idx] = slots[nxt];
                idx   = nxt;
                nxt   = (idx + 1) & mask;
            }
            slots[idx] = 0;                       // 最終空スロット
            return (slot >> 32) | (slot << 32);
        }

        if (((idx - (uint32_t)slot) & mask) < d)
            return 0;                           // 存在しない可能性が高い
    }
}

---

イテレーション（Iteration）

配列を線形スキャンし、ゼロでないスロットだけを訪問関数へ渡します。

void table_iterate(hash_table_t *table,
                   void (*visit)(uint32_t key, uint32_t val)) {
    uint64_t *slots = table->slots;
    uint32_t mask   = table->mask;

    for (uint32_t idx = 0; ; ++idx) {
        uint64_t slot = slots[idx];
        if (slot != 0)
            visit((uint32_t)slot, (uint32_t)(slot >> 32));

        if (idx == mask)
            break;
    }
}

---

拡張（Extensions）

ランダムでないキー

挿入・検索・削除の前に可逆ハッシュ

h(key)

を適用します。
ハッシュが等しければキーも等しいので、探索はそのままです。イテレーション時のみ逆ハッシュを使って元のキーを復元します。

uint32_t u32_hash(uint32_t h) {
    h ^= h >> 16;
    h *= 0x21f0aaad;
    h ^= h >> 15;
    h *= 0x735a2d97;
    h ^= h >> 15;
    return h;
}
uint32_t u32_unhash(uint32_t h) {
    h ^= h >> 15; h ^= h >> 30;
    h *= 0x97132227;
    h ^= h >> 15; h ^= h >> 30;
    h *= 0x333c4925;
    h ^= h >> 16;
    return h;
}

大きなキー／値

別にキー／バリュー配列を保持し、テーブルには 32‑bit ハッシュ＋インデックスだけを格納します。

hash == 0

を禁止するか、

index+1

を保存すれば (3) は維持できます。探索時はハッシュ一致後に実際のキー比較が必要です。

可変長キー／値

シリアライズされたペアをバイトバッファに格納し、テーブルには 32‑bit ハッシュとそのオフセットだけを保持します。

---

結論

線形探索で 2 のべき乗サイズのロビン・フッドハッシュテーブルは：

• コンパクト – エントリごとに 64‑bit 単語、墓碑不要。
• 高速 – 現代 CPU 上で数命令程度、インデックス計算も簡単。
• 拡張しやすい – ハッシュ関数の変更、大きなキー／値、可変長データも自然に統合可能。

同時実行性（lock‑free）や SIMD を活かした設計ではありませんが、多くのシングルスレッドワークロードで優れた性能と低メモリオーバーヘッドを提供します。