在Java中比较两个数据结构的最快方法

Question

我想知道在Java 1.5中比较两个数据结构的最快方法。

我的数据结构表示一个可能非常大的树。我可以遍历整个数据结构并逐个比较节点（这可能会很慢）。或者我可以计算数据结构的哈希值以更快地完成比较，对吗？

那么，最好的（高效且不太长）计算哈希值的方法是什么？

我不想花费太多时间来计算哈希值...

希望我表达清楚了.. :-) ...

- LB40

Answer 1

您是否考虑过保持一个运行的hashCode，随着元素被插入或从您的树中删除而不断更新？这样，通过hashCode在任何给定时间比较树将是瞬间完成的。

根据您如何实现哈希函数以及您插入和删除节点的频率，这可能是一种可怕的解决方案。如果您的哈希函数很快，您没有进行太多更改，并且您需要进行大量比较，则可以使用此方法。

- gdm

---

"这可能是一个可怕的解决方案。" 我同意。 - Ben S

Answer 2

public void preOrderTraversal(Node r1, Node r2) {

       if (r1 != r2 )  { // implement equals here !!  

           System.exit(0); // exit and print not equal
       }

       preOrderTraversal(r1.left(),r2.left());
       preOrderTraversal(r1.right(),r2.right());
}

- Srinivas

Answer 3

每个对象都继承了 .equals() 和 .hashCode() 自 Object。

Java 中的标准数据结构应该已经为您实现了一个相对快速的 .hashCode() 方法（哈希可能是增量计算的，也可能需要迭代每个元素，请检查您正在使用的数据结构的源代码以确保）。

即使数据结构不完全相同，哈希冲突 也可能发生，您应该意识到这一点。

为了进行准确的比较，我会同时在两棵树上执行树遍历，比较每个元素。这样，树的形状以及包含的元素将在O(n)时间内进行比较，其中n是最大树的大小。

- Ben S

---

它不一定快。集合实现取决于集合中元素的实现。 - erickson

是的，但是考虑到可能的哈希算法集合，我相信Java开发人员选择了一种相对较快的算法。 - Ben S

请注意，默认的 .equals() 实现仅检查 "=="（两个对象是否实际上是同一个对象）。您的类应该重写 equals() 方法，以执行有意义的比较。 - Scott Stanchfield

Answer 4

计算哈希值需要遍历两棵树的所有节点。您必须检查每个节点的属性并执行哈希计算。例如，如果节点中有一个String，则必须迭代其字符并进行一些数学运算。然后，您必须将节点的哈希与其他节点的哈希组合起来。

因此，为两个结构计算哈希值的成本与比较它们的相等性的成本相同（可能稍微更昂贵）。实际上，因为在执行相等性比较时，只要检测到任何差异，就可以停止，所以单个相等性测试平均速度会快得多。

仅当您缓存哈希值并多次重复使用它时，哈希才有可能有益。请记住，由于不同树的哈希值可能会发生冲突，因此仍然需要实现相等性比较。

- erickson

---

我计划缓存一些哈希数...如果两个哈希数相同，我仍然必须遍历树并逐个比较它们的节点吗？ - LB40

是的，您仍然需要比较树的相等性。有一种“完美”的哈希函数，它不会在指定范围内生成任何冲突，但我认为您无法为树结构设计一个这样的函数。两个不同的树可能具有相同的哈希值。如果您拥有大量的树并且正在寻找匹配项，则良好的哈希代码将缩小候选项。然后，您可以逐个节点进行比较，以查看您的短列表中是否真正存在匹配项。 - erickson

Answer 5

正如gdm所说，您可以保留一个运行中的hashCode，这将使您能够快速确定两个树是否不同（然后您需要在确定它们具有相同的哈希值后进行深度比较）。您可以使用节点的hashCode的异或（例如）来为所有节点计算，这使得添加和删除非常简单：

this.hashcode ^= nodeInQuestion.hashCode;

或者，您可以创建一个不可变结构，然后将其内部化。虽然这会增加更改的开销，但是没有比引用相等更快的比较了。这取决于您是针对修改还是比较进行优化，是否需要在正面和负面方面具有类似的速度，以及最重要的是您的树的大小是否真的很明显。

- Mark

Answer 6

根据比较节点的开销高低，先仅比较树的拓扑结构，仅在树结构相同的情况下比较每一对节点可能是值得的。

- jdisk

Answer 7

如果图谱中的所有对象都实现了比较器-compareTo，您只需调用compareTo。 可能的话，我总是在POJOS上实现comparable（以及hashcode和equals）。

为加快速度，您可以实现快捷方式，以便不匹配的对象尽早返回。 我们这样做确实很有帮助。

在对其运行真正的分析器之前，我不会尝试过早地优化其他方法（Netbeans免费且具有非常好的分析器）。

添加compareTo的好处是它为您提供了一种通用功能，可在其他地方使用：TreeMaps，排序集合等

- Fortyrunner