10 ms·

Which hashing algorithm is best for uniqueness and speed?

243 points by fekberg 13y ago

ColinWright 13y ago
It's worth remembering that when selecting things at random from a given pool, there is always a chance of collision. If you think of a hash as taking a value to a "random" result, with different objects going to results uniformly "at random", then you have to expect collisions. This is why the term "perfect hash" is defined so carefully. For those who are interested, the probability of collision, then size of the hash destination, and the number of objects chosen are related by this formula: Choosing from N items, with N large, and wanting a probability T of having no collisions, the number of items you can choose at random with replacement is: k ~ sqrt( -2 N ln(T) ) So T ~ exp(-(k^2)/(2N)) Source: http://www.solipsys.co.uk/new/TheBirthdayParadox.html?HN20131014 http://www.solipsys.co.uk/new/TheBirthdayParadox.html?HN2013...
- dllthomas 13y ago
  There's always a chance of a collision, but for a large enough pool relative to the number of objects the chance may be sufficiently smaller than the chance of hardware failure that it can be legitimately ignored. For something where the entire space must in some way be realized (eg. hashtable) this won't be the case, obviously.
  - Someone 13y ago
    Most of the time, that isn't true. Hardware failures are (barring quality control issues) independent, hash collisions are not. For example, if you assume your hash will not have collisions, and design your hash table without any mechanism for coping with one, and it happens to have a clash on "Jones" and "Smith", your address book app will become unreliable for a rather large fraction of your users.
    - dllthomas 13y ago
      But at the scales we're talking about, it won't happen to have a clash on "Jones" and "Smith". This won't be a hash table - this will be things like a git commit hash, where generating 1/ns is likely to give a collision in 3 years, before which the storage required just to store hashes is in the yottabytes.
sukaka 13y ago
seeing at least 1 collision the tests makes me wonder why the chance of a bitcoin address collision is almost nil. https://en.bitcoin.it/wiki/Weaknesses#Generating_tons_of_addresses https://en.bitcoin.it/wiki/Weaknesses#Generating_tons_of_add...
- betterunix 13y ago
  Cryptographic hashes are an entire category of hash functions unto themselves. The absolute minimum guarantee that a cryptographic hash makes is that for any polynomial time algorithm, the probability of the algorithm computing a pair (x,y) such that x != y and H(x) = H(y) is "negligible" i.e. is smaller than 1/p(n) for all polynomials p and large enough n; in other words, cryptographic hashes guarantee that collisions are extremely rare. Much like you can create a cipher with security that is reducible to the hardness of some problem (e.g. ElGamal is secure if the Diffie-Hellman problem is hard), it is possible to create collision resistant hashes with such security proofs, e.g. Very Smooth Hash, SWIFFT. In practice, though, we just use hashes that are believed to be security according to heuristic tests; hence the need to periodically update standard hash functions, rather than to just increase parameter sizes. Also interesting is universal hashing, which has applicability in cryptography (for randomness extraction, among other things): https://en.wikipedia.org/wiki/Universal_hashing https://en.wikipedia.org/wiki/Universal_hashing
- vertex-four 13y ago
  Bitcoin uses a cryptographic hash function, SHA256. There are, at present, no known collisions with SHA256. This question is about non-cryptographic hash functions, as are commonly used in hash tables[1] which implement associative arrays, or sharding databases based on the hash of the record key. Non-cryptographic hash functions are simply not in the same league as cryptographic ones; cryptographic hash functions are optimized to make it infeasible for an attacker to generate a different message with the same hash, while a non-cryptographic hash function generally simply has to have uniformly random output over its keyspace. [1] http://en.wikipedia.org/wiki/Hash_table http://en.wikipedia.org/wiki/Hash_table
  - VLM 13y ago
noelwelsh 13y ago
Nice analysis. Since that post was submitted Murmurhash 3 and a number of other notable hash functions have been released. If you liked the linked post you should go read Aggregate Knowledge's series of posts on hash functions for a look at some newer algorithms: http://blog.aggregateknowledge.com/2012/02/02/choosing-a-good-hash-function-part-3/ http://blog.aggregateknowledge.com/2012/02/02/choosing-a-goo...
devx 13y ago
Would the security of such algorithms improve dramatically if say 5 years from now we'd live in a world where everyone has a 64-bit device or machine, and the algorithms can be optimized for 64-bit? Are current algorithms limited by 32-bit a lot or not really?
- ctz 13y ago
  Security of such algorithms now: none. Security of such algorithms now where everyone has a 64-bit device: none. Don't confuse hash functions like these and cryptographic hash functions.
