小编典典

python中最短的哈希值,用于命名缓存文件

python

python中可用的最短哈希(以文件名可用形式,如hexdigest)是什么?我的应用程序想要为某些对象保存 缓存文件
。这些对象必须具有唯一的repr(),以便用于“播种”文件名。我想为每个对象(可能不多)生成一个可能唯一的文件名。它们不应发生冲突,但是如果这样做,我的应用程序将仅缺少该对象的缓存(并且将不得不重新索引该对象的数据,这对应用程序来说是很小的开销)。

因此,如果发生一次冲突,我们将丢失一个缓存文件,但这是缓存所有对象的缓存节省使应用程序启动快得多,因此没关系。

现在我实际上正在使用abs(hash(repr(obj)));
是的,字符串哈希!尚未发现任何冲突,但我想拥有一个更好的哈希函数。hashlib.md5在python库中可用,但如果放入文件名,则hexdigest确实很长。具有合理的耐碰撞性的替代品?

编辑:用例是这样的:数据加载器获取数据承载对象的新实例。唯一类型具有唯一代表。因此,如果hash(repr(obj))存在用于的缓存文件,我将解开该缓存文件并将obj替换为未选取的对象。如果发生冲突,并且缓存是错误的匹配,我会注意到。因此,如果我们没有缓存或错误匹配,则改为初始化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("=")

阅读 282

收藏
2021-01-20

共1个答案

小编典典

生日悖论适用:给出了良好的散列函数,在碰撞发生前散列的预期数量为约SQRT(N),其中N是哈希函数可以取不同的值的数目。(我指向的维基百科条目给出了确切的公式)。因此,例如,如果您希望使用不超过32位,则对于大约64K个对象(即,2**16对象-2**32哈希函数可以采用的不同值的平方根),您的冲突担忧非常严重。您期望有几个对象(数量级)?

既然您提到碰撞是一个小麻烦,所以我建议您将哈希长度的目标设定为大约要拥有的对象数的平方,或者少一些,但不要少很多。

您想创建一个文件名-
是区分大小写的文件系统上的文件名(如Unix上的典型文件名),还是必须兼顾不区分大小写的系统?这很重要,因为您的目标是短文件名,但是在区分大小写的系统和不敏感的系统上,可以用来表示哈希作为文件名的每个字符的位数发生了巨大变化。

在区分大小写的系统上,您可以使用标准库的base64模块(我建议使用编码的“
urlsafe”版本,即函数,因为避免在普通的base64中出现“
/”字符在Unix文件名中很重要)。这样每个字符有6个可用位,比十六进制的4位/字符好得多。

即使在不区分大小写的系统上,您仍然可以比十六进制做得更好-使用base64.b32encode并获得每个字符5位。

这些函数接受并返回字符串。struct如果您选择的哈希函数生成数字,请使用模块将数字转换为字符串。

如果确实有成千上万个对象,我想您可以使用内置的哈希(32位,所以6-7个字符取决于您选择的编码)就可以了。对于一百万个对象,您需要40位左右(7或8个字符)-您可以将sha256折叠(异或,不要截断;-)以合理的位数(例如128左右)将sha256折叠到很长的长度,并%在编码之前使用运算符将其进一步切成所需的长度。

2021-01-20