7 ms·

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

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

allenz 8y ago
This is for a hashmap library where the hash functions are user-defined, so a secondary hash is justifiable.
- aappleby 8y ago
  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.
  - vidarh 8y ago
    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.
  - flurrything 8y ago
    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.
  - thomasmg 8y ago
    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-function-are-good-that-accepts-an-integer-hash-key/12996028#12996028 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.
aappleby 8y ago
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.
- fis 8y ago
  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 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?
  - aappleby 8y ago
    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.
    - bradleyjg 8y ago
      This one? https://github.com/stg7/haesni https://github.com/stg7/haesni
      - injinj 8y ago
        Look at the aeshash in the go runtime: https://github.com/golang/go/blob/master/src/runtime/asm_amd64.s https://github.com/golang/go/blob/master/src/runtime/asm_amd...
CephalopodMD 8y ago
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?
- vidarh 8y ago
  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.
- jrochkind1 8y ago
  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.
  - jrootabega 8y ago
    Perhaps for DOS resistance like the hashdos vulnerability from 2011? https://nakedsecurity.sophos.com/2011/12/28/large-percentage-of-websites-vulnerable-to-hashdos-denial-of-service-attack/ https://nakedsecurity.sophos.com/2011/12/28/large-percentage...
flurrything 8y ago
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.
- tankenmate 8y ago
  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.
mickronome 8y ago
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.
- ghusbands 8y ago
  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.
  - junctioniv 8y ago
    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.
    - ghusbands 8y ago
      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."
- attractivechaos 8y ago
  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.

allenz 8y ago

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

aappleby 8y ago
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.
- vidarh 8y ago
  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.
- flurrything 8y ago
  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.
- thomasmg 8y ago
  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-function-are-good-that-accepts-an-integer-hash-key/12996028#12996028 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.

aappleby 8y ago

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.

fis 8y ago
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 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?
- aappleby 8y ago
  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.
  - bradleyjg 8y ago
    This one? https://github.com/stg7/haesni https://github.com/stg7/haesni
    - injinj 8y ago
      Look at the aeshash in the go runtime: https://github.com/golang/go/blob/master/src/runtime/asm_amd64.s https://github.com/golang/go/blob/master/src/runtime/asm_amd...

CephalopodMD 8y ago

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?

vidarh 8y ago
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.
jrochkind1 8y ago
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.
- jrootabega 8y ago
  Perhaps for DOS resistance like the hashdos vulnerability from 2011? https://nakedsecurity.sophos.com/2011/12/28/large-percentage-of-websites-vulnerable-to-hashdos-denial-of-service-attack/ https://nakedsecurity.sophos.com/2011/12/28/large-percentage...

flurrything 8y ago

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.

tankenmate 8y ago
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.

mickronome 8y ago

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.

ghusbands 8y ago
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.
- junctioniv 8y ago
  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.
  - ghusbands 8y ago
    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."
attractivechaos 8y ago
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.