Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Efficient hashCode() implementation

I often auto-generate an class's hashCode() method using IntelliJ IDEA and typically the method takes the form:

result = 31 * result + ...

My question is what is the purpose of multiplying by 31? I know this is a prime number but why pick 31 specifically? Also, if implementing a hashCode() for a particularly small / large dataset would people approach this problem differently?

like image 552
Adamski Avatar asked Jul 02 '09 14:07

Adamski


1 Answers

Multiplying by 31 is fast because the JIT can convert it to a shift left by 5 bits and a subtract:

x * 31 == (x << 5) - x

Without any particular extra information, I'd stick to this approach. It's reasonably fast and likely to end up with reasonably well-distributed hash codes, and it's also easy to get right :)

The size of the dataset doesn't really matter, but if you have particular extra information about the values you'll be work with (e.g. "it's always even") then you may be able to design a better hash function. I'd wait until it's an actual problem first though :)

like image 177
Jon Skeet Avatar answered Oct 24 '22 14:10

Jon Skeet