为什么这是一个糟糕的散列函数？

Question

我目前正在讨论散列和哈希表，我想知道为什么像下面这样的东西被认为是糟糕的哈希函数(伪代码)：

function hash(String_t word, Int table_size)
    i = randomly generated number with 0<i<table_size 
    j = ASCII code of the first letter of word

    return i * j % table_size

假设在函数调用期间可以存储i的值以实现一致性(例如，使用C中的static关键字将i值存储在函数范围内)，为什么这是一个糟糕的哈希函数？

Answer 1

一个好的哈希函数应该能很好地工作在不同的输入大小上，条件是表的大小是输入数的常数倍。这不符合这一标准，原因有几点：

1. 散列值仅由第一个字母确定。因此，可能的散列值的总数被可能的首字母数限制，这是很小的。为大量输入选择一个较大的表大小没有任何影响:您仍然会得到大量的冲突。
2. 由于单词的首字母分布很不均匀，所以会有很多碰撞。在定义函数时，至少要使用单词的所有字母，但是您确实需要更多的建议来拯救这个构造。
3. 定义d= gcd(i，表大小)。在某些情况下，d将大于1，在这种情况下，表中的每个d元素中只有一个元素有机会被填充:其他元素将被浪费空间(因此会有更多的冲突)。也就是说，只有0，d，2d，3d，.可能是哈希值。至少限制为i值与d=1，以防止这些退化的情况。
4. 我乘以最大的j值，有时会小于表的大小(当我很小的时候)，这意味着表的顶部永远不会被触及。更多的浪费空间。

人们通常会试图想出一些哈希函数，这些函数一般都能很好地工作，而且你可以证明它们的一些优点。这里有一个非常具体的例子，对我来说最明显的是否定的情况，所以非常怀疑你是否能证明这个构造的任何积极的方面。