9

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

问题是什么是最好的？（性能和碰撞之间的妥协......）。

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

另一方面，我有来自标准 java 发行版的 MessageDigest 方法和 SHA-1 算法。我认为它不会有效率，但我可能会有更少的碰撞。我对吗 ？在我的情况下这是一个正确的解决方案还是我完全错了？

问题是我不知道物体的大小。另请注意，计算的值不会在 HashTable 中使用。

谢谢...

4

5 回答 5

15

请参阅以下内容：

请记住以下几点：

  • 一个对象可能不相等，但具有相同的哈希码
  • 您的碰撞可能性取决于您遇到的对象数量。
  • 哈希码的有用程度取决于您如何实施检查

通常，您可以根据预期对象的数量和可能的散列数（最大散列值）来确定发生冲突的可能性。有关详细说明，请参阅http://en.wikipedia.org/wiki/Birthday_paradox。

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

于 2009-05-12T15:39:21.730 回答
11

就个人而言，我会使用hashCode()对象，直到证明任何可能的冲突都是实际问题，以避免抢先优化您可能实际上没有的问题。

于 2009-05-12T15:27:56.723 回答
7

由于生日问题，碰撞的可能性取决于您正在处理的项目数量。

SHA-1 的 160 位空间是如此之大，以至于我怀疑您是否有足够的项目来查看碰撞。

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

为了应用像 SHA-1 这样的加密摘要，您需要将图形转换为字节串，这可能计算量很大，并且可能很复杂。

于 2009-05-12T15:40:35.953 回答
6

通常对于重复文件/数据检测，MD5 是速度和碰撞机会之间的良好折衷。如果有人故意制作文件来欺骗您的程序（它有点容易受到碰撞攻击），则 MD5 是不合适的。但是，如果您只是担心偶然发生冲突，那么它的 128 位宽度目前实际上总是足够的。

SHA-1 和 SHA-256 为您提供了一些针对故意碰撞攻击的保护（理论上但没有已知的 SHA-1 实际攻击；对于密钥数据，几乎不值得超过 160 位哈希码宽度）。SHA-1 的速度大约是 MD5 的一半。

当然，如果您使用 MD5，性能可能不会成为太大的问题。但这显然取决于数据的大小。您可能对我整理的有关Java中安全散列函数性能的一些信息感兴趣。

如果您确实需要更快的东西并且您只处理几百万条数据，那么另一个需要考虑的选项是 Numerical Recipes 作者提出的 64 位哈希算法。

Java's standard hashCode() implementation (of, say, String) is probably not suitable: aside from any issues about the quality of the hash, its 32-bit width means that you'll expect a collision after just 16,000 items or so.

于 2009-05-12T16:08:37.767 回答
2

我赞同 matt b 的说法“在需要优化之前不要优化”。

但是，如果您决定以后需要的不仅仅是哈希码...我使用消息摘要（在我的情况下为 MD5）来“唯一”识别从 RSS 提要下载的各种项目，所以我最终没有得到相同的当我一遍又一遍地轮询时，项目在列表中出现了很多次。这些通常是小帖子，因此可以快速计算摘要。根据我的经验，它非常有效并且运作良好。

由于它们通常是一种对输入数据中非常小的变化做出强烈反应的方法，因此您肯定不太可能与 MD5 或 SHA-1 发生冲突。

于 2009-05-12T15:40:29.557 回答