Tuple's GetHashCode hack

Question

Knowing that to obtain hashcode for two objects it is common practice to do XOR of their respective hashcodes I wanted to check how Tuple deals with situation where Item1 == Item2. This is what I found in the source code:

internal static int CombineHashCodes(int h1, int h2) {
        return (((h1 << 5) + h1) ^ h2);
    }

I assume this is to avoid having the same hashcode for all equal objects, because x ^ x = 0. Why h1 << 5 though? Is there a reason why it's specifically 5? Could it be just 1? Help me understand this please.

Lots of ways to write a hashing function that's better than a plain xor and still very fast. This is Bernstein's hash, aka djb2, minus the seed. Multiplying by 33 is not arbitrary, covered in [this Q+A](http://stackoverflow.com/questions/1579721/why-are-5381-and-33-so-important-in-the-djb2-algorithm). — Hans Passant, Mar 15 '16 at 09:18
@HansPassant this is the best aswer my question so far, thank you! — DevNewb, Mar 15 '16 at 10:07

Valery Petrov · Accepted Answer · 2016-03-15T08:29:01.467

5

((h1 << 5) + h1) is equivalent to h1 * 33 and 33 is 3 * 11.
Java uses 31 in some hashes since it's prime and h1 * 31 is (h1 << 5) - h which is almost the same, but without additional overflows which might happen in case of sum.

edited Mar 15 '16 at 08:29

answered Mar 15 '16 at 08:16

Valery Petrov

653
7
19

You may also read some answers here https://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier For example, this one is quiet informative http://stackoverflow.com/a/300111/2577420 (the constants 31, 33, 37, 39, and 41 produce not much collisions) – Valery Petrov Mar 15 '16 at 08:32
1

`h1 << 5` is actually `h1 * 32` – György Kőszeg Mar 15 '16 at 08:33
1

@taffer Which means that after adding `h1` again, it becomes `* 33` or after subtracting it becomes `* 31`. – Lasse V. Karlsen Mar 15 '16 at 08:55

score 1 · Answer 2 · edited Nov 04 '21 at 12:23

1

Found something here here

Read the section on Shift-Add-XOR hash

edited Nov 04 '21 at 12:23

sergtk

10,714
15
75
130

answered Mar 15 '16 at 08:12

KarmaEDV

1,631
16
27

@MarcL. You realize this Answer is from 5 years ago? – KarmaEDV May 11 '21 at 18:06
Yes. The "internet is forever" but individual links are not. That is why [link-only answers are frowned upon](https://stackoverflow.com/help/how-to-answer) (see "Provide Context for Links"). If you can dredge the content up and add some context, I'll be happy to +2. – Marc L. May 12 '21 at 18:52

score 0 · Answer 3 · edited May 23 '17 at 12:24

0

Thanks to @HansPassant for pointing me to below question which best explains what I wanted to know:

Why are 5381 and 33 so important in the djb2 algorithm?

edited May 23 '17 at 12:24

Community

1
1

answered Apr 10 '16 at 18:48

DevNewb

841
7
19

Tuple's GetHashCode hack

3 Answers3