シノニムの発生

なんでさん  
(No.1)
https://www.ap-siken.com/bunya.php?m=2&s=2&no=60

この問題についてですが、参考書では「イ」だとシノニムが発生するからと記載がありますが、
どちらが正しいのでしょうか?

自分の意見としてはキーの範囲は1~16なのでシノニムなんて起こらないと思うので、サイト派です。
2019.01.12 19:08
双葉さん 
(No.2)
>Xは値1~256を一様にとり,Yは値1~16を一様にとる
と問題文にあることから、「2整数X,Yをキーとするデータ」は一つではなくて
複数あるようですね。そもそも入力データが複数ないと、ハッシュ関数で分ける
意味がありませんから。

すると、選択肢の「イ」はハッシュ値は16通りにしかならず、17回データの
入力が発生すれば、必ずシノニムが発生することになります。
2019.01.12 19:39
助け人さん 
AP ゴールドマイスター
(No.3)
私はこう考えました。

ア~エは、いずれもシノニムが発生しますが、最もシノニムが発生するものはどれかが問われていると。

解説に少し疑問がありますので、別スレで管理人様に問い合わせます。
2019.01.12 20:00
双葉さん 
(No.4)
補足説明ありがとうございます。
ア~エはどれもシノニムが発生しますが、その頻度が最も高い「イ」が「最も不適切」と
考えています。他に不適切の候補を挙げるならば、ハッシュ値の頻度が偏る「エ」でしょうが、
それよりも、シノニム発生が多い「イ」だと見ています。

実験用プログラムをC#でコーディングしましたので、環境がある方はコンパイルして
やってみてもらえればと思います。コンソールアプリケーションです。
以下、実験用コード

using System;
namespace abc
{
    class ex
    {
        static void Main(string[] args)
        {
            int[] ha = new int[256];
            int[] hi = new int[256];
            int[] hu = new int[256];
            int[] he = new int[256];
            int n = 256;

            for (int x = 1; x <= 256; x++)
            {
                for (int y = 1; y <= 16; y++)
                {
                    ha[x % n]++;
                    hi[y % n]++;
                    hu[(x + y) % n]++;
                    he[(x * y) % n]++;
                }
            }

            Console.WriteLine("ハッシュ値と生成回数の関係");
            Console.WriteLine("値\tア\tイ\tウ\tエ");
            for (int i = 0; i < 256; i++)
            {
                Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}", i,ha[i],hi[i],hu[i],he[i]);
            }

            Console.ReadLine();
        }
    }
}
2019.01.12 21:34

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。

その他のスレッド


Pagetop