Best implementation for hashCode method for a collection

Question

How do we decide on the best implementation of hashCode() method for a collection (assuming that equals method has been overridden correctly) ?

Monopolize

with Java 7+, I guess Objects.hashCode(collection) should be a perfect solution! – Scrimshaw

@Scrimshaw I don't think that answers the question at all - that method simply returns collection.hashCode() (hg.openjdk.java.net/jdk7/jdk7/jdk/file/9b8c96f96a0f/src/share/…) – Rapine

Answer 1

The best implementation? That is a hard question because it depends on the usage pattern.

A for nearly all cases reasonable good implementation was proposed in Josh Bloch's Effective Java in Item 8 (second edition). The best thing is to look it up there because the author explains there why the approach is good.

A short version

1. Create a int result and assign a non-zero value.

2. For every field f tested in the equals() method, calculate a hash code c by:

   • If the field f is a boolean: calculate (f ? 0 : 1);
   • If the field f is a byte, char, short or int: calculate (int)f;
   • If the field f is a long: calculate (int)(f ^ (f >>> 32));
   • If the field f is a float: calculate Float.floatToIntBits(f);
   • If the field f is a double: calculate Double.doubleToLongBits(f) and handle the return value like every long value;
   • If the field f is an object: Use the result of the hashCode() method or 0 if f == null;
   • If the field f is an array: see every field as separate element and calculate the hash value in a recursive fashion and combine the values as described next.

3. Combine the hash value c with result:

   result = 37 * result + c
   

4. Return result

This should result in a proper distribution of hash values for most use situations.

Ellis

Interesting answer. Are there some link to a mathematical proof for why this formula works? – Willms

Yeah I'm particularly curious about where the number 37 comes from. – Gaff

I'm not aware of any proof. The number of 37 is arbitrary, but it should be prime. Why? I'm not really sure but it has to do with modulo arthritics and properties of prime numbers which lead to go distributions. – Ellis

Thank you for detailed answer. Could you please tell me, which reference/guidelines you used to create this set of advices? Also I wonder, why multiply by 37? What is the magic in 37? Why multiply is better then right shift (result = result << 16 + c)? – Midweek

I used item 8 of Josh Bloch's "Effective Java" book. – Ellis

@Midweek The reason for using prime numbers and the method described in this answer is to ensure that the computed hashcode will be unique. When using non-prime numbers, you cannot guarantee this. It does not matter which prime nummer you choose, there is nothing magical about the number 37 (too bad 42 isn't a prime number, eh?) – Jordison

@SimonAndréForsberg Well, computed hash code cannot be always unique :) Is a hashcode. However I got the idea: the prime number has only one multiplier, while non-prime has at least two. That creates an extra combination for multiplication operator to result the same hash, i.e. cause collision. – Midweek

@Midweek Yes, that's what I meant :) Of course it cannot be unique at all times (otherwise comparing hashCode would be enough to determine .equals), using prime numbers just reduces the collisions. – Jordison

Any particular reason for true mapping to 0 and false to 1, and not the other way around? – Armoury

@afsantos: I can't think of any. The code from the book is more a general guideline as a law and by no means the only correct way to do it. – Ellis

