字符串的快速哈希

Question

我有一组 ASCII 字符串，假设它们是文件路径。它们可以很短也可以很长。

我正在寻找一种可以计算此类字符串的哈希值的算法，该哈希值也是一个字符串，但长度固定，例如 youtube 视频 ID：

 https://www.youtube.com/watch?v=-F-3E8pyjFo
                                ^^^^^^^^^^^

MD5 似乎是我所需要的，但是拥有一个短的哈希字符串对我来说至关重要。

是否有可以执行此操作的 shell 命令或 python 库？

原文由 Anthony 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

我想这个问题是题外话，因为基于意见，但至少给你一个提示，我知道 FNV 哈希，因为 模拟人生 3 使用它来根据不同内容包之间的名称查找资源。他们使用 64 位版本，所以我想这足以避免在相对较大的一组参考字符串中发生冲突。 哈希很容易实现，如果没有模块满足你（ 例如 pyfasthash 有它的实现）。

要从中获取一个短字符串，我建议您使用 base64 编码。例如，这是 base64 编码的 64 位散列的大小： nsTYVQUag88= （你可以删除或填充 = ）。

_编辑_：我终于遇到了和你一样的问题，所以我实现了上面的想法： https ://gist.github.com/Cilyan/9424144

原文由 Cilyan 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

Python 有一个内置的 hash() 函数，它非常快速并且非常适合大多数用途：

 >>> hash("dfds")
3591916071403198536

然后你可以让它无符号：

 >>> hashu=lambda word: ctypes.c_uint64(hash(word)).value

然后你可以把它变成一个 16 字节的十六进制字符串：

 >>> hashu("dfds").to_bytes(8,"big").hex()

或者一个 N*2 字节的字符串，其中 N <= 8：

 >>> hashn=lambda word, N  : (hashu(word)%(2**(N*8))).to_bytes(N,"big").hex()

..ETC。如果你希望 N 大于 8 个字节，你可以只散列两次。 Python 的内置速度非常快，除非您需要安全性，否则永远不值得将 hashlib 用于任何事情……而不仅仅是抗碰撞性。

 >>> hashnbig=lambda word, N  : ((hashu(word)+2**64*hashu(word+"2"))%(2**(N*8))).to_bytes(N,"big").hex()

最后，使用 urlsafe base64 编码生成比“hex”更好的字符串

>>> hashnbigu=lambda word, N  : urlsafe_b64encode(((hashu(word)+2**64*hash(word+"2"))%(2**(N*8))).to_bytes(N,"big")).decode("utf8").rstrip("=")
>>> hashnbigu("foo",16)
'ZblnvrRqHwAy2lnvrR4HrA'

注意事项：

• 请注意，在 Python 3.3 及更高版本中，此函数是随机的，不适用于某些用例。您可以使用 PYTHONHASHSEED=0 禁用它

• 请参阅 https://github.com/flier/pyfasthash 以获取快速、稳定的哈希值，这些哈希值同样不会使非加密应用程序的 CPU 过载。

• 不要在真正的代码中使用这种 lambda 风格……写出来！在你的代码中填充诸如 2**32 之类的东西，而不是让它们成为常量是错误的形式。

• 最后，对于较小的应用程序，8 个字节的抗碰撞性是可以的……如果条目少于一百万，您的碰撞几率 < 0.0000001%。这是一个 12 字节的 b64 编码字符串。但对于更大的应用程序来说可能还不够。

• 对于缓存中的 UUID/OID 等，16 个字节就足够了。

从字节输入生成 300k 16 字节哈希的速度比较。

 builtin: 0.188
md5: 0.359
fnvhash_c: 0.113

对于复杂的输入（例如 3 个整数的元组），您必须转换为字节才能使用非内置哈希，这会增加大量转换开销，从而使内置功能大放异彩。

 builtin: 0.197
md5: 0.603
fnvhash_c: 0.284

原文由 Erik Aronesty 发布，翻译遵循 CC BY-SA 4.0 许可协议