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

114

■

5

章 探索

（すなわち元の

C

にも）

t

が存在しないことを示す。

5.3.2

 文脈

213,557

語の整列した英単語の配列

＊

1

があるとする。もし

二分探索

を用いるなら、

この配列で単語を見つけるには平均で約

18

回（

log (213557)

＝

17.70

であるから）

の文字列比較が必要となる。

ハッシュに基づいた探索

では、文字列比較の回数は、

集まりのサイズではなく、リンク付きリストの長さに依存する。

ハッシュ関数をまず定義する必要がある。目的は、できる限り多くの異なる値を

生成することだが、それらすべてが異なる必要はない。ハッシュの研究は何十年と

行われており、効果的なハッシュ関数について述べた論文は多数あるが、用途は探

索に限らない。例えば、暗号学において、ある種のハッシュ関数が本質的役割を担う。

探索においては、ハッシュ関数は衝突が少なくて、計算が速いものが求められる。

よく使われるのは、元の文字列の中の文字から値を生成するもの

である。例えば、

hashCode(s)

＝

s[0] * 31

(

len

−

1)

＋

s[1] * 31

(

len

−

2)

＋… ＋

s[len

−

1]

のような関数である。ここで、

s [i ]

は、

i

番目の文字（値としては、

ASCII

で

0

から

255

の間）、

len

は文字列

s

の長さを表す。この関数の計算は、例 5-5（

Open

JDK

ソースコード

＊

2

から持ってきた）の

Java

コードに示されるように単純である。

chars

が文字列を定義する文字配列である。クラス

java.lang.String

の