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.
Which hashing algorithm is best for uniqueness and speed?
61–70 of 110 posts
Re: Which hashing algorithm is best for uniqueness and speed?
#62Why don't I see any mentions of the latest research? There are people out there that do this for a living people!
Re: Which hashing algorithm is best for uniqueness and speed?
#63Earlier quoted context omitted.
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.
> 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.
Look up an algorithm called a Bloom Filter.
Re: Which hashing algorithm is best for uniqueness and speed?
#64Earlier quoted context omitted.
> 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.
Yeah sure you could waste all the space you want why in the world would you do that? Using a linked list is slow and inefficient with memory usage especially when you can do the same thing with a byte array. Look up an algorithm called a Bloom Filter.
Bloom filters are only useful (in this context) to augment a proper Set implementation, in which case they increase the memory cost, in exchange for decreasing (on average) the I/O cost.
Re: Which hashing algorithm is best for uniqueness and speed?
#65Earlier quoted context omitted.
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.
Doing constant modulo on an integer is very fast - we're talking a few CPU operations.
Re: Which hashing algorithm is best for uniqueness and speed?
#66Re: Which hashing algorithm is best for uniqueness and speed?
#67Earlier 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.
>@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.
Re: Which hashing algorithm is best for uniqueness and speed?
#68If 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.
Re: Which hashing algorithm is best for uniqueness and speed?
#69Re: Which hashing algorithm is best for uniqueness and speed?
#70Earlier quoted context omitted.
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.
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-fun... and: http://stackoverflow.com/questions/1191112/password-hashing-... to learn more about preventing brute-force attacks
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.