Now Reading
Fibonacci Hashing: The Optimization that the World Forgot (or: a Higher Various to Integer Modulo)

Fibonacci Hashing: The Optimization that the World Forgot (or: a Higher Various to Integer Modulo)

2023-04-28 05:43:50

I not too long ago posted a weblog submit a few new hash desk, and every time I do one thing like that, I study at the least one new factor from my feedback. In my final remark part Wealthy Geldreich talks about his hash desk which makes use of “Fibonacci Hashing”, which I hadn’t heard of earlier than. I’ve labored rather a lot on hash tables, so I assumed I’ve at the least heard of all the massive necessary tips and strategies, however I additionally know that there are such a lot of small tweaks and enhancements which you could’t probably know all of them. I assumed this is likely to be one other neat small trick so as to add to the gathering.

Seems I used to be improper. This can be a massive one. And everybody needs to be utilizing it. Hash tables shouldn’t be prime quantity sized and they need to not use an integer modulo to map hashes into slots. Fibonacci hashing is simply higher. But someway no person is utilizing it and plenty of massive hash tables (together with all the massive implementations of std::unordered_map) are a lot slower than they need to be as a result of they don’t use Fibonacci Hashing. So let’s determine this out.

To begin with how do we discover out what this Fibonacci Hashing is? Wealthy Geldreich referred to as it “Knuth’s multiplicative methodology,” however earlier than trying it up in The Artwork of Laptop Programming, I attempted googling for it. The highest consequence proper now’s this page which is outdated, with a copyright from 1997. Fibonacci Hashing isn’t talked about on Wikipedia. You will see a number of extra pages mentioning it, largely from universities who current this of their “introduction to hash tables” materials.

From that I assumed it’s a kind of strategies that they educate in college, however that no person finally ends up utilizing as a result of it’s truly costlier for some cause. There are many these in hash tables: Issues that get taught as a result of they’re good in concept, however they’re dangerous in observe so no person makes use of them.

Besides someway, on this one, the wires received crossed. Everybody makes use of the algorithm that’s unnecessarily gradual and results in extra issues, and no person is utilizing the algorithm that’s quicker whereas on the similar time being extra strong to problematic patterns. Knuth talked about Integer Modulo and about Fibonacci Hashing, and all people ought to have taken away from that that they need to use Fibonacci Hashing, however they didn’t and all people makes use of integer modulo.

Earlier than diving into this, let me simply present you the outcomes of a easy benchmark: Trying up objects in a hash desk:

unordered_map_comparison_larger_font

On this benchmark I’m evaluating numerous unordered_map implementations. I’m measuring their lookup pace when the hot button is simply an integer. On the X-axis is the dimensions of the container, the Y-axis is the time to seek out one merchandise. To measure that, the benchmark is simply spinning in a loop calling discover() on this container, and on the finish I divide the time that the loop took by the variety of iterations within the loop. So on the left hand aspect, when the desk is sufficiently small to slot in cache, lookups are quick. On the appropriate hand aspect the desk is simply too massive to slot in cache and lookups grow to be a lot slower as a result of we’re getting cache misses for many lookups.

However the principle factor I need to draw consideration to is the pace of ska::unordered_map, which makes use of Fibonacci hashing. In any other case it’s a very regular implementation of unordered_map: It’s only a vector of linked lists, with each ingredient being saved in a separate heap allocation. On the left hand aspect, the place the desk matches in cache, ska::unordered_map might be greater than twice as quick because the Dinkumware implementation of std::unordered_map, which is the following quickest implementation. (that is what you get while you use Visible Studio)

So when you use std::unordered_map and look issues up in a loop, that loop may very well be twice as quick if the hash desk used Fibonacci hashing as an alternative of integer modulo.

The way it works

So let me clarify how Fibonacci Hashing works. It’s associated to the golden ratio phi=1.6180339... which is expounded to the Fibonacci numbers, therefore the identify. One property of the Golden Ratio is that you need to use it to subdivide any vary roughly evenly with out ever looping again to the beginning place. What do I imply by subdividing? For instance if you wish to divide a circle into 8 sections, you’ll be able to simply make every step across the circle be an angle of 360^circ/8 levels. And after eight steps you’ll be again at the beginning. And for any n variety of steps you need to take, you’ll be able to simply change the angle to be 360^circ/n. However what when you don’t know forward of time what number of steps you’re going to take? What if the n worth is set by one thing you don’t management? Like possibly you have got an image of a flower, and also you need to implement “each time the person clicks the mouse, add a petal to the flower.” In that case you need to use the golden ratio: Make the angle from one petal to the following 360^circ/phi and you’ll loop across the circle eternally, including petals, and the following petal will at all times match neatly into the largest hole and also you’ll by no means loop again to your beginning place. Vi Hart has video concerning the subject:

