什么是好的哈希函数？我在大学的数据结构课程中看到了很多哈希函数和应用程序，但是我大多数都知道要创建一个好的哈希函数非常困难。为了避免发生冲突，我的教授说：

function Hash(key)
  return key mod PrimeNumber
end

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

质数应为哈希表的大小。我知道这是一个不错的功能，可以避免碰撞，而又可以避免快速碰撞，但是我该如何做得更好呢？是否有针对数字键的字符串键更好的哈希函数？

解决方案

回答

我想说，主要的经验法则是不要自己动手。尝试使用经过全面测试的产品，例如SHA-1或者类似的产品。

回答

没有用于通用哈希的良好哈希函数之类的东西(ed。是的，我知道有诸如通用哈希之类的东西，但这不是我的意思)。取决于上下文，不同的标准确定哈希的质量。已经有两个人提到SHA。这是一个加密哈希，对于我们可能要说的哈希表根本没有好处。

哈希表有非常不同的要求。但是，仍然很难普遍地找到一个好的哈希函数，因为不同的数据类型会公开不同的可以哈希的信息。根据经验，最好将一种类型的所有信息都考虑在内。这并不总是容易的，甚至是不可能的。出于统计的原因(并因此产生冲突)，在问题空间(即所有可能的对象)上产生良好的分布也很重要。这意味着当对100到1050之间的数字进行哈希处理时，让最高有效位在哈希表中扮演重要角色是不好的，因为对于约90％的对象，该数字将为0。让最后三个数字更重要数字确定哈希。

同样，在对字符串进行哈希处理时，重要的是要考虑所有字符，除非事先知道所有字符串的前三个字符将是相同的。考虑这些，那是浪费。

实际上，这是我建议阅读Knuth在《计算机编程艺术》第一卷中要说的内容之一。 3.另一本好书是朱丽安·沃克的《散列的艺术》。

回答

一个好的哈希函数具有以下属性：

• 在给定消息散列的情况下，攻击者在计算上无法找到另一条消息以使其散列相同，这在计算上是不可行的。
• 给定一对消息m'和m，找到两个使得h(m)= h(m')的消息在计算上是不可行的

两种情况不一样。在第一种情况下，我们要尝试查找冲突的现有哈希值。在第二种情况下，我们尝试查找任何两条冲突的消息。由于生日"悖论"，第二项任务要容易得多。

如果性能不是一个大问题，则应始终使用安全的哈希函数。通过强制哈希中的冲突可以执行非常聪明的攻击。如果从一开始就使用强壮的东西，那么我们将确保自己免受这些伤害。

不要在新设计中使用MD5或者SHA-1. 包括我在内的大多数密码学家都会认为它们已损坏。这两种设计的弱点的主要根源在于，我上面概述的第二个属性不适用于这些结构。如果攻击者可以生成两条消息m和m'，它们都散列为相同的值，则他们可以对我们使用这些消息。 SHA-1和MD5也遭受消息扩展攻击，如果我们不小心，它们可能致命地削弱应用程序。

诸如Whirpool之类的更现代的哈希是更好的选择。它不受这些消息扩展攻击的影响，并且使用与AES用于证明针对各种攻击的安全性相同的数学方法。

希望对我们有所帮助！

回答

哈希函数有两个主要目的：

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

不知道我们要使用的哈希是不可能推荐哈希的。

如果我们只是在程序中创建哈希表，则不必担心算法的可逆性或者可破解性……SHA-1或者AES对此完全没有必要，最好使用FNV的变体。 FNV比我们提到的简单质数模型具有更好的分散性(因此减少了冲突)，并且更适应于各种输入大小。

如果我们使用散列来隐藏和认证公共信息(例如对密码或者文档进行哈希处理)，则应使用由公众审查审查的主要哈希算法之一。哈希函数休息室是一个不错的起点。

回答

这是一个很好的例子，也是一个为什么你永远不想写一个的例子。
它是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-1A算法，而不是原始FVN-1算法：改进的算法可以更好地分散哈希中的最后一个字节。我相应地调整了算法。

回答

对于Paul Hsieh的这种对任何类型的数据进行"正常"哈希表查找，这是我使用过的最好的数据。

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

如果我们关心加密安全性或者其他更高级的内容，请使用YMMV。如果我们只想在哈希表查找中使用踢屁股通用哈希函数，那么这就是我们想要的。