データ構造における非対称ハッシュ（Asymmetric Hashing）とは？仕組みと性能評価を解説

非対称ハッシュ（Asymmetric Hashing）とは

非対称ハッシュは、複数選択ハッシング（multiple choice hashing）を発展させたハッシュ技法の一つで、チェーンの長さの偏りを抑え、検索・挿入性能を向上させることを目的としています。ここでは、非対称ハッシュの基本的な仕組みと、理論的に保証される性能について解説します。

基本構造：ハッシュテーブルの分割

非対称ハッシュでは、まずハッシュテーブル全体を d 個のブロックに分割します。各ブロックの長さは n/d となります。

このとき、探査値（probe value）x_i（0 ≤ i ≤ d−1）は、以下の範囲から一様ランダムに選択されます。

$$\left\{ \frac{i \cdot n}{d},\ \ldots,\ \frac{(i+1) \cdot n}{d} - 1 \right\}$$

つまり、各探査値はそれぞれ異なるブロックの中から独立に決められる点が、通常の複数選択ハッシングとの大きな違いです。

挿入アルゴリズム

要素 x を挿入する手順は、複数選択ハッシングと同じ考え方に基づいています。

1. リスト A[x₀]、A[x₁]、…、A[x_d−1] の長さをそれぞれ調べる。
2. x を最も短いリストに追加する。

複数のリストが同率で最短となった場合（タイのとき）は、添字（インデックス）が最も小さいリストに挿入されます。この「最短リストへの挿入」というシンプルな戦略が、全体のバランスを保つ鍵となります。

最長リスト長の期待値

Vocking の解析によれば、非対称ハッシュにおける最長リストの長さ W の期待値 E[W] は、次のように上から抑えられます。

$$E[W] \leq \frac{\ln \ln n}{d \cdot \ln \phi_{2}} + O(1)$$

ここで登場する関数 φ_d は黄金比の一般化であり、d = 2 の場合には黄金比そのものと一致します。

$$\phi_{2} = \frac{1 + \sqrt{5}}{2}$$

まとめ

非対称ハッシュは、テーブルを d 個のブロックに分割し、各ブロック内から候補位置を選び、最短のリストへ要素を挿入することでチェーンの偏りを防ぐ手法です。最長リスト長の期待値が ln ln n / (d ln φ₂) + O(1) に抑えられることが理論的に示されており、大規模なデータに対しても安定した高性能な検索を実現できることが分かります。