(The video is a component two of a three-part collection, half one is here)

I knew about that trick as a result of it’s helpful in procedural content material technology: Any time that you really want one thing to look randomly distributed, however you need to make sure that there are not any clusters, you must at the least attempt to see if you need to use the golden ratio for that. (if that doesn’t work, Halton Sequences are additionally price making an attempt earlier than you strive random numbers) However someway it had by no means occurred to me to make use of the identical trick for hash tables.

So right here’s the concept: Let’s say our hash desk is 1024 slots giant, and we need to map an arbitrarily giant hash worth into that vary. The very first thing we do is we map it utilizing the above trick into the complete 64 bit vary of numbers. So we multiply the incoming hash worth with 2^{64}/phi approx 11400714819323198485. (the quantity 11400714819323198486 is nearer however we don’t need multiples of two as a result of that might throw away one bit) Multiplying with that quantity will overflow, however simply as we wrapped across the circle within the flower instance above, it will wrap round the entire 64 bit vary in a pleasant sample, giving us a fair distribution throughout the entire vary from 0 to 2^{64}. For example, let’s simply take a look at the higher three bits. So we’ll do that:

size_t fibonacci_hash_3_bits(size_t hash)
{
    return (hash * 11400714819323198485llu) >> 61;
}

This may return the higher three bits after doing the multiplication with the magic fixed. And we’re simply three bits as a result of it’s simple to see how the golden ratio wraparound behaves once we simply take a look at the highest three bits. If we cross in some small numbers for the hash worth, we get the next outcomes from this:

fibonacci_hash_3_bits(0) == 0
fibonacci_hash_3_bits(1) == 4
fibonacci_hash_3_bits(2) == 1
fibonacci_hash_3_bits(3) == 6
fibonacci_hash_3_bits(4) == 3
fibonacci_hash_3_bits(5) == 0
fibonacci_hash_3_bits(6) == 5
fibonacci_hash_3_bits(7) == 2
fibonacci_hash_3_bits(8) == 7
fibonacci_hash_3_bits(9) == 4
fibonacci_hash_3_bits(10) == 1
fibonacci_hash_3_bits(11) == 6
fibonacci_hash_3_bits(12) == 3
fibonacci_hash_3_bits(13) == 0
fibonacci_hash_3_bits(14) == 5
fibonacci_hash_3_bits(15) == 2
fibonacci_hash_3_bits(16) == 7

This offers a reasonably even distribution: The quantity 0 comes up 3 times, all different numbers come up twice. And each quantity is much faraway from the earlier and the following quantity. If we improve the enter by one, the output jumps round fairly a bit. So that is beginning to appear to be hash perform. And in addition a great way to map a quantity from a bigger vary into the vary from 0 to 7.

In reality we have already got the entire algorithm proper right here. All we’ve got to do to get an arbitrary energy of two vary is to alter the shift quantity. So if my hash desk is measurement 1024, then as an alternative of simply trying on the prime 3 bits I need to take a look at the highest 10 bits. So I shift by 54 as an alternative of 61. Simple sufficient.

Now when you truly run a full hash perform evaluation on this, you discover that it doesn’t make for an excellent hash perform. It’s not horrible, however you’ll rapidly discover patterns. But when we make a hash desk with a STL-style interface, we don’t management the hash perform anyway. The hash perform is being supplied by the person. So we’ll simply use Fibonacci hashing to map the results of the hash perform into the vary that we would like.

The issues with integer modulo

So why is integer modulo dangerous anyhow? Two causes: 1. It’s gradual. 2. It may be actual silly about patterns within the enter information. So to begin with how gradual is integer modulo? In the event you’re simply doing the easy implementation like this:

size_t hash_to_slot(size_t hash, size_t num_slots)
{
    return hash % num_slots;
}

