字符串的快速哈希

新手上路,请多包涵

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

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

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

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

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

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

阅读 852
2 个回答

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

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

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

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

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 许可协议

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题