我正在散列大量文件，为了避免散列冲突，我还存储了文件的原始大小 - 这样，即使存在散列冲突，文件大小也不太可能相同。这是声音（哈希冲突同样可能是任何大小），还是我需要另一条信息（如果冲突更有可能与原始信息的长度相同）。
或者，更一般地说：无论原始文件大小如何，每个文件是否都可能产生特定的哈希？
问问题
4876 次
5 回答
11
哈希函数通常被编写为在所有结果桶中均匀分布数据。
如果您假设您的文件均匀分布在固定的可用大小范围内，假设您的文件只有 1024 (2^10) 个均匀分布的不同大小。存储文件大小最多只能通过不同文件大小的数量减少冲突的机会。
注意：我们可以假设它是 2^32 均匀分布和不同的大小，它仍然不会改变其余的数学。
人们普遍认为，在 MD5（例如）上发生碰撞的一般概率是1/(2^128).
除非有专门内置在哈希函数中的东西，否则的话。给定任何有效X使得概率与任何两个随机值 { , }P(MD5(X) == MD5(X+1)) 保持相同即= =对于,和的任何值。YZP(MD5(Y) == MD5(Z))P(MD5(X) == MD5(X+1))1/(2^128)XYZ
将其与 2^10 个不同文件相结合意味着通过存储文件大小，您最多可以获得额外的 10 位，表示项目是否不同（再次假设您的文件针对所有值均匀分布）。
因此，最好的情况是为 <=N 字节的唯一值添加另一个 N 字节的存储空间（它永远不会 >N）。因此，您最好使用诸如 SHA-1/2 之类的东西来增加散列函数返回的字节数，因为与存储文件大小相比，这更有可能为您提供散列值的均匀分布数据。
简而言之，如果 MD5 不足以应对冲突，则使用更强的散列，如果更强的散列太慢，则使用冲突可能性低的快速散列，例如 MD5，然后使用较慢的散列，例如 SHA-1或 SHA256 以减少碰撞的机会，但如果 SHA256 足够快并且加倍空间不是问题，那么您可能应该使用 SHA256。
于 2013-03-07T12:18:22.467 回答
6
取决于您的散列函数，但一般来说，大小相同但内容不同的文件不太可能产生与大小不同的文件相同的散列。尽管如此，与您自己的解决方案（如存储文件大小）相比，简单地使用具有更大空间的经过时间考验的哈希（例如，MD5 代替 CRC32，或 SHA1 代替 MD5）可能会更干净。
于 2010-03-14T15:39:00.560 回答
2
散列函数被设计成很难发生碰撞的方式，否则它们将不起作用。
如果您有绝对令人难以置信的哈希冲突1 : number_of_possible_hashes 概率，这与文件大小无关。
如果您真的想对哈希冲突进行双重确定，您可以为同一个文件计算两个不同的哈希 - 这比保存哈希 + 文件大小更不容易出错。
于 2010-03-14T15:39:40.483 回答
2
无论原始数据的大小如何，散列的大小都是相同的。由于可能的哈希值数量有限，理论上两个不同大小的文件可能具有相同的哈希值。但是，这意味着两个大小相同的文件也可能具有相同的哈希值。
于 2010-03-14T15:41:43.510 回答
0
密码散列系列（MD5、SHA-x 等）的全部意义在于使冲突几乎不可能消失。这个概念是，官方法律程序准备依赖于故意制造碰撞是不切实际的。所以，真的，在这些哈希的吊带上添加一条腰带是对空间和 CPU 时间的不好利用。
于 2010-03-14T19:14:05.477 回答