[HN Gopher] Fibonacci Hashing: The Optimization That the World F...
___________________________________________________________________
Fibonacci Hashing: The Optimization That the World Forgot
Author : juancampa
Score : 94 points
Date : 2025-04-14 01:02 UTC (2 days ago)
(HTM) web link (probablydance.com)
(TXT) w3m dump (probablydance.com)
| peterlada wrote:
| To summarize: multiplication hashes are inferior but when used
| with the golden ratio derived integer, they are actually superior
| Sesse__ wrote:
| No, plenty of systems use other factors. The golden ratio has
| some nice properties, but it's not essential.
| btilly wrote:
| Poor summary.
|
| Better summary. Fibonacci hashing isn't a great hash function,
| but it is a really good solution to mapping large integers to
| small integers. Using it for that doubles the speed of hashing
| in practice.
| infoaddicted wrote:
| The youtube video is marked private?
| skerit wrote:
| This is a pretty old video, even the series linked to it
| underneath is now private. Strange.
| softblush wrote:
| Part 1 https://vimeo.com/147913571
|
| Part 2 https://vimeo.com/147799853
|
| Part 3 https://vimeo.com/147913569
| Calwestjobs wrote:
| vimeo and dailymotion to the rescue XD
| nayuki wrote:
| Vihart's YouTube now has exactly one publicly visible video:
| https://www.youtube.com/@Vihart/videos ,
| https://www.youtube.com/watch?v=hmKix-75dsg "On Gender"
| [2015-06-08]
| 317070 wrote:
| Why the golden ratio? Because the continued fraction of the
| golden ratio is all 1's [0]. So it is uniquely hard to
| approximate with a rational number. The golden ratio is the bound
| on Hurwitz's theorem [1]. And avoiding a rational number is what
| you want for good hashing, because multiplying with a rational
| number doesn't mix your digits well.
|
| [0]
| https://codegolf.stackexchange.com/questions/48589/generate-...
| [1]
| https://en.m.wikipedia.org/wiki/Hurwitz%27s_theorem_(number_...
| Genbox wrote:
| I opened this post in a tab 3 days ago, but now it says "5 hours
| ago". Someone is playing around.
| IggleSniggle wrote:
| I h8 it when thir teens get all cheeky like that. Hopefully
| they'll have matured a bit by 21.
|
| Edit: it seems people don't like my Fibonacci joke. I thought I
| had this kind of thing figured out by 34.
| Calwestjobs wrote:
| maybe they are confused because they never heard of
| mathematical operation of maturing.
| willvarfar wrote:
| No idea in this particular case, but in the past I've got
| pinged by HN mods suggesting I resubmit posts that I recently
| submitted but bombed. I imagine HN has an automated system for
| finding some posts with potential that never got the attention
| they deserved and boosting them to give them a second chance?
|
| The article is 2018.
| pixl97 wrote:
| >Someone is playing around
|
| No, not really. It's called the second chance pool.
|
| https://news.ycombinator.com/item?id=26998308
| hyperbrainer wrote:
| Needs (2018)
| igtztorrero wrote:
| The Fibonacci series, as fascinating as its name, the origin of
| the spiral in nature, and the Debian logo, ever-present in
| computing. The algorithm is surely better as the author says, but
| most of the time we use what's available. Perhaps the Python,
| Golang, and JS core programmers could review it.
| jlebar wrote:
| I think the author has misunderstood things here.
|
| This technique is orthogonal to integer mod. Indeed the author
| multiplies by their magic constant and then does an integer mod
| to map into their hashtable's buckets.
|
| This technique is actually just applying a fast integer hash on
| the input keys to the hashtable before mapping the keys to
| buckets. You can then map to buckets however you want.
|
| The additional hash is useful if and only if the input hash
| function for your table's keys doesn't appear to be a random
| function, i.e. it doesn't mix its bits for whatever reason. If
| your input hash functions are indeed random then this is a (small
| but perhaps measurable) waste of time.
|
| Using prime-numbered table sizes is another way to accomplish
| basically the same thing. Dividing the input hash key by a prime
| forces you to look at all the bits of the input. In practice
| these are written as division by a constant, so they use
| multiplies and shifts. It's basically a hash function. (Though
| I'd use multiply by a magic number over divide by a prime, mul
| alone should be faster.)
|
| Relatedly see this post by Daniel Lemire about an alternative to
| integer mod, https://lemire.me/blog/2016/06/27/a-fast-
| alternative-to-the-... which is interesting if your number of
| buckets is not a power of 2 for some reason.
| sdenton4 wrote:
| I think the post talks about exactly this? The method is
| combining hashing the keys and finding a position in the target
| range. There's a bit where he talks about how Knuth uses the
| term 'hash function' as the combination of these two
| operations, while modern texts look at the two operations in
| isolation.
|
| So maybe one way of looking at this is as an efficient fusion
| operation, which doesn't look special when you look at the ops
| in isolation, but combine to something that is both fast and
| advised problems with input patterns.
| bmn__ wrote:
| https://github.com/rurban/smhasher#:~:text=fibonacci
___________________________________________________________________
(page generated 2025-04-16 17:01 UTC)