我想使用一个使用 3 个步骤的简单散列函数对以下键“LOWELL”进行散列:
第 1 步:将 key 转换为数字。
LOWELL = | L | O | W | E | L | L | | | | | | |
ASCII code: 76 79 87 69 76 76 32 32 32 32 32 32
my question here why it added more 6 empty positions with fixed ASCII code 32
第 2 步:折叠并相加(切下数字并相加 他们在一起)
7679|8769|7676|3232|3232|3232|
7679+8769+7676+3232+3232+3232 = 33,820
第三步:用质数取模
33,820 模 19937 = 13,883
Another question here for why dividing by prime numbers i found this answer : Dividing by a number is good when there are sequences of consecutive numbers. If there are many dierent sequences of consecutive numbers, dividing by a number that has many small factors may result in lots of collisions. A prime number is a better choice. but i didn't get it
第四步:除以地址空间的大小(最好是素数)。 13,883 模 101 = 46
finally why it divided the address space ?!
您可以找到详细步骤here (幻灯片 350) 非常感谢您的帮助
最佳答案
由于您的地址空间仅包含 101 个槽，因此您不能将记录放在地址超过此限制的位置。
因此，您需要注意将哈希函数(在您的情况下为 13,883)的输出除以地址空间，以确保记录的位置落在允许的地址空间内.
因此 h(s) % address_space 将始终在您的地址空间内提供允许的位置。
关于您的第一个问题，为什么我们在散列中使用质数，这个线程将帮助您: Why use a prime number in hashCode?
关于algorithm - 通过折叠然后除以素数来散列 key ？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37212536/