Fibonacci Hashing: The Optimization That the World Forgot | Hacker News Reader

Fibonacci Hashing: The Optimization That the World Forgot

probablydance.com

405 pointsingve75 comments

Don't do this. Use a real hash function that guarantees a highly random distribution, make your hash tables power-of-two sized, and map from hash value to table index using (hash & (size-1)).

The fibonacci constant thing will help clean up the distribution of a bad hash function, but it does nothing for collision resistance if the underlying hash function is weak.

-Austin, author of Murmurhash and SMHasher

Also, there is nothing magic about his fibonacci constant. Any large odd constant with roughly half the bits set at random will do the same thing.

I also did not follow what is special about 2^n/phi. I found this more concise justification: http://mathforum.org/kb/message.jspa?messageID=431065

"Knuth's finding was that the dispersion of indexes for a sequence of consecutive keys is maximized when M is chosen this way, thus a multiplicative hash table with a dense set of keys will have the fewest possible collisions when M approx= 2^N * R."

Although, if the keys are dense, then we could just use the low bits directly. I guess the unstated assumption is that in the real world, we'll have a mix of keys that are sequential and keys that are strided in such a way that using low bits directly would cause a lot of collisions. So we need a multiplicative hash to take care of the latter and we should use 2^n/phi to take care of the former.

Austin, you've done a lot of great work on this. What is the hash function you'd use today for small (<=32byte) keys?

Murmur3 has good distribution properties and is much less code than City/Highway/Spooky. There are also some hashes based on hardware AES instructions (not crypto, just taking advantage of the mixing properties) that are near perfect but I don't recall their names and haven't benchmarked them.

This one? https://github.com/stg7/haesni

Look at the aeshash in the go runtime:

https://github.com/golang/go/blob/master/src/runtime/asm_amd...

The code for these hash tables is open source. You keep repeating that he should be using your hash functions for reasons xyz. Honestly, if you really believe this, show that doing so is better.

Just because you are the author of uvw does not make yo right.

The best is currently Leonid Yuriev's t1ha. See https://github.com/rurban/smhasher/

Note that in contrast with what Andy or DJB say, the collision safety is not a problem of the hash function per se, as you cannot fix collision attacks with any "safer" hash function. You can easily brute-force even the worst of all siphash in under 4min. Safety begins with 256 bits, in a hash table you got typically 10-14, max 32 to attack. It is only making it marginably safer, but much slower. It is only doable by checking collision attacks in the collision scheme, either by collision counting or using a non-attackable collision scheme.

Unfortunately most implementations have no idea, and just go with the slowest of all. The latest such sin done in the linux network stack. I thought at least those guys were above that, but apparently not.

This simple multiplication hash is indeed superior, just with linear probing it has problems. You would use double hashing with another similar constant then. Or find two such constants dynamically, as this would be universal then.

And also note that the upper bits of a hash function are always superior to the lower bits. power-by-2 & checks are thus always worse than right-shifting as with this one.

Thanks. Also, from smhasher text:

"See e.g. A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing

https://infosys.cs.uni-saarland.de/publications/p249-richter...

for a concise overview of the best hash table strategies, confirming that the simpliest Mult hashing (bernstein, FNV*, x17, sdbm) always beat "better" hash functions (Tabulation, Murmur, Farm, ...) when used in a hash table."

The conclusion is not properly stated, it's surely not "always" but there are enough use cases where the simple multiplications (or, even more probably, the "rotate, multiply, xor" and variants) are the fastest in practice.

From the paper:

"We could observe that Mult produces indeed more collisions than the expected amount on uniformly distributed keys. However, this larger amount of collisions does not get highly reflected in the observed performance. Thus, we consider Mult as the best candidate to be used in practice when quality results on high throughputs is desired, but at the cost of a high variance across data distributions."

It’s still a trade-off, but a good choice in some use cases.

I haven't found a usecase yet where a better hash function leads to a faster hash table. Theoretically this would happen with CPUs with extremely slow or small cache.

It's also confirmed with the recent trend to add slower hash functions everywhere, leading to dramatic performance regressions.

> You can easily brute-force even the worst of all siphash in under 4min

