143

什么是好的哈希函数？我在大学的数据结构课程中看到了很多散列函数和应用程序，但我大多都知道要制作一个好的散列函数非常困难。作为避免碰撞的经验法则，我的教授说：

function Hash(key)
  return key mod PrimeNumber
end

（mod 是 C 和类似语言中的 % 运算符）

以素数为哈希表的大小。我知道这是一种避免碰撞和快速的功能，但我怎样才能做出更好的功能呢？对于数字键，字符串键是否有更好的哈希函数？

4

9 回答 9

53

对于通用散列，没有“好的散列函数”之类的东西（编辑。是的，我知道有“通用散列”之类的东西，但这不是我的意思）。根据上下文不同的标准确定散列的质量。两个人已经提到了SHA。这是一个加密哈希，它对您可能的意思的哈希表一点也不好。

哈希表有非常不同的要求。但是，要普遍找到一个好的散列函数仍然很困难，因为不同的数据类型暴露了不同的可以散列的信息。作为一个经验法则，最好考虑一个类型所拥有的所有信息。这并不总是容易的，甚至是不可能的。出于统计原因（以及因此的冲突），在问题空间（即所有可能的对象）上产生良好的分布也很重要。这意味着当散列 100 到 1050 之间的数字时，让最重要的数字在散列中发挥重要作用是不好的，因为对于大约 90% 的对象，这个数字将是 0。让最后三个数字更重要数字确定哈希。

同样，在对字符串进行散列处理时，考虑所有字符也很重要——除非事先知道所有字符串的前三个字符都相同；考虑到这些是一种浪费。

这实际上是我建议阅读 Knuth 在The Art of Computer Programming卷中所说的内容之一。3. 另一本好书是 Julienne Walker 的The Art of Hashing。

于 2008-08-29T16:31:53.830 回答
39

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

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

如果您关心加密安全或更高级的东西，那么 YMMV。如果您只是想要一个用于哈希表查找的通用哈希函数，那么这就是您要寻找的。

于 2009-04-14T08:13:55.077 回答
10

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

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

在不知道您使用它的目的的情况下推荐哈希是不可能的。

如果您只是在程序中制作哈希表，那么您无需担心算法的可逆性或可破解性... SHA-1 或 AES 对此完全没有必要，您最好使用FNV的一种变体。与您提到的简单素数模型相比，FNV 实现了更好的分散（因此更少的碰撞），并且它更适应不同的输入大小。

如果您使用散列来隐藏和验证公共信息（例如散列密码或文档），那么您应该使用经过公众审查的主要散列算法之一。哈希函数休息室是一个很好的起点。

于 2008-10-25T14:26:08.283 回答
7

这是一个很好的例子，也是一个你永远不想写的例子。它是 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 算法：改进后的算法更好地分散散列中的最后一个字节。我相应地调整了算法。
于 2009-03-09T15:06:49.080 回答
4

我想说，主要的经验法则是不要自己动手。尝试使用经过彻底测试的东西，例如 SHA-1 或类似的东西。

于 2008-08-29T16:20:05.467 回答
1

一个好的散列函数具有以下属性：

  1. 给定消息的哈希值，攻击者在计算上不可能找到另一条消息，使得它们的哈希值相同。

  2. 给定一对消息 m' 和 m，要找到两个满足 h(m) = h(m') 的消息在计算上是不可行的

这两种情况并不相同。在第一种情况下，有一个预先存在的哈希，您正试图为其查找冲突。在第二种情况下，您试图找到任何两条发生冲突的消息。由于生日“悖论”，第二个任务要容易得多。

在性能不是那么大的问题的情况下，您应该始终使用安全的散列函数。可以通过强制哈希中的冲突来执行非常聪明的攻击。如果你从一开始就使用强大的东西，你会保护自己免受这些伤害。

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

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

希望有帮助！

于 2008-08-29T16:41:57.927 回答
1

你在这里说的是你想要一个使用具有抗碰撞性的东西。尝试使用 SHA-2。或者尝试以单向压缩功能（以前从未尝试过）使用（良好的）分组密码，例如 Miyaguchi-Preenel 模式中的 AES。问题是你需要：

1）有一个IV。尝试使用 Khinchin 常数小数部分的前 256 位或类似的东西。2）有一个填充方案。简单的。从像 MD5 或 SHA-3（Keccak [发音为 'ket-chak']）这样的哈希中取出它。如果您不关心安全性（其他一些人这么说），请查看 Bob Jenkins 的 FNV 或 lookup2（实际上我是第一个推荐 lookup2 的人）也可以尝试 MurmurHash，它很快（检查这个：.16 cpb ）。

于 2013-05-06T00:41:44.997 回答
1

一个好的散列函数应该

  1. 在可能的情况下，双射以不丢失信息，并具有最少的冲突
  2. 尽可能多且均匀地级联，即每个输入位应该以 0.5 的概率翻转每个输出位并且没有明显的模式。
  3. 如果在加密上下文中使用，则不应该存在一种有效的方法来反转它。

素数模不满足任何这些点。这根本不够。它通常总比没有好，但它甚至不快。乘以一个无符号整数并取一个二次方模数也可以很好地分配值，这根本不是很好，但是只有大约 2 个 cpu 周期，它比素数模数需要的 15 到 40 快得多（是的整数除法真的很慢）。

要创建一个快速并能很好地分配值的哈希函数，最好的选择是从具有较低质量的快速排列组合它，就像他们使用PCG生成随机数时所做的那样。

有用的排列包括：

  • 与不均​​匀整数相乘
  • 二进制旋转
  • 异或移位

按照这个秘诀，我们可以创建自己的哈希函数，或者我们采用经过测试并被广泛接受的splitmix 。

如果需要加密质量，我强烈建议使用 sha 系列的功能，该功能经过良好测试和标准化，但出于教育目的，您可以这样做：

首先，您采用一个良好的非加密散列函数，然后应用单向函数，例如对素数字段求幂，或者在结果散列中的位数为时穿插 xorshiftk的许多应用。(n*(n+1)/2) mod 2^kk

于 2020-09-16T19:53:47.647 回答
0

我强烈推荐 SMhasher GitHub 项目https://github.com/rurban/smhasher，它是哈希函数的测试套件。此处列出了没有已知质量问题的最快的最先进的非加密哈希函数：https ://github.com/rurban/smhasher#summary 。

于 2021-11-14T15:05:36.513 回答