python中可用的最短哈希(文件名可用形式,如hexdigest)是什么？我的应用程序想要保存某些对象的缓存文件.对象必须具有唯一的repr(),因此它们用于"种子"文件名.我想为每个对象生成一个可能唯一的文件名(不是那么多).它们不应该发生冲突,但是如果它们发生了我的应用程序将只是缺少该对象的缓存(并且必须重新索引该对象的数据,这是应用程序的一个小成本).
因此,如果存在一个冲突,我们会丢失一个缓存文件,但是收集的缓存所有对象的节省使得应用程序启动速度更快,因此无关紧要.
现在我实际上正在使用abs(hash(repr(obj))); 那是对的,字符串哈希!还没有找到任何碰撞,但我希望有更好的哈希函数.hashlib.md5在python库中可用,但如果放入文件名,则hexdigest非常长.替代方案,具有合理的抗冲击性？
编辑:用例是这样的:数据加载器获取数据携带对象的新实例.独特的类型有独特的repr.因此,如果存在缓存文件hash(repr(obj)),我将取消该缓存文件并将obj替换为unpickled对象.如果发生碰撞并且缓存是假匹配,我注意到.因此,如果我们没有缓存或具有错误匹配,我改为初始化obj(重新加载其数据).
结论(？)
strpython中的哈希可能已经足够好了,我只担心它的碰撞阻力.但是如果我可以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("=")
Ale*_*lli 37
的生日悖论适用:给出了良好的散列函数,在碰撞发生前散列的预期数量为约SQRT(N),其中N是哈希函数可以取不同的值的数目.(我指出的维基百科条目给出了确切的公式).因此,例如,如果你想使用不超过32位,你的碰撞担心对于大约64K对象(即2**16对象 - 2**32你的散列函数可以采用的不同值的平方根)是非常严重的.你期望有多少个物体,如一个数量级？
既然你提到碰撞是一个轻微的烦恼,我建议你的目标是一个哈希长度大致是你将拥有的对象数量的平方,或者稍微少一点但不比那个少.
你想创建一个文件名 - 就像区分大小写的文件系统一样,在Unix上是典型的,或者你是否也必须满足不区分大小写的系统？这很重要,因为你的目标是短文件名,但是你可以用来表示你的哈希作为文件名的每个字符的位数在区分大小和不敏感的系统上发生了显着变化.
在区分大小写的系统上,您可以使用标准库的base64模块(我推荐编码的"urlsafe"版本,即此函数,因为在Unix文件名中,避免可能存在于普通base64中的'/'字符很重要).这为每个字符提供了6个可用位,比十六进制中的4位/字符要好得多.
即使在不区分大小写的系统上,您仍然可以比hex更好 - 使用base64.b32encode并获得每个字符5位.
这些函数接受并返回字符串; struct如果您选择的哈希函数生成数字,则使用该模块将数字转换为字符串.
如果你确实有几万个对象,我认为你可以使用内置哈希(32位,所以6-7个字符取决于你选择的编码).对于一百万个对象,你需要40位左右(7或8个字符) - 你可以折叠(xor,不要截断;-) sha256到一个长的,有一个合理的位数,比如128左右,并%在编码之前使用操作员将其进一步切割到所需的长度.
Mar*_*wis 26
字符串的内置哈希函数是相当无冲突的,也很短.它有2**32值,所以你不太可能遇到碰撞(如果你使用它的abs值,它只有2**31值).
你一直在要求最短的哈希函数.那当然是
def hash(s):
return 0
但我猜你并不是那么真的意思......