You assume that you know the seed or can directly observe the output, which is rare in practice.

> upper bits of a hash function are always superior to the lower bits

Why is that? The identity hash for ints is quite common. And for good hashes, the difference should be negligible.

Phi is the most irrational of the irrational numbers, meaning that successive rational approximations are just slightly better: 1/1, 1/2, 2/3, 3/5, 5/8, 8/13, etc. There are no rational approximations that "jump out" as being much better, so you won't find any unexpected patterns when using it.

The Golden Ratio (why it is so irrational) - Numberphile https://www.youtube.com/watch?v=sj8Sg8qnjOg

In fact, if you actually choose a random odd number, you'll get multiply-shift, which is probably the fastest universal hash function that exists.

Actually there is something special about the using the golden ratio. By some measure it is "the most irrational" number, and that property makes it really good at distributing numbers evenly along an interval.

You can use it to generate a nice sequence of different colours - set the hue to (n * the golden ratio) mod 1.

But I don't know if that property is really necessary for a hash table. I guess only if you are using a terrible key hash.

This is for a hashmap library where the hash functions are user-defined, so a secondary hash is justifiable.

A good secondary hash would be the fmix methods from Murmur, or multiply-byteswap-multiply.

However, having seen a lot of terrible user-defined hashes (I do a bit of consulting on an internal Google mailing list), I strongly advise against rolling your own.

It'd be interesting seeing comparisons there given that the issue here was that none of the widespread implementations he surveyed, including a Google one, even tries to address this, and several of them use methods that are both worse and slower.

Seems like it's something that has gotten little attention.

The secondary hash must primarily be good at mapping the hashed value into a slot: that is, be as cheap as possible (ideally 0 cycles, fib hashing is ~5 cycles) if the primary hash was good while preventing catastrophic performance if the primary hash was bad. All of this without knowing anything about the primary hash.

As a secondary (supplemental) hash, I found the Murmur finalizer methods are ok, but you can get better if you use different constants. See my result in this answer: https://stackoverflow.com/questions/664014/what-integer-hash...

I measured the avalanche effect (the number of output bits that change if a single input bit is changed; should be nearly 16 on average for a 32 bit hash), independence of output bit changes (output bits should not depend on each other), and the probability of a change in each output bit if any input bit is changed.

Wait, I thought the author was saying to use this _after_ using a more secure hash function, not instead of it. Why wouldn't you do that?

Yes, the author specifically points out that there are really two separate steps here: a hash function, and scaling that result down to the number of bits needed at the current number of hash slots.

He's arguing that the fibonacci approach is both faster than modulo and at the same time is better when the input is bad.

He's certainly not arguing it replaces a good hash when you can provide one.

More pointing out that if writing a general hash table implementation you need to expect bad inputs, and since you need to scale the result down anyway you might as well improve on the input if you can do so very cheaply.

It's about "hash tables" (ie associative arrays, HashMap), right?

Is security even an issue in hash functions for this purpose? I honestly don't know, it's not obvious to me that it is.

Perhaps for DOS resistance like the hashdos vulnerability from 2011?

https://nakedsecurity.sophos.com/2011/12/28/large-percentage...

The whole point of fibonacci hashing is making hash tables more resistant to bad hash functions.

Expecting everybody to be using the perfect hash function for each case is extremely naive, and even then, it just takes somebody else refactoring some code and adding a new member to a struct somewhere without updating the hash function to break that completely.

Doubly so if you are making a library where de facto you don't know what the input data might be and hence you don't know in advance what the perfect hash function is.

He's clearly, and obviously not talking about using it as a hash, or even to consider it as a secondary hash as someone mentioned.

The use case according to the article is strictly to replace integer modulo to map into buckets for cases where that operation is the limiting factor. In his case that's when 9ns per key is too much, and roughly 1ns is good.

For small hash tables sometimes the worst case of a linear scan of the entire table is perfectly acceptable, and the additional performance the other 99.999% of the time is a welcome bonus.

He is talking about using it as a hash function and clearly states so. To quote:

> 1. Hash the key > 2. Map the hash value to a slot

> Knuth [Fibonacci Hash] uses the term “hash function” to refer to something that does both step 1 and step 2.