ot 13y ago
A more thorough test suite for hash function is SMHasher, by the same author of MurmurHash. It measures collisions, output uniformity, biased bits, etc... as well as speed, under several input distributions. https://code.google.com/p/smhasher/ https://code.google.com/p/smhasher/ Here is the output for some popular hash functions: https://code.google.com/p/smhasher/wiki/SMHasherDump https://code.google.com/p/smhasher/wiki/SMHasherDump
- tibbe 13y ago
  If someone could run smhasher for the hash functions in the original article (and perhaps also MurmurHash 2/3) and summarize the result for the small key sizes I will give them a cookie.
  - gregrata 13y ago
    I REALLY think we're all tired of random people giving us yet another cookie to store...
easytiger 13y ago
cityhash - http://code.google.com/p/cityhash/ http://code.google.com/p/cityhash/
deleted 13y ago
[deleted]
waynecochran 13y ago
> Yes. I started writing my test program to see if hash > collisions actually happen - and are not just a theoretical construct. This should be no surprise. The birthday paradox, as Knuth points in in TAoCP, makes it clear why collisions happen. Given 23 people in a room, there is a greater that 50% chance that at least two have the same birthday. Placing only 23 keys into a hash table with 365 entries with a perfectly random hash function will probably result in at least one collision.
- ColinWright 13y ago
  Placing only 23 keys into a hash table with 365 entries with a perfectly random hash function will probably result in at least one collision. No, it won't "probably" result in at least one collision, it will result in at least one collision with probability about 1/2. As quoted elsewhere, placing k objects in a hash table with N entries will result in no collisions with probability about exp(-(k^2)/(2N)).
  - abentspoon 13y ago
    Interesting. I was going to complain, as I thought "probably" meant the probability of occurrence was greater than 50%.. That doesn't seem to be the case. Probably: almost certainly; as far as one knows or can tell I would guess waynecochran thought something similar.
    - ColinWright 13y ago
      Curious. I've just taken a straw poll in the office. I asked "if someone said something was probably going to happen, what probability would you give it?" The answers were: * 80% * 50% to 90% * 90% * > 80% * 80% * 80% to 90%
      - StavrosK 13y ago
        My guess would have been "exactly strictly higher than 50%".
jameshart 13y ago
One issue to be careful of is assuming that you don't need the guarantees a cryptographic hash provides (preimage resistance, extension resistance, etc.) in your application. If an adversary can force hash collisions they may, depending on your uses for the hashing algorithm, be able to cause degredation or denial of service, or perhaps trigger information disclosures if they're very smart. If there's any way in which an attacker might be able to have some control over the dataset you are hashing you should probably be looking at using a cryptographic hash anyway.
- fragsworth 13y ago
  Is denial of service from an attacker who has your source something you actually consider when building a product? I can see trying to prevent data breaches and such, but going so far as to be wary of denial of service attacks from people who have your source code might be wasted effort.
  - dllthomas 13y ago
    You should code as if any attacker has your source. If denial of service attacks are something you need to consider, you need to consider them from someone who has your source.
    - fragsworth 13y ago
      Denial of service attacks are usually not devastating (they've happened to many large services multiple times) and there's a very real engineering cost in being absolutely certain that you are immune to such attacks. I think most people here don't fall under the umbrella of those who need to consider denial-of-service attacks. When your primary goal should be to launch your product (which you aren't even sure will take off) I would think trying to prevent denial-of-service attacks is a waste of time.
      - dllthomas 13y ago
        I'm not sure I disagree with any of that. I simply said that if you need to consider DoS you should consider DoS with the assumption your attacker has access to your source.
