字符串的快速哈希

Question

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

我正在寻找一种可以计算此类字符串的哈希的算法，该哈希也将是字符串，但具有固定的长度，例如youtube video id：

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

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

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

Answer 1

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

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

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

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()

..等等。如果你想让 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 个字节的抗碰撞性是可以的……如果条目少于 100 万，则碰撞几率小于 0.0000001%。这是一个 12 字节的 b64 编码字符串。但对于较大的应用程序来说，这可能还不够。

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