アルゴリズム(全101問中98問目)
No.98解説へ
2整数X，Yをキーとするデータを，ハッシュ関数h(X，Y)を使って，要素数256の1次元配列に格納する。Xは値1～256を一様にとり，Yは値1～16を一様にとる。ハッシュ関数として最も不適切なものはどれか。ここで，N＝256であり，A mod BはA÷Bの余りを表す。
出典：平成17年春期 問12
- X mod N
- Y mod N
- (X＋Y) mod N
- (X×Y) mod N
広告
解説
「Xは値1～256を一様にとり，Yは値1～16を一様にとる」ので、X，Yをキーとするデータは(256×16＝)4,096種類あることになります。
ハッシュ探索を用いる場合には、なるべくハッシュ値の重複が起こらないようにハッシュ関数を設計する必要があります。この問題の場合には、4,096種類のデータを要素数256の1次元配列に格納するので、シノニム(格納場所の衝突)の発生は避けられませんが、データの格納場所を256要素すべてに一様に割り振ることでシノニムの発生確率を最小限に抑えることができます。つまり、データの格納場所を決定するハッシュ関数は、256種類の値を均等に返す設計になっている必要があります。
ハッシュ探索を用いる場合には、なるべくハッシュ値の重複が起こらないようにハッシュ関数を設計する必要があります。この問題の場合には、4,096種類のデータを要素数256の1次元配列に格納するので、シノニム(格納場所の衝突)の発生は避けられませんが、データの格納場所を256要素すべてに一様に割り振ることでシノニムの発生確率を最小限に抑えることができます。つまり、データの格納場所を決定するハッシュ関数は、256種類の値を均等に返す設計になっている必要があります。
- X＝1～256、N＝256なので、ハッシュ関数からの戻り値は0～255になります。256種類の値を返す関数なので適切です。
- 正しい。Y＝1～16、N＝256なので、ハッシュ関数からの戻り値は1～16になります。256個の要素のうち16要素しか利用できなければ、全要素を利用する場合と比較してシノニムの発生確率・発生回数は増加します。よって、ハッシュ関数の設計としては不適切です。
- (X＋Y)＝2～272、N＝256なので、ハッシュ関数からの戻り値は0～255になります。256種類の値を返す関数なので適切です。
- (X×Y)＝1～4096、N＝256なので、ハッシュ関数からの戻り値は0～255になります。256種類の値を返す関数なので適切です。
広告