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

5.3

 ハッシュに基づいた探索

■

111

5.3

 ハッシュに基づいた探索

これまで述べた探索は、要素が少ない集まり（

逐次探索

）か、整列済みの集まり

（

二分探索

）に適したものだった。必ずしも整列されていない、もっと大きな集まり

を扱う強力な技法が必要だ。最もよく使われるのは、ハッシュ関数を使って、探索

対象の要素の

1

つ以上の特性をハッシュ表の添字に変換する方法である。

ハッシュ

に基づいた探索

は、本章で記述された他の探索アルゴリズムよりも平均時性能に優

れる。アルゴリズムの本が多数、ハッシュ表の項目（

Cormen et al., 2009

の

11

章）

で、

ハッシュに基づいた探索

を論じている。ハッシュ表について説明しているデータ

構造の本にも掲載されている。

ハッシュに基づいた探索

では、まず

n

個の要素からなる集まり

C

を、

b

個の区画

（

bin

）を持つ配列のハッシュ表

H

に読み込む。この前処理は

O(n)

性能だが、その後

の探索性能を向上させる。ハッシュ関数という

概念がそれを可能にする。

ハッシュ関数は、各要素

C

i

を整数値

h

i

にマップする確定関数である。とりあえ

ず、

0

≦

h

i

＜

b

と仮定する。ハッシュ表に要素をロードすると、要素

C

i

は、区画

H [h

i

]

に挿入される。全要素がハッシュ表に格納されると、要素

t

の探索は、区画

H [hash(t)]

内の探索に帰着する。

ハッシュ関数は、

2

要素

C

i

と

C

j

が等しければ、

hash(C

i

)

＝

hash(C

j

)

ということし

か保証しない。

C

の（異なる）複数の要素が同じハッシュ値をとること