哈希码计算

Question

我刚刚讨论了散列码的概念，遇到了一行：与素数相乘不会将信息从低端转移出去，就像乘以2的幂一样

我没有得到这条线，有人能帮我吗？

谢谢。




Answer 1

在许多哈希代码的使用中，只有哈希代码中最不重要的部分的更改才起作用。换句话说，3和5之间的差异很重要，但3000和5000也可能是相同的数字。

原因是hashcode用于根据hashcode的值将值粗略地“排序”到“bucket”中。这使得哈希表这样的结构只能在bucket中搜索特定的值，而不是搜索表中的每个元素。

问题是，有超过40亿个可能的哈希代码，但通常要将值放入的存储桶数量要少得多。

想象一个场景，你将散列成10个桶。哈希代码0-9都可以放入不同的桶中，但是10需要与0放入同一个桶中，11需要与1放入同一个桶中，以此类推。如果你有1、145、42、5830这样的哈希代码，一切都很好，因为这些值都可以放在不同的存储桶中。另一方面，对于像1、131、593021、63421这样的值，它们都将进入同一个存储桶，因为它们以相同的数字结束，这就是我们所看到的，因为我们只有10个存储桶。因此，对我们来说真正重要的只是哈希代码中最不重要的部分的变化。

Answer 2

该建议适用于计算基于多个字段的哈希代码。它基于这样一种观察：在0到32之间乘以2的幂等于将数字向左移位相应的位数，从而“调零”数字的右侧。

考虑一个情况，当你需要构造一个十字段的哈希代码时，你将每个字段的哈希代码乘以32。这相当于将哈希代码向左移动五位。如果这样做，结束哈希代码将不依赖于前三个字段的哈希代码，因为它们的哈希代码的值将从结果哈希代码中移出。

这种行为是不可取的，因为最后七个字段相同的项将具有相同的哈希代码，即使前三个字段可能不同。这很糟糕，因为它增加了散列冲突的可能性。相反，如果乘以2以上的素数，每个字段的哈希值的一些信息会影响最终结果，从而产生更好的哈希函数。