散列码计算

Question

我正要通过的哈希码的概念，并遇到了线multiplying by primes will not tend to shift information away from lower end - as would multiplying by a power of 2

我没有得到这条线，任何人都可以帮我这个。

谢谢。

Answer 1

该建议针对基于多个字段的计算散列码给出。它基于这样的观察，即在0和32之间乘以2的幂相当于将剩下的数字移位相应的位数，从而将该数字的右侧“归零”。

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

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

Answer 2

在散列码的许多用途中，只有散列码最不重要的部分发生变化。换句话说，3和5之间的差异很重要，但是3000和5000也可能是相同的数字。

原因是哈希码用于根据哈希码的值对“桶”进行粗略的“排序”。这允许像散列表这样的结构仅在存储桶内搜索特定值，而不是搜索表中的每个元素。

问题是，有超过40亿个可能的哈希码，但通常会有数量更少的桶来放入值。

想象一下，您将一个场景散列为10个桶。哈希码0-9可以全部进入单独的桶中，​​但是然后10需要进入与0相同的桶，11与1相同，等等。如果你有像1，145，42，5830这样的hashcode，那么所有的工作都很好，因为每个值都可以放入不同的桶中。像1,131,593021,63421那样的数值，他们都会进入同一个水桶，因为他们以相同的数字结束，这就是我们所看到的，因为我们只有10个水桶。所以它只会改变我们hashcode中最不重要的部分。