Then that is actual gradual. It takes roughly 9 nanoseconds on my machine. Which, if the hash desk is in cache, is about 5 instances longer than the remainder of the lookup takes. In the event you get cache misses then these dominate, nevertheless it’s not good that this integer modulo is making our lookups a number of instances slower when the desk is in cache. Nonetheless the GCC, LLVM and enhance implementations of unordered_map use this code to map the hash worth to a slot within the desk. And they’re actually gradual due to this. The Dinkumware implementation is slightly bit smarter: It takes benefit of the truth that when the desk is sized to be an influence of two, you are able to do an integer modulo by utilizing a binary and:

size_t hash_to_slot(size_t hash, size_t num_slots_minus_one)
{
    return hash & num_slots_minus_one;
}

Which takes roughly 0 nanoseconds on my machine. Since num_slots is an influence of two, this simply chops off all of the higher bits and solely retains the decrease bits. So as a way to use this you must make certain that each one the necessary info is within the decrease bits. Dinkumware ensures this by utilizing a extra difficult hash perform than the opposite implementations use: For integers it makes use of a FNV1 hash. It’s a lot quicker than a integer modulo, nevertheless it nonetheless makes your hash desk twice as gradual because it may very well be since FNV1 is dear. And there’s a larger drawback: In the event you present your personal hash perform since you need to insert a customized kind into the hash desk, you must learn about this implementation element.

We have now been bitten by that implementation element a number of instances at work. For instance we had a customized ID kind that’s only a wrapper round a 64 bit integer which consists from a number of sources of data. And it simply so occurs that that ID kind has actually necessary info within the higher bits. It took surprisingly lengthy till somebody observed that we had a gradual hash desk in our codebase that might actually be made 100 instances quicker simply by altering the order of the bits within the hash perform, as a result of the integer modulo was chopping off the higher bits.

Different tables, like google::dense_hash_map additionally use an influence of two hash measurement to get the quick integer modulo, nevertheless it doesn’t present it’s personal implementation of std::hash<int> (as a result of it will possibly’t) so you must be actual cautious about your higher bits when utilizing dense_hash_map.

Speaking about google::dense_hash_map, integer modulo brings much more issues with it for open addressing tables it. As a result of when you retailer all of your information in a single array, patterns within the enter information instantly begin to matter extra. For instance google::dense_hash_map will get actually, actually gradual when you ever insert loads of sequential numbers. As a result of all these sequential numbers get assigned slots proper subsequent to one another, and when you’re then making an attempt to search for a key that’s not within the desk, you must probe by means of loads of densely occupied slots earlier than you discover your first empty slot. You’ll by no means discover this when you solely search for keys which are truly within the map, however unsuccessful lookups might be dozens of instances slower than they need to be.

Regardless of these flaws, all the quickest hash desk implementations use the “binary and” strategy to assign a hash worth to a slot. And then you definately normally attempt to compensate for the issues by utilizing a extra difficult hash perform, like FNV1 within the Dinkumware implementation.

Why Fibonacci Hashing is the Answer

Fibonacci hashing solves each of those issues. 1. It’s actually quick. It’s a integer multiplication adopted by a shift. It takes roughly 1.5 nanoseconds on my machine, which is quick sufficient that it’s getting actual arduous to measure. 2. It mixes up enter patterns. It’s such as you’re getting a second hashing step free of charge after the primary hash perform finishes. If the primary hash perform is definitely simply the id perform (appropriately for integers) then this offers you at the least slightly bit of blending that you simply wouldn’t in any other case get.

However actually it’s higher as a result of it’s quicker. Once I labored on hash tables I used to be at all times annoyed by how a lot time we’re spending on the straightforward drawback of “map a big quantity to a small quantity.” It’s actually the slowest operation within the hash desk. (exterior of cache misses in fact, however let’s fake you’re doing a number of lookups in a row and the desk is cached) And the one different was the “energy of two binary and” model which discards bits from the hash perform and might result in all types of issues. So your choices are both gradual and secure, or quick and dropping bits and getting doubtlessly many hash collisions when you’re ever not cautious. And all people had this drawback. I googled rather a lot for this drawback considering “absolutely any person should have methodology for bringing a big quantity right into a small vary” however all people was both doing gradual or dangerous issues. For instance here is an strategy (referred to as “fastrange”) that just about re-invents Fibonacci hashing, nevertheless it exaggerates patterns the place Fibonacci hashing breaks up patterns. It’s the identical pace as Fibonacci hashing, however after I’ve tried to make use of it, it by no means labored for me as a result of I might instantly discover patterns in my hash perform that I wasn’t even conscious of. (and with fastrange your delicate patterns instantly get exaggerated to be big issues) Regardless of its issues it’s being utilized in Tensorflow, as a result of all people is determined for a quicker answer of this the issue of mapping a big quantity right into a small vary.

