Fastest way to compare two data structures in java

Question

I would like to know what is the fastest way in java 1.5 to compare two data structures.

My data structure represents a tree that can be pretty big. I can traverse the whole data structure and compare the 2 node by node (which I guess will be slow). Or I can compute a hash of the data structure to do it faster, right ?

What is the best (efficient and not too long) way to compute this hash ?

I wouldn't like to need too much time to compute hash...

Hope I'm clear.. :-)...

Answer 1

Have you considered keeping a running hashCode which is continually updated as elements are inserted or removed from your trees? This way, comparing a tree at any given time by hashCode will be instantaneous.

Depending on how you implement your hash function, and how frequently you insert and remove nodes, this could be a horrible solution. If your hash function is fast, you aren't making many changes, and you need to do a lot of comparisons, this could work.

Answer 2

Every object inherits .equals() and .hashCode() from Object.

The standard data-structures in Java should already implement a relatively fast .hashCode() method for you (The hash might be incrementally calculated or might require iterating over each element, check the source of the data-structure you're using to be sure).

You should be aware that hash collisions might occur even if the data-structures aren't identical.

To have an accurate comparison I would perform a tree traversal simultaneously on both tree comparing each element. This way the shape of the tree as well as the contained elements would be compared in O(n) time where n is the size of the largest tree.