在Python中生成最短哈希以命名缓存文件
在Python中，最短的哈希值（可以用在文件名中的形式，比如十六进制字符串）是什么？我的应用程序想要为一些对象保存缓存文件。这些对象必须有唯一的表示形式（repr()），所以我想用它来“生成”文件名。我希望为每个对象生成一个可能唯一的文件名（数量不多）。这些文件名不应该重复，但如果重复了，我的应用程序就会缺少该对象的缓存（需要重新索引该对象的数据，这对应用程序来说成本很小）。
所以，如果出现一次重复，我们就会丢失一个缓存文件，但缓存所有对象所节省的时间会让应用程序启动更快，所以这并不太重要。
现在我实际上在使用abs(hash(repr(obj)))；没错，就是字符串哈希！到目前为止还没有发现任何重复，但我想要一个更好的哈希函数。Python库中有hashlib.md5，但如果把它的十六进制字符串放在文件名里就太长了。有其他选择吗，能合理抵抗重复的？
编辑：使用案例是这样的：数据加载器获取一个新的数据承载对象实例。唯一类型有唯一的表示形式，所以如果存在hash(repr(obj))的缓存文件，我就会解压这个缓存文件，并用解压后的对象替换obj。如果出现了重复，缓存是错误匹配，我会注意到。因此，如果我们没有缓存或者有错误匹配，我就会重新初始化obj（重新加载它的数据）。
结论（？）
Python中的str哈希可能已经足够好了，我只是担心它的重复抵抗能力。但如果我能用它哈希2**16个对象，那就绝对足够了。
我发现了如何将十六进制哈希（来自任何哈希源）以紧凑的方式存储为base64：
# 'h' is a string of hex digits
bytes = "".join(chr(int(h[i:i+2], 16)) for i in xrange(0, len(h), 2))
hashstr = base64.urlsafe_b64encode(bytes).rstrip("=")
8 个回答
你可以通过简单地截断哈希值来让它变得更短。比如，md5哈希总是32个十六进制数字，但你可以从中任意取一部分（或者其他哈希值），这部分依然具备哈希的特点：相同的输入会产生相同的哈希值，而且这些值分布得很广。
内置的字符串哈希函数碰撞率很低，而且结果也比较短。它有 2**32 种可能的值，所以你遇到碰撞的可能性相对较小（如果你使用它的绝对值，那它只有 2**31 种可能的值）。
你一直在寻找最短的哈希函数。那肯定是
def hash(s):
return 0
不过我想你并不是这个意思...
所谓的生日悖论，简单来说就是：如果你有一个好的哈希函数，预计在发生碰撞之前，你需要计算的哈希值数量大约是不同值数量的平方根，也就是sqrt(N)。这里的N是哈希函数可以产生的不同值的数量。举个例子，如果你想用不超过32位的哈希值，当对象数量达到大约64K（也就是2**16个对象）时，你就要开始担心碰撞的问题了，因为这是2**32个不同值的平方根。你预计会有多少个对象呢？
既然你提到碰撞只是个小麻烦，我建议你选择的哈希长度大约是你预计对象数量的平方，或者稍微少一点，但不要少得太多。
你想要生成一个文件名，这个文件系统是区分大小写的吗？在Unix系统上通常是区分大小写的，还是说你也需要考虑不区分大小写的系统？这个很重要，因为你想要短文件名，但在区分和不区分大小写的系统中，每个字符可以用来表示哈希的位数差别很大。
在区分大小写的系统中，你可以使用标准库的base64模块（我推荐使用“安全URL”版本的编码，也就是这个函数，因为在Unix文件名中避免使用可能出现的'/'字符是很重要的）。这样你每个字符可以使用6个位，比十六进制的4位要好得多。
即使在不区分大小写的系统中，你也可以比十六进制更好——使用base64.b32encode，每个字符可以得到5个位。
这些函数处理的是字符串；如果你选择的哈希函数生成的是数字，可以使用struct模块将数字转换成字符串。
如果你有几万个对象，我认为使用内置的哈希函数就足够了（32位，所以根据你选择的编码，哈希值大约是6到7个字符）。如果对象数量达到一百万，你可能需要大约40位（7或8个字符）——你可以将sha256的结果折叠（使用异或，不要截断；-)）到一个合理的位数，比如128位，然后使用%运算符进一步裁剪到你想要的长度再进行编码。