If Fibonacci Hashing is so nice, why is no person utilizing it?

That’s a difficult query as a result of there’s so little details about Fibonacci hashing on the Web, however I believe it has to do with a historic misunderstanding. In The Artwork of Laptop Programming, Knuth introduces three hash features to make use of for hash tables:

  1. Integer Modulo
  2. Fibonacci Hashing
  3. One thing associated to CRC hashes

The inclusion of the integer modulo on this record is a bit bizarre from as we speak’s perspective as a result of it’s not a lot of a hash perform. It simply maps from a bigger vary right into a smaller vary, and doesn’t in any other case do something. Fibonacci hashing is definitely a hash perform, not the best hash perform, nevertheless it’s introduction. And the third one is simply too difficult for me to grasp. It’s one thing about arising with good coefficients for a CRC hash that has sure properties about avoiding collisions in hash tables. In all probability very intelligent, however any person else has to determine that one out.

So what’s occurring right here is that Knuth makes use of the time period “hash perform” otherwise than we use it as we speak.  As we speak the steps in a hash desk are one thing like this:

  1. Hash the important thing
  2. Map the hash worth to a slot
  3. Examine the merchandise within the slot
  4. If it’s not the appropriate merchandise, repeat step 3 with a unique merchandise till the appropriate one is discovered or some finish situation is met

We use the time period “hash perform” to seek advice from step 1. However Knuth makes use of the time period “hash perform” to seek advice from one thing that does each step 1 and step 2. So when he refers to a hash perform, he means one thing that each hashes the incoming key, and assigns it to a slot within the desk. So if the desk is barely 1024 objects giant, the hash perform can solely return a worth from 0 to 1023. This explains why “integer modulo” is a hash perform for Knuth: It doesn’t do something in step 1, nevertheless it does work nicely for step 2. So if these two steps have been only one step, then integer modulo does job at that one step because it does job at our step 2. However once we take it aside like that, we’ll see that Fibonacci Hashing is an enchancment in comparison with integer modulo in each steps. And since we’re solely utilizing it for step 2, it permits us to make use of a quicker implementation for step 1 as a result of the hash perform will get some assist from the extra mixing that Fibonacci hashing does.

However this distinction in phrases, the place Knuth makes use of “hash perform” to imply one thing completely different than “hash perform” means for std::unordered_map, explains to me why no person is utilizing Fibonacci hashing. When judged as a “hash perform” in as we speak’s phrases, it’s not that nice.

After I discovered that Fibonacci hashing isn’t talked about wherever, I did extra googling and was extra profitable trying to find “multiplicative hashing.” Fibonacci hashing is only a easy multiplicative hash with a well-chosen magic quantity. However the language that I discovered describing multiplicative hashing explains why no person is utilizing this. For instance Wikipedia has this to say about multiplicative hashing:

Multiplicative hashing is an easy kind of hash perform usually utilized by academics introducing college students to hash tables. Multiplicative hash features are easy and quick, however have greater collision charges in hash tables than extra subtle hash features.

So simply from that, I actually don’t really feel inspired to take a look at what this “multiplicative hashing” is. Or to get a sense for a way academics introduce this, here is MIT teacher Erik Demaine (who’s movies I very a lot suggest) introducing hash features, and he says this:

I’m going to provide you three hash features. Two of that are, let’s say frequent observe, and the third of which is definitely theoretically good. So the primary two should not good theoretically, you’ll be able to show that they’re dangerous, however at the least they offer you some taste.

Then he talks about integer modulo, multiplicative hashing, and a mix of the 2. He doesn’t point out the Fibonacci hashing model of multiplicative hashing, and the introduction most likely wouldn’t encourage individuals to go hunt down extra info it.

So I believe individuals simply study that multiplicative hashing isn’t hash perform, and so they by no means study that multiplicative hashing is a good way to map giant values right into a small vary.

