快速字符串哈希

Question

我有一组ASCII字符串，比如文件路径。它们可能既短又很长。

我正在寻找一种算法，可以计算此类字符串的哈希值，而这个哈希值也将是一个字符串，但将具有固定长度，就像YouTube视频ID一样：

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

我似乎需要使用MD5，但关键是我需要一个短的哈希字符串。

是否有一个能够实现这一点的shell命令或python库？

- Anthony

---

除了标准的 md5 模块以外，你是指什么？（已弃用，现在可以使用 hashlib 代替） - Ricardo Cárdenes

问题更多地涉及算法而非实现。 - Anthony

对于您来说，没有碰撞有多重要？速度有多重要？与其他算法相比，MD5实际上并不是非常快也不是非常短。您可以使用生日悖论公式（请参见维基百科）计算碰撞的风险。 - Thomas Mueller

Answer 1

从 Python 3 开始，这种方法不再适用：

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字节的冲突防护足够了...... 小于一百万条目，则冲突几率小于0.0000001%。 这是一个12字节的b64编码字符串。 但是对于较大的应用程序可能不够。

• 16个字节对于缓存中的UUID / OID已经足够了。

以字节输入方式生成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

---

在Python 3中，该函数是随机的，这可能在某些情况下会成为问题。 - Tim

感谢 @Tim，根据文档：默认情况下，str、bytes 和 datetime 对象的 __hash__() 值会与一个不可预测的随机值混合（"salted"）；可以通过设置环境变量 PYTHONHASHSEED=0 来禁用随机化，从而允许一组 Python 进程共享哈希值。 - Rabash

hash('asd').to_bytes(8, 'little') 溢出错误：无法将负整数转换为无符号整数 - iperov

@iperov 最好将哈希值设为无符号。ctypes 似乎是唯一干净的方法。 - Erik Aronesty

@BorisKalinin 我来澄清一下：上面的方法很好，而且速度很快。MD5和其他加密哈希算法会消耗太多的CPU资源，这就是区别。 - Erik Aronesty

Answer 2

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

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

编辑：我最终也遇到了与您相同的问题，因此我实施了上述想法：https://gist.github.com/Cilyan/9424144

- Cilyan

---

FNV是我最喜欢的哈希算法。 - Erik Aronesty

Answer 3

另一个选择：hashids的设计目的就是解决这个问题，并已被移植到许多语言中，包括Python。它不是像MD5或SHA1那样的单向哈希；hashids的“哈希”是可逆的。

您需要使用秘密值对库进行种子处理并选择最小哈希长度。

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

我在这个答案中提供了更多细节。

- Chris

Answer 4

你可以使用sum程序（假设你在linux上），但要记住，哈希越短，可能发生的冲突就越多。你也可以截断MD5/SHA哈希值。

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

- eugecm

---

这个在这里有讲解：链接 - eugecm

Answer 5

需要记住的一点是哈希码是单向函数 - 你不能用它们来生成“视频ID”，因为你无法从哈希返回到原始路径。除此之外，哈希冲突相当普遍，你最终会得到两个哈希值都指向同一个视频而不是不同的视频。

要创建像YouTube一样的ID，最简单的方法是以可逆的方式将唯一ID（例如数据库中的自动键列）映射到唯一字符串。

例如，你可以将整数ID映射到36进制的0-9a-z...甚至是62进制的0-9a-zA-Z，如果ID本身不足以提供足够的字符，则填充生成的字符串到所需的长度。

- Tim B