What datastructure to use for finding the intersection of 2 trees

Question

I have two tree, which contains nodes, after I've created them, I take all the nodes of the first tree to a linkedlist, and the second ones to a hashmap, as the keys of the map. I would like to find two nodes from the trees, which has the same variable called: states (long type). So after the creation I call:

List<Node> list;
HashMap<Node, Node> hashtable;

...create nodes, take them to the collections

for(Node n : list){
    if(hashtable.containsKey(n)){
        //doSomething          
    }
}

I'm using hashmap, because it is very fast, though I have 4000000 (4 million) nodes. I've overridden the equals method of the Node class, but seems like the containskey method checks the hashcodes, however as far as I understood it only has to check the equals method link to java reference. So the question is what datastructure should I use, to check this thing, or how should i rewrite the code?

Here's my equals method:

    @Override
    public boolean equals(Object obj) {
    if(obj instanceof Node){
        Node node = (Node)obj;
        return (states == node.getStates());
    }
    return false;
}

Answer 1

You have to override hashCode() method when overriding equals() so that equal objects must have the same hash code. Refer to http://docs.oracle.com/javase/6/docs/api/java/lang/Object.html#equals(java.lang.Object).