4 ms·

Could someone explain what the point is? Is there a use-case for this for "general hashing" and such, where sha256 is _genuinely_ insufficient?

chadaustin 10y ago
Hi, I recently used a hash function like this as part of a React-style delta calculation engine but for Swift / iOS. I needed a hash function that was fast but collision-resistant, and I did not need a cryptographic hash, as all data is trusted (and a hash collision would not actually matter that much). I chose SpookyHash V2 based on the advice of some peers and http://aras-p.info/blog/2016/08/09/More-Hash-Function-Tests/ http://aras-p.info/blog/2016/08/09/More-Hash-Function-Tests/ Hope that helps, Chad
- libeclipse 10y ago
  Even when I've not needed a cryptographic hash, I've still used one, because why not? I've never not needed one so bad as to resort to some barely studied, homemade hashing algorithm. > A hash collision wouldn't matter that much. Interesting. What was the use for the hash function then?
  - ticki_ 10y ago
    In hash tables, you never use cryptographic hash functions. Why? Because they're slower. Take SHA3, which is around 50x slower than SeaHash. That is really really bad for hash tables. When hash collisions happen in hash tables, they're resolved through collision-resolution strategy, such a linear proping. Fingerprints are one very narrow usecase for hash functions, and there are tousands of other uses.
  - jjaredsimpson 10y ago
    > Even when I've not needed a cryptographic hash, I've still used one, because why not? To avoid wasting cpu cycles preserving a property you don't need. Seahash should be 50x faster than sha3
  - matt4077 10y ago
    Caching often relies on hash functions. If you run the Cloudflare cache, you'll start caring, considering hashing is usually >50% of the CPU workload and an optimized non-cryptographic hash function can be 20x faster.
  - falcolas 10y ago
    A trade off between collision potential vs. speed. Sometimes you need speed more than you need cryptographic levels of collision avoidance. For example, finding unique files on the file system. After looking at size, first and last bytes, it would be better to filter quickly on an imperfect hash (with, say, a 1 in 1^56 chance of collision) than slowly on a perfect hash (with a 1 in 1^256 chance).
    - mdergosits 10y ago
      I hope you mean 2^56 and 2^256 :)
      - stcredzero 10y ago
        We can increase that by one to the fourth power! http://aperiodical.com/2013/05/the-maths-of-star-trek-the-original-series-part-iii/ http://aperiodical.com/2013/05/the-maths-of-star-trek-the-or...
  - zeveb 10y ago
    > Even when I've not needed a cryptographic hash, I've still used one, because why not? Performance. Take a look at djb's (non-cryptographic) hash, with a constant multiplier chosen to be implemented with a shift and an add — that's the level of performance a non-cryptographic hash (e.g. for hash tables & similar purposes) needs. https://gist.github.com/hmic/1676398 https://gist.github.com/hmic/1676398
    - ticki_ 10y ago
      Please don't. DJB2 is a poor hash function. It's similar to FNV: Entropy only moves upwards, so flipping higher bits doesn't affect lower bits. In other words, you risk mapping `n` and `-n` to the same value under some modulus.
pranjalv123 10y ago
This isn't a cryptographic hash. SHA-256 and other cryptographic hashes are much slower, but give certain guarantees about difficulty of doing things like finding hash collisions. The advantage of SeaHash is that it's even faster than other commonly used non-cryptographic hashes, and has attractive statistical properties that will result in fewer collisions than other hash functions.
llimllib 10y ago
A good example is for a bloom filter: using sha256 is much too slow for good filter performance, you want something like siphash or some other non-cryptographic hash. Here's a good story of the performance benefits of switching from cryptographic to non-crypto hashes: https://github.com/bitly/dablooms/pull/19 https://github.com/bitly/dablooms/pull/19 (But I don't recommend you use murmur anymore: https://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/ https://emboss.github.io/blog/2012/12/14/breaking-murmur-has... (although tbh I could be wrong on this one, not an expert)) (Shameless plug for my bloom filter tutorial https://llimllib.github.io/bloomfilter-tutorial/ https://llimllib.github.io/bloomfilter-tutorial/ )
- loeg 10y ago
  > But I don't recommend you use murmur anymore I think xxHash was/is the fastest good non-crypto hash, and now SeaHash may be best. Although I'd like to see a bit more data on that (small keys? large keys? benchmarking methodology) than SeaHash's author is providing.
  - llimllib 10y ago
    yeah I should look into that more. aapleby seems to have given some pretty good arguments against SeaHash in the previous discussion: https://news.ycombinator.com/item?id=13058652 https://news.ycombinator.com/item?id=13058652
    - Null-Set 10y ago
      That argument depends on the initial values being the same, you can easily make sure they are not.
loeg 10y ago
> Is there a use-case for this for "general hashing" and such, where sha256 is _genuinely_ insufficient? Yeah. There are often times when you want to hash data but don't want to waste sha256-levels of cycles doing so. Applications are pretty much everything except cryptographic signing. Load-balancing, higher-quality checksuming, etc.
ticki_ 10y ago
A lot of stuff. SHA256 is very slow, and that's no surprise. It's cryptographic after all. Here's a small list of usecases for non-cryptographic hash functions: - Checksums and error correction codes, as long as there is no way to maliciously use this. - Hash tables. These always use non-cryptographic hash functions. - Bloom filters. - Heuristic fingerprinting. They're not strong enough to be used for normal data fingerprints, but they can be used as a way to decide if two buffers are "probably equal" or "certainly not equal". Hash tables are the main one. Cryptographic hash functions are almost never used in them. SipHash is a popular choice, but it is not cryptographic. That is a misunderstanding: It's a MAC function.
- xorxornop 10y ago
  I may be totally off-base here, but can't the SHA256 CPU instructions be used for this? Then it'd just be 1 (? Or is it more) instruction to perform?

chadaustin 10y ago

Hi, I recently used a hash function like this as part of a React-style delta calculation engine but for Swift / iOS. I needed a hash function that was fast but collision-resistant, and I did not need a cryptographic hash, as all data is trusted (and a hash collision would not actually matter that much). I chose SpookyHash V2 based on the advice of some peers and http://aras-p.info/blog/2016/08/09/More-Hash-Function-Tests/ http://aras-p.info/blog/2016/08/09/More-Hash-Function-Tests/ Hope that helps, Chad

libeclipse 10y ago
Even when I've not needed a cryptographic hash, I've still used one, because why not? I've never not needed one so bad as to resort to some barely studied, homemade hashing algorithm. > A hash collision wouldn't matter that much. Interesting. What was the use for the hash function then?
- ticki_ 10y ago
  In hash tables, you never use cryptographic hash functions. Why? Because they're slower. Take SHA3, which is around 50x slower than SeaHash. That is really really bad for hash tables. When hash collisions happen in hash tables, they're resolved through collision-resolution strategy, such a linear proping. Fingerprints are one very narrow usecase for hash functions, and there are tousands of other uses.
- jjaredsimpson 10y ago
  > Even when I've not needed a cryptographic hash, I've still used one, because why not? To avoid wasting cpu cycles preserving a property you don't need. Seahash should be 50x faster than sha3
- matt4077 10y ago
  Caching often relies on hash functions. If you run the Cloudflare cache, you'll start caring, considering hashing is usually >50% of the CPU workload and an optimized non-cryptographic hash function can be 20x faster.
- falcolas 10y ago
  A trade off between collision potential vs. speed. Sometimes you need speed more than you need cryptographic levels of collision avoidance. For example, finding unique files on the file system. After looking at size, first and last bytes, it would be better to filter quickly on an imperfect hash (with, say, a 1 in 1^56 chance of collision) than slowly on a perfect hash (with a 1 in 1^256 chance).
  - mdergosits 10y ago
    I hope you mean 2^56 and 2^256 :)
    - stcredzero 10y ago
      We can increase that by one to the fourth power! http://aperiodical.com/2013/05/the-maths-of-star-trek-the-original-series-part-iii/ http://aperiodical.com/2013/05/the-maths-of-star-trek-the-or...
- zeveb 10y ago
  > Even when I've not needed a cryptographic hash, I've still used one, because why not? Performance. Take a look at djb's (non-cryptographic) hash, with a constant multiplier chosen to be implemented with a shift and an add — that's the level of performance a non-cryptographic hash (e.g. for hash tables & similar purposes) needs. https://gist.github.com/hmic/1676398 https://gist.github.com/hmic/1676398
  - ticki_ 10y ago
    Please don't. DJB2 is a poor hash function. It's similar to FNV: Entropy only moves upwards, so flipping higher bits doesn't affect lower bits. In other words, you risk mapping `n` and `-n` to the same value under some modulus.

pranjalv123 10y ago

This isn't a cryptographic hash. SHA-256 and other cryptographic hashes are much slower, but give certain guarantees about difficulty of doing things like finding hash collisions. The advantage of SeaHash is that it's even faster than other commonly used non-cryptographic hashes, and has attractive statistical properties that will result in fewer collisions than other hash functions.

llimllib 10y ago

A good example is for a bloom filter: using sha256 is much too slow for good filter performance, you want something like siphash or some other non-cryptographic hash. Here's a good story of the performance benefits of switching from cryptographic to non-crypto hashes: https://github.com/bitly/dablooms/pull/19 https://github.com/bitly/dablooms/pull/19 (But I don't recommend you use murmur anymore: https://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/ https://emboss.github.io/blog/2012/12/14/breaking-murmur-has... (although tbh I could be wrong on this one, not an expert)) (Shameless plug for my bloom filter tutorial https://llimllib.github.io/bloomfilter-tutorial/ https://llimllib.github.io/bloomfilter-tutorial/ )

loeg 10y ago
> But I don't recommend you use murmur anymore I think xxHash was/is the fastest good non-crypto hash, and now SeaHash may be best. Although I'd like to see a bit more data on that (small keys? large keys? benchmarking methodology) than SeaHash's author is providing.
- llimllib 10y ago
  yeah I should look into that more. aapleby seems to have given some pretty good arguments against SeaHash in the previous discussion: https://news.ycombinator.com/item?id=13058652 https://news.ycombinator.com/item?id=13058652
  - Null-Set 10y ago
    That argument depends on the initial values being the same, you can easily make sure they are not.

loeg 10y ago

> Is there a use-case for this for "general hashing" and such, where sha256 is _genuinely_ insufficient? Yeah. There are often times when you want to hash data but don't want to waste sha256-levels of cycles doing so. Applications are pretty much everything except cryptographic signing. Load-balancing, higher-quality checksuming, etc.

ticki_ 10y ago

A lot of stuff. SHA256 is very slow, and that's no surprise. It's cryptographic after all. Here's a small list of usecases for non-cryptographic hash functions: - Checksums and error correction codes, as long as there is no way to maliciously use this. - Hash tables. These always use non-cryptographic hash functions. - Bloom filters. - Heuristic fingerprinting. They're not strong enough to be used for normal data fingerprints, but they can be used as a way to decide if two buffers are "probably equal" or "certainly not equal". Hash tables are the main one. Cryptographic hash functions are almost never used in them. SipHash is a popular choice, but it is not cryptographic. That is a misunderstanding: It's a MAC function.

xorxornop 10y ago
I may be totally off-base here, but can't the SHA256 CPU instructions be used for this? Then it'd just be 1 (? Or is it more) instruction to perform?