アルゴリズムクイックリファレンス 第2版

5.4

 ブルームフィルタ

■

127

画が増えれば、ハッシュ表の既存の要素すべては新たな構造に再ハッシュして挿入

される。これは、将来の探索コストを削減する高価な操作なので、最低限に抑えな

いと、ハッシュ表のならし

O(1)

性能が達成できない。

ハッシュ表の要素が均等に配分できていないことを発見したら、再ハッシュをす

べきだろう。これは、ハッシュ表の負荷率がその値を超えたら再ハッシュを行うよ

うな閾値を設定すればできる。クラス

java.util.Hashtable

のデフォルトの負荷率

の閾値は

0.75

である。この閾値を十分大きくすると、ハッシュ表の再ハッシュは決

して起こらない。

これらの例では、文字列の固定集合からハッシュ表を作った。このような特殊な

場合には、完全ハッシュ法

(perfect hashing)

を用いて、最適性能を実現できる。

完全ハッシュには

2

つのハッシュ関数を用いる。標準的な関数

hash()

が

1

次ハッ

シュ表

H

へのマップに用いられる。各区画

H [i ]

は、より小さな二次ハッシュ表

S

i

を指し、これにはハッシュ関数

hash

i

が付随する。区画

H [i ]

に

k

個のキーがハッシュ

されるならば、

S

i

は

k

2

個の区画を持つ。これは、メモリを無駄遣いしているようだ

が、最初のハッシュ関数の選択が賢明であれば、これまで述べた変形と同じ程度の

オーバーヘッドで済む。適切なハッシュ関数を選択すれば、二次ハッシュ表で衝突

がないことが保証される。これは、定数性能

O(1)

のアルゴリズムを意味する。

完全ハッシュ