python中可用的最短哈希(以文件名可用形式,如hexdigest)是什么?我的应用程序想要为某些对象保存 缓存文件 。这些对象必须具有唯一的repr(),以便用于“播种”文件名。我想为每个对象(可能不多)生成一个可能唯一的文件名。它们不应发生冲突,但是如果这样做,我的应用程序将仅缺少该对象的缓存(并且将不得不重新索引该对象的数据,这对应用程序来说是很小的开销)。
因此,如果发生一次冲突,我们将丢失一个缓存文件,但这是缓存所有对象的缓存节省使应用程序启动快得多,因此没关系。
现在我实际上正在使用abs(hash(repr(obj))); 是的,字符串哈希!尚未发现任何冲突,但我想拥有一个更好的哈希函数。hashlib.md5在python库中可用,但如果放入文件名,则hexdigest确实很长。具有合理的耐碰撞性的替代品?
编辑:用例是这样的:数据加载器获取数据承载对象的新实例。唯一类型具有唯一代表。因此,如果hash(repr(obj))存在用于的缓存文件,我将解开该缓存文件并将obj替换为未选取的对象。如果发生冲突,并且缓存是错误的匹配,我会注意到。因此,如果我们没有缓存或错误匹配,则改为初始化obj(重新加载其数据)。
hash(repr(obj))
结论(?)
strpython中的哈希值可能足够好,我只担心它的抗碰撞性。但是,如果我可以2**16用它来哈希对象,那就足够了。
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("=")
的生日悖论适用:给出了良好的散列函数,在碰撞发生前散列的预期数量为约SQRT(N),其中N是哈希函数可以取不同的值的数目。(我指向的维基百科条目给出了确切的公式)。因此,例如,如果您希望使用不超过32位,则对于大约64K个对象(即,2**16对象-2**32哈希函数可以采用的不同值的平方根),您的冲突担忧非常严重。您期望有几个对象(数量级)?
2**32
既然您提到碰撞是一个小麻烦,所以我建议您将哈希长度的目标设定为大约要拥有的对象数的平方,或者少一些,但不要少很多。
您想创建一个文件名- 是区分大小写的文件系统上的文件名(如Unix上的典型文件名),还是必须兼顾不区分大小写的系统?这很重要,因为您的目标是短文件名,但是在区分大小写的系统和不敏感的系统上,可以用来表示哈希作为文件名的每个字符的位数发生了巨大变化。
在区分大小写的系统上,您可以使用标准库的base64模块(我建议使用编码的“ urlsafe”版本,即此函数,因为避免在普通的base64中出现“ /”字符在Unix文件名中很重要)。这样每个字符有6个可用位,比十六进制的4位/字符好得多。
base64
即使在不区分大小写的系统上,您仍然可以比十六进制做得更好-使用base64.b32encode并获得每个字符5位。
这些函数接受并返回字符串。struct如果您选择的哈希函数生成数字,请使用模块将数字转换为字符串。
struct
如果确实有成千上万个对象,我想您可以使用内置的哈希(32位,所以6-7个字符取决于您选择的编码)就可以了。对于一百万个对象,您需要40位左右(7或8个字符)-您可以将sha256折叠(异或,不要截断;-)以合理的位数(例如128左右)将sha256折叠到很长的长度,并%在编码之前使用运算符将其进一步切成所需的长度。
%