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

5.3

 ハッシュに基づいた探索

■

113

n

＝

6

個の

異なる要素

キー値

key

を計算する。

重複もある。

b

＝

4

個 の 区 画

を 持 つ

A

の 添 字

h=hash(e)

を計算

する。

選択肢：リンク付きリストを

格納

選択肢：オープンアドレス

衝突が起こると、

異 な る 場 所 に 値

を格納する。

図5-1　ハッシュの一般的な方式

配列とリンク付きリストを使って情報をメモリに格納する。

ハッシュに基づいた探索

には、課題が

2

つある。ハッシュ関数の設計と、衝突をど

う扱うかである。ハッシュ関数の選択が適切でないと、一次記憶でのキーの配置が

偏ってしまう。キーの配置が偏ると、

2

つの問題が起こる。ハッシュ表の多くの区

画が使われないままでスペースの無駄が生じること、もう

1

つは、多くのキーが同

じ区画で衝突することによる性能の低下である。

5.3.1

 入出力

二分探索

とは異なり、

ハッシュに基づいた探索

は元の集まり

C

が整列されていなく

ても構わない。実際、

C

が整列されていても、ハッシュ表

H

に要素を挿入するハッ

シュ法では

H

内でその順序を保持しようとはしない。

ハッシュに基づいた探索

の入力は、計算したハッシュ表

H

と探索の目標要素

t

とな

る。アルゴリズムは、

H [h ]

（

h

＝

hash(t )

とする）のリンク付きリストに

t

が存在すれ

ば

true

を返す。

H [h ]

のリンク付きリストに

t

が存在しなければ

false

を返し、

H

に