Re: hashcode calculation for a Collection of objects

From:

Patricia Shanahan <pats@acm.org>

Newsgroups:

comp.lang.java.programmer

Date:

Tue, 07 Aug 2007 18:17:05 -0700

Message-ID:

<f9b5ij$1q5q$1@ihnp4.ucsd.edu>

Lew wrote:

Jimmy wrote:

If 2 Collections contain 2 List of objects, and the type of this
object has hashCode() override (hashcode calculation using all fields
in this object), can these 2 different List instances compare by using
list1.hashCode() == list2.hashCode(); without iterate through each
list by comparing each item?

Daniel Pitts wrote:

Assuming that the Collection implementations are the same, and List
implementations are the same, you can call c1.equals(c2) (that way you
don't have to iterate over them yourself)

If that is an expensive operation, then you can use "c1.hashCode() ==
c2.hashCode() && c1.equals(c2)"

This will more than double the time to evaluate equal lists and increase
the time for all others, compared to just using equals():

<http://java.sun.com/javase/6/docs/api/java/util/List.html#hashCode()>

The hash code of a list is defined to be the result of the following
calculation:

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

If anything, because equals() doesn't need to perform the multiply-add
operations the simpler approach is probably faster always.

Also, equals can stop early. The AbstractList implementation stops
without examining any elements if the two references are equal or the
other is not a List. Given two distinct List references, it stops at the
first inequality or when it runs out of elements in the shorter List.

Patricia