什么是好的哈希函数？

什么是好的哈希函数？我在大学的数据结构课程中看到了很多哈希函数和应用程序,但我大多认为很难创建一个好的哈希函数.作为避免碰撞的经验法则,我的教授说:

function Hash(key)
  return key mod PrimeNumber
end

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

使用素数作为哈希表的大小.我觉得这是一个很好的功能,以避免碰撞和快速,但我怎么能做一个更好的？字符串键对数字键有更好的散列函数吗？

1> Konrad Rudol..：

---

对于通用哈希来说,没有"良好的哈希函数"这样的东西(编辑.是的,我知道有"普遍哈希"这样的东西,但这不是我的意思).根据上下文,不同的标准决定了散列的质量.两个人已经提到了SHA.这是一个加密哈希,它对你可能意味着的哈希表一点都不好.

哈希表具有非常不同的要求.但是,普遍找到一个好的散列函数很难,因为不同的数据类型会暴露可以散列的不同信息.根据经验,最好考虑一种类型的所有信息.这并不总是容易甚至可能.出于统计(以及碰撞)的原因,在问题空间(即所有可能的对象)上产生良好的分布也很重要.这意味着当散列数在100到1050之间时,让最重要的数字在散列中起很大作用是没有好处的,因为对于~90%的对象,这个数字将为0.让最后三个数字更重要.数字确定哈希值.

类似地,当散列字符串时,考虑所有字符是很重要的 - 除非事先知道所有字符串的前三个字符都是相同的; 考虑到这些就是浪费.

这实际上是我建议阅读Knuth在"计算机编程艺术"第一卷中所说的内容之一.另一个好读物是Julienne Walker的"哈希艺术".

2> Chris Harris..：

---

对于基本上任何类型的数据进行"正常"哈希表查找 - Paul Hsieh的这个是我用过的最好的.

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

如果您关心加密安全或其他更高级的东西,那么YMMV.如果你只想要一个用于哈希表查找的kick ass通用哈希函数,那么这就是你要找的东西.

---

@cobarzan你的里程可能会变化

---

YMMV代表什么？

---

Hsieh的哈希函数很糟糕,碰撞的次数比我们想要的要多一个数量级.特别是,仅在最后4个字节中不同的字符串可能很容易发生冲突.如果您有一个30个字符的字符串,在最后4个字节中有所不同,在28个字节进行处理后,哈希值仅在最后2个字节中有所不同.这意味着您保证对其余两个字节值之一进行冲突.(是的,它很快.那么.)

3> Myrddin Emry..：

---

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

将数据点均匀地分散为n位.

安全地识别输入数据.

如果不知道你正在使用什么,就不可能推荐哈希.

如果您只是在程序中创建哈希表,那么您不必担心算法的可逆性或可破解性...... SHA-1或AES对此完全没必要,您最好使用它FNV的变种.FNV比你提到的简单素数模型实现更好的色散(因此更少的碰撞),并且它更适应不同的输入尺寸.

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

4> Nick Van Bru..：

---

这是一个很好的例子,也是你永远不想写一个的例子.这是一个Fowler/Noll/Vo(FNV)Hash,它是计算机科学天才和纯巫术的平等部分:

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-1A算法而不是原始的FVN-1算法:改进的算法更好地分散了散列中的最后一个字节.我相应地调整了算法.

---

您可能需要查看此站点以获取有关选择这些值的原因的一些信息:http://isthe.com/chongo/tech/comp/fnv/#fnv-prime