首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >什么是好的哈希函数?

问什么是好的哈希函数?
EN

Stack Overflow用户
提问于 2008-08-29 16:15:37
回答 9查看 170.7K关注 0票数 143

什么是好的哈希函数?我在大学的数据结构课程中看到了很多哈希函数和应用程序,但我主要了解到很难制作一个好的哈希函数。作为避免冲突的经验法则,我的教授说:

代码语言:javascript
复制
function Hash(key)
  return key mod PrimeNumber
end

(在C和类似语言中,mod是%运算符)

其中质数是哈希表的大小。我知道这是一个比较好的函数来避免冲突,而且速度也很快,但是我怎么才能做得更好呢?对于字符串键和数字键,有没有更好的哈希函数?

EN

回答 9

Stack Overflow用户

回答已采纳

发布于 2009-04-14 08:13:55

用于在基本上任何类型的数据上执行“普通”哈希表查找- Paul Hsieh的这个是我使用过的最好的一个。

http://www.azillionmonkeys.com/qed/hash.html

如果您关心密码安全或任何其他更高级的东西,那么YMMV。如果你只是想要一个用于哈希表查找的强大的通用哈希函数,那么这就是你正在寻找的。

票数 39
EN

Stack Overflow用户

发布于 2008-08-29 16:31:54

对于通用散列,没有“好的散列函数”这样的东西。是的,我知道有一种叫做“通用散列”的东西,但这不是我的意思)。根据上下文的不同,不同的标准决定了散列的质量。已经有两个人提到了SHA。这是一个加密的哈希,它对哈希表来说一点也不好,你的意思可能是。

哈希表有非常不同的要求。但是,由于不同的数据类型公开了不同的信息,可以对其进行散列,因此很难找到一个通用的散列函数。作为一条经验法则,最好将一个类型包含的所有信息都考虑在内。这并不总是那么容易,甚至是不可能的。出于统计(因此冲突)的原因,在问题空间上生成良好的扩散也是很重要的,即所有可能的对象。这意味着当对100到1050之间的数字进行散列时,让最重要的数字在散列中扮演重要角色是不好的,因为对于大约90%的对象来说,这个数字将是0。更重要的是让最后三个数字决定哈希值。

同样,在对字符串进行散列时,考虑所有字符也很重要-除非事先知道所有字符串的前三个字符是相同的;考虑这些字符是一种浪费。

这实际上是我建议阅读Knuth在《计算机编程艺术》第三卷中所说的内容的案例之一。另一个很好的读物是Julienne Walker的The Art of Hashing。

票数 53
EN

Stack Overflow用户

发布于 2008-10-25 14:26:08

散列函数有两个主要目的:

  • 用于将数据点均匀分散到n位中。
  • 用于安全地识别输入数据。

如果不知道哈希的用途,推荐它是不可能的。

如果你只是在程序中创建一个哈希表,那么你不需要担心算法的可逆性或可破解性……SHA-1或AES是完全不必要的,你最好使用variation of FNV。与您提到的简单素数模式相比,FNV实现了更好的离散性(因此冲突更少),并且更适合于不同的输入大小。

如果您使用散列来隐藏和验证公共信息(例如散列密码或文档),那么您应该使用经过公众审查的主要散列算法之一。The Hash Function Lounge是一个很好的起点。

票数 10
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/34595

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档