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

5.3

 ハッシュに基づいた探索

■

119

して、負数を返す場合にも対処している。剰余演算子（

%

）は、負数を与えられたと

きに負数を返すので、この処理は必須である（すなわち、

Java

では式

-5%3

の値は−

2

になる）。例えば、

String

オブジェクトに対して

JDK

のメソッド

hashCode

を使う

と、文字列「

aaaaaa

」に対する値は、−

1,425,372,064

となる。

5.3.4

 分析

ハッシュ関数がほぼ均等に要素を分散する限り、

ハッシュに基づいた探索

は優れ

た性能を示す。要素を探索する平均時間は、定数、すなわち

O(1)

となる。探索では、

H

でのハッシュ照合の後、衝突した短いリストを線形探索する。ハッシュ表での要

素探索のステップは、次の通り。

●

ハッシュ値の計算

●

ハッシュ値を添字として表の要素を取り出す

●

衝突があったときに、指定された値を見つける

すべての

ハッシュに基づいた探索

アルゴリズムで、最初の

2

つは共通だが、

3

つ目

の衝突処理には複

数の方式がある。

ハッシュ値計算のコストは、上限が定数で抑えられる。本節の単語例では、ハッ

シュ値計算は、文字列長に比例する。有限個の単語の集まりでは、

T

k

を最長文字列

のハッシュ値を計算する時間とすると、どのハッシュ値の計算でも

t

k

時間あればよ

い。したがって、ハッシュ値計算は定数時間演算となる。

第

2

の部分も定数時間で行われる。ハッシュ表が二次記憶に貯えられていると、

要素の位置と、装置の位置決めにかかる時間に変動があるかもしれないが、それも

定数上限で抑え