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

使用哈希跟踪文件的唯一版本

collision-detection hash

SqlRyan · 技术社区 · 15 年前

我将跟踪可能数百万个不同文件的不同版本,我的目的是散列它们,以确定我已经看到了该文件的特定版本。目前,我只使用MD5(该产品仍在开发中,所以它还没有处理数百万个文件),显然它不够长,无法避免冲突。

不过,这是我的问题- 如果我使用两种不同的方法散列文件并同时存储散列(例如,sha1和md5),或者如果我选择一个更长的散列(如sha256)并单独依赖它,我是否更有可能避免冲突? 我知道选项1有288个散列位,选项2只有256个散列位,但假设我的两个选项的总散列长度相同。

由于我正在处理可能数百万个文件(以及随着时间推移这些文件的多个版本),所以我想尽我所能避免冲突。然而,CPU时间并不是完全免费的,所以我对社区对这种权衡的看法很感兴趣——按比例增加散列中的位,计算起来更昂贵,与给定相同数量的单个、更长散列相比,多个不同散列有什么优势吗?两种解决方案中的位?

2 回复 | 直到 15 年前

mrjoltcola 15 年前

对于文件版本跟踪,我认为不同文件之间的冲突不是一个问题。对于每个文件,您都使用散列来确定该文件是否更改,并且只更改了该文件。该文件的哈希是否与另一个文件冲突无关,不是吗?

编辑:您正在应用哈希作为优化,以避免将每个新文件与数百万个现有文件进行比较。冲突不是避免使用快速哈希的原因。只需通过存储文件的新版本来处理冲突情况(如果发生)。这两个哈希方案都将提供优化。为什么对可能不会发生的事情过度优化。如果你有一个超快速的散列,它将在1000000中碰撞1。这对加密不好,但对版本控制来说是好的。

即使在使用guid时,系统也会检测并处理冲突。系统不需要为统计上永远不会发生的事情进行优化。

Joey Adams 15 年前

我已经考虑并处理了很多这个问题,我建议使用sha256来保持安全(它比较慢,但是CPU仍然应该能够跟上)。我不知道这是否会显著削弱散列强度,但是您可能希望将散列包在16MB块中(例如),然后在末尾散列散列,这样您就可以并行处理。

我学到的一个教训就是,处理大量的文件和散列操作:一次将数百万条记录添加到PostgreSQL数据库中并不太快。当我编写一个程序来散列一百万个文件并将它们存储在PostgreSQL数据库中时,数据库常常是瓶颈。我没有尝试过MySQL,但我推测它大致相同。由于没有客户机/服务器开销,SQLite可能更快。我建议先试试sqlite。可能太慢了。

另外,如果您将一百万个文件按哈希存储到一个目录中,并丢失索引文件,那么很难找到这些东西:)