HashCode与SHA-1

Question

我想比较一些代表树的大型对象并缓存一些东西,以避免每次新对象与已存在的对象进行比较...

问题是什么是最好的东西？(性能和碰撞之间的妥协......).

一方面,我有一个基于各种字段值的常规hashCode函数(遵循有效Java的第3章.但是我无法评估这种方法所带来的潜在冲突.

另一方面,我使用带有SHA-1算法的标准java发行版的MessageDigest方法.我认为它不会有效但我可能会减少碰撞.我对吗 ？在我的背景下它是一个正确的解决方案还是我完全错了？

问题是我不知道对象的大小.另请注意,计算的值不会在HashTable中使用.

谢谢...

Answer 1

请参阅以下内容:

• http://www.javapractices.com/topic/TopicAction.do?Id=28
• https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#hashCode--
• http://www.ibm.com/developerworks/java/library/j-jtp05273.html

请记住以下内容:

• 对象可能不相等,但具有相同的哈希码
• 您的碰撞潜力取决于您遇到的物体数量.
• 哈希代码的有用性取决于您实现检查的方式

通常,您可以根据预期对象的数量和可能的哈希值(最大哈希值)来确定冲突的可能性.有关详细说明,请参见http://en.wikipedia.org/wiki/Birthday_paradox.

亲身？Java对象(实例化类)<10,000？哈希码.代表文件/ blob /大量数据？SHA-1.我在数据库中使用SHA-1哈希来阻止人们多次在同一个文件上进行ETL工作.然后我再次在第二级使用SHA-1哈希,以防止人们在多个文件中ETL相同的部分(例如,不同的文件,但相同的顺序显示两次).

Answer 2

我个人会用hashCode()这些对象,直到它被证明任何可能的碰撞是一个实际问题,以避免先发制人地优化你可能实际上没有的问题.

Answer 3

由于生日问题,碰撞的可能性取决于您使用的物品数量.

SHA-1的160位空间非常大,我怀疑你有足够的物品来看碰撞.

在hashCode()您拥有超过50,000个项目之前,32位空间不应该有大量冲突.但是,这取决于使用良好的哈希算法.

为了应用像SHA-1这样的加密摘要,您需要将图形转换为字符串,这可能是计算上昂贵的,并且可能很复杂.

Answer 4

通常对于重复文件/数据检测,MD5是速度和碰撞机会之间的良好折衷.MD5是不合适的,如果有人可能故意制作文件来欺骗你的程序(它有点容易受到碰撞攻击).但如果你只是偶然担心碰撞,那么它的128位宽度目前几乎总是足够的.

SHA-1和SHA-256为您提供了一些防止故意碰撞攻击的保护(理论上但是没有实际的SHA-1攻击;对于键入数据,它很少值得进入160位散列码宽度).SHA-1的速度大约是MD5的一半.

当然,如果你使用MD5,性能可能不应该是一个太大的问题.但显然这取决于数据的大小.您可能对我在Java中提供有关安全散列函数性能的一些信息感兴趣.

如果你确实需要更快的东西并且你只处理几百万项数据,那么另一个需要考虑的选择是由Numerical Recipes的作者提出的64位散列算法.

Java的标准hashCode()实现(比方说,String)可能不合适:除了有关哈希质量的任何问题外,它的32位宽度意味着你只能在16,000个左右的项目之后发生冲突.