5 ms·

There is also a great resource with more up do date stuff on hashing and benchmarks right here: https://github.com/rurban/smhasher/ https://github.com/rurban/sm

by diziet 10y ago

There is also a great resource with more up do date stuff on hashing and benchmarks right here: https://github.com/rurban/smhasher/ https://github.com/rurban/smhasher/

erichocean 10y ago
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.
nabla9 10y ago
It's no surprise that SipHash from DJB is so commonly used as default hash function for hash tables. It's resistant against hash-flooding attacks and really fast.
- kbd 10y ago
  From the SMhasher page: > The hash table attacks described in SipHash... cannot not be the problem of the hash function, but the hash table collision resolution scheme. You can attack every single hash function, even the best and most secure if you detect the seed, e.g. from the sort-order, so you need to protect your collision handling scheme from the worst-case O(n)... > I.e. the usage of siphash for their hash table in Python 3.4, ruby, rust, systemd, OpenDNS, Haskell and OpenBSD is pure security theatre. siphash is not secure enough for security purposes and not fast enough for general usage. ... Provable secure is only uniform hashing, i.e. 2-5 independent Mult or Tabulation, or using a guaranteed logarithmic or linear collision scheme, such as Robin Hood or Cockoo hashing.
  - Manishearth 10y ago
    I think that comment is a bit extreme. > You can attack every single hash function, even the best and most secure if you detect the seed, e.g. from the sort-order, so you need to protect your collision handling scheme from the worst-case O(n), i.e. separate chaining with linked lists or protect the seed from being revealed. Timing attacks can be used to reveal the seed in some situations, but not all. It also says "for security purposes", which is pretty vague. It's certainly not secure enough for a security-related application. But for most use cases it's fine when you want to just have some protection against map DOSes. Not being useful for security-related applications doesn't make it security theater. It also says that it's useless in Rust (among others), and then goes on to say that robin hood hashing is a solution. Rust has had robin hood hashing for years.
    - rurban 10y ago
      I wrote that. It is not extreme. "Security purposes" is mostly attacking routers, dns daemons or kernels via hash flooding which don't have that bad hash tables as the mentioned languages. Interestingly those devs are snake oil resistant. Security theatre is the claim by siphash and its proponents. The siphash paper analyzes a very small part of hash tables usage, and then wildly exaggerates its logic. People are reading it as the claims in the section before "7 Application: defense against hash flooding" would affect hash tables also. No, they are talking purely about the hash function there. But then in section 7 they act as like all hash tables are only implemented as the simpliest and worst of all, linked lists chaining. Only the worst hash tables are using this collision resolution scheme. It is slow and it is "insecure" by default. There is no need to add a pseudo-secure layer of siphash on top of it as it does not help. The idea how such a hash table would be attacked are from 2003. We are now in 2016, and people are using efficient sat solvers (first just z3 in python, then producing scripts which produce CNF, and then eventually cbmc which can use the siphash code verbatim), not the simple ad hoc attempts they are describing. Their analysis is partially sound, but the result and claim is completely wrong. We are just lucky that such hash flooding is uncool, as attacking an application service is nowadays much easier. You can read about it here almost every other day. Rust uses a uselessly slow hash function while it was already protected by the balancing characteristics of robin hood. Therefore switching to siphash is doing more harm than good. It's using a 10-100x slower hash function which is completely useless. Count the average collisions before and after, and compare the time won there against the time lost in the hash function. It's a dramatic loss. It wasn't a dramatic loss in python, no idea why. I guess they have some other grave mistake in their hash table. It is a dramatic loss in perl5. Even if their hash table is the worst of all open source projects. Well, at least they randomize the iterator now. Before they used a zero-invariant function (trivial to attack by adding \0), and didn't count collisions when fighting collision attacks.

by diziet 10y ago

There is also a great resource with more up do date stuff on hashing and benchmarks right here: https://github.com/rurban/smhasher/ https://github.com/rurban/smhasher/

erichocean 10y ago

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.

nabla9 10y ago

It's no surprise that SipHash from DJB is so commonly used as default hash function for hash tables. It's resistant against hash-flooding attacks and really fast.

kbd 10y ago
From the SMhasher page: > The hash table attacks described in SipHash... cannot not be the problem of the hash function, but the hash table collision resolution scheme. You can attack every single hash function, even the best and most secure if you detect the seed, e.g. from the sort-order, so you need to protect your collision handling scheme from the worst-case O(n)... > I.e. the usage of siphash for their hash table in Python 3.4, ruby, rust, systemd, OpenDNS, Haskell and OpenBSD is pure security theatre. siphash is not secure enough for security purposes and not fast enough for general usage. ... Provable secure is only uniform hashing, i.e. 2-5 independent Mult or Tabulation, or using a guaranteed logarithmic or linear collision scheme, such as Robin Hood or Cockoo hashing.
- Manishearth 10y ago
  I think that comment is a bit extreme. > You can attack every single hash function, even the best and most secure if you detect the seed, e.g. from the sort-order, so you need to protect your collision handling scheme from the worst-case O(n), i.e. separate chaining with linked lists or protect the seed from being revealed. Timing attacks can be used to reveal the seed in some situations, but not all. It also says "for security purposes", which is pretty vague. It's certainly not secure enough for a security-related application. But for most use cases it's fine when you want to just have some protection against map DOSes. Not being useful for security-related applications doesn't make it security theater. It also says that it's useless in Rust (among others), and then goes on to say that robin hood hashing is a solution. Rust has had robin hood hashing for years.
  - rurban 10y ago
    I wrote that. It is not extreme. "Security purposes" is mostly attacking routers, dns daemons or kernels via hash flooding which don't have that bad hash tables as the mentioned languages. Interestingly those devs are snake oil resistant. Security theatre is the claim by siphash and its proponents. The siphash paper analyzes a very small part of hash tables usage, and then wildly exaggerates its logic. People are reading it as the claims in the section before "7 Application: defense against hash flooding" would affect hash tables also. No, they are talking purely about the hash function there. But then in section 7 they act as like all hash tables are only implemented as the simpliest and worst of all, linked lists chaining. Only the worst hash tables are using this collision resolution scheme. It is slow and it is "insecure" by default. There is no need to add a pseudo-secure layer of siphash on top of it as it does not help. The idea how such a hash table would be attacked are from 2003. We are now in 2016, and people are using efficient sat solvers (first just z3 in python, then producing scripts which produce CNF, and then eventually cbmc which can use the siphash code verbatim), not the simple ad hoc attempts they are describing. Their analysis is partially sound, but the result and claim is completely wrong. We are just lucky that such hash flooding is uncool, as attacking an application service is nowadays much easier. You can read about it here almost every other day. Rust uses a uselessly slow hash function while it was already protected by the balancing characteristics of robin hood. Therefore switching to siphash is doing more harm than good. It's using a 10-100x slower hash function which is completely useless. Count the average collisions before and after, and compare the time won there against the time lost in the hash function. It's a dramatic loss. It wasn't a dramatic loss in python, no idea why. I guess they have some other grave mistake in their hash table. It is a dramatic loss in perl5. Even if their hash table is the worst of all open source projects. Well, at least they randomize the iterator now. Before they used a zero-invariant function (trivial to attack by adding \0), and didn't count collisions when fighting collision attacks.