Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

There are hash functions that are as fast or faster than FNV and stastically stronger (and faster) than xxhash. There are multiple hash function families that should be used before either of the above in modern applications unless you need backward compatibility (like the CRC case in the article). This is an active research area and both of the above, while adequate for many casual use cases, should not be used for checksums for the same reason CRC32 should not be used for checksums in large systems.

As an example from one of my hash function research projects, MetroHash64 will outperform xxhash both for speed and stastical robustness (which is quasi-cryptographic). If you only need 32 bits, truncate larger hashes; if they have very strong stastical properties, that works well.

Lots of people working on this stuff.



Comparing xxHash with FNV is a strawman, it's apples and oranges in terms of quality.

You are discounting xxHash considerably. xxHash is one of the best, if not the best, all factors considered.

SMHasher:

  xxHash, speed=5.4 GB/s, quality=10
  MurmurHash 3a, speed=2.7 GB/s, quality=10
  SBox, speed=1.4 GB/s, quality=9
  Lookup3, speed=1.2 GB/s, quality=9
  CityHash64, speed=1.05 GB/s, quality=10
  FNV, speed=0.55 GB/s, quality=5
  CRC32, speed=0.43 GB/s, quality=9	
  MD5-32, speed=0.33 GB/s, quality=10
  SHA1-32, speed=0.28 GB/s, quality=10


With all due respect, xxHash is a decent hash function but you are comparing it against some relatively weak or slow hash functions. As was pointed out last time this came up, the Metro64 hash example I offered is simultaneously faster and higher quality than xxHash. There are hash functions that are faster than xxHash and stronger than some of the cryptographic hashes, and xxHash definitely has much more bias than even MD5.

Getting a perfect score with SMHasher is table stakes. The default settings on SMHasher are much too loose for current research; I know it well, I have hacked it extensively. A state-of-the-art non-cryptographic hash function today generally has the following properties:

- statistical quality greater than or equal to MD5, a cryptographic hash. xxHash is not close to MD5 in quality.

- faster than xxHash on large keys, and for really good hashes, memory bandwidth bound. (Metro64 is, again, faster than xxHash, though not memory bandwidth bound.)

- faster than xxHash on small keys (Metro64, to use that example, is almost 2x faster)

There are a lot of good hash functions being developed by researchers. But empirically, xxHash is nowhere near the state-of-the-art any way you slice it. It is a decent hash function but there are many functions produced by many researchers that are both faster and higher quality. It isn't personal, people can measure it for themselves.


Yes, I remember reading your post on Metro64 at the time:

http://www.jandrewrogers.com/2015/05/27/metrohash/

Interesting that you based your results there on SMHasher. Are there better benchmarks available?




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: