How to properly define hash function for a list of objects?

Question

I have a data structure containing a list of objects, like this:

class A {
  private List<Object> list;
}

How to properly define a hash function for the list, assuming each element of the list has correct hashCode()?

(It's strange that I couldn't easily find the solution via Google.)

Answer 1

Why do you want to define hashCode for your list, when it already has it implemented (along with equals)?

(Provided it is java.util.List of course - however if not, the link above shows you the exact implementation you can use for your own list type.)

Answer 2

If the actual List implementation is fully conformant to the interface, the provided hashCode implementation should be sufficient:

Returns the hash code value for this list. The hash code of a list is defined to be the result of the following calculation:

hashCode = 1;
  Iterator i = list.iterator();
  while (i.hasNext()) {
      Object obj = i.next();
      hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
  }

(List documentation)

The List interface requires conforming implementations to provide equals based on the elements of the list. Thus, they had to specify the hashCode algorithm explicitely

Answer 3

The hash code of a list is defined by the List interface of List. This can be used as part of your object's hash code, though there are a couple of cases where you might not want to use it - if the elements of your list have an expensive hash code function, or if the list can hold a reference to the object, and you would then get a stack overflow if the list's algorithm was used. In that case, just use the length of the list or another hash value.

Answer 4

In the Java library, List implementations (LinkedList, ArrayList) use the default hashCode implementation provided by AbstractList. which is defined as:

int hashCode = 1;
Iterator<E> i = iterator();
while (i.hasNext()) {
    E obj = i.next();
    hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
}
return hashCode;