Actually that quote is in the article for the opposite reason. He is referencing that because historically Fibonochi hashing was coupled with a hashing function and that is why it’s overlooked as a mapping function. His article is specifically advocating using the Fibonacci method only for mapping.

He is writing from the context of writing a hash table library where the user is expected to provide their own hashing function.

When someone else pointed out that you need another hash function on the front:

Author: "Why [would] Fibonacci hashing not work as a hash function alone? It should, unless you have a use case that results in lots of Fibonacci numbers being inserted. You can use the identity function as the hash when you use Fibonacci hashing to assign a hash to an index."

Fibonacci hashing takes the form of "h * k>>(64-b)", where k is determined by golden ratio and b is the bit size of the table. This involves one generic multiplication, which is the bottleneck. This multiplication is not strictly necessary. You can replace it with k=1033 for example, which can be implemented as "h+(h<<10)+(h<<3)". This will be a good enough safeguard against naive hash functions but is much faster to compute.

With "h * k>>(64-b)", the result has a cycle of 2^b. Suppose b=3 and you have input 1<<3|1, 2<<3|1 and 3<<3|1, Fibonacci hashing will put them to the same bucket – it is not that effective. A safer strategy is to use a proper integer hash function like Thomas Wang's 32-bit hash function. Although it involves more steps, it only involves plus and bit operations and probably can be computed faster than generic multiplication.

At the end of day, however, Fibonacci hashing or similar ideas only helps when you hash keys to similar integers but has no effect when you hash different keys to the same integer. You have to use a reasonable hash function anyway.

> Although it involves more steps, it only involves plus and bit operations and probably can be computed faster than generic multiplication.

It the most recent popular CPUs the multiplication is exactly "one step" long, that's how wonderfully fast they got to be. See e.g. Agner Fog instruction tables. And where not, the number of "steps" is typically not more than 2 or 3. The multiplication is implemented very efficiently today, unless the CPU has to be with a very low transistor count (linke in some embedded systems). The more exotic CPUs can, of course, be different.

Of course it's a secondary hash. He's mapping buckets by a hash and a shift. This is not a new strategy, and xor, Fibonacci, and "real" hashes fall along a spectrum of average vs worst case runtime tradeoffs.

Summary: The article is looking for an efficient way to map a hash code into a smaller power-of-two-sized range, for use as a hashtable index. It dismisses the common solution, masking off the high bits, because it discards information, and proposes Fibonacci hashing: multiply by the golden ratio and shift down. It gives measurements suggesting this gives better performance in practice, and some theory as to why this might be.

But later it mentions, in passing, a simpler approach: just shift the high bits down and xor! The author only tries doing this as a preprocessing step in front of Fibonacci hashing to avoid "bad patterns". So I'm left wondering: might shift-down-and-xor be good enough on its own?

Yep. The high-bits thing puzzled me as well because I thought shift-and-xor folding was standard practice. Also multiply-and-shift-down still tends to favour certain bits over others.

The article presents Fibonacci hashing as an operation to map a hash code into a smaller range, but it isn't that, really. The operation that does that is still just taking some bits from the hash code.

What Fibonacci hashing actually is is a way of stirring a hash code before use, to spread its entropy out more, so that the bits you end up taking a more likely to be well-distributed.

If your hash codes are already well-distributed, then this is pointless. But if they aren't, it's useful. So, it seems to me that rather than applying Fibonacci hashing to all hash codes, it would be better to use it as the original hash function for types which currently have bad hash functions. This is something a C++ standard library could easily do.

For example, LLVM's libc++ implements string hashing using MurmurHash2 on 32-bit machines, and CityHash on 64-bit machines:

https://github.com/llvm-mirror/libcxx/blob/master/include/__...

https://github.com/llvm-mirror/libcxx/blob/master/include/ut...

But hashes all sizes of integers to themselves:

https://github.com/llvm-mirror/libcxx/blob/master/include/ex...

Changing that to a Fibonacci hash, or a simpler shift-and-xor, could be a quick win.

Provided that libc++'s unordered_map uses power-of-two table sizes, that is. The code is labyrinthine, but i think, rather gloriously, sometimes it does, and sometimes it doesn't:

