短的Python字母数字哈希，冲突最小

Question

我想给一个表设置非整数的主键，打算用某种哈希函数。md5() 这个函数生成的结果好像太长了，有32个字符。

有没有其他的哈希函数，可以用字母和数字，生成的字符串长度可能更短，而且碰撞率（也就是不同的输入产生相同的输出的概率）比较低呢？

谢谢！

Answer 1

下面是一个解决方案，它使用字母和数字，还有一些标点符号。这个方法返回的字符串非常短，大约只有8个字符。

import binascii, struct

def myhash(s):
    return binascii.b2a_base64(struct.pack('i', hash(s)))

Answer 2

我知道的最小的内置哈希函数是md5。

>>> import hashlib, base64
>>> d=hashlib.md5(b"hello worlds").digest(); d=base64.b64encode(d); 
>>> print(d)

b'S27ylES0wiLdFAGdUpFgCQ=='

低碰撞率和短长度这两个特性有点矛盾，这和生日悖论有关。

为了让它在网址中安全使用，你需要用到base64模块里的一个函数。

>>> import base64
>>> base64.urlsafe_b64encode(hashlib.md5("hello world").digest())
'XrY7u-Ae7tCTyyK7j1rNww=='

不过，把16字节的md5摘要以二进制形式存储在数据库里应该没有问题。

>>> md5bytes=hashlib.md5("hello world").digest()
>>> len(md5bytes)
16
>>> urllib.quote_plus(md5bytes)
'%5E%B6%3B%BB%E0%1E%EE%D0%93%CB%22%BB%8FZ%CD%C3'

Python 2

>>> base64.urlsafe_b64encode(md5bytes)
'XrY7u-Ae7tCTyyK7j1rNww=='

Python 3

>>> base64.urlsafe_b64encode(md5bytes).decode('ascii')
'XrY7u-Ae7tCTyyK7j1rNww=='

你可以选择使用quote_plus或者urlsafe_b64encode来处理你的网址，然后在查找数据库之前，用对应的函数unquote_plus或urlsafe_b64decode进行解码。

Answer 3

为什么不直接截断SHA1或MD5呢？这样做会增加碰撞的可能性，但总比自己设计一个要好。值得注意的是，你可以把截断后的哈希值用base64编码，而不是用十六进制表示。例如：

import base64
import hashlib
hasher = hashlib.sha1("The quick brown fox")
base64.urlsafe_b64encode(hasher.digest()[:10])

你可以根据自己的需要截断，想截多少就截多少，或者根本不截，只要你明白这样做的利弊。

补充一下：既然你提到要安全的URL，你可以使用 urlsafe_b64encode 和 urlsafe_b64decode，它们使用 - 和 _ 来代替 + 和 /。