132

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 '19 at 23:00
219

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.

  • 10
    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 '19 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 '19 at 9:20
  • 9
    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 '19 at 16:44
  • 3
    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 '19 at 17:59
  • 4
    @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 '19 at 3:30
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.

example:

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
  • 30
    "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. – Duncan X Simpson Dec 16 '19 at 19:53
  • 15
    @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 '19 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 '19 at 0:47
  • 14
    "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 '19 at 7:42
  • 7
    only the Sith deal in absolutes! – NKCampbell Dec 17 '19 at 14:52
5
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. – Matthieu M. Dec 16 '19 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 '19 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 :( – Matthieu M. Dec 16 '19 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 '19 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.