I edited the post but this minimum number of characters is really annoying when doing minor mark-up adjustments :( If accepted, could somebody please remove EDITED near bullet 1? Thanks. – Wimsatt

+1 Excellent explanation, and I really like that you gave the source (i.e. Bloch's book, not the source code) in the event someone wants more information. – Sundew

If the field f is an array, you also have the option of using the java.util.Arrays.hashCode methods to compute that field's hash value. – Crissycrist

I think Bloch multiplies by 31, not 37, for its ease of optimization. – Diamond

What if the field is a string? It definitely is an object but what should be the implementation of hte hashcode – Flaunch

How to calculate in the case of String Member type of object – Jealous

One of the main goals of a hash function is that it should be inexpensive to evaluate. I just wrote a hash function for a formal parameter data structure in a compiler. The equality test of course must check every parameter name and type, after ensuring structural isometry. But as for "For every field f tested in the equals() method", one could well find the hash lookup nearly as expensive as a linear search. You need only to create a trivial hash function that yields a broad distribution of results across usage patterns. Empirical measurement and experimentation, rather than guessing, helps. – Springe

@Cope: I disagree that the main goal of a hash function is speed. While there are certain special cases for other hashCode implementations, this is a very good start. Certainly it is a correct implementation. Most "smart" ones are just plain wrong. – Ellis

Hej @Ellis — I stand my ground. It's very simple. 1. The primary goal of a hash function (in data structures, rather than, e.g., in encryption) is speed — to avoid the cost of a linear search. 2. There is a tradeoff between the cost of computing the hash and the cost of a linear search, and on multi-field structures even just searching on the right key can be enough to adequately lower the cost. 3. For large data structures (like my formal parameters) the number of computations would be in the dozens if you measure "every field." 4. There is no universal answer — so you must measure. – Springe

I saw that 37 elsewhere for calculating string hash code algorithm and judged that there are 26 letters and 10 numbers plus space character which comes up with 37 lol – Tessellation

Could someone please explain what this line is doing in case of long? f ^ (f >>> 32) – Villosity

In the third version of Effective Java, the content of Item 8 has nothing to do with hashcode so maybe remove the mention of the item. – Unplaced

I think Item 8 was based on the second edition. The third edition has a page at the end how the different items map from edition to edition. – Ellis

With good hashing, the probability for hash collision should be 2^-32, but with 37, you can easily run into collisions. For example, for an object with two ints (x, y), the hashcodes for (1, -37), (0, 0), (-1, 37) would all evaluate to 0. So in real life (with small values much more likely than large), the probability is nowhere near 2^-32. Better use a prime like 912376189. – Filtrate

This function handles double like .Net, and my recent testing shows that it is very poor when your doubles are not truly random, but really integers, or have only one or two decimal places. The re-hash function from HashMap helps, but still isn't as good as just using the HashCode for int on the value in this case. – Chess

@demister Can you explain the logic of the long data type hash code (int)(f ^ (f >>> 32)) – Gog

@Gaff It is common practice to use powers of 2 to assign hash buckets; because it makes the modulus operation very fast, effectively turning it into a binary AND operation %4 -> AND( 0x0003). To get a decent distribution in the new space from a well distributed input, one wants to multiply the input by a coprime, of which 37 is coprime to all powers of 2. Other numbers would work, but you want one small enough to work with char, and large enough to overflow the limit quickly. 37 shifts the input by one, three, and six places, helping the input bits spread out more. 37, 31, 27 etc also work. – Encage

Another tip I found out the hard way. Don't use fields in hashCode() that change during the lifetime of the object. I use a WeakHashMap and there was an entry but after a while it returned NULL because one of the field changed. So the hashCode() was also changed, and the HashMap couldn't find the object anymore. – Spongioblast

@StijnLeenknegt mutable objects are generally not accepted as keys into hashmaps for this reason. If the object is mutated, then the hash will change, which is a no-no. In a sense, when you mutate the object it ceases to be the original object. At that point, you might be better off comparing the objects based on their id/address rather than based on their fields/attributes. – Knell

Answer 2

If you're happy with the Effective Java implementation recommended by dmeister, you can use a library call instead of rolling your own:

@Override
public int hashCode() {
    return Objects.hash(this.firstName, this.lastName);
}

This requires either Guava (com.google.common.base.Objects.hashCode) or the standard library in Java 7 (java.util.Objects.hash) but works the same way.

Nedanedda

Unless one has a good reason not to use these, one should definitely use these in any case. (Formulating it stronger, as it IMHO should be formulated.) The typical arguments for using standard implementations/libraries apply (best practices, well tested, less error prone, etc). – Pineda

The case to not use a library implementation is when you have implemented a custom Object#equals(Object obj) method. See the Object#hashcode() JavaDoc, "If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result." Using either of these library implementations will generate a"pseudo" memory address hash code which may violate the described requirement. – Entrenchment

@Entrenchment you seem to be confused. The only case you should override hashCode is if you have a custom equals, and that is precisely what these library methods are designed for. The documentation is quite clear on their behaviour in relation to equals. A library implementation does not claim to absolve you from knowing what the characteristics of a correct hashCode implementation are - these libraries make it easier for you to implement such a conforming implementation for the majority of cases where equals is overriden. – Nedanedda

You're absolutely right. Thank you for pointing that out, I don't know where I was coming from on that one. :) – Entrenchment

For any Android developers looking at the java.util.Objects class, it was only introduced in API 19, so make sure you're running on KitKat or above otherwise you'll get NoClassDefFoundError. – Unthinking

Best answer IMO, although by way of example I would rather have chosen the JDK7 java.util.Objects.hash(...) method than the guava com.google.common.base.Objects.hashCode(...) method. I think most people would choose the standard library over an extra dependency. – Quasijudicial

If there are two arguments or more and if any of them is an array, the result might be not what you expect because hashCode() for an array is just its java.lang.System.identityHashCode(...). – Hadleigh

@Hadleigh Yes - the helper methods do not absolve you from having to understand what you're doing. They just help you to avoid certain mistakes and duplicate code. – Nedanedda

@Nedanedda Of course. I just left my comment so that whoever learns about these methods from this post learns about their limitations as well. – Hadleigh

The comments about association of overriding equals() are correct. hashCode() is not implemented in a vacuum and must be directly related to how equals() is implemented per the documentation (two objects can have the same hashCode but NOT be equal - yet two equal objects MUST have the same hashCode). – Drysalter

@Pineda On the opposite: Using the standard implementation leads to standard collisions. – Dictate

@AndrewKelly It's been a few years but for anyone else who comes across this and is still supporting < 19, now there's ObjectsCompat.hash(...) and its implementation is just Arrays.hashCode(...) for API < 19, which appears to be the exact same implementation in Objects.hash(...). Android Studio has a code generator for this that will insert Objects.hash(...) though no matter what your minSdkVersion is so devs should be aware they can just replace that with ObjectsCompat and they'll be fine. – Meaningless

Objects.hashCode() is one of the APIs that is now desugared by D8 automatically in Android Studio 4+, so you can use the original API on targets earlier than API 19 (no need for the ObjectsCompat). For a full list of desugared APIs, check this file. jakewharton.com/static/files/d8_api_desugar_list.txt – Unthinking

Answer 3

Although this is linked to Android documentation (Wayback Machine) and My own code on Github, it will work for Java in general. My answer is an extension of dmeister's Answer with just code that is much easier to read and understand.

@Override 
public int hashCode() {

    // Start with a non-zero constant. Prime is preferred
    int result = 17;

    // Include a hash for each field.

    // Primatives

    result = 31 * result + (booleanField ? 1 : 0);                   // 1 bit   » 32-bit

    result = 31 * result + byteField;                                // 8 bits  » 32-bit 
    result = 31 * result + charField;                                // 16 bits » 32-bit
    result = 31 * result + shortField;                               // 16 bits » 32-bit
    result = 31 * result + intField;                                 // 32 bits » 32-bit

    result = 31 * result + (int)(longField ^ (longField >>> 32));    // 64 bits » 32-bit

    result = 31 * result + Float.floatToIntBits(floatField);         // 32 bits » 32-bit

    long doubleFieldBits = Double.doubleToLongBits(doubleField);     // 64 bits (double) » 64-bit (long) » 32-bit (int)
    result = 31 * result + (int)(doubleFieldBits ^ (doubleFieldBits >>> 32));

    // Objects

    result = 31 * result + Arrays.hashCode(arrayField);              // var bits » 32-bit

    result = 31 * result + referenceField.hashCode();                // var bits » 32-bit (non-nullable)   
    result = 31 * result +                                           // var bits » 32-bit (nullable)   
        (nullableReferenceField == null
            ? 0
            : nullableReferenceField.hashCode());

    return result;

}

EDIT

Typically, when you override hashcode(...), you also want to override equals(...). So for those that will or has already implemented equals, here is a good reference from my Github...

@Override
public boolean equals(Object o) {

    // Optimization (not required).
    if (this == o) {
        return true;
    }

    // Return false if the other object has the wrong type, interface, or is null.
    if (!(o instanceof MyType)) {
        return false;
    }

    MyType lhs = (MyType) o; // lhs means "left hand side"

            // Primitive fields
    return     booleanField == lhs.booleanField
            && byteField    == lhs.byteField
            && charField    == lhs.charField
            && shortField   == lhs.shortField
            && intField     == lhs.intField
            && longField    == lhs.longField
            && floatField   == lhs.floatField
            && doubleField  == lhs.doubleField

            // Arrays

            && Arrays.equals(arrayField, lhs.arrayField)

            // Objects

            && referenceField.equals(lhs.referenceField)
            && (nullableReferenceField == null
                        ? lhs.nullableReferenceField == null
                        : nullableReferenceField.equals(lhs.nullableReferenceField));
}

Patinous

Android Documentation now does not include the above code anymore, so here is a cached version from the Wayback Machine - Android Documentation (Feb 07, 2015) – Patinous

Answer 4

It is better to use the functionality provided by Eclipse which does a pretty good job and you can put your efforts and energy in developing the business logic.

Prevot

+1 A good practical solution. dmeister's solution is more comprehensive, but I tend to forget to handle nulls when I try to write hashcodes myself. – Chasten

+1 Agree with Quantum7, but I would say it's also really good to understand what the Eclipse-generated implementation is doing, and where it gets its implementation details from. – Sundew

Sorry but answers involving "functionality provided by [some IDE]" are not really relevant in the context of the programming language in general. There are dozens of IDEs and this does not answer the question... namely because this is more about algorithmic determination and directly associated to equals() implementation - something an IDE will know nothing about. – Drysalter

Answer 5

First make sure that equals is implemented correctly. From an IBM DeveloperWorks article:

• Symmetry: For two references, a and b, a.equals(b) if and only if b.equals(a)
• Reflexivity: For all non-null references, a.equals(a)
• Transitivity: If a.equals(b) and b.equals(c), then a.equals(c)

Then make sure that their relation with hashCode respects the contact (from the same article):

• Consistency with hashCode(): Two equal objects must have the same hashCode() value

Finally a good hash function should strive to approach the ideal hash function.

Offish

Answer 6

about8.blogspot.com, you said

if equals() returns true for two objects, then hashCode() should return the same value. If equals() returns false, then hashCode() should return different values

I cannot agree with you. If two objects have the same hashcode it doesn't have to mean that they are equal.

If A equals B then A.hashcode must be equal to B.hascode

but

if A.hashcode equals B.hascode it does not mean that A must equals B

Wawro

If (A != B) and (A.hashcode() == B.hashcode()), that's what we call hash function collision. It's because hash function's codomain is always finite, while it's domain is usually not. The bigger the codomain is, the less often the collision should occur. Good hash function's should return different hashes for different objects with greatest possibility achievable given particular codomain size. It can rarely be fully guaranteed though. – Respite

This should just be a comment to the above post to Grey. Good information but it does not really answer the question – Patinous

Good comments but be careful about using the term 'different objects' ... because equals() and thus the hashCode() implementation are not necessarily about different objects in an OO context but are usually more about their domain model representations (e.g., two people can be considered the same if they share a country code and country ID - though these may be two different 'objects' in a JVM - they are considered 'equal' and having a given hashCode)... – Drysalter

Answer 7

There's a good implementation of the Effective Java's hashcode() and equals() logic in Apache Commons Lang. Checkout HashCodeBuilder and EqualsBuilder.

Bushire

The downside of this API is you pay the cost of object construction every time you call equals and hashcode (unless your object is immutable and you precompute the hash), which can be a lot in certain cases. – Rhizopod

this was my favorite approach, until recently. I have ran into StackOverFlowError while using a criteria for SharedKey OneToOne association. More over, Objects class provides hash(Object ..args) & equals() methods from Java7 on. These are recommended for any applications using jdk 1.7+ – Scrimshaw

@Scrimshaw I guess, your problem was a cycle in the object graph and then you're out of luck with most implementation as you need to ignore some reference or to break the cycle (mandating an IdentityHashMap). FWIW I use an id-based hashCode and equals for all entities. – Dictate

Answer 8

If you use eclipse, you can generate equals() and hashCode() using:

Source -> Generate hashCode() and equals().

Using this function you can decide which fields you want to use for equality and hash code calculation, and Eclipse generates the corresponding methods.

Kriskrischer

Answer 9

Just a quick note for completing other more detailed answer (in term of code):

If I consider the question how-do-i-create-a-hash-table-in-java and especially the jGuru FAQ entry, I believe some other criteria upon which a hash code could be judged are:

• synchronization (does the algo support concurrent access or not) ?
• fail safe iteration (does the algo detect a collection which changes during iteration)
• null value (does the hash code support null value in the collection)

Limey

Answer 10

If I understand your question correctly, you have a custom collection class (i.e. a new class that extends from the Collection interface) and you want to implement the hashCode() method.

If your collection class extends AbstractList, then you don't have to worry about it, there is already an implementation of equals() and hashCode() that works by iterating through all the objects and adding their hashCodes() together.

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

Now if what you want is the best way to calculate the hash code for a specific class, I normally use the ^ (bitwise exclusive or) operator to process all fields that I use in the equals method:

public int hashCode(){
   return intMember ^ (stringField != null ? stringField.hashCode() : 0);
}

Tarlatan

Answer 11

I use a tiny wrapper around Arrays.deepHashCode(...) because it handles arrays supplied as parameters correctly

public static int hash(final Object... objects) {
    return Arrays.deepHashCode(objects);
}

Hadleigh

Answer 12

@about8 : there is a pretty serious bug there.

Zam obj1 = new Zam("foo", "bar", "baz");
Zam obj2 = new Zam("fo", "obar", "baz");

same hashcode

you probably want something like

public int hashCode() {
    return (getFoo().hashCode() + getBar().hashCode()).toString().hashCode();

(can you get hashCode directly from int in Java these days? I think it does some autocasting.. if that's the case, skip the toString, it's ugly.)

Ogive

the bug is in the long answer by about8.blogspot.com -- getting the hashcode from a concatenation of strings leaves you with a hash function that is the same for any combination of strings that add up to the same string. – Ogive

So this is meta-discussion and not related to the question at all? ;-) – Ampulla

It's a correction to a proposed answer that has a fairly significant flaw. – Ogive

This is a very limited implementation – Patinous

Your implementation avoid the problem and introduces another one; Swapping foo and bar leads to the same hashCode. Your toString AFAIK does not compile, and if it does, then it's terrible inefficient. Something like 109 * getFoo().hashCode() + 57 * getBar().hashCode() is faster, simpler and produces no needless collisions. – Dictate

Answer 13

As you specifically asked for collections, I'd like to add an aspect that the other answers haven't mentioned yet: A HashMap doesn't expect their keys to change their hashcode once they are added to the collection. Would defeat the whole purpose...

Congeal

Answer 14

Use the reflection methods on Apache Commons EqualsBuilder and HashCodeBuilder.

Sirenasirenic

If you are going to use this be aware that reflection is expensive. I honestly wouldn't use this for anything besides throw away code. – Rhizopod

Answer 15

any hashing method that evenly distributes the hash value over the possible range is a good implementation. See effective java ( http://books.google.com.au/books?id=ZZOiqZQIbRMC&dq=effective+java&pg=PP1&ots=UZMZ2siN25&sig=kR0n73DHJOn-D77qGj0wOxAxiZw&hl=en&sa=X&oi=book_result&resnum=1&ct=result ) , there is a good tip in there for hashcode implementation (item 9 i think...).

Doubloon

Answer 16

I prefer using utility methods fromm Google Collections lib from class Objects that helps me to keep my code clean. Very often equals and hashcode methods are made from IDE's template, so their are not clean to read.

Wawro

Answer 17

Here is another JDK 1.7+ approach demonstration with superclass logics accounted. I see it as pretty convinient with Object class hashCode() accounted, pure JDK dependency and no extra manual work. Please note Objects.hash() is null tolerant.

I have not include any equals() implementation but in reality you will of course need it.

import java.util.Objects;

public class Demo {

    public static class A {

        private final String param1;

        public A(final String param1) {
            this.param1 = param1;
        }

        @Override
        public int hashCode() {
            return Objects.hash(
                super.hashCode(),
                this.param1);
        }

    }

    public static class B extends A {

        private final String param2;
        private final String param3;

        public B(
            final String param1,
            final String param2,
            final String param3) {

            super(param1);
            this.param2 = param2;
            this.param3 = param3;
        }

        @Override
        public final int hashCode() {
            return Objects.hash(
                super.hashCode(),
                this.param2,
                this.param3);
        }
    }

    public static void main(String [] args) {

        A a = new A("A");
        B b = new B("A", "B", "C");

        System.out.println("A: " + a.hashCode());
        System.out.println("B: " + b.hashCode());
    }

}

Highborn

Answer 18

The standard implementation is weak and using it leads to unnecessary collisions. Imagine a

class ListPair {
    List<Integer> first;
    List<Integer> second;

    ListPair(List<Integer> first, List<Integer> second) {
        this.first = first;
        this.second = second;
    }

    public int hashCode() {
        return Objects.hashCode(first, second);
    }

    ...
}

Now,

new ListPair(List.of(a), List.of(b, c))

and

new ListPair(List.of(b), List.of(a, c))

have the same hashCode, namely 31*(a+b) + c as the multiplier used for List.hashCode gets reused here. Obviously, collisions are unavoidable, but producing needless collisions is just... needless.

There's nothing substantially smart about using 31. The multiplier must be odd in order to avoid losing information (any even multiplier loses at least the most significant bit, multiples of four lose two, etc.). Any odd multiplier is usable. Small multipliers may lead to faster computation (the JIT can use shifts and additions), but given that multiplication has latency of only three cycles on modern Intel/AMD, this hardly matters. Small multipliers also leads to more collision for small inputs, which may be a problem sometimes.

Using a prime is pointless as primes have no meaning in the ring Z/(2**32).

So, I'd recommend using a randomly chosen big odd number (feel free to take a prime). As i86/amd64 CPUs can use a shorter instruction for operands fitting in a single signed byte, there is a tiny speed advantage for multipliers like 109. For minimizing collisions, take something like 0x58a54cf5.

Using different multipliers in different places is helpful, but probably not enough to justify the additional work.

Dictate

Answer 19

When combining hash values, I usually use the combining method that's used in the boost c++ library, namely:

seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);

This does a fairly good job of ensuring an even distribution. For some discussion of how this formula works, see the StackOverflow post: Magic number in boost::hash_combine

There's a good discussion of different hash functions at: http://burtleburtle.net/bob/hash/doobs.html

Epiglottis

This is a question about Java, not C++. – Ruralize

Answer 20

For a simple class it is often easiest to implement hashCode() based on the class fields which are checked by the equals() implementation.

public class Zam {
    private String foo;
    private String bar;
    private String somethingElse;

    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }

        if (obj == null) {
            return false;
        }

        if (getClass() != obj.getClass()) {
            return false;
        }

        Zam otherObj = (Zam)obj;

        if ((getFoo() == null && otherObj.getFoo() == null) || (getFoo() != null && getFoo().equals(otherObj.getFoo()))) {
            if ((getBar() == null && otherObj. getBar() == null) || (getBar() != null && getBar().equals(otherObj. getBar()))) {
                return true;
            }
        }

        return false;
    }

    public int hashCode() {
        return (getFoo() + getBar()).hashCode();
    }

    public String getFoo() {
        return foo;
    }

    public String getBar() {
        return bar;
    }
}

The most important thing is to keep hashCode() and equals() consistent: if equals() returns true for two objects, then hashCode() should return the same value. If equals() returns false, then hashCode() should return different values.

Accepted

Like SquareCog have already noticed. If hashcode is generated once from concatenation of two strings it is extremely easy to generate masses of collisions: ("abc"+""=="ab"+"c"=="a"+"bc"==""+"abc"). It is severe flaw. It would be better to evaluate hashcode for both fields and then calculate linear combination of them (preferably using primes as coefficients). – Respite

@KrzysztofJabłoński Right. Moreover, swapping foo and bar produces a needless collision, too. – Dictate