Re: hashcode calculation for a Collection of objects

From:

Lew <lew@lewscanon.nospam>

Newsgroups:

comp.lang.java.programmer

Date:

Tue, 07 Aug 2007 20:51:42 -0400

Message-ID:

<t86dnZ8KFcwDjiTbnZ2dnUVZ_uOmnZ2d@comcast.com>

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.

Extra points to those who know why List.hashCode() multiplies by the magic
number 31.

--
Lew