After all it may be that I missed some unknown massive draw back to Fibonacci hashing and that there’s a actual good cause why no person is utilizing this, however I didn’t discover something like that. Nevertheless it may very well be that I didn’t discover something dangerous about Fibonacci hashing just because it’s arduous to seek out something in any respect about Fibonacci hashing, so let’s do our personal evaluation:

Analyzing Fibonacci Hashing

So I’ve to admit that I don’t know a lot about analyzing hash features. It looks like one of the best check is to see how shut a hash perform will get to the strict avalanche criterion which “is happy if, every time a single enter bit is modified, every of the output bits modifications with a 50% chance.”

To measure that I wrote a small program that takes a hash H, and runs it by means of Fibonacci hashing to get a slot within the hash desk S. Then I alter a single bit in H, giving me H', and after I run that by means of Fibonacci hashing I get a slot S'. Then I measure relying on which bit I modified in H', which bits are prone to change in S' in comparison with S and which bits are unlikely to alter.

I then run that very same check each time after I doubled a hash desk, as a result of with completely different measurement hash tables there are extra bits within the output: If the hash desk solely has 4 slots, there are solely two bits within the output. If the hash desk has 1024 slots, there are ten bits within the output. Lastly I coloration code the consequence and plot the entire thing as an image that appears like this:

Avalanche_fibonacci.png

Let me clarify this image. Every row of pixels represents one of many 64 bits of the enter hash. The underside-most row is the primary bit, the topmost row is the sixty fourth bit. Every column represents one bit within the output. The primary two columns are the output bits for a desk of measurement 4, the following three columns are the output bits for a desk of measurement 8 and many others. till the final 23 bits are for a desk of measurement eight million. The colour coding means this:

  • A black pixel signifies that when the enter pixel for that row modifications, the output pixel for that column has a 50% probability of fixing. (that is ideally suited)
  • A blue pixel implies that when the enter pixel modifications, the ouput pixel has a 100% probability of fixing.
  • A purple pixel implies that when the enter pixel modifications, the output pixel has a 0% probability of fixing.

For a extremely good hash perform the complete image could be black. So Fibonacci hashing isn’t a extremely good hash perform.

The worst sample we are able to see is on the prime of the image: The final little bit of the enter hash (the highest row within the image) can at all times solely have an effect on the final little bit of the output slot within the desk. (the final column of every part) So if the desk has 1024 slots, the final little bit of the enter hash can solely decide the bit within the output slot for the quantity 512. It should by no means change another bit within the output. Decrease bits within the enter can have an effect on extra bits within the output, so there’s extra mixing occurring for these.

Is it dangerous that the final bit within the enter can solely have an effect on one bit within the output? It will be dangerous if we used this as a hash perform, nevertheless it’s not essentially dangerous if we simply use this to map from a wide variety right into a small vary. Since every row has at the least one blue or black pixel in it, we might be sure that we don’t lose info, since each bit from the enter will probably be used. What could be dangerous for mapping from a wide variety right into a small vary is that if we had a row or a column that has solely purple pixels in it.

Let’s additionally take a look at what this is able to appear to be for integer modulo, beginning with integer modulo utilizing prime numbers:

Avalanche_prime.png

This one has extra randomness on the prime, however a clearer sample on the backside. All that purple implies that the primary few bits within the enter hash can solely decide the primary few bits within the output hash. Which is smart for integer modulo. A small quantity modulo a big quantity won’t ever end in a big quantity, so a change to a small quantity can by no means have an effect on the later bits.

This image continues to be “good” for mapping from a wide variety right into a small vary as a result of we’ve got that diagonal line of vibrant blue pixels in every block. To point out a foul perform, right here is integer modulo with an influence of two measurement:

Avalanche_power_of_two.png

This one is clearly dangerous: The higher bits of the hash worth have fully purple rows, as a result of they are going to merely get chopped off. Solely the decrease bits of the enter have any impact, and so they can solely have an effect on their very own bits within the output. This image proper right here reveals why utilizing an influence of two measurement requires that you’re cautious along with your selection of hash perform for the hash desk: If these purple rows signify necessary bits, you’ll merely lose them.

Lastly let’s additionally take a look at the “fastrange” algorithm that I briefly talked about above. For energy of two sizes it appears actually dangerous, so let me present you what it appears like for prime sizes:

Avalanche_fastrange_prime.png

