15 ms·

Which hashing algorithm is best for uniqueness and speed?

336 points by suprgeek 14y ago

mlok 14y ago
There is a python wrapper for murmur3 here : http://stackoverflow.com/a/5400389 http://stackoverflow.com/a/5400389
jorangreef 14y ago
FNV despite much popularity is a relatively poor quality hash. Murmur2 has a major flaw, hence Murmur3. CRC32 is slow. Not mentioned in the post, but if you're thinking Fletcher or Adler, they have terrible distribution. For a fast 32-bit hash, much better to go with Bob Jenkin's one-at-a-time hash (http://en.wikipedia.org/wiki/Jenkins_hash_function#one-at-a-time http://en.wikipedia.org/wiki/Jenkins_hash_function#one-at-a-...) which is simpler than Murmur3 and displays much better avalanche characteristics than the other hashes.
- dkersten 14y ago
  According to this site[1], CrapWow seems to be the best in raw performance: http://www.team5150.com/~andrew/noncryptohashzoo/CrapWow.html http://www.team5150.com/~andrew/noncryptohashzoo/CrapWow.htm... (Crap8 in second place and Murmur3 in third place - one at a time performs quite badly in this guys benchmarks) Performance graphs: http://www.team5150.com/~andrew/noncryptohashzoo/speed.html http://www.team5150.com/~andrew/noncryptohashzoo/speed.html [1] http://www.team5150.com/~andrew/noncryptohashzoo/ http://www.team5150.com/~andrew/noncryptohashzoo/
  - trebor 14y ago
    What about its randomness compared to Murmur2/3?
moe 14y ago
Why did he omit the standards (MD5 and SHA1) from the comparison?
- afsina 14y ago
  These are not cryptographic hashes. Comparison would be unfair as cryptographic ones are rather slow . These are used in structures like Hash tables or Bloom Filters etc. they need to be very fast and provide reasonable randomness (low collision). Bu their collision rates are very high comparing to say SHA1.
  - bennysaurus 14y ago
    >@Orbling, for implementation of a hash dictionary. So collisions should be kept to a minimal, but it has no security purpose at all. – Earlz SHA-1 is very fast though so it is a good point for comparison.
    - IsTom 14y ago
      SHA-1 was designed as a cryptographic hash functions, they are puprposely slow. No, SHA-1 is not as fast as functions from the article.
      - pjscott 14y ago
        You've got it backwards; cryptographic hash functions are designed to be as fast as possible without giving up their cryptographic properties. If you need a slow hash (e.g. for password storage), you use something like bcrypt that's designed to be slow.
    - masklinn 14y ago
      > SHA-1 is very fast though SHA-1 is fast for a cryptographic hash function, but it's orders of magnitude slower than "hashmap" hashes. crc32 is more than an order of magnitude faster, and as you can see in TFA's table it's ~half the speed of the best non-crypto hashes.
  - moe 14y ago
    Still it would be useful to see them as a point of reference - to determine whether it's worth bothering with anything else in first place.
esbwhat 14y ago
isn't slow better in this case? I mean if it's fast to generate, it's fast to crack, right?
- bmj1 14y ago
  Given Moore's law and the prevalence of botnets and cloud computing - hash speed really isn't a very strong means of defence against cracking... Also see: http://cyberarms.wordpress.com/2010/10/21/cracking-14-character-complex-passwords-in-5-seconds/ http://cyberarms.wordpress.com/2010/10/21/cracking-14-charac...
  - masklinn 14y ago
    Uh? Hash speed is pretty much the only means of defense against brute-force cracking (assuming the hash function isn't broken and the attacker has no other vector available). (low) hash speed is the whole point of PBKDF2, bcrypt or scrypt.
    - bmj1 14y ago
      You'll find that adding a long salt, unique to each password, is a far more effective protector against brute force than "hash speed". See this: http://net.tutsplus.com/tutorials/php/understanding-hash-functions-and-keeping-passwords-safe/ http://net.tutsplus.com/tutorials/php/understanding-hash-fun... and: http://stackoverflow.com/questions/1191112/password-hashing-salt-and-storage-of-hashed-values http://stackoverflow.com/questions/1191112/password-hashing-... to learn more about preventing brute-force attacks
      - masklinn 14y ago
        > You'll find that adding a long salt, unique to each password, is a far more effective protector against brute force than "hash speed". No, I'll find that you've apparently stopped your education at hashing 101 and hashing speed is covered in hashing 102. 1. It's not an either-or situation, all three hashes I mentioned not only specifically include salts in their hashing interface but go as far as mandating a salt for brypt and scrypt (I don't believe PBKDF2 mandates one though it surely is recommended) 2. Salts don't protect much against brute-force attacks, their primary role is to protect against rainbow tables (dictionary attacks) in case the hashed data is leaked. They do add cost to brute-forcing a series of passwords (if salts are unique), but that cost is low compared to 3. Hash speed mitigates brute-forcing from both inside (leaked data) and outside (provide built-in rate-limiting, of course additional rate-limiting is still a good idea). Increasing the raw cost of computing the hash by multiple orders of magnitude and adding data dependencies within the hash (to prevent trivial parallelization) are very much vital against brute-force attacks. 4. You might have wanted to read your own bloody links, the first one specifically mentions hash speed to mitigate brute force attacks, and mentions salts only against rainbow tables; responses to the second one specifically note that salt mitigate rainbow table attacks but do not significantly mitigate brute force attacks especially on weak passwords.
MichaelGG 14y ago
MurmurHash2, which is pretty great, has some issues: "MurmurHash2_x86_64 computes two 32-bit results in parallel and mixes them at the end, which is fast but means that collision resistance is only as good as a 32-bit hash. I suggest avoiding this variant."[1] Murmurhash3 has a 128-bit variant, which might be more along the lines of what he's looking for (the original post mentions SHA256). 1: http://code.google.com/p/smhasher/wiki/MurmurHash3 http://code.google.com/p/smhasher/wiki/MurmurHash3
- martincmartin 14y ago
  Computing two 32-bit results in parallel and mixing them at the end does NOT mean collision resistance is only as good as a 32-bit hash. For that, you need to compute ONE 32-bit result, then transform it into a 64-bit result.
  - finnw 14y ago
    Depends whether the two 32-bit hashes are correlated with each other. If there is no correlation then a pair of 32-bit hashes is no more likely to collide than a single 64-bit hash. But this is difficult to achieve, and you should not assume (for example) running the same algorithm twice with different initial states will produce uncorrelated hashes.
    - martincmartin 14y ago
      Very true.
- ecaron 14y ago
  I thought Google's CityHash - http://code.google.com/p/cityhash/source/browse/trunk/README http://code.google.com/p/cityhash/source/browse/trunk/README - was their successor to the MurmurHash variants.
  - spullara 14y ago
    CityHash doesn't have a 32-bit variant to participate in the benchmark. http://code.google.com/p/cityhash/issues/detail?id=2 http://code.google.com/p/cityhash/issues/detail?id=2
p4bl0 14y ago
Very interesting, thanks for sharing. "CRC32 collisions: codding collides with gnu". At first I read "coding" and I was all "haha this must be an easter egg of the implementation".
- drucken 14y ago
  The irony is that codding [British English] means a practical joke or trick on someone. :)
tmeasday 14y ago
Why don't I see any mentions of the latest research? There are people out there that do this for a living people!
- marcusf 14y ago
  I find stuff like this terribly interesting, so please elaborate. Any journal or so that is recommended for someone curious?
  - tmeasday 14y ago
    I'm not active in the field right now, so I can't give specifics (the comment was more borne out of frustration with people putting in so much effort 'reinventing the wheel' in an academic sense). But if I was you, I'd start with Knuth (he, as another commenter mentioned, covers hashes in great detail), head to the references, and then use Google Scholar to find well-cited recent articles that reference the important papers mentioned there.
    - pwaring 14y ago
      Unfortunately though, a lot of the papers that turn up in Google Scholar are behind paywalls. It is very expensive to get hold of academic papers if you don't work/study somewhere with an institutional licence (anything from $10 upwards per paper).
      - tmeasday 14y ago
        Yup, that's the world of academic publishing unfortunately. A tip: often you can get a 'preprint' copy of the paper from one of the authors' websites. Probably not strictly legal, but it does happen a lot.
    - marcusf 14y ago
      Thanks very much! Might be finally time to cough up the dough for TAOCP then and take it from there.
akg 14y ago
Donald Knuth's Art of Computer Programming Volume 3 has an excellent exposition on hash functions and hash tables in general. If you can get yourself a copy I would highly recommend the read.
IgorPartola 14y ago
Honest question: why not use 2-3 different hash algorithms to minimize collisions if you are simply after uniqueness (e.g.: verifying that a downloaded file is correct)? As for hash tables, can't you guarantee uniqueness by using only reversible operations? I remember reading a lengthy post about this on HN, but can't find the link anymore.
- gizzlon 14y ago
  >As for hash tables, can't you guarantee uniqueness by using only reversible operations? Wouldn't that make the output almost as long as the input, defeating the purpose?
  - its_so_on 14y ago
    actually, just as long. Any set of possible bits is a valid input, so the input has one bit of entropy per bit. If the hash were not "just as long" then one of the following must be true: - it collides (two possible inputs would have the same hash) - some inputs could not hash - the algorithm encodes more than 2 bits of entropy per bit. This is not possible by the pigeonhole principle. http://en.wikipedia.org/wiki/Pigeonhole_principle http://en.wikipedia.org/wiki/Pigeonhole_principle There's probably a more rigorous proof here but I'm lazy. I guess something like imagine the input is going to be n bits (like 16 bits)...make an array of length 2^n and initialize them all to -1, and then for each possible input (0..2^n-1) hash it and - since the hash is not longer than the input, the representation of the hash is there in the array if you simply interpret it as the index (subscript). Set that to the n that produced it, if it's not already set (otherwise abort with a collision). After you have reached 2^n-1, you have set 2^n indices (including whatever hash 0 produced). Is it possible for you not to have made a collision? (Yes, easily: for example anything hashes to the next integer, except binary all 1's which hash to all 0's). Could some of the indices to be empty? No. If you put 2^n values in 2^n holes distinctly, there is one value per hole. Conversely, if you had anything LESS than that many holes to put it into (for example, you're trying to hash 32 bits of input into just the lower half of the indices, by creating a hash that uniquely hashes to 16 bits of output) then by the pigeonhole prinicpal you have to put two n's into the same index. So, any hash that would be unique (that can hash anything) has to be at least exactly as long as what it's hashing. If there are any outputs that are never hashed to, it would have to be even longer. Note that this proof depends on iterating on every possible input. If some inputs aren't possible, the hash could be unique while being shorter than the input. This is how lossless compression works.
potkor 14y ago
Going by just the subject, maybe a perfect hash function generated with eg. GNU gperf?
leif 14y ago
I wish he provided the architecture he ran on. Nehalem and later cores have crc32 instructions that are quite zippy.
memset 14y ago
Question: say you use a hash which returns a 32-bit integer. If you were actually implementing a hash table, would you need to declare a structure with 2^32 elements? `int buckets[2^32]`? This seems unwieldy! Would an actual hash table only use, say, the first 10 bits or something of a hash function (int buckets[1024]) to make it less sparse (albeit increase collisions?) If you decide you want more buckets later on, would you have to re-hash everything in your array and move it to a new, bigger one?
- jrmg 14y ago
  Yeah, you've pretty much got it. A common alternative to masking bits off of the hash is to take hash modulo the size of the table as the index (although you have to be careful with a modulo strategy, so as not to introduce a bias towards certain table slots). There are strategies to make the resize not be so expensive. Wikipedia's page on Hash Tables covers this at http://en.wikipedia.org/wiki/Hash_table#Dynamic_resizing http://en.wikipedia.org/wiki/Hash_table#Dynamic_resizing [edit: clarity in the first paragraph]
  - viggity 14y ago
    iirc, there is a major advantage to using a prime number of slots that prevents the biasing
    - hythloday 14y ago
      It's to protect against bad hashing algorithms: http://www.concentric.net/~Ttwang/tech/primehash.htm http://www.concentric.net/~Ttwang/tech/primehash.htm
  - Jabbles 14y ago
    Does the modulo operation add a negligible cost to these (very cheap) hashing functions? i.e. if you're hashing a 10 character (non-unicode) word with FNV-1a you're using 10 multiplications and 10 xors. Adding a modulo (by a prime†) operation in there could feasibly double the time taken. †Not 2...
losethos 14y ago
I use this: result=0; while (ch=*src++) result=result<<1+ch; I do it an assembly language. I'm self confident enough to say, it can't be beat.
gizzlon 14y ago
Found these by coincidence, might be interesting to some of you.. (can't speak to the content) http://blog.aggregateknowledge.com/2011/12/05/choosing-a-good-hash-function-part-1/ http://blog.aggregateknowledge.com/2011/12/05/choosing-a-goo... http://blog.aggregateknowledge.com/2011/12/29/choosing-a-good-hash-function-part-2/ http://blog.aggregateknowledge.com/2011/12/29/choosing-a-goo... http://blog.aggregateknowledge.com/2012/02/02/choosing-a-good-hash-function-part-3/ http://blog.aggregateknowledge.com/2012/02/02/choosing-a-goo...
bmm6o 14y ago
If you think this is the sort of answer that Stack Overflow should strive for, note that the author edited it too many times and it fell into "Community Wiki" status. Until this was reverted in a manual process, the author didn't receive any points for his answer.
- sathyabhat 14y ago
  Well, not entirely. Reverting the CW restores the rep, subject to daily rep limit. The answer's been given 3 separate bounties (100, 100,50) which are not affected by CW.
  - bmm6o 14y ago
    1) It still required manual intervention from a moderator. 2) I'm certainly not an expert on how SE distributes its points, but the moderator comment in the related meta post (http://meta.programmers.stackexchange.com/questions/3527/remove-cw-status-for-this-answer-hashing-algorithms-testing-by-ian-boyd http://meta.programmers.stackexchange.com/questions/3527/rem...) states "I don't think there is a way to refund the reputation the answer gained while it was CW [...]"
- dclowd9901 14y ago
  Community Wiki is immortality.
pbreit 14y ago
How do folks generally take an autoincrementing database ID and generate a hash to be used "in public" when trying to avoid revealing obviously serial numbers? I don't think I need something airtight, in fact in one system we just multiplied/divided by a 4 digit prime number. While this worked fine, it seemed a little loose.
- eli 14y ago
  HASH(<id> + "static string pad") is how I imagine most people do it. Depends how much you care about a dedicated attacker figuring out that ID. If this is a thing you're going to use a lot, I'd probably just add a database column and give each record a random unique "public ID" -- then there is literally no connection between the public ID and the private one..
- buddydvd 14y ago
  Look into format-preserving encryption. I wrote something that allows you to generate permutations for an arbitrary sized range. With it, there are no collisions.
jorangreef 14y ago
If you're doing 32-bit hashes in Javascript and are willing to trade a bit, then a 31-bit hash may be at least an order of magnitude faster due to VM implementation: https://groups.google.com/d/msg/v8-users/zGCS_wEMawU/6mConTiBUyMJ https://groups.google.com/d/msg/v8-users/zGCS_wEMawU/6mConTi...
kolo32 14y ago
More tests: http://www.strchr.com/hash_functions http://www.strchr.com/hash_functions

336 points by suprgeek 14y ago

mlok 14y ago

There is a python wrapper for murmur3 here : http://stackoverflow.com/a/5400389 http://stackoverflow.com/a/5400389

FNV despite much popularity is a relatively poor quality hash. Murmur2 has a major flaw, hence Murmur3. CRC32 is slow. Not mentioned in the post, but if you're thinking Fletcher or Adler, they have terrible distribution. For a fast 32-bit hash, much better to go with Bob Jenkin's one-at-a-time hash (http://en.wikipedia.org/wiki/Jenkins_hash_function#one-at-a-time http://en.wikipedia.org/wiki/Jenkins_hash_function#one-at-a-...) which is simpler than Murmur3 and displays much better avalanche characteristics than the other hashes.

dkersten 14y ago
According to this site[1], CrapWow seems to be the best in raw performance: http://www.team5150.com/~andrew/noncryptohashzoo/CrapWow.html http://www.team5150.com/~andrew/noncryptohashzoo/CrapWow.htm... (Crap8 in second place and Murmur3 in third place - one at a time performs quite badly in this guys benchmarks) Performance graphs: http://www.team5150.com/~andrew/noncryptohashzoo/speed.html http://www.team5150.com/~andrew/noncryptohashzoo/speed.html [1] http://www.team5150.com/~andrew/noncryptohashzoo/ http://www.team5150.com/~andrew/noncryptohashzoo/
- trebor 14y ago
  What about its randomness compared to Murmur2/3?

moe 14y ago

Why did he omit the standards (MD5 and SHA1) from the comparison?

afsina 14y ago
These are not cryptographic hashes. Comparison would be unfair as cryptographic ones are rather slow . These are used in structures like Hash tables or Bloom Filters etc. they need to be very fast and provide reasonable randomness (low collision). Bu their collision rates are very high comparing to say SHA1.
- bennysaurus 14y ago
  >@Orbling, for implementation of a hash dictionary. So collisions should be kept to a minimal, but it has no security purpose at all. – Earlz SHA-1 is very fast though so it is a good point for comparison.
  - IsTom 14y ago
    SHA-1 was designed as a cryptographic hash functions, they are puprposely slow. No, SHA-1 is not as fast as functions from the article.
    - pjscott 14y ago
      You've got it backwards; cryptographic hash functions are designed to be as fast as possible without giving up their cryptographic properties. If you need a slow hash (e.g. for password storage), you use something like bcrypt that's designed to be slow.
  - masklinn 14y ago
    > SHA-1 is very fast though SHA-1 is fast for a cryptographic hash function, but it's orders of magnitude slower than "hashmap" hashes. crc32 is more than an order of magnitude faster, and as you can see in TFA's table it's ~half the speed of the best non-crypto hashes.
- moe 14y ago
  Still it would be useful to see them as a point of reference - to determine whether it's worth bothering with anything else in first place.

esbwhat 14y ago

isn't slow better in this case? I mean if it's fast to generate, it's fast to crack, right?

bmj1 14y ago
Given Moore's law and the prevalence of botnets and cloud computing - hash speed really isn't a very strong means of defence against cracking... Also see: http://cyberarms.wordpress.com/2010/10/21/cracking-14-character-complex-passwords-in-5-seconds/ http://cyberarms.wordpress.com/2010/10/21/cracking-14-charac...
- masklinn 14y ago
  Uh? Hash speed is pretty much the only means of defense against brute-force cracking (assuming the hash function isn't broken and the attacker has no other vector available). (low) hash speed is the whole point of PBKDF2, bcrypt or scrypt.
  - bmj1 14y ago
    You'll find that adding a long salt, unique to each password, is a far more effective protector against brute force than "hash speed". See this: http://net.tutsplus.com/tutorials/php/understanding-hash-functions-and-keeping-passwords-safe/ http://net.tutsplus.com/tutorials/php/understanding-hash-fun... and: http://stackoverflow.com/questions/1191112/password-hashing-salt-and-storage-of-hashed-values http://stackoverflow.com/questions/1191112/password-hashing-... to learn more about preventing brute-force attacks
    - masklinn 14y ago
      > You'll find that adding a long salt, unique to each password, is a far more effective protector against brute force than "hash speed". No, I'll find that you've apparently stopped your education at hashing 101 and hashing speed is covered in hashing 102. 1. It's not an either-or situation, all three hashes I mentioned not only specifically include salts in their hashing interface but go as far as mandating a salt for brypt and scrypt (I don't believe PBKDF2 mandates one though it surely is recommended) 2. Salts don't protect much against brute-force attacks, their primary role is to protect against rainbow tables (dictionary attacks) in case the hashed data is leaked. They do add cost to brute-forcing a series of passwords (if salts are unique), but that cost is low compared to 3. Hash speed mitigates brute-forcing from both inside (leaked data) and outside (provide built-in rate-limiting, of course additional rate-limiting is still a good idea). Increasing the raw cost of computing the hash by multiple orders of magnitude and adding data dependencies within the hash (to prevent trivial parallelization) are very much vital against brute-force attacks. 4. You might have wanted to read your own bloody links, the first one specifically mentions hash speed to mitigate brute force attacks, and mentions salts only against rainbow tables; responses to the second one specifically note that salt mitigate rainbow table attacks but do not significantly mitigate brute force attacks especially on weak passwords.

MichaelGG 14y ago

MurmurHash2, which is pretty great, has some issues: "MurmurHash2_x86_64 computes two 32-bit results in parallel and mixes them at the end, which is fast but means that collision resistance is only as good as a 32-bit hash. I suggest avoiding this variant."[1] Murmurhash3 has a 128-bit variant, which might be more along the lines of what he's looking for (the original post mentions SHA256). 1: http://code.google.com/p/smhasher/wiki/MurmurHash3 http://code.google.com/p/smhasher/wiki/MurmurHash3

martincmartin 14y ago
Computing two 32-bit results in parallel and mixing them at the end does NOT mean collision resistance is only as good as a 32-bit hash. For that, you need to compute ONE 32-bit result, then transform it into a 64-bit result.
- finnw 14y ago
  Depends whether the two 32-bit hashes are correlated with each other. If there is no correlation then a pair of 32-bit hashes is no more likely to collide than a single 64-bit hash. But this is difficult to achieve, and you should not assume (for example) running the same algorithm twice with different initial states will produce uncorrelated hashes.
  - martincmartin 14y ago
    Very true.
ecaron 14y ago
I thought Google's CityHash - http://code.google.com/p/cityhash/source/browse/trunk/README http://code.google.com/p/cityhash/source/browse/trunk/README - was their successor to the MurmurHash variants.
- spullara 14y ago
  CityHash doesn't have a 32-bit variant to participate in the benchmark. http://code.google.com/p/cityhash/issues/detail?id=2 http://code.google.com/p/cityhash/issues/detail?id=2

p4bl0 14y ago

Very interesting, thanks for sharing. "CRC32 collisions: codding collides with gnu". At first I read "coding" and I was all "haha this must be an easter egg of the implementation".

drucken 14y ago
The irony is that codding [British English] means a practical joke or trick on someone. :)

tmeasday 14y ago

Why don't I see any mentions of the latest research? There are people out there that do this for a living people!

marcusf 14y ago
I find stuff like this terribly interesting, so please elaborate. Any journal or so that is recommended for someone curious?
- tmeasday 14y ago
  I'm not active in the field right now, so I can't give specifics (the comment was more borne out of frustration with people putting in so much effort 'reinventing the wheel' in an academic sense). But if I was you, I'd start with Knuth (he, as another commenter mentioned, covers hashes in great detail), head to the references, and then use Google Scholar to find well-cited recent articles that reference the important papers mentioned there.
  - pwaring 14y ago
    Unfortunately though, a lot of the papers that turn up in Google Scholar are behind paywalls. It is very expensive to get hold of academic papers if you don't work/study somewhere with an institutional licence (anything from $10 upwards per paper).
    - tmeasday 14y ago
      Yup, that's the world of academic publishing unfortunately. A tip: often you can get a 'preprint' copy of the paper from one of the authors' websites. Probably not strictly legal, but it does happen a lot.
  - marcusf 14y ago
    Thanks very much! Might be finally time to cough up the dough for TAOCP then and take it from there.

akg 14y ago

Donald Knuth's Art of Computer Programming Volume 3 has an excellent exposition on hash functions and hash tables in general. If you can get yourself a copy I would highly recommend the read.

IgorPartola 14y ago

Honest question: why not use 2-3 different hash algorithms to minimize collisions if you are simply after uniqueness (e.g.: verifying that a downloaded file is correct)? As for hash tables, can't you guarantee uniqueness by using only reversible operations? I remember reading a lengthy post about this on HN, but can't find the link anymore.

gizzlon 14y ago
>As for hash tables, can't you guarantee uniqueness by using only reversible operations? Wouldn't that make the output almost as long as the input, defeating the purpose?
- its_so_on 14y ago
  actually, just as long. Any set of possible bits is a valid input, so the input has one bit of entropy per bit. If the hash were not "just as long" then one of the following must be true: - it collides (two possible inputs would have the same hash) - some inputs could not hash - the algorithm encodes more than 2 bits of entropy per bit. This is not possible by the pigeonhole principle. http://en.wikipedia.org/wiki/Pigeonhole_principle http://en.wikipedia.org/wiki/Pigeonhole_principle There's probably a more rigorous proof here but I'm lazy. I guess something like imagine the input is going to be n bits (like 16 bits)...make an array of length 2^n and initialize them all to -1, and then for each possible input (0..2^n-1) hash it and - since the hash is not longer than the input, the representation of the hash is there in the array if you simply interpret it as the index (subscript). Set that to the n that produced it, if it's not already set (otherwise abort with a collision). After you have reached 2^n-1, you have set 2^n indices (including whatever hash 0 produced). Is it possible for you not to have made a collision? (Yes, easily: for example anything hashes to the next integer, except binary all 1's which hash to all 0's). Could some of the indices to be empty? No. If you put 2^n values in 2^n holes distinctly, there is one value per hole. Conversely, if you had anything LESS than that many holes to put it into (for example, you're trying to hash 32 bits of input into just the lower half of the indices, by creating a hash that uniquely hashes to 16 bits of output) then by the pigeonhole prinicpal you have to put two n's into the same index. So, any hash that would be unique (that can hash anything) has to be at least exactly as long as what it's hashing. If there are any outputs that are never hashed to, it would have to be even longer. Note that this proof depends on iterating on every possible input. If some inputs aren't possible, the hash could be unique while being shorter than the input. This is how lossless compression works.

potkor 14y ago

Going by just the subject, maybe a perfect hash function generated with eg. GNU gperf?

leif 14y ago

I wish he provided the architecture he ran on. Nehalem and later cores have crc32 instructions that are quite zippy.

memset 14y ago

Question: say you use a hash which returns a 32-bit integer. If you were actually implementing a hash table, would you need to declare a structure with 2^32 elements? `int buckets[2^32]`? This seems unwieldy! Would an actual hash table only use, say, the first 10 bits or something of a hash function (int buckets[1024]) to make it less sparse (albeit increase collisions?) If you decide you want more buckets later on, would you have to re-hash everything in your array and move it to a new, bigger one?

jrmg 14y ago
Yeah, you've pretty much got it. A common alternative to masking bits off of the hash is to take hash modulo the size of the table as the index (although you have to be careful with a modulo strategy, so as not to introduce a bias towards certain table slots). There are strategies to make the resize not be so expensive. Wikipedia's page on Hash Tables covers this at http://en.wikipedia.org/wiki/Hash_table#Dynamic_resizing http://en.wikipedia.org/wiki/Hash_table#Dynamic_resizing [edit: clarity in the first paragraph]
- viggity 14y ago
  iirc, there is a major advantage to using a prime number of slots that prevents the biasing
  - hythloday 14y ago
    It's to protect against bad hashing algorithms: http://www.concentric.net/~Ttwang/tech/primehash.htm http://www.concentric.net/~Ttwang/tech/primehash.htm
- Jabbles 14y ago
  Does the modulo operation add a negligible cost to these (very cheap) hashing functions? i.e. if you're hashing a 10 character (non-unicode) word with FNV-1a you're using 10 multiplications and 10 xors. Adding a modulo (by a prime†) operation in there could feasibly double the time taken. †Not 2...

losethos 14y ago

I use this: result=0; while (ch=*src++) result=result<<1+ch; I do it an assembly language. I'm self confident enough to say, it can't be beat.

gizzlon 14y ago

Found these by coincidence, might be interesting to some of you.. (can't speak to the content) http://blog.aggregateknowledge.com/2011/12/05/choosing-a-good-hash-function-part-1/ http://blog.aggregateknowledge.com/2011/12/05/choosing-a-goo... http://blog.aggregateknowledge.com/2011/12/29/choosing-a-good-hash-function-part-2/ http://blog.aggregateknowledge.com/2011/12/29/choosing-a-goo... http://blog.aggregateknowledge.com/2012/02/02/choosing-a-good-hash-function-part-3/ http://blog.aggregateknowledge.com/2012/02/02/choosing-a-goo...

bmm6o 14y ago

If you think this is the sort of answer that Stack Overflow should strive for, note that the author edited it too many times and it fell into "Community Wiki" status. Until this was reverted in a manual process, the author didn't receive any points for his answer.

sathyabhat 14y ago
Well, not entirely. Reverting the CW restores the rep, subject to daily rep limit. The answer's been given 3 separate bounties (100, 100,50) which are not affected by CW.
- bmm6o 14y ago
  1) It still required manual intervention from a moderator. 2) I'm certainly not an expert on how SE distributes its points, but the moderator comment in the related meta post (http://meta.programmers.stackexchange.com/questions/3527/remove-cw-status-for-this-answer-hashing-algorithms-testing-by-ian-boyd http://meta.programmers.stackexchange.com/questions/3527/rem...) states "I don't think there is a way to refund the reputation the answer gained while it was CW [...]"
dclowd9901 14y ago
Community Wiki is immortality.

pbreit 14y ago

How do folks generally take an autoincrementing database ID and generate a hash to be used "in public" when trying to avoid revealing obviously serial numbers? I don't think I need something airtight, in fact in one system we just multiplied/divided by a 4 digit prime number. While this worked fine, it seemed a little loose.

eli 14y ago
HASH(<id> + "static string pad") is how I imagine most people do it. Depends how much you care about a dedicated attacker figuring out that ID. If this is a thing you're going to use a lot, I'd probably just add a database column and give each record a random unique "public ID" -- then there is literally no connection between the public ID and the private one..
buddydvd 14y ago
Look into format-preserving encryption. I wrote something that allows you to generate permutations for an arbitrary sized range. With it, there are no collisions.

jorangreef 14y ago

If you're doing 32-bit hashes in Javascript and are willing to trade a bit, then a 31-bit hash may be at least an order of magnitude faster due to VM implementation: https://groups.google.com/d/msg/v8-users/zGCS_wEMawU/6mConTiBUyMJ https://groups.google.com/d/msg/v8-users/zGCS_wEMawU/6mConTi...

kolo32 14y ago

More tests: http://www.strchr.com/hash_functions http://www.strchr.com/hash_functions