algorithm - 通过链接和大小为m的使用表进行哈希处理

我在计算机科学课上遇到了一个例子。
假设我们使用hashing和chaining，并使用sizem的表。哈希函数将键k的记录映射到k mod m槽中。如果我们知道记录键是{i^2 | 1 <= i <= 100}的子集，那么在最坏的情况下，m的搜索成本值哪个更低？
a）11个
b）7个
c）9个
d）12个
我的助教说（1）是真的，但我认为这是假的事实上我不知道我们怎么得到这个！知道吗？

最佳答案

你可以用一个简单的代码来检验它：

    int[] mVals = {11, 7, 9, 12};
    for (int m : mVals) {
        int[] cells = new int[m];
        for (int i = 1; i<= 100; i++) {
            int x = i*i % m;
            cells[x]++;
        }
        System.out.println("m=" + m + " cells=" + Arrays.toString(cells));
    }

将产生：

m=11 cells=[9, 19, 0, 18, 18, 18, 0, 0, 0, 18, 0]
m=7 cells=[14, 29, 28, 0, 29, 0, 0]
m=9 cells=[33, 23, 0, 0, 22, 0, 0, 22, 0]
m=12 cells=[16, 33, 0, 0, 34, 0, 0, 0, 0, 17, 0, 0]

由于您的值在指定的范围内，您可以看到m=11表中的“最差”单元格对于要插入其中的元素具有19/100的概率，而对于m的所有其他值，最高的概率更高。
至于原因，目前有几个因素：
通常首选较大的值m-要理解它，请确保您了解当m=1（所有元素都在一个列表中）或m=2（两个列表中每个元素的一半）时会发生什么情况
素数是首选的，对于散列函数来说“表现得更好”。本主题在线程Why should hash functions use a prime number modulus?中进行了详细讨论这个想法是质数对于元素的特定区域的偏差是不易受攻击的，你的平方数集就是这样的一个例子。

关于algorithm - 通过链接和大小为m的使用表进行哈希处理，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28697002/