What we see right here is that fastrange throws away the decrease bits of the enter vary. It solely makes use of the higher bits. I had used it earlier than and I had observed {that a} change within the decrease bits doesn’t appear to make a lot of a distinction, however I had by no means realized that it simply fully throws the decrease bits away. This image completely explains why I had so many issues with fastrange. Fastrange is a foul perform to map from a wide variety right into a small vary as a result of it’s throwing away the decrease bits.

Going again to Fibonacci hashing, there’s truly one easy change you may make to enhance the dangerous sample for the highest bits: Shift the highest bits down and xor them as soon as. So the code modifications to this:

size_t index_for_hash(size_t hash)
{
    hash ^= hash >> shift_amount;
    return (11400714819323198485llu * hash) >> shift_amount;
}

It’s nearly trying extra like a correct hash perform, isn’t it? This makes the perform two cycles slower, nevertheless it provides us the next image:

Avalanche_fibxor

This appears a bit nicer, with the problematic sample on the prime gone. (and we’re seeing extra black pixels now which is the perfect for a hash perform) I’m not utilizing this although as a result of we don’t actually need hash perform, we’d like perform to map from a wide variety right into a small vary. And that is on the crucial path for the hash desk, earlier than we are able to even do the primary comparability. Any cycle added right here makes the entire line within the graph above transfer up.

So I carry on saying that we’d like perform to map from a wide variety right into a small vary, however I haven’t outlined what “good” means there. I don’t know of a correct check just like the avalanche evaluation for hash features, however my first try at a definition for “good” could be that each worth within the smaller vary is equally prone to happen. That check may be very simple to satisfy although: all the strategies (together with fastrange) fulfill that standards. So how about we choose a sequence of values within the enter vary and verify if each worth within the output is equally seemingly. I had given the examples for numbers 0 to 16 above. We may additionally do multiples of 8 or all powers of two or all prime numbers or the Fibonacci numbers. Or let’s simply strive as many sequences as attainable till we work out the conduct of the perform.

Trying on the above record we see that there is likely to be a problematic sample with multiples of 4: fibonacci_hash_3_bits(4) returned 3, for fibonacci_hash_3_bits(8) returned 7, fibonacci_hash_3_bits(12) returned 3 once more and fibonacci_hash_3_bits(16) returned 7 once more. Let’s see how this develops if we print the primary sixteen multiples of 4:

Listed here are the outcomes:

0 -> 0
4 -> 3
8 -> 7
12 -> 3
16 -> 7
20 -> 2
24 -> 6
28 -> 2
32 -> 6
36 -> 1
40 -> 5
44 -> 1
48 -> 5
52 -> 1
56 -> 4
60 -> 0
64 -> 4

See Also

Doesn’t look too dangerous truly: Each quantity reveals up twice, besides the #1 reveals up 3 times. What about multiples of eight?

0 -> 0
8 -> 7
16 -> 7
24 -> 6
32 -> 6
40 -> 5
48 -> 5
56 -> 4
64 -> 4
72 -> 3
80 -> 3
88 -> 3
96 -> 2
104 -> 2
112 -> 1
120 -> 1
128 -> 0

As soon as once more doesn’t look too dangerous, however we’re undoubtedly getting extra repeated numbers. So how about multiples of sixteen?

0 -> 0
16 -> 7
32 -> 6
48 -> 5
64 -> 4
80 -> 3
96 -> 2
112 -> 1
128 -> 0
144 -> 7
160 -> 7
176 -> 6
192 -> 5
208 -> 4
224 -> 3
240 -> 2
256 -> 1

This appears a bit higher once more, and if we have been to have a look at multiples of 32 it could look higher nonetheless. The rationale why the quantity 8 was beginning to look problematic was not as a result of it’s an influence of two. It was beginning to look problematic as a result of it’s a Fibonacci quantity. If we take a look at later Fibonacci numbers, we see extra problematic patterns. For instance listed below are multiples of 34:

0 -> 0
34 -> 0
68 -> 0
102 -> 0
136 -> 0
170 -> 0
204 -> 0
238 -> 0
272 -> 0
306 -> 0
340 -> 1
374 -> 1
408 -> 1
442 -> 1
476 -> 1
510 -> 1
544 -> 1

