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

eclipse implements hashcode() function singly linked list's node class 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() node dependent on hash code of nodes follow it.

so, every call of hashcode() take amortized linear time in length of linked list. using hashset<node> become unfeasible.

one way around cache value of hashcode in variable(call hash) computed once. in case, hash become invalid once node's val changed. , again take linear time modify hashcode of nodes follow current node.

so ways of implementing hashing such linked list node?

my first thought upon reading question was: linkedlist do? digging source, see there no hashcode() or equals() defined on inner linkedlist.node class (link source).

why make sense? well, nodes internal data structures, visible list itself. not going placed collections or other data structure comparing equality , hash-codes necessary. no external code has access them.

you in question:

thus using hashset<node> become unfeasible.

but argue have no need place nodes in such data structure. definition, nodes link each other , require no additional classes facilitate relationship. , unless plan expose class outside list (which isn't necessary), never end in hashset.

i propose follow linkedlist.node model , avoid creating these methods on nodes. outer list can base hashcode , equality on values stored in nodes (but not nodes themselves), how linkedlist - see abstractlist (link source).

_{source links openjdk source, in case identical source supplied oracle jdks}