https://github.com/llvm-mirror/libcxx/blob/master/include/__...

__constrain_hash is a simple but entertaining bit of bit-dickery (reformatted slightly):

    size_t __constrain_hash(size_t __h, size_t __bc) {
        return !(__bc & (__bc - 1))
            ? __h & (__bc - 1)
            : (__h < __bc ? __h : __h % __bc);
    }

The x & (x - 1) tests whether a number is a power of two, because for any number that is not a power of two, subtracting one leaves the top bit set, so the bitwise and will contain at least one set bit. If the bucket count (number of slots) is a power of two, use a mask to extract the bottom bits of the hash. If it's not, do a modulus - but spend a branch to avoid that if the hash is already in the right range, which i'm surprised is a win.

> LLVM's libc++

Great find!

So the library solutions are still often suboptimal, and it's even more easy to hide bad decisions in the C++ sources, so whoever has the approach "just use the default library" should be aware of that once the performance is important.

Yes, even the simple multiplicative constants can significantly improve the hash if it by default doesn't do anything with the input! The libraries definitely should be fixed, and adding the multiplication step is really a simple and fast change for a great benefit.

As an inspiration, Kernighan and Ritchie in their book about C used a simple number 31, and that simple hash is still quite good compared to much more complex and more recent solutions as K&R also haven't used the (I guess misleadingly named) "open addressing" for their hash table. Their solution is amazingly minimalistic and in that context amazingly good for chain hash tables. I wouldn't be surprised if just changing

    return __c;

    return __c * 31;

