Efficient hashCode() implementation

Question

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?

Jon Skeet · Accepted Answer · 2009-07-02 14:01:12Z

22

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 :)

answered Jul 2, 2009 at 14:01

Jon Skeet

1.5m893 gold badges9.3k silver badges9.3k bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

oxbow_lakes Over a year ago

Then why not 7? That's a shift by 3 and a subtract. And it's a prime

Adamski Over a year ago

Thanks Jon. If this is the reason it's strange that IDEA doesn't just put (x << 5) - x in the generated code. Is the JIT likely to actually spot this optimisation?

Tom Hawtin - tackline Over a year ago

7 allows strings that differ only in two adjacent characters to often end up with the same hash code. In fact pretty much any processor from the last decade or two should be able to manage a multiply by an eight bit number (so long as it is in a register) in a cycle.

Bombe Over a year ago

Last time I checked 31 was prime, too.

Jon Skeet Over a year ago

@dma_k: I'm afraid I don't know the details of it... only that it's meant to work well. (I thought Effective Java suggested 31 actually... maybe it's the second edition which does so?)

|

Collectives™ on Stack Overflow

Efficient hashCode() implementation

1 Answer 1

7 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related