Why don't I see any mentions of the latest research? There are people out there that do this for a living people!
I find stuff like this terribly interesting, so please elaborate. Any journal or so that is recommended for someone curious?
Which hashing algorithm is best for uniqueness and speed?
21–30 of 110 posts
Re: Which hashing algorithm is best for uniqueness and speed?
#22Why 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.
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.
Re: Which hashing algorithm is best for uniqueness and speed?
#23Earlier quoted context omitted.
Using a slower hash would make the issue worse (linearly): the collisions would still be there, but now each insertion would take even more time due to the extra computational cost of the hash.
[deleted]
> No, using a slower cryptographic hash would produce better distribution
That absolutely isn't an intrinsic property of cryptographic hashes.
Re: Which hashing algorithm is best for uniqueness and speed?
#24Earlier quoted context omitted.
Using a slower hash would make the issue worse (linearly): the collisions would still be there, but now each insertion would take even more time due to the extra computational cost of the hash.
[deleted]
EDIT: parent basically said "use a cryptographic hash".
You need some kind of random salt, too - it's not that hard to find a decent number of near-collisions even in cryptographic hashes. (E.g. if your hash table doubles in size whenever two keys end up in the same bucket, an attacker needs to spend O(2^n) operations to find two keys that agree in the first n bits, which will make you do O(2^n) operations and use O(2^n) memory.)
Re: Which hashing algorithm is best for uniqueness and speed?
#25Earlier quoted context omitted.
Using a slower hash would make the issue worse (linearly): the collisions would still be there, but now each insertion would take even more time due to the extra computational cost of the hash.
[deleted]
Using a faster cryptographic hash would be better.
Re: Which hashing algorithm is best for uniqueness and speed?
#26Honest 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.
Re: Which hashing algorithm is best for uniqueness and speed?
#27Honest 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?
Re: Which hashing algorithm is best for uniqueness and speed?
#28Going by just the subject, maybe a perfect hash function
generated with eg. GNU gperf?
Re: Which hashing algorithm is best for uniqueness and speed?
#29I wish he provided the architecture he ran on. Nehalem and later cores have crc32 instructions that are quite zippy.
Re: Which hashing algorithm is best for uniqueness and speed?
#30Honest 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?
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.