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

我目前覆盖哈希和哈希表，我想知道为什么像被认为是不好的散列函数（伪）以下：为什么这是一个糟糕的散列函数？

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的值存储在函数范围内），为什么这是一个糟糕的哈希函数？

来源

2016-05-11 JavascriptLoser

一个好的散列函数应该适用于各种输入大小，只有条件是表大小是一个常数倍大于输入数。由于以下几个原因，这不符合该标准：

散列值仅由第一个字母确定。因此，可能的散列值的总数受限于可能的第一个字母的数量，该数字很小。为大量输入选择较大的表格大小没有任何影响：您仍然会遇到大量碰撞。
由于第一个单词的字母非常不均匀分布，所以会产生很多冲突。至少在定义你的函数时使用单词的所有字母，但你真的需要的不仅仅是那个建议来拯救这个构造。
定义d = gcd（i，表格大小）。在某些情况下，d将大于1，在这种情况下，表格中每个d元素中只有一个元素将有机会被填充：其他元素将会浪费空间（并因此导致更多的碰撞）。也就是说，只有0，d，2d，3d ......可能是一个散列值。至少限制在d = 1的i值，以防止这些退化情况。
我乘以j的最大值偶尔会小于表格大小（当我很小时），这意味着表格的顶端永远不会被触摸。浪费更多的空间。

人们通常会试图想出散列函数，这些散列函数在一般情况下运行良好，并且您可以证明它们的优点。在这里，你有一个特定的案件的意图，什么是最明显的负面情况，所以非常非常怀疑，你可以证明这个构造的任何积极的事情。 “

来源

2016-05-11 11:19:02 TheGreatContini

”散列值仅由第一个字母确定“。散列值是不是由第一个字母和随机值决定的？另外，d = gcd（i，表格大小）是什么意思？ – JavascriptLoser

@PythonNewb：取决于你如何看待它！按照我观察它的方式，随机值在开始时选择，然后固定。在该值固定后，如果且仅当它们具有相同的第一个字母时，两个单词才会发生碰撞。 Gcd是最大的公约数。该属性来自模块算术。 – TheGreatContini

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

回答

相关问题