什么是好的散列函数？
什么是一个好的哈希函数？ 我在大学的数据结构课程中看到了很多散列函数和应用程序，但是我大部分都知道要做一个好的散列函数是相当困难的。 作为避免碰撞的经验法则，我的教授说：
function Hash(key) return key mod PrimeNumber end （mod是C和类似语言中的％运算符）
质数是散列表的大小。 我觉得这是一个比较好的避免碰撞和快速的function，但是我怎样才能做出更好的？ string键对数字键有更好的散列函数吗？
对于基本上任何types的数据进行“正常”散列表查找 – 这是保罗·谢的这一个是我用过的最好的。
http://www.azillionmonkeys.com/qed/hash.html
如果你关心密码安全或其他更先进的事情，那么YMMV。 如果你只是想一个哈希表查找一个通用的散列函数，那么这就是你在找什么。
对于通用哈希来说，没有什么“好的哈希函数”（编辑，是的，我知道有“通用哈希”之类的东西，但这不是我的意思）。 取决于上下文，不同的标准决定了散列的质量。 两个人已经提到了SHA。 这是一个encryption散列，对于你可能认为的散列表来说并不是那么好。
哈希表有非常不同的要求。 但是，仍然普遍地find一个好的散列函数是很困难的，因为不同的数据types公开了不同的可以散列的信息。 作为一个经验法则，考虑所有types的信息是平等的。 这并不总是很容易，甚至是不可能的。 出于统计的原因（也就是碰撞），在问题空间（即所有可能的对象）上产生良好的分布也很重要。 这意味着当哈希数在100到1050之间时，让最重要的数字在哈希中起很大作用是不好的，因为对于大约90％的对象来说，这个数字将是0.更重要的是让后三个数字决定散列。
类似地，当对string进行散列时，重要的是要考虑所有字符 – 除非事先知道所有string的前三个字符是相同的; 考虑到这些是浪费。
这实际上是我build议阅读Knuth在“艺术计算机程序devise” （ The Art of Computer Programming ） 另一个很好的阅读是Julienne Walker的“哈希艺术” （ The Art of Hashing） 。
哈希函数有两个主要用途：
- 将数据点统一分散到n位。
- 安全地识别input数据。
不知道你在用什么来推荐一个散列是不可能的。
如果你只是在一个程序中做一个哈希表，那么你不必担心algorithm是可逆的还是可以破解的。SHA-1或AES对于这个是完全没有必要的，你最好使用FNV的一个变种 。 FNV可以达到更好的分散（因此碰撞less），比你提到的简单主模块更适应不同的input尺寸。
如果您使用哈希来隐藏和validation公共信息（例如哈希密码或文档），那么您应该使用经公共审查审查的主要哈希algorithm之一。 哈希函数rest室是一个很好的开始。
这是一个很好的例子，也是你为什么永远不想写一个的例子。 这是一个Fowler / Noll / Vo（FNV）哈希计算机科学天才和纯伏都教相等的部分：
unsigned fnv_hash_1a_32 ( void *key, int len ) { unsigned char *p = key; unsigned h = 0x811c9dc5; int i; for ( i = 0; i < len; i++ ) h = ( h ^ p[i] ) * 0x01000193; return h; } unsigned long long fnv_hash_1a_64 ( void *key, int len ) { unsigned char *p = key; unsigned long long h = 0xcbf29ce484222325ULL; int i; for ( i = 0; i < len; i++ ) h = ( h ^ p[i] ) * 0x100000001b3ULL; return h; }
编辑：
- Landon Curt Noll在他的网站上推荐了FVN-1Aalgorithm，使用原始的FVN-1algorithm：改进后的algorithm更好地分散了散列中的最后一个字节。 我相应地调整了algorithm。
我会说，主要的经验法则是不要推出自己的。 尝试使用经过彻底testing的东西，例如SHA-1或其他东西。
一个好的散列函数具有以下属性：
-
给定一条消息的散列，攻击者find另一条消息使得它们的哈希值是相同的，这在计算上是不可行的。
-
给定一对消息m'和m，find两个h（m）= h（m'）在计算上是不可行的
这两种情况是不一样的。 在第一种情况下，有一个预先存在的散列，你试图find一个碰撞。 在第二种情况下，你试图find任何两个相互冲突的消息。 由于生日的“悖论”，第二项任务要容易得多。
在性能不是那么重要的问题，你应该总是使用一个安全的散列函数。 有一些非常聪明的攻击可以通过在散列中强制冲突来执行。 如果你从一开始就使用强大的东西，你会保护自己免受这些。
在新devise中不要使用MD5或SHA-1。 包括我在内的大多数密码学家都会认为他们是破产的。 这两种devise的弱点的主要原因在于，我上面概述的第二个属性并不适用于这些结构。 如果攻击者可以产生两个消息，m和m'，它们都散列到相同的值，他们可以使用这些消息对你。 SHA-1和MD5也受到消息扩展攻击的困扰，如果不小心的话，会严重削弱您的应用程序。
Whirpool等更现代的散列是更好的select。 它不会受到这些消息扩展攻击的影响，并使用与AES相同的math来certificate针对各种攻击的安全性。
希望有所帮助！
你在这里说的是你想要有一个使用有碰撞抵抗。 尝试使用SHA-2。 或者尝试在单向压缩function中使用（好的）分组密码（以前从未尝试过），就像宫口平面模式下的AES一样。 问题在于你需要：
1）有一个IV。 尝试使用Khinchin常数的小数部分的前256位或类似的东西。 2）有一个填充scheme。 简单。 从MD5或SHA-3（Keccak [发音为'ket-chak'））的哈希中挖掘出来。 如果你不关心安全性（其他人也这么说），看看FNV或者Bob Jenkins的lookup2（实际上我是第一个推荐lookup2的人）。另外试试MurmurHash，它很快（检查这个：.16 cpb ）。