svag 13y ago
It is worth mentioning that the libstdc++, in version 4.6.3 at least, it has implemented the Murmur and FNV hash function for user defined key types. If you want to use Murmur you use std::_Hash_impl::hash and for FNV you use std::_Fnv_hash_impl::hash. (Include bits/functional_hash.h) The implementation is at libsupc++/hash_bytes.cc
ppierald 13y ago
gperf - https://www.gnu.org/software/gperf/ https://www.gnu.org/software/gperf/ This is a "perfect" application of a "perfect hash" generator.
bcoates 13y ago
I often see these "plot the output of the RNG on a 2d grid" things. I understand they're useful for demonstrating non-randomness, but if you're searching for patterns, do they reveal anything an FFT wouldn't?
- baq 13y ago
  isn't fft just a different way of looking at the data?
  - USNetizen 13y ago
    Essentially, yes, that was my understanding, too. I've only used in in signal processing - converting from the time domain to the frequency domain. Not sure how that would apply to this.
    - bcoates 13y ago
      I was thinking specifically of this: When i look at the FNV-1a "number" map, i think i see subtle vertical patterns. With Murmur i see no patterns at all. What do you think? Wouldn't that vertical repetition, and the other repeating patterns the other hashes form, show up as a nice spike in the frequency domain? Whereas I would expect uniform hashing to generate a flat, white-noise spectrum.
      - edwintorok 13y ago
        I find the avalanche maps used here easier to grasp: http://home.comcast.net/~bretm/hash/5.html http://home.comcast.net/~bretm/hash/5.html Here is FNV, quite a lot of reds: http://home.comcast.net/~bretm/hash/6.html http://home.comcast.net/~bretm/hash/6.html And of course all green for SHA-1: http://home.comcast.net/~bretm/hash/9.html http://home.comcast.net/~bretm/hash/9.html
  - anxrn 13y ago
    A Fourier transform is not merely another graphical representation of data (although, it could be used as such). Among other things, it lends itself to generating features and analysis that can be used for detecting patterns by computer, not just humans.
edwintorok 13y ago
It doesn't mention SipHash: https://131002.net/siphash/ https://131002.net/siphash/
- JoachimS 13y ago
  If you have the reputation points, please suggest it to be included in the test on Stack Exchange. SipHash was developed to replace CityHash, Murmurhash as well as being a fast and secure PRF.
  - ygra 13y ago
    I added a comment to suggest it.
    - JoachimS 13y ago
      Thanks!
