寻找一种快速的哈希函数

Question

我正在寻找一种特殊的哈希函数。假设我有一个大字符串列表，如果我按照它们的哈希值排序，它们应该是准随机的。

最重要的是：它必须非常快速。我已经尝试过md5和sha1，但它们使用了太多的CPU资源。

碰撞不是问题。

我正在使用JavaScript，因此实现不应该太复杂。

- Julian

---

请参见以下程序相关内容：http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed - rogerdpack

Answer 1

可以看一下 Murmur 哈希。它有一个不错的空间/碰撞权衡：

http://sites.google.com/site/murmurhash/

- Nils Pipenbrinck

Answer 2

看起来你想要使用哈希表中使用的哈希函数类型，而不是用于检测重复或篡改的类型。在谷歌上搜索可获得大量关于替代哈希函数的信息。首先，避免使用加密签名哈希（如MD-5或SHA-1），因为它们解决另一个问题。你可以阅读这个、这个或者这个作为开始。请注意保留HTML标记。

- bmargulies

Answer 3

如果速度至关重要，您可以实现一个简单的临时哈希，例如取字符串的第一个和最后一个字母，并按照最后一个字母然后是第一个字母的顺序对其进行排序。结果看起来像是“准随机”的，而且速度很快。例如，按照这种方式排序的我的答案的一部分会像这样：

ca ad-hoc
el like
es simple
gt taking
hh hash
nc can
ti implement
uy you

- Tomislav Nakic-Alfirevic

---

如果哈希无法很好地避免冲突，那么在哈希过程中获得的任何速度优势都会因冲突而丧失。关键是要在两者之间找到平衡点。 - Steven Sudit

Julian在他的问题中明确表示冲突并不是一个问题，我可以理解为什么。像这样的简单哈希会提供一个非显然准随机单词顺序：如果多个单词有相同的哈希值，他可能不关心进一步对它们进行排序，并且只取它们按照原始顺序而没有任何性能损失。显然，这个特定的哈希函数不适用于所有类型的数据集，但你似乎并没有谈论到边缘情况。 - Tomislav Nakic-Alfirevic

Answer 4

Hsieh, Murmur, Bob Jenkin's 这些名字浮现在我的脑海中。
一个有关哈希函数的不错页面，其中包含一些质量测试和一个简单的 S-box 哈希函数。

- Andras Vass

---

听起来最好远离SuperFastHash。(上面的第一个链接) http://www.team5150.com/~andrew/blog/2007/03/breaking_superfasthash.html - hookenz

@Matt，基于此，您应该避免在任何答案中提到的所有哈希，因为它们不是加密哈希 - 相反，它们比例如SHA要快得多，并且 - 正如OP所要求的那样 - 可以轻松地在JS中实现。;-)。请注意加密与“标准”哈希之间的区别：http://security.stackexchange.com/questions/11839/what-is-the-difference-between-a-hash-function-and-a-cryptographic-hash-function - Andras Vass