关于算法：什么是好的哈希函数？

What is a good Hash Function?

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

1
2
3

function Hash(key)
return key mod PrimeNumber
end

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

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

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

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

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

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

基本上可以对任何类型的数据执行"正常"哈希表查找-Paul Hsieh的这是我用过的最好的数据。

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

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

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

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

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

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

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

这是一个很好的例子，也是一个为什么你永远不想写一个的例子。
它是Fowler / Noll / Vo(FNV)哈希，它既是计算机科学的天才，又是纯巫毒的一部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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算法：改进的算法可以更好地分散哈希中的最后一个字节。我相应地调整了算法。

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

您在这里所说的是要使用一种具有抗碰撞性的产品。尝试使用SHA-2。或者尝试以一种单向压缩功能(以前从未尝试过)使用(好的)分组密码，就像宫口Preenel模式下的AES一样。问题在于您需要：

1)进行静脉注射。尝试使用Khinchin常数的小数部分的前256位或类似内容。
2)有一个填充方案。简单。使用MD5或SHA-3(Keccak [发音为'ket-chak'])之类的哈希值来对其进行Barrow操作。
如果您不关心安全性(其他一些人这样说)，请查看Bob Jenkins的FNV或lookup2(实际上，我是第一个推荐lookup2的人)。还可以尝试MurmurHash，速度很快(请检查：.16 cpb) )。

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

给定消息的哈希值，攻击者在计算上无法找到另一条消息以使它们的哈希值相同，这在计算上是不可行的。

给定一对消息m'和m，找到两个使得h(m)= h(m')的消息在计算上是不可行的

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

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

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

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

希望有帮助！