WayneS 13y ago
Nice answer. However in practice current Intel processors do CRC32 in hardware. This blows away the rest and has really nice results. So I use portable code that using Intel's slicing-by-8 CRC32 code for generic machines and then automatically uses SSE4.2 on x86's that most people are actually using.
dagss 13y ago
This seems to be very of date? My understanding was that when SipHash arrived it knocked out all of these? (Please correct me if I'm wrong.) This may be an interesting weakness with the StackOverflow system; if there's an answer that used to be very good, it may take a lot to knock it out of the first position when reality changes.
- bcoates 13y ago
  You can wiki-edit any SO answer (with low karma it's queued for approval before being shown), unfortunately it looks like something in the culture or UI prevents this from being common.
- mcguire 13y ago
  I don't know of a performance comparison between SipHash and other secure hashes other than [1], which compares it to MD5, "Python's new randomized hash, with a 128-bit key and 64-bit output", and a couple of SHA's. It is significantly slower than DJB2, though. [1] http://bench.cr.yp.to/results-auth.html http://bench.cr.yp.to/results-auth.html
ultimoo 13y ago
>>FNV-1a collisions >>altarage collides with zinke >>altarages collides with zinkes I found this most interesting. I have no idea how FNV-1a is constructed but I'm sure this is an interesting (mathematical?) quirk in an otherwise great algorithm since it had only 4 collisions for more than a couple of hundred thousand inputs.
- Brandon0 13y ago
  I saw that too. DJB2a also has >>playwright collides with snush >>playwrighting collides with snushing
- netdog 13y ago
  It's not surprising, and it is not peculiar to FNV-1a. Most of these hashes will exhibit this same behavior. Since the hash iterates over the characters in the string, once you find two colliding strings S and T, if you append any other string to both S and T, the hashes of S' and T' will also be identical. Try it yourself: #include <stdio.h> #include "hash_32a.c" int main(int argc, char* argv[]) { const char* s[] = { "altarage", "zinke", "altarage_foo", "zinke_foo", "altarage_xyzzy", "zinke_xyzzy" }; int i; for (i = 0; i < sizeof s / sizeof (char*); ++i) { Fnv32_t x = fnv_32a_str(s[i], FNV1_32A_INIT); printf("%s: %08x\n", s[i], x); } } $ ./test_fnv1a altarage: e460d8b6 zinke: e460d8b6 altarage_foo: 3d8619c5 zinke_foo: 3d8619c5 altarage_xyzzy: 2a6373cf zinke_xyzzy: 2a6373cf
- joshdick 13y ago
  Yeah, that seems to violate the goal of the avalanche effect. http://en.wikipedia.org/wiki/Avalanche_effect http://en.wikipedia.org/wiki/Avalanche_effect
  - dreish 13y ago
    That's a design goal for cryptographic hash functions, which these are not.
tracker1 13y ago
I'm curious as to why the emphasis on speed here? I would think that hashes are mostly for either confirming a payload, or as a security measure against plain text passwords/keys. I would think that at least in the latter, that less fast, more cpu/memory intensive would be more desirable. Something like SCRYPT may be overkill, especially if you use if for password hashes, under load for a lot of logins, but the comparison seems to fly in the face of that. This also doesn't really mention random seed/salt values.
- bradleyjg 13y ago
  I'd think it's far more common to use hashes for various data structures (i.e. hash map) than for cryptographic or data integrity purposes.
  - DerpDerpDerp 13y ago
    Even for data structures, you generally want to use a cryptographic hash function, to prevent collision and other similar attacks from degrading the performance of a data structure. For example, if I can sufficiently reverse your hashing process, I can degrade a hash tree in to a linked list for a particular set of data - something your firewalls and other security measures will have virtually no chance of stopping, but which will greatly increase the run time taken to parse (malicious) instructions about that data. A common use of this is maliciously chosen inserts of new items, to cause the tree structure to become a list building on it.
    - cheese_factory 13y ago
      Well, there are various applications when you don't necessarily need the cryptographic property. Hashing is widely used for large-scale back-end machine learning tasks (LSH, linear models...) where speed and randomness are the only properties that matter.
    - tibbe 13y ago
      Until recently I don't think any major hash table implementation (e.g. not Java, STL, Python, Ruby, etc) used a cryptographically secure hashing algorithm. They're just too slow. Slow enough that you might as well use a tree-based data structure, which doesn't suffer from hash-collision based attacks. This is changing a bit now when SipHash is available. Unfortunately SipHash still is a bit too slow and forces an uncomfortable trade-off.
dgacmu 13y ago
My research group at CMU uses a lot of hashing these days and we care mostly about performance. We've settled on three as our basics: - CityHash as a nice, general purpose hash, particularly on newer machines with CRC32c support in hardware; - SpookyHash for longer strings, particularly with no CRC32 support; - CRC32c in hardware for a quick & dirty hash with possibly slightly more poor distribution. It depends a lot on what you're hashing. For strings, both City and Spooky are great. You should benchmark both on your target architecture(s). If you're trying to take, e.g., integers to integers, we've found that CRC32c is a pretty darn good fallback if you need insanely high performance. If you're running a hash table exposed to externally controlled input, then you also want to consider (whether you need) algorithms that provide decent resistance against "hash flooding". SipHash is the strongest contender there short of throwing your hands in the air and using MD5 with a local secret seed.
- mcguire 13y ago
  I think it's worth reiterating your last paragraph. If your hash table is exposed to external input, an effective DoS attack can be mounted by turning your hash table into an expensive linked list. http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.h...
rkalla 13y ago
For those that love this topic, xxhash[1] has a SMHasher score of 10[2] and is ~2x as fast as MurMur3 -- really interesting, incredibly fast, high quality hash function. [1] https://code.google.com/p/xxhash [2] https://code.google.com/p/xxhash/wiki/xxh32
- tg3 13y ago
  I was going to say this as well. It has a Node.js port that I'm using for static file versioning, and the speed is great.
dllthomas 13y ago
The best hash algorithm for uniqueness and speed uses knowledge of the distribution of the incoming values and exploits whatever patterns are available. It's not one-size-fits-all. If I am being fed arbitrary binary blobs, taking the first 4 bytes might be as unique as any other approach (and will clearly be faster than anything else that actually depends on the data). If I am being fed English test, that is going to perform horribly on uniqueness. If the source of the data might benefit (DoS attack being a common example) from deliberately causing collisions then there are additional constraints and looking at cryptographic hash functions may be warranted.
arek2 13y ago
>CRC32 collisions >codding collides with gnu accident?
jorangreef 13y ago
If you are hashing fixed-size keys, then tabulation hashing is simple and fast with good theoretical properties: http://en.wikipedia.org/wiki/Tabulation_hashing http://en.wikipedia.org/wiki/Tabulation_hashing http://rcoh.me/pyhash.pdf http://rcoh.me/pyhash.pdf

243 points by fekberg 13y ago

It's worth remembering that when selecting things at random from a given pool, there is always a chance of collision. If you think of a hash as taking a value to a "random" result, with different objects going to results uniformly "at random", then you have to expect collisions. This is why the term "perfect hash" is defined so carefully. For those who are interested, the probability of collision, then size of the hash destination, and the number of objects chosen are related by this formula: Choosing from N items, with N large, and wanting a probability T of having no collisions, the number of items you can choose at random with replacement is: k ~ sqrt( -2 N ln(T) ) So T ~ exp(-(k^2)/(2N)) Source: http://www.solipsys.co.uk/new/TheBirthdayParadox.html?HN20131014 http://www.solipsys.co.uk/new/TheBirthdayParadox.html?HN2013...

dllthomas 13y ago
There's always a chance of a collision, but for a large enough pool relative to the number of objects the chance may be sufficiently smaller than the chance of hardware failure that it can be legitimately ignored. For something where the entire space must in some way be realized (eg. hashtable) this won't be the case, obviously.
- Someone 13y ago
  Most of the time, that isn't true. Hardware failures are (barring quality control issues) independent, hash collisions are not. For example, if you assume your hash will not have collisions, and design your hash table without any mechanism for coping with one, and it happens to have a clash on "Jones" and "Smith", your address book app will become unreliable for a rather large fraction of your users.
  - dllthomas 13y ago
    But at the scales we're talking about, it won't happen to have a clash on "Jones" and "Smith". This won't be a hash table - this will be things like a git commit hash, where generating 1/ns is likely to give a collision in 3 years, before which the storage required just to store hashes is in the yottabytes.

sukaka 13y ago

seeing at least 1 collision the tests makes me wonder why the chance of a bitcoin address collision is almost nil. https://en.bitcoin.it/wiki/Weaknesses#Generating_tons_of_addresses https://en.bitcoin.it/wiki/Weaknesses#Generating_tons_of_add...

betterunix 13y ago
Cryptographic hashes are an entire category of hash functions unto themselves. The absolute minimum guarantee that a cryptographic hash makes is that for any polynomial time algorithm, the probability of the algorithm computing a pair (x,y) such that x != y and H(x) = H(y) is "negligible" i.e. is smaller than 1/p(n) for all polynomials p and large enough n; in other words, cryptographic hashes guarantee that collisions are extremely rare. Much like you can create a cipher with security that is reducible to the hardness of some problem (e.g. ElGamal is secure if the Diffie-Hellman problem is hard), it is possible to create collision resistant hashes with such security proofs, e.g. Very Smooth Hash, SWIFFT. In practice, though, we just use hashes that are believed to be security according to heuristic tests; hence the need to periodically update standard hash functions, rather than to just increase parameter sizes. Also interesting is universal hashing, which has applicability in cryptography (for randomness extraction, among other things): https://en.wikipedia.org/wiki/Universal_hashing https://en.wikipedia.org/wiki/Universal_hashing
vertex-four 13y ago
Bitcoin uses a cryptographic hash function, SHA256. There are, at present, no known collisions with SHA256. This question is about non-cryptographic hash functions, as are commonly used in hash tables[1] which implement associative arrays, or sharding databases based on the hash of the record key. Non-cryptographic hash functions are simply not in the same league as cryptographic ones; cryptographic hash functions are optimized to make it infeasible for an attacker to generate a different message with the same hash, while a non-cryptographic hash function generally simply has to have uniformly random output over its keyspace. [1] http://en.wikipedia.org/wiki/Hash_table http://en.wikipedia.org/wiki/Hash_table
- VLM 13y ago

noelwelsh 13y ago

Nice analysis. Since that post was submitted Murmurhash 3 and a number of other notable hash functions have been released. If you liked the linked post you should go read Aggregate Knowledge's series of posts on hash functions for a look at some newer algorithms: http://blog.aggregateknowledge.com/2012/02/02/choosing-a-good-hash-function-part-3/ http://blog.aggregateknowledge.com/2012/02/02/choosing-a-goo...

devx 13y ago

Would the security of such algorithms improve dramatically if say 5 years from now we'd live in a world where everyone has a 64-bit device or machine, and the algorithms can be optimized for 64-bit? Are current algorithms limited by 32-bit a lot or not really?

ctz 13y ago
Security of such algorithms now: none. Security of such algorithms now where everyone has a 64-bit device: none. Don't confuse hash functions like these and cryptographic hash functions.

ot 13y ago

A more thorough test suite for hash function is SMHasher, by the same author of MurmurHash. It measures collisions, output uniformity, biased bits, etc... as well as speed, under several input distributions. https://code.google.com/p/smhasher/ https://code.google.com/p/smhasher/ Here is the output for some popular hash functions: https://code.google.com/p/smhasher/wiki/SMHasherDump https://code.google.com/p/smhasher/wiki/SMHasherDump

tibbe 13y ago
If someone could run smhasher for the hash functions in the original article (and perhaps also MurmurHash 2/3) and summarize the result for the small key sizes I will give them a cookie.
- gregrata 13y ago
  I REALLY think we're all tired of random people giving us yet another cookie to store...

easytiger 13y ago

cityhash - http://code.google.com/p/cityhash/ http://code.google.com/p/cityhash/

deleted 13y ago

[deleted]

waynecochran 13y ago

> Yes. I started writing my test program to see if hash > collisions actually happen - and are not just a theoretical construct. This should be no surprise. The birthday paradox, as Knuth points in in TAoCP, makes it clear why collisions happen. Given 23 people in a room, there is a greater that 50% chance that at least two have the same birthday. Placing only 23 keys into a hash table with 365 entries with a perfectly random hash function will probably result in at least one collision.

ColinWright 13y ago
Placing only 23 keys into a hash table with 365 entries with a perfectly random hash function will probably result in at least one collision. No, it won't "probably" result in at least one collision, it will result in at least one collision with probability about 1/2. As quoted elsewhere, placing k objects in a hash table with N entries will result in no collisions with probability about exp(-(k^2)/(2N)).
- abentspoon 13y ago
  Interesting. I was going to complain, as I thought "probably" meant the probability of occurrence was greater than 50%.. That doesn't seem to be the case. Probably: almost certainly; as far as one knows or can tell I would guess waynecochran thought something similar.
  - ColinWright 13y ago
    Curious. I've just taken a straw poll in the office. I asked "if someone said something was probably going to happen, what probability would you give it?" The answers were: * 80% * 50% to 90% * 90% * > 80% * 80% * 80% to 90%
    - StavrosK 13y ago
      My guess would have been "exactly strictly higher than 50%".

jameshart 13y ago

One issue to be careful of is assuming that you don't need the guarantees a cryptographic hash provides (preimage resistance, extension resistance, etc.) in your application. If an adversary can force hash collisions they may, depending on your uses for the hashing algorithm, be able to cause degredation or denial of service, or perhaps trigger information disclosures if they're very smart. If there's any way in which an attacker might be able to have some control over the dataset you are hashing you should probably be looking at using a cryptographic hash anyway.

fragsworth 13y ago
Is denial of service from an attacker who has your source something you actually consider when building a product? I can see trying to prevent data breaches and such, but going so far as to be wary of denial of service attacks from people who have your source code might be wasted effort.
- dllthomas 13y ago
  You should code as if any attacker has your source. If denial of service attacks are something you need to consider, you need to consider them from someone who has your source.
  - fragsworth 13y ago
    Denial of service attacks are usually not devastating (they've happened to many large services multiple times) and there's a very real engineering cost in being absolutely certain that you are immune to such attacks. I think most people here don't fall under the umbrella of those who need to consider denial-of-service attacks. When your primary goal should be to launch your product (which you aren't even sure will take off) I would think trying to prevent denial-of-service attacks is a waste of time.
    - dllthomas 13y ago
      I'm not sure I disagree with any of that. I simply said that if you need to consider DoS you should consider DoS with the assumption your attacker has access to your source.

svag 13y ago

It is worth mentioning that the libstdc++, in version 4.6.3 at least, it has implemented the Murmur and FNV hash function for user defined key types. If you want to use Murmur you use std::_Hash_impl::hash and for FNV you use std::_Fnv_hash_impl::hash. (Include bits/functional_hash.h) The implementation is at libsupc++/hash_bytes.cc

ppierald 13y ago

gperf - https://www.gnu.org/software/gperf/ https://www.gnu.org/software/gperf/ This is a "perfect" application of a "perfect hash" generator.

bcoates 13y ago

I often see these "plot the output of the RNG on a 2d grid" things. I understand they're useful for demonstrating non-randomness, but if you're searching for patterns, do they reveal anything an FFT wouldn't?

baq 13y ago
isn't fft just a different way of looking at the data?
- USNetizen 13y ago
  Essentially, yes, that was my understanding, too. I've only used in in signal processing - converting from the time domain to the frequency domain. Not sure how that would apply to this.
  - bcoates 13y ago
    I was thinking specifically of this: When i look at the FNV-1a "number" map, i think i see subtle vertical patterns. With Murmur i see no patterns at all. What do you think? Wouldn't that vertical repetition, and the other repeating patterns the other hashes form, show up as a nice spike in the frequency domain? Whereas I would expect uniform hashing to generate a flat, white-noise spectrum.
    - edwintorok 13y ago
      I find the avalanche maps used here easier to grasp: http://home.comcast.net/~bretm/hash/5.html http://home.comcast.net/~bretm/hash/5.html Here is FNV, quite a lot of reds: http://home.comcast.net/~bretm/hash/6.html http://home.comcast.net/~bretm/hash/6.html And of course all green for SHA-1: http://home.comcast.net/~bretm/hash/9.html http://home.comcast.net/~bretm/hash/9.html
- anxrn 13y ago
  A Fourier transform is not merely another graphical representation of data (although, it could be used as such). Among other things, it lends itself to generating features and analysis that can be used for detecting patterns by computer, not just humans.

edwintorok 13y ago

It doesn't mention SipHash: https://131002.net/siphash/ https://131002.net/siphash/

JoachimS 13y ago
If you have the reputation points, please suggest it to be included in the test on Stack Exchange. SipHash was developed to replace CityHash, Murmurhash as well as being a fast and secure PRF.
- ygra 13y ago
  I added a comment to suggest it.
  - JoachimS 13y ago
    Thanks!

WayneS 13y ago

Nice answer. However in practice current Intel processors do CRC32 in hardware. This blows away the rest and has really nice results. So I use portable code that using Intel's slicing-by-8 CRC32 code for generic machines and then automatically uses SSE4.2 on x86's that most people are actually using.

dagss 13y ago

This seems to be very of date? My understanding was that when SipHash arrived it knocked out all of these? (Please correct me if I'm wrong.) This may be an interesting weakness with the StackOverflow system; if there's an answer that used to be very good, it may take a lot to knock it out of the first position when reality changes.

bcoates 13y ago
You can wiki-edit any SO answer (with low karma it's queued for approval before being shown), unfortunately it looks like something in the culture or UI prevents this from being common.
mcguire 13y ago
I don't know of a performance comparison between SipHash and other secure hashes other than [1], which compares it to MD5, "Python's new randomized hash, with a 128-bit key and 64-bit output", and a couple of SHA's. It is significantly slower than DJB2, though. [1] http://bench.cr.yp.to/results-auth.html http://bench.cr.yp.to/results-auth.html

ultimoo 13y ago

>>FNV-1a collisions >>altarage collides with zinke >>altarages collides with zinkes I found this most interesting. I have no idea how FNV-1a is constructed but I'm sure this is an interesting (mathematical?) quirk in an otherwise great algorithm since it had only 4 collisions for more than a couple of hundred thousand inputs.

Brandon0 13y ago
I saw that too. DJB2a also has >>playwright collides with snush >>playwrighting collides with snushing
netdog 13y ago
It's not surprising, and it is not peculiar to FNV-1a. Most of these hashes will exhibit this same behavior. Since the hash iterates over the characters in the string, once you find two colliding strings S and T, if you append any other string to both S and T, the hashes of S' and T' will also be identical. Try it yourself: #include <stdio.h> #include "hash_32a.c" int main(int argc, char* argv[]) { const char* s[] = { "altarage", "zinke", "altarage_foo", "zinke_foo", "altarage_xyzzy", "zinke_xyzzy" }; int i; for (i = 0; i < sizeof s / sizeof (char*); ++i) { Fnv32_t x = fnv_32a_str(s[i], FNV1_32A_INIT); printf("%s: %08x\n", s[i], x); } } $ ./test_fnv1a altarage: e460d8b6 zinke: e460d8b6 altarage_foo: 3d8619c5 zinke_foo: 3d8619c5 altarage_xyzzy: 2a6373cf zinke_xyzzy: 2a6373cf
joshdick 13y ago
Yeah, that seems to violate the goal of the avalanche effect. http://en.wikipedia.org/wiki/Avalanche_effect http://en.wikipedia.org/wiki/Avalanche_effect
- dreish 13y ago
  That's a design goal for cryptographic hash functions, which these are not.

tracker1 13y ago

I'm curious as to why the emphasis on speed here? I would think that hashes are mostly for either confirming a payload, or as a security measure against plain text passwords/keys. I would think that at least in the latter, that less fast, more cpu/memory intensive would be more desirable. Something like SCRYPT may be overkill, especially if you use if for password hashes, under load for a lot of logins, but the comparison seems to fly in the face of that. This also doesn't really mention random seed/salt values.

bradleyjg 13y ago
I'd think it's far more common to use hashes for various data structures (i.e. hash map) than for cryptographic or data integrity purposes.
- DerpDerpDerp 13y ago
  Even for data structures, you generally want to use a cryptographic hash function, to prevent collision and other similar attacks from degrading the performance of a data structure. For example, if I can sufficiently reverse your hashing process, I can degrade a hash tree in to a linked list for a particular set of data - something your firewalls and other security measures will have virtually no chance of stopping, but which will greatly increase the run time taken to parse (malicious) instructions about that data. A common use of this is maliciously chosen inserts of new items, to cause the tree structure to become a list building on it.
  - cheese_factory 13y ago
    Well, there are various applications when you don't necessarily need the cryptographic property. Hashing is widely used for large-scale back-end machine learning tasks (LSH, linear models...) where speed and randomness are the only properties that matter.
  - tibbe 13y ago
    Until recently I don't think any major hash table implementation (e.g. not Java, STL, Python, Ruby, etc) used a cryptographically secure hashing algorithm. They're just too slow. Slow enough that you might as well use a tree-based data structure, which doesn't suffer from hash-collision based attacks. This is changing a bit now when SipHash is available. Unfortunately SipHash still is a bit too slow and forces an uncomfortable trade-off.

dgacmu 13y ago

My research group at CMU uses a lot of hashing these days and we care mostly about performance. We've settled on three as our basics: - CityHash as a nice, general purpose hash, particularly on newer machines with CRC32c support in hardware; - SpookyHash for longer strings, particularly with no CRC32 support; - CRC32c in hardware for a quick & dirty hash with possibly slightly more poor distribution. It depends a lot on what you're hashing. For strings, both City and Spooky are great. You should benchmark both on your target architecture(s). If you're trying to take, e.g., integers to integers, we've found that CRC32c is a pretty darn good fallback if you need insanely high performance. If you're running a hash table exposed to externally controlled input, then you also want to consider (whether you need) algorithms that provide decent resistance against "hash flooding". SipHash is the strongest contender there short of throwing your hands in the air and using MD5 with a local secret seed.

mcguire 13y ago
I think it's worth reiterating your last paragraph. If your hash table is exposed to external input, an effective DoS attack can be mounted by turning your hash table into an expensive linked list. http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.h...

rkalla 13y ago

For those that love this topic, xxhash[1] has a SMHasher score of 10[2] and is ~2x as fast as MurMur3 -- really interesting, incredibly fast, high quality hash function. [1] https://code.google.com/p/xxhash [2] https://code.google.com/p/xxhash/wiki/xxh32

tg3 13y ago
I was going to say this as well. It has a Node.js port that I'm using for static file versioning, and the speed is great.

dllthomas 13y ago

The best hash algorithm for uniqueness and speed uses knowledge of the distribution of the incoming values and exploits whatever patterns are available. It's not one-size-fits-all. If I am being fed arbitrary binary blobs, taking the first 4 bytes might be as unique as any other approach (and will clearly be faster than anything else that actually depends on the data). If I am being fed English test, that is going to perform horribly on uniqueness. If the source of the data might benefit (DoS attack being a common example) from deliberately causing collisions then there are additional constraints and looking at cryptographic hash functions may be warranted.

arek2 13y ago

>CRC32 collisions >codding collides with gnu accident?

jorangreef 13y ago

If you are hashing fixed-size keys, then tabulation hashing is simple and fast with good theoretical properties: http://en.wikipedia.org/wiki/Tabulation_hashing http://en.wikipedia.org/wiki/Tabulation_hashing http://rcoh.me/pyhash.pdf http://rcoh.me/pyhash.pdf