什么是好的散列函数？

什么是好的 Hash 函数？我在大学的数据结构课程中看到了很多哈希函数和应用程序，但大多数时候我都明白，要想写出一个好的哈希函数是相当困难的。为了避免冲突，我的教授说:

function Hash(key)
return key mod PrimeNumber
end

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

质数与哈希表的大小相同。我知道这是一个很好的避免冲突的函数，而且速度很快，但是我怎样才能做出一个更好的函数呢？对于字符串键和数字键，是否有更好的散列函数？

179660 次浏览
小开

我得说经验法则就是不要卷自己的。尝试使用一些经过彻底测试的东西，例如 SHA-1或者类似的东西。

小开

对于通用散列(ed) ，没有“好的散列函数”这样的东西。是的，我知道有“全域哈希”这回事，但我不是这个意思)。根据上下文，不同的标准决定散列的质量。有两个人已经提到了 SHA。这是一个加密散列，对于您可能指的散列表一点也不好。

哈希表有非常不同的要求。但是，要找到一个普遍适用的散列函数仍然很困难，因为不同的数据类型公开了可以散列的不同信息。根据经验法则，最好将 所有信息等量考虑在一个类型中。这并不总是容易的，甚至不可能。出于统计学原因(因此也会发生碰撞) ，在问题空间(即所有可能的对象)上生成良好的分布也很重要。这意味着当散列100到1050之间的数字时，最有意义的数字在散列中占很大比例是不好的，因为对于大约90% 的对象，这个数字将为0。让最后三位数决定散列要重要得多。

类似地，当散列字符串时，考虑所有字符是很重要的——除非事先知道所有字符串的前三个字符是相同的; 因此考虑这些字符是一种浪费。

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

小开

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

  1. 给定一条消息的散列，攻击者在计算上不可能找到另一条消息，这样它们的散列就是相同的。

  2. 给定一对消息 m’和 m，在计算上不可能找到两个使得 h (m) = h (m’)的消息

这两个病例的 没有是一样的。在第一种情况下，有一个预先存在的散列，您试图找到一个冲突。在第二种情况下，您试图找到 任何两个相互冲突的消息。由于生日“悖论”，第二个任务要容易得多

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

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

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

希望能帮上忙！

小开

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

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

如果不知道它的用途，就不可能推荐一个 hash。

如果你只是在一个程序中创建一个哈希表，那么你就不需要担心算法的可逆性和可破解性... ... SHA-1或 AES 对此完全没有必要，你最好使用 流动噪音感应强的地方。FNV 比前面提到的一个简单的基本模块获得了更好的分散性(因此碰撞也更少) ，并且更适合于不同的输入大小。

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

小开

这是一个很好的例子，也是一个为什么你永远不想写一个例子。 这是一个 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算法: 改进的算法更好地分散散列中的最后一个字节。我相应地调整了算法。
小开
最佳答案

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

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

如果您关心加密安全或其他更高级的东西，那么 YMMV。如果您只是想要一个非常棒的通用散列函数来进行散列表查找，那么这就是您正在寻找的。

小开

你在这里说的是，你想要有一个，使用具有碰撞阻力。试试用 SHA-2。或者尝试在单向压缩功能中使用(良好的)分组密码(以前从未尝试过) ，就像 Miyaguchi-Preenel 模式下的 AES。问题是，你需要:

1)静脉注射。试着用 Khinchin 常数的前256位或者类似的东西。 2)有一个填充方案。简单。从一个像 MD5或 SHA-3(Keccak [读作‘ ket-chak’])的散列中推出它。 如果你不关心安全性(其他一些人也这么说) ，看看 Bob Jenkins 的 FNV 或者 lookup2(实际上我是第一个推荐 lookup2的人)也试试 MurmurHash，它很快(检查这个: .16 cpb)。

小开

一个好的哈希函数应该

  1. 在可能的情况下，要保持信息的客观性，尽量减少冲突
  2. 级联尽可能多和尽可能均匀，即每个输入位应翻转每个输出位的概率为0.5，没有明显的模式。
  3. 如果在加密上下文中使用，就不应该存在一种有效的方法来反转它。

素数模不满足这些点中的任何一个。这远远不够。总比没有强，但还不够快。用一个无符号整数乘以一个幂为2的模数来分配数值也是一样的，这一点都不好，但是只有大约2个 CPU 周期，它比一个素数模数所需要的15到40要快得多(是的，整数除法真的很慢)。

要创建一个快速且分布良好的散列函数，最好的选择是用质量较低的快速排列组合它，就像用于随机数生成的 PCG那样。

有用的排列方式包括:

  • 非均匀整数乘法
  • 二进制旋转
  • Xorshift

按照这个配方，我们可以创建我们自己的 散列函数或者我们采取的 分裂组合是测试和良好的接受。

如果需要加密质量，我强烈推荐使用 sha 系列的一个函数，这个函数经过了很好的测试，并且已经标准化，但出于教育目的，你可以这样做:

首先你需要一个很好的非加密散列函数，然后你应用一个类似于质数字段的求幂的单向函数，或者 k许多 (n*(n+1)/2) mod 2^k的应用程序中都有一个 xorshift，当 k是结果散列中的位数时。

小开

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

小开

不同的应用场景对哈希算法有不同的设计要求，但是一个好的哈希函数应该有以下三点:

  • 防碰撞 : 尽量避免冲突。如果很难找到散列到相同输出的两个输入，那么散列函数是防冲突的
  • 抗篡改 : 只要改变一个字节，它的哈希值就会大不相同。
  • 计算效率 : 哈希表是一种在时间消耗和空间消耗之间进行权衡的算法。

在2022年，我们可以选择 SHA-2系列在安全加密中使用，SHA-3更安全，但有更大的性能损失。一种比较安全的方法是加盐和混合加密，我们可以选择 SHA-2家族用于安全加密，SHA-3更安全，但性能损失更大。一种更安全的方法是添加 salt 并混合加密。


提交答案