in the functions discovered would result in great improvement. The good side of such a constant is that it can give the fast and small code even on the old architectures where the "normal" multiplication is slow (e.g. even if there's no fast multiplier the result can be obtained by one shift and one subtraction!). Also on modern architectures using this constant can't result in any performance degradation but improving the hash behavior of these formerly unprocessed inputs guarantees speedup. And there are surely use cases when using more complex functions is much better, e.g. those suggested by aappleby:

https://news.ycombinator.com/item?id=17330787

Back to the "open addressing", if you are rolling your own hash table and don't plan too much hash tables to be present in memory at once, it's often much faster to use "chains" (like in the K&R C book) than trying to store everything only in the table (which is misleadingly often called "open addressing" even if "closed hashing" is a better term) and jump through the table in the collision case. Maintaining lists per entry is typically much faster when the table is fuller, provided the allocation routines are fast.

https://www.strchr.com/hash_functions

By the way, MurmurHash2 or 3 and CityHash are definitely very good functions, the problem is when they aren't used in the library, like, it seems, in libcxx. And in the cases where the simpler code is needed, even a simple * 31 is much, much better than nothing!

And note, it seems there are even problems with these good functions, security wise: apparently the language implementations or the services accepting uncontrolled inputs also have to care about the security aspects of their hash functions:

https://131002.net/siphash/

"Jointly with Martin Boßlet, we demonstrated weaknesses in MurmurHash (used in Ruby, Java, etc.), CityHash (used in Google), and in Python's hash. Some of the technologies affected have switched to SipHash."

"SipHash was designed as a mitigation to hash-flooding DoS attacks. It is now used in the hash tables implementation of Python, Ruby, Perl 5, etc."

"SipHash was designed by Jean-Philippe Aumasson and Daniel J. Bernstein."

> "SipHash was designed as a mitigation to hash-flooding DoS attacks. It is now used in the hash tables implementation of Python, Ruby, Perl 5, etc."

It's also the default hasher in Rust.

Rust's hashing is interesting. Types that want to be hashable implement the Hash trait. What the Hash trait requires is that a type knows how to feed its fields to a Hasher, as a sequence of primitives - it doesn't require that it actually computes a hash itself. It's the Hasher which computes the hash. This is nice, because it's very easy to implement Hash; indeed, so easy that it can be done automatically using a derive macro. The downside is that it's not possible for a type to implement a custom hash that takes particular advantage of its own structure, and so to get a particularly good tradeoff of distribution against performance. The only place to make that tradeoff is in the choice of Hasher, where it has to be made generically across all types.

That said, you can choose the hasher used for individual HashMaps, so if you have a HashMap where you know the keys are integers, you can use a Hasher which just does a Fibonacci hash.

It's not really fair to compare a custom implementation against the standard unordered_map implementations, which need to be fully general. See https://news.ycombinator.com/item?id=9675608

Still, I'm shocked that GCC, LLVM, and boost all assign buckets using modulus, which is very slow. I would love to know the reasoning. I assumed that they mask the high bit (or & with the table size).

Fast hashmaps use xor to mix information from low bits (examples below). Fibonacci hashing amounts to running a second multiplicative hash over your input, which is only worthwhile if you're paranoid about your input distribution.

Java SDK: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/s...

Android (C++): https://android.googlesource.com/platform/system/core/+/mast...

std::unordered_map is a bit of a red-headed stepchild in the C++ world. I'm not surprised that it hasn't had nearly the amount of tuning that hashmaps have had in other languages.

When i asked some C++ers about it, they warned me off using it, for reasons i didn't fully understand, but i got the impression that there are structural reasons why it can never be really fast, so anyone who needs a really fast hashmap uses some non-standard one anyway.

Yes, but it's also important to understand what you lose when using these better-performing hashtables. First thing that comes to mind is that when performing a successful lookup on a std::unordered_map, the reference is guarrantied to be valid until either (a) you erase that element or (b) the table itself is destroyed. Almost all faster hashtables around give up that properties for better lookup performance. Any insert operation might break all references.

So, in a sense, it's a bit unfair because std::unordered_map, in a real-world scenario, will potentially require you to perform less lookup because you can cache the references. With the others, you can't.

Yes, I agree with you that unordered_map should be slower. For context, the author shows off a graph where his custom Fibonacci implementation is the fastest, which proves nothing about Fibonacci hashing.

I had an application several years ago in which the executable was 10x as fast when using khash instead of std::unordered_map.

> It's not really fair to compare a custom implementation against the standard unordered_map implementations, which

But he is comparing the standard unordered_map implementation to his own implementation of the standard unordered_map (same API).

It's the same API, but I highly doubt that his implementation is fully compliant with the C++ standard.

It is, and so is boost::unordered_map, that's the whole point of the comparison. Just check the implementation out.

Source on that claim? Here's a comment chain where the author admits that his library is noncompliant: https://probablydance.com/2017/02/26/i-wrote-the-fastest-has.... Also note the complete lack of a standards test suite.

This library uses Robin Hood hashing for speed. As my original link explains, standard implementations use chained buckets so that users can cache lookups and to have better worst-case performance: https://news.ycombinator.com/item?id=9675964

Hash table design in libraries is an exercise in minimizing the costs of the worst case, and it's made harder by typically only being able to control one side of the equation - the table and not the hash function.

Thus general purpose hash table implementations need to choose whether they will help naive programmers by doing modulus with a prime number of buckets, or if they will leave a potential performance bomb for people who e.g. hash integers to themselves. The article argues for a third way which is somewhere in the middle: faster than prime modulus, but not as dangerous as bit masking.

It's usually easy to beat any general purpose hash table for these reasons, as long as you control the hash function you can tweak your implementation to suit.

The Golden Ratio is proposed as a special multiplier for what is otherwise known as 'linear congruential' psuedorandom number generation. I'm not clear on whether the non-repetitive property of the ratio will benefit its performance at all.

This decimal is computed for 2^64 /1.618... 11400714819323198486 -it looks like this in binary: 1001111000110111011110011011100101111111010010100111110000010101

The runs of 7 ones, 5 zeros and 5 ones could be sub-optimal.

[1] Donald Knuth himself discovered this one for 64bits: 101100001010001111101000010110101001100100101010111111100101101

It contains a run of 7 ones, and 5, but maximum zeros in a row is 4.

I did once mine multipliers for LCGs of different bitlengths by comparing quickly measured ratios in their output to those precomputed from good psuedorandom sequences (average deviation etc) Then having found numbers which achieved the basic signature of random data, they were tested with Marsaglia's old 'diehard' battery of tests - and often passed.

Here is a multiplier discovered for a 32bit LCG 110010011101110100001011

I had a list of them I meant to examine here, but have lost it :(

Anyway, there is plenty of academic work to read on this subject:

1 - https://en.wikipedia.org/wiki/Linear_congruential_generator#...

It's a strangely distinct memory that when I needed to implement a hash table in 1992, I read Knuth--in 1992 I guess there wasn't much else to do--and apparently read it correctly. The beauty of the golden ratio technique made it memorable and I've been doing "multiply by 2^n/phi" ever since! In fact just last week I launched Ruby to calculate it again...

I wonder if, under some circumstances, one ought to use this instead for optimality of this or something similar:

https://en.wikipedia.org/wiki/Plastic_number for a similar use. It shares a property with phi which no other irrational shares with it (They are known as the only two Morphic numbers, which one must avoid confabulating with a similarly named concept whose name I can't recall right now.). And Knuth liked it (well, the reciprocal of it's square anyway, albeit the cubed version seems more interesting to me.), but never found any application for it. (He even made a special TeX symbol for the square of it, 'High Phi', see Wikipedia for details.)

As @twic and the OP discussed, the equal distribution of numbers within a defined range is naturally achieved through low discrepancy sequences (eg recurrence,Halton, Sobol, etc..) Furthermore, in ultra high-speed / low-level computing situations the additive recurrence methods are often preferred due to the incredibly fast and simple method of calculating the each successive term simply by adding (modulo) a constant value to the previous term.

For the one-dimensional case, it is well known, and relatively easily proven that the the additive recurrence method based on the golden ratio offers the optimal 'evenness' [low discrepancy] in distribution [1]. For higher dimensions, it is still an open research question as to how to create provably optimal methods. However, one of my recent blog posts [2] explores the idea that a generalization of the golden ratio, produces results that are possibly optimal, and better than existing contemporary low discrepancy sequences. In the one dimensional case, the critical additive constant is of course, the golden ratio. In the two dimensional case, the additive constant is based on integral powers of the plastic number. The generalization to even higher dimensions follows other Pisot numbers.

[1] https://en.wikipedia.org/wiki/Low-discrepancy_sequence#Addit...

[2] http://www.extremelearning.com.au/unreasonable-effectiveness...

If you need to map a uniform b-bit integer x into the [0, n) range, using ((x * n) >> b) will work just as well as the modulo in terms of (quasi-)even distribution, and it avoids integer division.

The idea is just to imagine x as a b-bit fixed-point uniformly random number in [0, 1), and rescaling it by multiplication.

This works great for hash tables whose size is not a power of 2, provided that you start from a good hash function.

Moral of the story: Always always consult Knuth.

Unless Knuth is outdated. With hash tables Knuth is seriously outdated. With hash functions you can consult his test functions, but he is also outdated.

E.g. the CRC scheme is the fastest by far (one even exists in HW), but too easily attackable. Trivial really, any 10 year old can do that, due to some unfortunate CRC properties.

> too easily attackable. Trivial really, any 10 year old can do that

In another comment you write:

> You can easily brute-force even the worst of all siphash in under 4min.

Can you please write what you mean by those statements? Is it about the "hash-flooding DoS" attacks or something else? Can you share a little more of your insights?

See the relevant smhasher discussions.

"smhasher discussions" where? This is not an answer.

Especially regarding "4 min" re siphash, about which kind of attack do you talk about at all, under which conditions?

The writings of those who try to protect from flooding attacks are more specific, e.g.:

https://github.com/google/highwayhash

"The author of SipHash has published C++ programs to generate" "'universal (key-independent) multicollisions' for CityHash and Murmur. Similar 'differential' attacks are likely possible for any hash function consisting only of reversible operations"

"attackers are only looking for multiple m mapping to the same bin rather than identical hash values."

"a strong hash function is not, by itself, sufficient to protect a chained hash table from flooding attacks. However, strong hash functions are important parts of two schemes for preventing denial of service. Using weak hash functions can slightly accelerate the best-case and average-case performance of a service, but at the risk of greatly reduced attack costs and worst-case performance."

Also, please also be specific about the "regressions" you mention in another post. Your statements, in the form they are, aren't of much use.

> any 10 year old can do that

Is this kind of hyperbole really necessary?

Yes, because almost nobody knows. But when you see it it's super trivial. Knuth would be ashamed.

Start with Knuth, don't end with him. ;-)

The article attempts to explain this property of phi:

> Maybe you have a picture of a flower, and you want to implement “every time the user clicks the mouse, add a petal to the flower.” In that case you want to use the golden ratio: Make the angle from one petal to the next 360/phi and you can loop around the circle forever, adding petals, and the next petal will always fit neatly into the biggest gap and you’ll never loop back to your starting position.

And points to a video. I think there's a much clearer explanation which shows how this is because (in some sense) phi is the "most irrational" ratio, stemming from its derivation from continued fractions: https://www.youtube.com/watch?v=sj8Sg8qnjOg

I freely admit I have not a clue how this does or doesn't improve hash algos, but it's a cool video! :)

If you have a reasonable hash function, why is power-of-two and bitmasking bad? If you're uniformly distributed over a range N you'll be uniformly distributed over N/2

It isn’t. You are correct. This is useful to support the underlying hash function but at that point you might as well just improve that and take the power of two, bitmask approach.

I think that boils down the problem nicely: if you're using a hash table or writing your own for a specialised use-case, you should pick a good hash function.

But if you're writing a general purpose hashtable implementation you have to deal with the fact that a lot of users won't use a good hash while some will, so you need to find a tradeoff between using their hash as-is and mixing it up to improve on the bad ones.

The latter need to come almost free, however, or you'll ruin performance for those who actually do their homework.

I think the search part is implementing the Fibonacci Search Technique[0]. It’s related to Golden ratio search[1].

[0] https://en.wikipedia.org/wiki/Fibonacci_search_technique

[1] https://en.wikipedia.org/wiki/Golden-section_search

On a related note, growing a hash table by a factor of two might not be optimal due to interactions with the memory allocator, more specifically the new allocation will be larger than all previous allocations combined so that you can not reuse previously allocated memory. Starting with m buckets one will allocate m * 2^t buckets after t growing operation, in total m * (2^(t + 1) - 1), but that is one bucket less than the m * 2^(t + 1) buckets required for growing again [1]. Whether this might be an issue obviously depends on the memory allocator used and other factors like the usage of a compacting garbage collector, phi appears again when looking for a better growth factor, and I will just leave this link to a Stack Overflow question [2] as a starting point because I am unable to find the article I had initially in mind.

[1] Assuming you can somehow incorporate the current allocation, previously freed were only m * (2^t - 1) buckets.

[2] https://stackoverflow.com/questions/2369467/why-are-hash-tab...

Light travels around a foot in a nanosecond.

Makes thinking about processing times a bit easier when you can visualise it as a distance.

https://www.youtube.com/watch?v=JEpsKnWZrJ8

This sounds quite similar to the fastrange [0] method. I’ve used it for random sampling but not a hash table. It’d be great for non-power-of-two tables while avoiding integer modulus.

[0] https://github.com/lemire/fastrange

fastrange is discussed in the article.

Am I correct in thinking that using this Fibonacci method of mapping hash values to buckets will solve the "accidentally quadratic" behavior in a Robin Hood hash table? Rust's default hash table suffered from the issue but their fix was much less elegant.

The comments here have given me an idea for my own hash tables.

Rather than accounting for poor hash functions using phi or fmix, I'm going to measure the hash function's distribution at run time and throw an error if its bad. For release builds I'll disable these checks.

Runtime errors seem a little bit fussy, but "try a fast approach that usually works, detect worst-case behavior, then fall back to a thing that's usually slower but avoids the worst case" is a common implementation pattern (think introsort). In principle, you could start with something trivial as your hash, then rehash your key with a better-behaved-but-slower function if your normal probing strategy is going on far longer than it ought to given the load factor.

But we rarely see that, and there are probably good reasons. Hash tables are more rarely the bottleneck in the real world than in benchmarks, and when they are an issue, other factors (size, concurrency, weird pathologies, mem latency) may matter more often than hashing time.

is there a way to use this technique for consistent hashing?

Great article, really blow my mind

Reply on news.ycombinator.com