How do we decide on the best implementation of hashCode()
method for a collection (assuming that equals method has been overridden correctly) ?
20 Answers
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
Create a
int result
and assign a non-zero value.For every field
f
tested in theequals()
method, calculate a hash codec
by:- If the field f is a
boolean
: calculate(f ? 0 : 1)
; - If the field f is a
byte
,char
,short
orint
: calculate(int)f
; - If the field f is a
long
: calculate(int)(f ^ (f >>> 32))
; - If the field f is a
float
: calculateFloat.floatToIntBits(f)
; - If the field f is a
double
: calculateDouble.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 iff == 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.
- If the field f is a
Combine the hash value
c
withresult
:result = 37 * result + c
Return
result
This should result in a proper distribution of hash values for most use situations.
-
52
-
20
-
43@dma_k 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?) Feb 15, 2013 at 13:58
-
38@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.– dma_kFeb 15, 2013 at 14:08
-
18I think Bloch multiplies by 31, not 37, for its ease of optimization.– ruffinJul 21, 2015 at 20:27
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.
-
9Unless 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).– KissakiJan 28, 2014 at 13:23
-
8@justin.hughey you seem to be confused. The only case you should override
hashCode
is if you have a customequals
, and that is precisely what these library methods are designed for. The documentation is quite clear on their behaviour in relation toequals
. A library implementation does not claim to absolve you from knowing what the characteristics of a correcthashCode
implementation are - these libraries make it easier for you to implement such a conforming implementation for the majority of cases whereequals
is overriden.– bacarMar 11, 2014 at 0:06 -
7For 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. Feb 5, 2015 at 5:30
-
3Best answer IMO, although by way of example I would rather have chosen the JDK7
java.util.Objects.hash(...)
method than the guavacom.google.common.base.Objects.hashCode(...)
method. I think most people would choose the standard library over an extra dependency. Nov 4, 2015 at 19:00 -
2If 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 itsjava.lang.System.identityHashCode(...)
. Dec 21, 2015 at 11:48
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));
}
-
1Android Documentation now does not include the above code anymore, so here is a cached version from the Wayback Machine - Android Documentation (Feb 07, 2015) Jul 18, 2017 at 9:14
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.
-
4+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.– Quantum7Apr 7, 2011 at 0:31
-
2+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.– jwir3Jan 27, 2014 at 21:05
-
18Sorry 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. Jun 3, 2016 at 18:59
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.
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
-
5If
(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. Apr 29, 2013 at 8:45 -
This should just be a comment to the above post to Grey. Good information but it does not really answer the question Sep 15, 2015 at 11:55
-
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)... Jun 3, 2016 at 19:04
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.
There's a good implementation of the Effective Java's hashcode()
and equals()
logic in Apache Commons Lang. Checkout HashCodeBuilder and EqualsBuilder.
-
1The 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. Feb 4, 2012 at 1:35
-
this was my favorite approach, until recently. I have ran into StackOverFlowError while using a criteria for SharedKey OneToOne association. More over,
Objects
class provideshash(Object ..args)
&equals()
methods from Java7 on. These are recommended for any applications using jdk 1.7+– DiabloMar 17, 2016 at 11:26 -
@Diablo 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. Dec 10, 2017 at 19:12
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)
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);
}
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);
}
@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.)
-
3the 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. Sep 22, 2008 at 13:53
-
1So this is meta-discussion and not related to the question at all? ;-)– HuppieSep 22, 2008 at 17:40
-
1It's a correction to a proposed answer that has a fairly significant flaw. Sep 22, 2008 at 22:13
-
-
Your implementation avoid the problem and introduces another one; Swapping
foo
andbar
leads to the samehashCode
. YourtoString
AFAIK does not compile, and if it does, then it's terrible inefficient. Something like109 * getFoo().hashCode() + 57 * getBar().hashCode()
is faster, simpler and produces no needless collisions. Dec 10, 2017 at 19:18
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...
Use the reflection methods on Apache Commons EqualsBuilder and HashCodeBuilder.
-
1If you are going to use this be aware that reflection is expensive. I honestly wouldn't use this for anything besides throw away code. Feb 4, 2012 at 1:31
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...).
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.
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());
}
}
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.
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
-
1
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.
-
1Like 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). Apr 30, 2013 at 6:34 -
@KrzysztofJabłoński Right. Moreover, swapping
foo
andbar
produces a needless collision, too. Dec 10, 2017 at 19:25
Objects.hashCode(collection)
should be a perfect solution!collection.hashCode()
(hg.openjdk.java.net/jdk7/jdk7/jdk/file/9b8c96f96a0f/src/share/…)