In code dealing with hash tables, I often find the constant 0x9e3779b9 or sometimes 0x9e3779b1. For example

hash = n * 0x9e3779b1 >>> 24

Why is this particular value used?

  • 3
    Some specific citations of code with this constant would be helpful. I found it in SQLite, for example.
    – dan04
    Dec 17, 2019 at 23:00

3 Answers 3


0x9e3779b9 is the integral part of the Golden Ratio's fractional part 0.61803398875… (sqrt(5)-1)/2, multiplied by 2^32.

Hence, if φ = (sqrt(5)+1)/2 = 1.61803398875 is the Golden Ratio, the hash function calculates the fractional part of n * φ, which has nice scattering properties. To convince yourself, just create a scatter plot of (n, n*c-FLOOR(n*c)) in your favourite spreadsheet, replacing c with φ, e, π, etc. Some interesting real-life issues when getting it wrong are described in https://lkml.org/lkml/2016/4/29/838.

This method is often referred to as "Golden Ratio Hashing", or "Fibonacci Hashing" and was popularised by Donald Knuth (The Art of Computer Programming: Volume 3: Sorting and Searching). In number theoretical terms, it mostly boils down to the Steinhaus Conjecture (https://en.wikipedia.org/wiki/Three-gap_theorem) and the recursive symmetry of the fractional parts of the multiples of the Golden Ratio φ.

Occasionally, you may also see 0x9e3779b1, which is the prime closest to 0x9e3779b9 (and appears to be a bit of "cargo cult" as this is not a modular hash). Similarly, 0x9e3779b97f4a7c15 and 0x9e3779b97f4a7c55 are the 64 bit equivalents of these numbers.

  • 11
    btw contrary to your answer, Linus claims in your link that $\phi$ is no better than $e$ or $\pi$, or any constant that "has a reasonable bit distribution".
    – stewbasic
    Dec 17, 2019 at 0:58
  • 2
    It's never a modular hash, which would be a hash of the form x % m. It's a multiplicative hash, and it's still a multiplicative hash if you use an other constant than Knuth recommended.
    – user353249
    Dec 17, 2019 at 9:20
  • 10
    The nice scattering properties do not actually come from the golden ratio. There is nothing inherently magical about the golden ratio other than people trying to find something divine in it for over half a millenium. That constant isn't any worse than thousand others, though, so one can as well use it. The "magic" of this class of hash functions lies in the combination of multiplying with a reasonably large odd constant, and then shifting/rotating to the right. Which will distribute bits in both directions (up and down).
    – Damon
    Dec 17, 2019 at 16:44
  • 4
    Reading the actual Knuth source states the following (page 517pp in my third edition), paraphrased: There exists a theorem for all irrational numbers that shows the good scattering properties but some irrational numbers lead to more uniformly distributed sequences and Exercise 9 proves that the golden ratio leads to the "most uniformly distributed sequences". So yes the claim that pi or e would work just as well is unproven afaics. Although I guess they might fall into the same category as phi (have fun whoever wants to prove or disprove that though).
    – Voo
    Dec 18, 2019 at 17:59
  • 7
    @Damon That's not true. The golden ratio is special. It's the "most irrational" number! And this is directly connected to its good equidistribution properties. See mathoverflow.net/a/304860.
    – user76284
    Dec 19, 2019 at 3:30

The other answers explain the intent behind those magic numbers, which is probably what you wanted to know. However one could say that where "they come from" is from bad programming practices. Magic numbers are bad, and they should never be used. Constants such as those mentioned should be given proper descriptive variable names, and perhaps even comments should be added to where they are defined. Then, every appearance of the values in the code should be in the form of the named variable. Where this the case in the codes where you met those values, you would not have been preplexed by their intent in the first place.


Bad example - uses magic numbers

hash = n * 0x9e3779b1

Better example - with comments and meaningful variable

# Golden Ratio constant used for better hash scattering
# See https://softwareengineering.stackexchange.com/a/402543 
GOLDEN_RATIO = 0x9e3779b1
hash = n * GOLDEN_RATIO
  • 31
    "Magic numbers are bad, and should never be used." Absolute general statements are almost always false. See crypto.stackexchange.com/a/76301 for some good reasons AES uses magic numbers. Dec 16, 2019 at 19:53
  • 16
    @DuncanXSimpson That linked answer is mostly wrong, and is clearly written by someone who doesn't code. The first point about parameterisation is kind of correct, but this answer doesn't suggest that. As for the other two points in the linked answer, they are simply flat wrong. All modern programming languages provide some mechanism for setting constant values, and most compilers additionally can optimise unchanging variable values. The linked code from the linked question even uses constant values with explanatory comments, in defiance of that incorrect answer.
    – Graham
    Dec 16, 2019 at 22:56
  • 24
    @Graham I think you and Duncan are using the term "magic number" differently and talking past each other. You and isilanes are talking about how the algorithm is expressed in code; specifically whether the source code makes clear the reason for using a particular value. This has no impact on behaviour. The linked question (which perhaps misuses the phrase "magic number") is about changing the behaviour of an encryption algorithm, making those values parameters supplied as input rather than constants. With this understanding, the three points in that answer make sense.
    – stewbasic
    Dec 17, 2019 at 0:47
  • 15
    "Absolute general statements are almost always false." Amen to that. For example the absolute general statement that absolute general statements are false is false (as you probably realized before sending the comment and added "almost" to not make your answer ironic). Some things are just always wrong, for example magic numbers (meaning unexplained arbitrary values) in code :)
    – isilanes
    Dec 17, 2019 at 7:42
  • 7
    only the Sith deal in absolutes!
    – NKCampbell
    Dec 17, 2019 at 14:52
