散列表大小和密钥的重要位 [英] hashtable size and significant bits of key

问题描述

我有一个关于散列表大小和模块散列的问题。我指的散列算法如下：
hash_key％table_size = array_index。
我正在阅读算法教科书，其中给出了以下几点建议：

如果表格大小不是素数，则可能是所有在确定array_index时，密钥的位不起作用。

任何人都可以用一个例子来解释这个意思吗？

解决方案

你想避免的是常见因素。有一个定理指出，每个数字都可以表示为素数的乘积。

因此，如果你有一个素数作为mod。你不会在该部门分享任何因素。

说A％30，所以2,3和5中的任何倍数将在分部中分享因子，并且该分数在该分部中将毫无用处。

250/30 = 50/6 = 25/3

你想尽量减少无用的因素。 p>

I have a question regarding hashtable size and modular hashing. The hashing algorithm I'm referring to is the following: hash_key % table_size = array_index. I'm reading an algorithms textbook where the following bit of advice is given:

If the table size is not prime, it may be the case that all of the bits of the key do not play a role in determining the array_index.

Can anyone explain what this means exactly with an example?

解决方案

What you want to avoid is common factors. There is a theorem that states that every number can be expressed as a product of prime numbers.

So as a consequence if you have a prime number as a mod. You will not share any factors in the division.

say A % 30, so any multiple of 2, 3 and 5 will share the factors in the division and that factor will be useless in the division.

250/30 = 50 / 6 = 25 / 3

You want to minimize useless factors.

这篇关于散列表大小和密钥的重要位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！