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

41–50 of 110 posts

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

#41

Post by viggity »

jrmg wrote: post #39
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_res…

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

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

#42

Post by gizzlon »

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…

I was indeed thinking of lossless compression: In practice it compresses almost all its input. If the the output length does not have to be constant, it's fine that some input actually gets inflated. As long as it compresses the average input.

But in this case the output length might have to be constant? If that's the case, you are of course correct.

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

#43

Post by Jabbles »

jrmg wrote: post #39
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_res…

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

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

#44

Post by ecaron »

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

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

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

#45

Post by viggity »

Jabbles wrote: post #43
jrmg wrote: post #39

Earlier quoted context omitted.

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

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

The modolo function is pretty much required unless you have 2^32 bytes of RAM available for each hashtable. Modolo is also ridiculously cheap, especially compared to the hashing function.

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

#46

Post by its_so_on »

mistercow wrote: post #40
its_so_on wrote: post #33

Earlier quoted context omitted.

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

Fair enough. The proof is that you can't shave even a single bit off of every output, so that given any file that's 1024 bytes, you can hash it to 1023 bytes. Not possible unless you're hiding that entropy somewhere (filename etc).

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

#47

Post by hythloday »

viggity wrote: post #41
jrmg wrote: post #39

Earlier quoted context omitted.

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

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

It's to protect against bad hashing algorithms:

http://www.concentric.net/~Ttwang/tech/primehash.htm

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

#48

Post by Jabbles »

viggity wrote: post #45
Jabbles wrote: post #43

Earlier quoted context omitted.

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

The modolo function is pretty much required unless you have 2^32 bytes of RAM available for each hashtable. Modolo is also ridiculously cheap, especially compared to the hashing function.

Certainly, if you are hashing a large amount of data then a single modulo operation isn't going to cost a lot. But if you're just hashing an English word, possibly even a URL, I'm not so sure.

You could shift or mask the result (as described above) to use a table size of any power of 2 to avoid the modulo.

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

#50

Post by finnw »

martincmartin wrote: post #36
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.

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.
Post reply on HN