Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Which hashing algorithm is best for uniqueness and speed?

programmers.stackexchange.com

Post reply on HN
Print view View original

31–40 of 110 posts

Re: Which hashing algorithm is best for uniqueness and speed?

#31

Post by arethuza »

afsina wrote: post #17
moe wrote: post #11

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

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.

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.

Re: Which hashing algorithm is best for uniqueness and speed?

#32

Post by acdha »

afsina wrote: post #17
moe wrote: post #11

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

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.

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.

Re: Which hashing algorithm is best for uniqueness and speed?

#33

Post by its_so_on »

gizzlon wrote: post #27
IgorPartola wrote: post #26

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.

>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?

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.

Re: Which hashing algorithm is best for uniqueness and speed?

#34

Post by mistercow »

afsina wrote: post #17
moe wrote: post #11

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

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.

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.

Re: Which hashing algorithm is best for uniqueness and speed?

#35

Post by swordswinger12 »

arethuza wrote: post #31
afsina wrote: post #17

Earlier quoted context omitted.

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.

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.

Neither are recommended for modern security needs, but MD5 is way, way more broken than SHA1. As far as I know, no SHA1 collision has ever been found, whereas any cs undergrad could implement arbitrary MD5 collisions using some work done by a Chinese team a few years back. SHA1 is deprecated because of some theoretical attacks which lower the complexity of finding a collision without really making it a tractable problem.

Re: Which hashing algorithm is best for uniqueness and speed?

#36

Post by martincmartin »

MichaelGG wrote: post #3

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/…

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.

Re: Which hashing algorithm is best for uniqueness and speed?

#37

Post by memset »

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?

Re: Which hashing algorithm is best for uniqueness and speed?

#38

Post by martincmartin »

IgorPartola wrote: post #26

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.

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.

Re: Which hashing algorithm is best for uniqueness and speed?

#39

Post by jrmg »

memset wrote: post #37

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,…

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]

Re: Which hashing algorithm is best for uniqueness and speed?

#40

Post by mistercow »

its_so_on wrote: post #33
gizzlon wrote: post #27

Earlier quoted context omitted.

>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?

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/Pi…

>actually, just as long

Well, more accurately, at least as long, on average.

It would be possible, though, to have a guaranteed unique string which is usually shorter than the input for real world data, which is called lossless compression. Obviously, it is not possible to provide a fixed digest length though, which makes it useless for many hash function applications, like bloom filters. And, of course, a hash table implementation based on DEFLATE would be hilariously inefficient.

Post reply on HN