自然数をキーとするデータを、ハッシュ表を用いて管理する。
キーx のハッシュ関数h (x )を
h (x ) = x mod n
とすると、キーa とb が衝突する条件はどれか。
ここで、n はハッシュ表の大きさであり、x mod n はx をn で割った余りを表す。
| ア | a + b がn の倍数 | イ | a - b がn の倍数 | |
| ウ | n がa + b の倍数 | エ | n がa - b の倍数 |
答え イ
【解説】
衝突が発生するのはキーについてハッシュ関数で求めた値が一致することなので
a mod n = b mod n
が成り立つときである。
この式を変形すると
(a mod n ) - (b mod n ) = 0
(a - b )mod n = 0
になる。
この式は、a - b がn で割り切れることなので、a - b がn の倍数(イ)である。
【キーワード】
・ハッシュ表
- ハッシュ表
データの格納方法で、データからハッシュ関数で用いたハッシュ値をキーとして格納位置を決めます。
異なったデータから同じハッシュ値になることを衝突(コリジョン)といい、衝突が発生した場合の格納位置の求め方も考慮しておく必要があります。
もっと、「ハッシュ表」について調べてみよう。
戻る
一覧へ
次へ