使用链接散列并使用大小为“m”的 table

Question

我运行进入计算机科学课程的一个例子。

假设我们使用带有链接的散列并使用大小 m 的 table。具有键 k 的哈希函数将记录映射到 k mod m 槽中。如果我们知道记录键是 {i^2 | 1 <= i <= 100} 的子集，那么在最坏的情况下 m 搜索成本的值较低？

一) 11

b) 7

c) 9

d) 12

我的助教说 (1) 是正确的，但我认为这是错误的。事实上我不知道我们是怎么得到这个的！有什么想法吗？

Answer 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 table 中的 "worst" 单元格有 19/100 的概率插入元素，而对于 m 的所有其他值 - 最高概率更高。

至于为什么，有几个因素：

通常首选 m 的较大值 - 要理解它，请确保您了解 m=1（所有元素都在一个列表中）或 m=2（一半两个列表中每个元素的数量）
首选素数，"behave nicer" 用于哈希函数。这个主题在线程 Why should hash functions use a prime number modulus? 中进行了彻底的讨论。这个想法是质数不太容易受到来自特定元素域的偏差的影响，而您的一组平方数就是这样的一个例子。

Answer 2

作为一般的经验法则，您通常希望在散列中对大质数进行模运算，因为它会生成更多不同的值，并且这些值会导致散列槽之间的分布更均匀 table.由于 11 是您列表中最大的素数，直觉上这将是最好的。

对于您的具体问题，我们有记录：

1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, ..., 10000

对于您的每个选项，我们必须找出此集合中有多少个不同的值数字以您的变体为模生成。

对于11：

if n mod 11 = 0 => n*n mod 11 = 0
if n mod 11 = 1 => n*n mod 11 = 1 (1)
if n mod 11 = 2 => n*n mod 11 = 4 (2)
            = 3               = 9 (3)
            = 4               = 5 (4)
            = 5               = 3 (5)
            = 6               = 3
            = 7               = 5
            = 8               = 9
            = 9               = 4
            = 10              = 1

对于7：

if n mod 7 = 0 => n*n mod 7 = 0 (1)
           = 1              = 1 (2)
           = 2              = 4 (3)
           = 3              = 2 (4)
           = 4              = 2
           = 5              = 4
           = 6              = 1

对于9：

if n mod 9 = 0 => n*n mod 9 = 0 (1)
           = 1              = 1 (2)
           = 2              = 4 (3)
           = 3              = 0
           = 4              = 7 (4)
           = 5              = 7
           = 6              = 0
           = 7              = 4
           = 8              = 1

与 12 类似。如您所见，11 是为正方形生成更多不同值的那个，因此它会将您的值更均匀地分布在散列 table 的容器中。在最坏的情况下，更均匀的分布导致搜索成本更低。

使用链接散列并使用大小为“m”的 table

Hashing with chaining and use table of size `m`

algorithm

hash

hashtable

hashmap

data-structures