応用情報技術者 試験情報＆徹底解説

管理人様

以下に、この問題についての私の解釈を書きます。管理人様の解説とは少し違うのですが、いかがでしょうか？

「2整数X，Yをキーとするデータ」ということは、一つのデータの中にキー1としてX、キー2としてYがあるととらえます。
「Xは値1～256を一様にとり，Yは値1～16を一様にとる」となると、
X＝1に対してY＝1,・・・,16
・・・
X＝256に対してY＝1,・・・,16
となり、このデータは、256×16＝4096種類あるととらえます。

この4096種類のデータを要素数256の配列に格納しようとすると、間違いなくシノニムが発生するのですが、シノニムの頻度が最も高いものが「最も不適切なもの」だと思います。
解説にあるように、ハッシュ値が0～255なら適切で、そうでなければ不適切というわけではなく、この場合、ア～エのどれも不適切で、その中で最も不適切なものが正解です。

アのX mod Nの取り得る値は0～255の256個で、シノニムは4096－256＝3840回
イのY mod Nの取り得る値は1～16の16個で、シノニムは4096－16＝4080回
ウの(X＋Y) mod Nの取り得る値は0～255の256個で、シノニムは4096－256＝3840回
エの(X×Y) mod Nの取り得る値は0～255の256個で、シノニムは4096－256＝3840回

したがって、正解はイ

それとも、要素数256の配列の全てに格納されるのが適切で、未格納が出てしまうのが不適切でしょうか？

ご指摘ありがとうございます。

私の考えとしては、要素数4,096個のデータを要素数256の配列に格納するという与えられた状況の中で、ハッシュ関数をどう設計すべきかという観点で適切・不適切を分けました。

本問では、助け人さんのおっしゃるようにシノニムの発生が不可避です。シノニムの発生確率を最小限に抑えるためには配列の全要素を均等に使うことが重要ですが、そのためにはハッシュ関数が均等に256種類の値を返す設計になっている必要があると考えました。

このため、16種類の値しか返さない「イ」は、他のハッシュ関数と比較して不適切な設計であるとなります。もちろん、なぜ16要素しか使わないと不適切であるかと問われれば、それはシノニムの発生確率・発生回数が多くなるからです。

上記の点が分かるように解説を書き直してみました。
  https://www.ap-siken.com/kakomon/19_haru/q12.html

管理人様
確認しました。ありがとうございました。