16進数で表される9個のデータ1A、35、3B、54、8E、A1、AF、B2、B3を順にハッシュ表に入れる。
ハッシュ値をハッシュ関数f (データ)=mod(データ, 8)で求めたとき、最初に衝突が起こるのはどのデータか。
ここで、mod(a , b )はa をb で割った余りを表す。
| ア | 54 | イ | A1 | ウ | B2 | エ | B3 |
答え ウ
【解説】
各データのハッシュ値を求めます。
ハッシュ値はハッシュ関数f (データ)=mod(データ, 8)から、データを8で割った余りです。(8で割った余りとは、データの下3ビットの値になります。)
| データ | ハッシュ値 | |
|---|---|---|
| 1 | 1A | 2 |
| 2 | 35 | 5 |
| 3 | 3B | 3 |
| 4 | 54 | 4 |
| 5 | 8E | 6 |
| 6 | A1 | 1 |
| 7 | AF | 7 |
| 8 | B2 | 2 |
| 9 | B3 | 3 |
【キーワード】
・ハッシュ関数
- ハッシュ関数
与えられたデータを一定のデータの要約を出力する処理のこと。
ハッシュ関数によって得られた値をハッシュ値といいます。
ハッシュ表はハッシュ値をキーとしてデータを格納するテーブルです。ハッシュ表の衝突とは既にデータが入っているところに、同じハッシュ値のデータを入れるときに発生します。
ハッシュ関数の特徴として「似たデータのハッシュ値は似ていない」「生成されるハッシュ値に偏りがない」などがあります。
もっと、「ハッシュ関数」について調べてみよう。
戻る
一覧へ
次へ