4 ms·

That compares hash functions, not hash tables (aka dictionaries, maps, key-value stores, etc.). Hash functions convert sparse keys to dense keys (with potentia

That compares hash functions, not hash tables (aka dictionaries, maps, key-value stores, etc.). Hash functions convert sparse keys to dense keys (with potential for collisions). Hash tables look up and store values by key using their hash (usually in-memory only, although this is not a requirement per se).

Gankro 10y ago
It's also a terrible comparison of hash functions for the purpose of hashmaps, because it tries to reduce the performance characteristics to a single number. The performance characteristics of a hash function varies over the size of the input. FarmHash is super complicated because it's basically a huge stable of hash functions that are selected based on input size. For instance, looking at these numbers you might conclude XXHash is strictly faster than FNV, but in reality FNV performs much better for the more common case of small inputs (breaking even around 16-32 bytes).
- diziet 10y ago
  I disagree, as this simple test suite is not meant to be a definitive guide on which hash function is the best. I would venture to say that your criticism is similar to saying that the Hutter Prize[1] is a terrible idea for someone who will need to do compression on a dataset as they will choose to use PAQ and it will run really slowly. Yes, there are trade-offs and optimizations for different use cases, but to say that it's a terrible comparison is unfair. 1) http://prize.hutter1.net/ http://prize.hutter1.net/
diziet 10y ago
I understand there are difference between hash functions and hash tables* (and between implementations of hash maps, dictionaries, etc). I do not understand the need to down-vote the comment that I think is relevant to the discussion of hash functions as implementing a hash table requires choosing a hash function along with choosing strategies for collision avoidance, collision handling, resizing, chaining, etc.

Gankro 10y ago

It's also a terrible comparison of hash functions for the purpose of hashmaps, because it tries to reduce the performance characteristics to a single number. The performance characteristics of a hash function varies over the size of the input. FarmHash is super complicated because it's basically a huge stable of hash functions that are selected based on input size. For instance, looking at these numbers you might conclude XXHash is strictly faster than FNV, but in reality FNV performs much better for the more common case of small inputs (breaking even around 16-32 bytes).

diziet 10y ago
I disagree, as this simple test suite is not meant to be a definitive guide on which hash function is the best. I would venture to say that your criticism is similar to saying that the Hutter Prize[1] is a terrible idea for someone who will need to do compression on a dataset as they will choose to use PAQ and it will run really slowly. Yes, there are trade-offs and optimizations for different use cases, but to say that it's a terrible comparison is unfair. 1) http://prize.hutter1.net/ http://prize.hutter1.net/

diziet 10y ago

I understand there are difference between hash functions and hash tables* (and between implementations of hash maps, dictionaries, etc). I do not understand the need to down-vote the comment that I think is relevant to the discussion of hash functions as implementing a hash table requires choosing a hash function along with choosing strategies for collision avoidance, collision handling, resizing, chaining, etc.