Why Java implement different hashcode method of Set and ArrayList?

Question

 // this is the hashCode method of Set
public int hashCode() {
    int h = 0;
    Iterator<E> i = iterator();
    while (i.hasNext()) {
        E obj = i.next();
        if (obj != null)
            h += obj.hashCode();
    }
    return h;
}



//this is the hashCode method of List
public int hashCode() {
    int hashCode = 1;
    for (E e : this)
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    return hashCode;
}

why java use these two different approaches? Is there anything related to the characteristic of Set and List? Why it uses 31 but not other numbers? Thanks!

I answered the part about List vs Set, because I couldn't find any other questions on SO about that. But the bit about 31 is already answered: see http://stackoverflow.com/questions/299304, as well as other answers if you search for why hash functions use prime numbers. — yshavit, Dec 13 '16 at 00:42

yshavit · Accepted Answer · 2016-12-13T00:36:15.063

Sets are unordered, so {a, b, c} must have the same hash code as {c, b, a}. Addition is commutative, so adding the elements' hashCodes gives you that property.

Lists are ordered, so while [a, b, c] may have the same hash code as [c, b, a], it does not need to -- and it'd be better if it didn't, since as much as possible non-equal objects should try to have non-equal hashCodes. The ArrayList.hashCode implementation has that property.

Note that Set and List both define how implementations must define equals and hashCode (Set.hashCode, List.hashCode), so any (compliant) implementation of those respective collections is going to look pretty much the same. This gives you the useful property that a Set containing the same elements is equal (and thus has the same hashCode) as any other Set, regardless of the underlying implementations.

Why Java implement different hashcode method of Set and ArrayList?

1 Answers1