23

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

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

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

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

是否有可以做到这一点的 shell 命令或 python 库？

4

5 回答 5

14

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 个字节就足够了。

于 2018-05-29T19:41:08.063 回答
11

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

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

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

于 2014-02-24T22:17:11.503 回答
4

另一种选择：hashids旨在解决这个问题，并已移植到许多语言，包括 Python。它不是真正意义上的 MD5 或 SHA1 哈希，它们是单向的；hashids“哈希”是可逆的。

您负责使用秘密值播种库并选择最小哈希长度。

完成后，该库可以在整数（单个整数，如简单的主键或整数列表，以支持复合键和分片等内容）和配置长度（或稍长）的字符串之间进行双向映射. 用于生成“哈希”的字母表是完全可配置的。

我在其他答案中提供了更多详细信息。

于 2014-02-27T13:41:54.077 回答
1

您可以使用该sum程序（假设您使用的是 linux），但请记住，哈希越短，您可能遇到的冲突就越多。您也可以随时截断 MD5/SHA 哈希。

编辑：这是哈希函数列表：哈希函数列表

于 2014-02-24T22:05:39.573 回答
0

需要记住的是，哈希码是一种单向函数 - 您不能将它们用于“视频 ID”，因为您无法从哈希返回到原始路径。除了其他任何事情之外，很可能会发生哈希冲突，并且您最终会得到两个哈希都指向同一个视频而不是不同的视频。

要创建像 youtube 这样的 ID，最简单的方法是创建一个唯一 ID，但是您通常会这样做（例如数据库中的自动键列），然后以可逆方式将其映射到唯一字符串。

例如，您可以获取一个整数 id 并将其映射到以 36 为基数的 0-9a-z ......甚至以 62 为基数的 0-9a-zA-Z ，如果其上的 id 将生成的字符串填充到所需的长度own 没有给出足够的字符。

于 2014-02-24T22:11:24.260 回答