代码之家 › 专栏 › 技术社区 › jthg

可交换的、基于累加器的函数,用于计算多个哈希的摘要

hash

jthg · 技术社区 · 15 年前

我正在写一些东西,通过散列文件内容的样本来总结文件系统中的文件。它构建了一个目录树和文件树。每个文件条目都有文件内容的哈希。对于每个目录条目,我希望存储目录中所有文件的内容的哈希,包括子目录中的文件-我将称之为目录内容哈希。

关于目录内容哈希的棘手之处在于,我希望它独立于目录的结构。即,如果两个目录包含相同的文件,但以不同的子目录结构组织,则哈希值应相同。

我能想到的只有两种方法:

计算所有文件内容哈希的串联MD5。为了获得所需的散列属性,我必须列出目录中的所有文件,按它们的散列进行排序,连接已排序的散列,然后在连接上运行MD5。这似乎比我想的要慢。在计算整个树中的目录内容哈希时,我可以通过使用merge-sort非常有效地进行排序,但是我无法避免在大型输入上计算大量MD5哈希。

如果有一个函数可以像方法#2中使用异或那样使用,但更具抗冲突性,那就更好了。我认为方法#1对于这个特定的案例来说足够快,但是为了探索所有的选择/智力好奇心/未来的应用,我想知道是否有一个函数满足标题中的描述(我有一个模糊的记忆,在过去有好几次想要这样的函数)。

谢谢。

3 回复 | 直到 15 年前

Slartibartfast 15 年前

散列集合的顺序独立散列(基本上就是您要找的,不是吗?)

听起来任何顺序无关的操作(如加法或乘法)都能帮到你。加法的好处是可以很好地溢出。我不记得乘法是否也能起作用。

Dan D. 11 年前

因为物品的数量很重要,但顺序不重要;只需对散列列表排序,然后对列表进行散列。

find . -print0 | xargs -0 sha1sum | cut -c -40 | sort | sha1sum

这将给出哈希值的类型,它对目录排列是不变的。

Theodore Hong 11 年前

如果你有GoogleGuava可用,它提供了一个实用方法Hashing.combinedUnordered(),可以满足你的需要(在内部,这是通过将所有哈希值相加来实现的。)

https://code.google.com/p/guava-libraries/wiki/HashingExplained

Erotemic 4 年前

我发现这篇文章: https://kevinventullo.com/2018/12/24/hashing-unordered-sets-how-far-will-cleverness-take-you/

虽然有几种有文档记录的方法来定义散列函数用于迭代顺序为当然,围绕最佳实践的讨论似乎较少用于为无序容器定义哈希函数。一个明显的方法是简单地对{(+)}或xor{(\oplus)}的哈希值求和容器的单个元素。这些方法的缺点存在散列为0的问题元素;当这样的时候元素被插入到任何容器中,容器散列将性质是加法还是异或,那哈希的选择就更聪明了无序容器上的函数可以避免这种情况。事实上,在在文章的结尾,我们用数学的方法证明了一个命题容器,可以基于现有的因为它具有相同的代数结构,特别是同样的问题元素。