How to efficiently implement hashCode() for a singly linked list node in Java?

Question

Eclipse implements the hashCode() function for a singly linked list's Node class the following way:

class Node{
    int val;
    Node next;

    public Node(int val){
        this.val = val;
        next = null;
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((next == null) ? 0 : next.hashCode());
        result = prime * result + val;
        return result;
    }
}

Now hashCode() for a node is dependent on the hash code of the nodes that follow it.

So, every call of hashCode() will take amortized linear time in the length of the linked list. Thus using a HashSet<Node> will become unfeasible.

One way to get around this is to cache the value of the hashCode in a variable(call it hash) so that it is computed only once. But even in this case, the hash will become invalid once any node's val is changed. And again it will take linear time to modify the hashCode of nodes that follow the current node.

So what are some good ways of implementing hashing for such a linked list Node?

Answer 1

My first thought upon reading your question was: what does LinkedList do? Digging into the source, we see that there is no hashCode() or equals() defined on the inner LinkedList.Node class (link to source).

Why does this make sense? Well, nodes are normally internal data structures, only visible to the list itself. They are not going to be placed into collections or any other data structure where comparing equality and hash-codes are necessary. No external code has access to them.

You say in your question:

Thus using a HashSet<Node> will become unfeasible.

But I would argue that you have no need to place your nodes in such a data structure. By definition, your nodes will link to each other and require no additional classes to facilitate that relationship. And unless you plan to expose this class outside your list (which isn't necessary), they will never end up in a HashSet.

I would propose you follow the LinkedList.Node model and avoid creating these methods on your nodes. The outer list can base its hashcode and equality on the values stored in the nodes (but not the nodes themselves), which is how LinkedList does it - see AbstractList (link to source).

_{Source links are to the OpenJDK source, but in this case they are identical to source supplied with Oracle JDKs}