アルゴリズム (全84問中55問目)
No.55
自然数をキーとするデータを，ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を
h(x)＝x mod n
とする。ここで，n はハッシュ表の大きさであり，x mod n は x を n で割った余りを表す。
キーaとbが衝突する条件はどれか。
h(x)＝x mod n
とする。ここで，n はハッシュ表の大きさであり，x mod n は x を n で割った余りを表す。
キーaとbが衝突する条件はどれか。
出典：平成19年秋期 問12
- [この問題の出題歴]
- 応用情報技術者 H21春期 問6
- 応用情報技術者 H23秋期 問5
- 応用情報技術者 H25秋期 問7
- 応用情報技術者 H27春期 問5
- ソフトウェア開発技術者 H16春期 問13
- ソフトウェア開発技術者 H17秋期 問13
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
イ
解説
キーaのハッシュ関数は a mod n，キーbのハッシュ関数は b mod nです。この2つが一致する場合を方程式で表すと
a mod n＝b mod n
(a mod n)−(b mod n)＝0
(a−b) mod n＝0
a−bがnで割りきれるときにこの等式が成り立つことがわかるので、衝突する条件は「a−bがnの倍数」ということになります。
a mod n＝b mod n
(a mod n)−(b mod n)＝0
(a−b) mod n＝0
a−bがnで割りきれるときにこの等式が成り立つことがわかるので、衝突する条件は「a−bがnの倍数」ということになります。