自然数をキーとするデータを、ハッシュ表を用いて管理する。
キーx のハッシュ関数をh (x )を
h (x )=x mod n
とする。
ここで、n はハッシュ表の大きさであり、x mod n はx をn で割った余りを表す。
キーa とb が衝突する条件はどれか。
| ア | a +b がn の倍数 | イ | a -b がn の倍数 | |
| ウ | n がa +b の倍数 | エ | n がa -b の倍数 |
答え イ
【解説】
問題からa とb のキー値が衝突するのは、キー値を求めるハッシュ関数が剰余計算であるので
a mod n =b mod n
のときである。
この式を変形すると、
a mod n -b mod n =0
(a -b )mod n =0
になり、これはa -b がn の倍数(イ)である。
【キーワード】
・ハッシュ法
- ハッシュ法
管理するデータを一定の規則(アルゴリズム)でハッシュ値(キー値)を求めそのキー値で格納することを決めるデータ管理方法である。
管理するデータのすべてのキー値が異なれば問題ないが、複数のデータのキー値が同じになる場合があり、それを衝突という。衝突が発生した場合には、そのときの処理方法を決めておきそれに則って処理を行う。
もっと、「ハッシュ法」について調べてみよう。
戻る
一覧へ
次へ