シノニムとは｜ハッシュ関数の衝突

シノニムとはハッシュ関数で計算した結果が同じになってしまう現象を指します。

発生する場面

ファイル保存などの場面でデータをキー値（データの住所のようなもの）とともに保存します。その際にハッシュ関数（例えばあるIDをある数値で割ってその余りの数値を出す）を使って計算した場合値が同じになってしまうことがあります。

シノニムの具体例

例えば以下のデータがあるとします。

ID	データ
51	牛丼
27	ハンバーガー
45	ピザ

これに以下のハッシュ関数で計算した値を使ってデータを格納しようとします。

f(x) = x % 13

xにはIDの値が入りますので以下のようになります。

ID	データ	ハッシュ値
51	牛丼	3
27	ハンバーガー	3
45	ピザ	6

牛丼とハンバーガーが同じハッシュ値となってしまいました。これをデータの住所に使用すればデータが意図せずに上書きされてしまいますね。これがシノニムになります。

基本情報技術者試験｜シノニムの問題

基本情報技術者令和3年免除 問8

自然数をキーとするデータを，ハッシュ表を用いて管理する。キー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=51 b=29 n=11として考えてみましょう。関数に当てはめてみると51も29も余りがどちらも7になります。これをa、bに当てはめて考えてみます。

ア　51＋29＝80が11の倍数→X
イ　51－29＝22が11の倍数→○
ウ　11が51＋29＝80の倍数→X
エ　11が51－29＝22の倍数→X

ここで仮設定（a=51 b=29 n=11 余りがどちらも7）の解説を補足します。

n=11というのは11個のデータがある表ということを想像してください。そしてaとbの値はその表の中から任意に選ぶ値です。今回のハッシュ関数がmodで割り算の余りを使うということなのでnとの計算で余りが同じ値になる数値をaとbに設定しています。これは問題の「任意のキーaとbが衝突する条件はどれか」という部分から決まってきます。