In code dealing with hash tables, I often find the constant 0x9e3779b9 or sometimes 0x9e3779b1

The other answer correctly explained why this value is used. However, if you often find this constant, what you may not be realizing that you often find code vulnerable to hash flooding attacks.

There are two strategies against hash flooding attacks:

  1. Use a secure hash function having a secret random seed. Your hash function doesn't have a secret random seed. Murmurhash3_32 has a secret random seed, but it has seed-independent multicollisions due to the small internal state. The best hash function having near cryptographical security and still nearly acceptable performance is probably SipHash. Unfortunately, it is slow, although not as slow as SHA512 etc.

  2. Use a hash function that is quick to calculate (such as the hash function you found, or Murmurhash3_32), and make each hash bucket into the root of a balanced binary search tree. So, an ordinary separately chained hash table has each bucket as a linked list, which is slow if lots of values hash to the same bucket. By making it a balanced binary search tree such as AVL tree or red-black tree, you still have guaranteed worst-case performance.

My opinion is that (2) is better because SipHash is so slow. Also, in operating system kernel space there may not be enough entropy to create a secret random seed early in boot-up stage, so in kernel space you may not have the ability to create random numbers early in bootup.

Hash tables are widely misused. It is easy to bring down many systems to a practical halt merely by sending lots of values that hash to the same bucket.

  • Note that a random seed can be re-seeded every time the hash table grows -- thus even if at boot-up a kernel has no entropy to draw from, so long as the attack comes later there is no problem. Dec 16, 2019 at 12:38
  • @MatthieuM. That's assuming you accept the latency of a hash table growth operation. In many cases, kernels cannot accept that and set the hash table size to a fixed value based on the memory amount in the computer.
    – juhist
    Dec 16, 2019 at 12:39
  • 3
    If that's a problem, it's also solvable: linear re-hashing which triggers on number of collisions would allow reseeding -- you'd just need a double look-up during the transition period. In general, I do prefer linear re-hashing, however hash map implementations are generally tuned for throughput over latency :( Dec 16, 2019 at 12:46
  • Amen on easy to calculate. Generally mod is not easy easy as a substring or high order truncation. Security and seeding are generally irrelevant if you are only balancing queues or generating a synthetic key. It may never need to be calculated again.
    – mckenzm
    Dec 18, 2019 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.