That’s trying dangerous. And later Fibonacci numbers will solely look worse. However then once more how usually are you going to insert multiples of 34 right into a hash desk? In reality when you needed to choose a bunch of numbers that’s going to provide you issues, the Fibonacci numbers should not the worst selection as a result of they don’t come up that usually naturally. As a reminder, listed below are the primary couple Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584… The primary couple numbers don’t give us dangerous patterns within the output, however something larger than 13 does. And most of these are fairly innocent: I can’t consider any case that might give out multiples of these numbers. 144 bothers me slightly bit as a result of it’s a a number of of 8 and also you may need a struct of that measurement, however even then your pointers will simply be eight byte aligned, so that you’d must get unfortunate for all of your tips that could be multiples of 144.

However actually what you do right here is that you simply establish the dangerous sample and also you inform your customers “when you ever hit this dangerous sample, present a customized hash perform to the hash desk that fixes it.” I imply persons are blissful to make use of integer modulo with powers of two, and for that it’s ridiculously simple to seek out dangerous patterns: Regular pointers are a foul sample for that. Because it’s more durable to give you use instances that spit out a number of multiples of Fibonacci numbers, I’m fantastic with having “multiples of Fibonacci numbers” as dangerous patterns.

So why are Fibonacci numbers a foul sample for Fibonacci hashing anyhow? It’s not apparent if we simply have the magic quantity multiplication and the bit shift. To begin with we’ve got to keep in mind that the magic fixed got here from dividing by the golden ratio: 2^{64}/phi approx 11400714819323198485. After which since we’re truncating the results of the multiplication earlier than we shift it, there’s truly a hidden modulo by 2^{64} in there. So every time we’re hashing a quantity x the slot is definitely decided by this:

slot_before_shift(x) = (x * 2^{64}/phi) % 2^{64}

I’m leaving out the shift on the finish as a result of that half doesn’t matter for determining why Fibonacci numbers are giving us issues. Within the instance of stepping round a circle (from the Vi Hart video above) the equation would appear to be this:

angle_for_leaf(x) = (x * 360/phi) % 360

This could give us an angle from 0 to 360. These features are clearly comparable. We simply changed 2^{64} with 360. So whereas we’re in math-land with infinite precision, we’d as nicely make the perform return one thing within the vary from 0 to 1, after which multiply the fixed in afterwards:

hash_0_to_1(x) = frac(x/phi)

The place frax(x) returns the fractional a part of a quantity. So frax(1.1) = 0.1. On this final formulation it’s simple to seek out out why Fibonacci numbers give us issues. Let’s strive placing in a number of Fibonacci numbers:

hash_0_to_1(144) = frac(144/phi) approx frac(89) = 0
hash_0_to_1(1587) = frac(1597/phi) approx frac(987) = 0
hash_0_to_1(8) = frac(8/phi) approx frac(4.94) = 0.94

What we see right here is that if we divide a Fibonacci quantity by the golden ratio, we simply get the earlier Fibonacci quantity. There is no such thing as a fractional half so we at all times find yourself with 0. So even when we multiply the complete vary of 2^{64} again in, we nonetheless get 0. However for smaller Fibonacci numbers there’s some imprecision as a result of the Fibonacci sequence is simply an integer approximation of golden ratio development. That approximation will get extra actual the additional alongside we get into the sequence, however for the quantity 8 it’s not that actual. That’s why 8 was not an issue, 34 began to look problematic, and 144 goes to be actual dangerous.

Besides that once we discuss badness, we even have to think about the dimensions of the hash desk. It’s very easy to seek out dangerous patterns when the desk solely has eight slots. If the desk is greater and has, say 64 slots, instantly multiples of 34 don’t look as dangerous:

0 -> 0
34 -> 0
68 -> 1
102 -> 2
136 -> 3
170 -> 4
204 -> 5
238 -> 5
272 -> 6
306 -> 7
340 -> 8
374 -> 9
408 -> 10
442 -> 10
476 -> 11
510 -> 12
544 -> 13

And if the desk has 1024 slots we get all of the multiples properly unfold out:

0 -> 0
34 -> 13
68 -> 26
102 -> 40
136 -> 53
170 -> 67
204 -> 80
238 -> 94
272 -> 107
306 -> 121
340 -> 134
374 -> 148
408 -> 161
442 -> 175
476 -> 188
510 -> 202
544 -> 215

At measurement 1024 even the multiples of 144 don’t look scary any extra as a result of they’re beginning to be unfold out now:

0 -> 0
144 -> 1020
288 -> 1017
432 -> 1014
576 -> 1011
720 -> 1008
864 -> 1004
1008 -> 1001
1152 -> 998

