CHD
完全ハッシュを構成するアルゴリズム
Compress, Hash, and Displace の略
Abstract. A hash function h, i.e., a function from the set U of all keys
to the range range m = {0, . . . , m − 1} is called a perfect hash function (PHF) for a subset S ⊆ U of size n ≤ m if h is 1–1 on S. The important
performance parameters of a PHF are representation size, evaluation
time and construction time. In this paper, we present an algorithm that
permits to obtain PHFs with representation size very close to optimal
while retaining O(n) construction time and O(1) evaluation time. For
example in the case m = 2n we obtain a PHF that uses space 0.67 bits
per key, and for m = 1.23n we obtain space 1.4 bits per key, which was
not achievable with previously known methods. Our algorithm is inspired
by several known algorithms; the main new feature is that we combine
a modification of Pagh’s “hash-and-displace” approach with data com-
pression on a sequence of hash function indices. That combination makes
it possible to significantly reduce space usage while retaining linear con-
struction time and constant query time. Our algorithm can also be used
for k-perfect hashing, where at most k keys may be mapped to the same
value. For the analysis we assume that fully random hash functions are
given for free; such assumptions can be justified and were made in pre-
vious papers.
サイズnのキー集合に対する完全ハッシュを、構築O(n)・評価O(1)を維持しながら、メモリサイズを効率化したアルゴリズム
Hash-and-displaceアルゴリズムの改良
スロット（値域）のサイズmは調整可能で、m = nにもできる。その場合は最小完全ハッシュになる。
ただしmを小さくすると、displacementテーブルのサイズが大きくなる
変数はキー集合のサイズn、スロットのサイズm、バケットあたりの平均キー数b
bは自由に調整可能で、4~6あたりにすることが多いらしい
また、ハッシュ関数を2つ使う
h0(key)：キーをバケットに割り当てるときに適度に分散させるために使う
h1(key, d)：キーをスロットに割り当てるために使う。整数dの入力が異なれば、出力される値も異なる必要がある
h1(key, d) = A(key) + d*B(key) , d = 0,1,2,...
1つ目のハッシュ関数で値が衝突したらdの値を増やして別のハッシュ関数の増分で調整する
実装的には、keyを入力にとって倍サイズの整数を出力するハッシュ関数の出力を上位と下位に分けて使うことが多いらしい
なんか聞いたことある話だな…？
構成方法
まず、サイズB = n / bのバケットを用意します
各キーをh0(key) % Bでバケットに（均等・ランダムに）割り当てます
各バケットB_iに対し、含まれるキーをスロットに割り当てていきます
サイズが大きいバケットから順に処理していきます
h1を使ったダブルハッシュで、キーがすべて空きスロットに割り当てられるようなdを0から順に線形探索します
条件を満たすdをdisplacementテーブルに（バケット番号iをindexとして）格納し、割り当てられたスロットは埋めます
これで完成です
h0(key)でバケット番号を得て、displacementテーブルからdを取ってきて、h1(key, d)を通すとスロットが得られます
d値の分布は幾何分布に近く、b = 4程度であればほとんどが小さい整数に収まることが期待できる
bのサイズを大きくするとdテーブルのサイズ（要素数）は下がるが、構築中のd値の探索中の衝突可能性が高まり、時間がかかるようになる（のに加えて、d値の最大値と大きい値の出現確率が上がる）
期待値としては、b=4でキー当たり2.07 bit、b=6で1.75 bit程度らしい
注意点として、構築時に渡したキー空間に含まれない値を渡してもスロットを返してしまうため、入力がキー空間に含まれるかどうかは別途チェックが必要