英文:
Go: How does this hash function range from 0-32 bits?
问题
我正在尝试编写一个使用30位哈希的自定义哈希函数。
下面是一个用于FNVa 32位哈希的代码示例：
func fnva32(data string) uint32 {
var hash uint32 = 2166136261
for _, c := range data {
hash ^= uint32(c)
hash *= 16777619
}
return hash
}
现在是我将小写字母a-z转换为30位哈希的代码：
func id(s string) uint {
var id uint
var power uint = 1
for _, c := range s {
id += (uint(c) - 96) * power
power *= 26
}
return id % 1073741824
}
这个代码通过对结果取模限制了哈希函数的最大位数为30位。但是，为什么FNVa32哈希函数限制在32位呢？它们没有使用取模操作，为什么不会生成超过32位的数字呢？
另外，你可能已经注意到我没有使用质数。我尝试了一些质数，但它增加了碰撞的数量。目前，我在对600,000个（真实的）单词进行哈希时，得到了291个碰撞，而FNVa32只有76个碰撞。
我的问题是...是什么使得FNVa32限制在32位，我该如何将其改为30位？
英文:
I'm trying to write my own hash function that uses a 30-bit hash.
Here is some code for a FNVa 32-bit hash.
func fnva32(data string) uint32 {
var hash uint32 = 2166136261
for _, c := range data {
hash ^= uint32(c)
hash *= 16777619
}
return hash
}
Now here is my code that converts lowercase letters a-z into a 30-bit hash:
func id(s string) uint {
var id uint
var power uint = 1
for _, c := range s {
id+=(uint(c)-96)*power
power*=26
}
return id%1073741824
}
That specifically limits my hash function to a maximum of 30-bit because I'm using a modulus against that number. But how is that FNVa32 hash limited to 32-bits? They are not using a modulus. How does it not generate a number larger than that?
Also you probably notice that I'm not using prime numbers. I tried some prime numbers but it increased the collisions. Currently I'm getting 291 collisions and FNVa32 is getting 76 collisions, from hashing 600,000 (real) words.
My question is... what is making FNVa32 limit to 32-bit, and how would I change it to be 30-bit instead?
答案1
得分: 2
fnva32函数的返回类型是uint32，因此它无法返回比32位更多的答案。此外，计算过程中使用了一个uint32变量。
英文:
The return type of the fnva32 function is uint32 so there is no way it could return an answer with more bits. Also, the calculation uses a uint32 variable internally.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论