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

122

■

5

章 探索

7

の結果がほぼ同じになっている。ハッシュ表構築時の再ハッシュは、要素連鎖の

平均長を短くすることによって、全体性能を向上させる。

5.3.5

 変形

ハッシュに基づいた探索

のよくある変形は、衝突の扱いを区画に

1

つの要素しか含

まないように制限する修正である。ハッシュした全要素をリンク付きリストに入れ

る代わりに、オープンアドレス（

open addressing

）という、衝突した要素を「ハッ

シュ表

H

の空いている区画に入れる」技法を使うことができる。この手法を図5-2に

示す。オープンアドレスは、衝突用リストをなくすことによりストレージのオーバー

ヘッドを減らすことができる。

オープンアドレスを使って要素を挿入するには、まず

e

が含まれる目標の区画

h

k

＝

hash (e)

を計算する。もし

H [h

k

]

が空なら、標準的アルゴリズムと同様に

H [h

k

]

＝

e

とする。空でないなら、次のような探査戦略を用いて

H

を探査して、最初に見

つ

けた空区画に

e

を入れる。

図5-2　オープンアドレス

線形探査法（LinearProbing）

h

k

＝

(h

k

＋

c*i)

％

b

で、他の区画を繰り返し探査する。ここで、

c

は整数オ

フセット、

i

は配列

H

への連続探査の回数。

c

＝

1

とすることが多い。こ

の戦略では

H

の要素が塊になる。

二乗探査法（QuadraticProbing）

h

k

= (h

k

＋

c

1

*i

＋

c

2

*i

2

)

％

b

で、他の区画を繰り返し探査する。ここで、

c

1

と

c

2

は定数である。この方式では、要素の塊を防ぐ。実用上役立つ ...