Which hashing algorithm is best for uniqueness and speed?

http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed/145633#145633

by suprgeek • 14 years ago

336 101 14 years ago

programmers.stackexchange.com

esbwhat• 14 years ago

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

yread• 14 years ago

The person specifically requested an algorithm for a hash table. Nobody is going to attempt to crack that

throwaway64• 14 years ago

nobody? This exact problem was a massive issue within the year.

https://www.securityweek.com/hash-table-collision-attacks-co...

rmc• 14 years ago

There are times you want something that won't be a cracking attack. E.g. to randomly (but consistantly) partition data (i.e. a hash table).

MichaelGG2• 14 years ago

Not if you're not looking for it to be hard to crack. Suppose you're generating quick checksums, using a hashtable, indexing non-malicious data, etc. In those cases you want a very fast hash function, and you're not worried about folks being able to find collisions for existing hashes, or create multiple values with the same hash.

bmj12• 14 years 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-charac...

masklinn5• 14 years 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.

masklinn5• 14 years ago

> isn't slow better in this case?

No, guy's looking for a hash table hash, not a cryptographic one. For a hash table you're looking for low collisions and high throughput (so your hash table is fast) first and foremost.

pjscott3• 14 years ago

Even for cryptographic hashes, fast is what you want most of the time. Look at it this way: when you connect to a web site via SSL, all the data you send will be hashed for authentication. Do you really want this to be slow?

MichaelGG2• 14 years 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

martincmartin3• 14 years 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• 14 years 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.

ecaron• 14 years ago

I thought Google's CityHash - http://code.google.com/p/cityhash/source/browse/trunk/README - was their successor to the MurmurHash variants.

spullara• 14 years ago

CityHash doesn't have a 32-bit variant to participate in the benchmark.

http://code.google.com/p/cityhash/issues/detail?id=2

moe2• 14 years ago

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

afsina• 14 years 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• 14 years 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.

moe2• 14 years 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.

arethuza• 14 years ago

I thought MD5 and SHA-1 were both designed as cryptographic hashes but now deprecated for this purpose - although SHA-1 is still used in applications such as git as a general purpose hash function.

acdha• 14 years ago

It'd still be interesting, particularly in a world where hardware is picking up the load for things which SSL uses. I'd expect the answer to be something along the lines of “more competitive as the data size increases” but it'd be interesting to know how great the margin is and whether the answer shifts significantly when comparing, say, a conventional hash to a cryptographic one on an embedded chip.

mistercow3• 14 years ago

There are, however, applications with both hash tables and bloom filters where some cryptographic properties are still useful/necessary, or where low-collision hashes are particularly important.

mlok• 14 years ago

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

_urga2• 14 years 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-...) which is simpler than Murmur3 and displays much better avalanche characteristics than the other hashes.

dkersten• 14 years ago

According to this site[1], CrapWow seems to be the best in raw performance: 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

[1] http://www.team5150.com/~andrew/noncryptohashzoo/

trebor• 14 years ago

What about its randomness compared to Murmur2/3?

p4bl0• 14 years 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• 14 years ago

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

tmeasday4• 14 years ago

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

marcusf2• 14 years ago

I find stuff like this terribly interesting, so please elaborate. Any journal or so that is recommended for someone curious?

tmeasday4• 14 years 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.

gwern• 14 years ago

I get the impression this is meant for more practical drop-in use for your hashtables - in which case the latest research is doubly unacceptable as it's still new and unreviewed, and there may be no suitable implementation (eg. a C binding in your distro's stable release).

akg• 14 years 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• 14 years 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.

gizzlon4• 14 years 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_on3• 14 years 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

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.

mseebach6• 14 years ago

> As for hash tables, can't you guarantee uniqueness by using only reversible operations?

This is called a perfect hash and its appropriateness depends on the input data.

The problem is that the problem domains where hashes are practical are where a very large space of inputs needs to fit into a finite number of buckets such that lookups are fast.

For that to work with a perfect hash, you need an infinite number of buckets which needs infinite space.

andreasvc2• 14 years ago

A perfect hash is able to avoid collisions when given the set of all possible keys in advance; it is not related to reversibility. The latter contradicts the very idea of a hash function, and would conceptually be a lossless compression technique.

martincmartin3• 14 years ago

Computing two 32-bit hashes is the same as computing 1 64-bit hash. In general, computing n m-bit hashes is the same as computing 1 n*m-bit hash.

delinka• 14 years ago

Any digest algorithm that takes variable-sized data as input and produces fixed-sized output will necessarily produce collisions for some inputs that are larger than the output.

potkor• 14 years ago

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

leif• 14 years ago

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

memset• 14 years 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• 14 years 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

[edit: clarity in the first paragraph]

viggity2• 14 years ago

iirc, there is a major advantage to using a prime number of slots that prevents the biasing

Jabbles2• 14 years 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...

yason• 14 years ago

If the hash function is any good, simply bitwise-and enough bits from the hash and use that as the index. (It's a modulo too, but simply modulo(2^x).)

Using 2's powers generally fits nicely with programming on binary computers. It also has the nice quality of producing number of slots that are always 2's powers and you can shove those naturally for example into a single memory page.

joeblau2• 14 years ago

It depends on your performance use case. 2^32 is only about 540MB of RAM so you can allocate that all at once and then all subsequent actions are read/writes.

mseebach6• 14 years ago

> 2^32 is only about 540MB of RAM

Yes, if you're only storing a single bit for each. Usually, you'll want to store a pointer to the head of a linked list. At 64 bits per pointer, you'll need to allocate 32 gigs of RAM - slightly less feasible.

drostie• 14 years ago

(1) The trick for resizing is, we only rehash all k elements to recalculate buckets every k inserts or so, and we double the hash table size. So, if you imagine that you just came from a resize, you had k elements and had performed N(k) hashes, then when you hit 2k elements you will have to resize again, and you will perform N(2k) = N(k) + k + 2k total hashes. This recurrence is solved by N(k) = 3k + C for an arbitrary constant C. Averaged over the elements you have inserted k, it's easy to see that for very large dictionaries, you only hash each element on average 2-3 times -- three times if you trigger a resize with k, 2 times if you come in just before triggering the resize.

(2) Strictly speaking you don't need this overhead and you can use trees to keep it sparse as well, although as far as I know the low-n overhead slows it down too much in practice when compared to the high-n space efficiency. That is, you could declare a binary tree structure with only those buckets and pathways of the 2^32 which you need, but to find something within the structure requires checking and following ~32 pointers and storing something requires creating ~32 nodes.

gizzlon4• 14 years 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-goo... http://blog.aggregateknowledge.com/2011/12/29/choosing-a-goo... http://blog.aggregateknowledge.com/2012/02/02/choosing-a-goo...

bmm6o2• 14 years 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• 14 years 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.

bmm6o2• 14 years 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/rem...) states "I don't think there is a way to refund the reputation the answer gained while it was CW [...]"

dclowd9901• 14 years ago

Community Wiki is immortality.

pbreit• 14 years 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• 14 years 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• 14 years 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.

_urga2• 14 years 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/6mConTi...

kolo32• 14 years ago

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

Which hashing algorithm is best for uniqueness and speed?

Related Stories