So the dangerous sample of multiples of Fibonacci numbers goes away with larger hash tables. As a result of Fibonacci hashing spreads out the numbers, and the larger the desk is, the higher it will get at that. This doesn’t show you how to in case your hash desk is small, or if you want to insert multiples of a bigger Fibonacci quantity, nevertheless it does give me confidence that this “dangerous sample” is one thing we are able to stay with.

So I’m OK with dwelling with the dangerous sample of Fibonacci hashing. It’s much less dangerous than making the hash desk an influence of two measurement. It may be barely extra dangerous than utilizing prime quantity sizes, so long as your prime numbers are nicely chosen. However I nonetheless assume that on common Fibonacci hashing is healthier than prime quantity sized integer modulo, as a result of Fibonacci hashing mixes up sequential numbers. So it fixes an actual drawback I’ve run into up to now whereas introducing a theoretical drawback that I’m struggling to seek out actual examples for. I believe that’s commerce.

Additionally prime quantity integer modulo can have issues when you select dangerous prime numbers. For instance enhance::unordered_map can select measurement 196613, which is 0b110000000000000101 in binary, which is a reasonably spherical quantity in the identical approach that 15000005 is a reasonably spherical quantity in decimal. Since this prime quantity is “too spherical of a quantity” this causes a number of hash collisions in one in every of my benchmarks, and I didn’t set that benchmark as much as discover dangerous instances like this. It was completely unintentional and took a number of debugging to determine why enhance::unordered_map does so badly in that benchmark. (the benchmark in query was set as much as discover issues with sequential numbers) However I gained’t go into that and can simply say that whereas prime numbers give fewer problematic patterns than Fibonacci hashing, you continue to have to decide on them nicely to keep away from introducing hash collisions.

Conclusion

Fibonacci hashing might not be one of the best hash perform, however I believe it’s the easiest way to map from a wide variety of numbers right into a small vary of numbers. And we’re solely utilizing it for that. When used just for that a part of the hash desk, we’ve got to match it in opposition to two current approaches: Integer modulo with prime numbers and Integer modulo with energy of two sizes. It’s nearly as quick as the facility of two measurement, nevertheless it introduces far fewer issues as a result of it doesn’t discard any bits. It’s a lot quicker than the prime quantity measurement, and it additionally provides us the bonus of breaking apart sequential numbers, which generally is a massive profit for open addressing hash tables. It does introduce a brand new drawback of getting issues with multiples of huge Fibonacci numbers in small hash tables, however I believe these issues might be solved by utilizing a customized hash perform while you encounter them. Expertise will inform how usually we must use this.

All of my hash tables now use Fibonacci hashing by default. For my flat_hash_map the property of breaking apart sequential numbers is especially necessary as a result of I’ve had actual issues attributable to sequential numbers. For the others it’s only a quicker default. It would nearly make the choice to make use of the facility of two integer modulo pointless.

It’s stunning that the world forgot about this optimization and that we’re all utilizing primer quantity sized hash tables as an alternative. (or use Dinkumware’s answer which makes use of an influence of two integer modulo, however spends extra time on the hash perform to make up for the issues of the facility of two integer modulo) Due to Wealthy Geldreich for writing a hash desk that makes use of this optimization and for mentioning it in my feedback. However that is an attention-grabbing instance as a result of academia had an answer to an actual drawback in current hash tables, however professors didn’t understand that they did. The most certainly cause for that’s that it’s not well-known how massive the issue of “mapping a big quantity right into a small vary” is and the way a lot time it takes to do an integer modulo.

For future work it is likely to be price trying into Knuth’s third hash perform: The one which’s associated to CRC hashes. It appears to be a approach to assemble CRC hash perform when you want a n-bit output for a hash desk. Nevertheless it was too difficult for me to look into, so I’ll depart that as an train to the reader to seek out out if that one is price utilizing.

Lastly here is the hyperlink to my implementation of unordered_map. My different two hash tables are additionally there: flat_hash_map has very quick lookups and bytell_hash_map can also be very quick however was designed extra to save lots of reminiscence in comparison with flat_hash_map.

Source Link

What's Your Reaction?
Excited
0
Happy
0
In Love
0
Not Sure
0
Silly
0
View Comments (0)

Leave a Reply

Your email address will not be published.

2022 Blinking Robots.
WordPress by Doejo

Scroll To Top