Live data from Hacker News

Which hashing algorithm is best for uniqueness and speed?

programmers.stackexchange.com

61–70 of 110 posts

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

#61
post #44

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.

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

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

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

#62

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

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

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

#63
post #52

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

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.

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

#64
post #63

Earlier 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 not suitable as stand-in replacements for hash tables when you are representing the Set abstract data type. They are not deterministic, they treat objects with the same hash as identical, and they do not actually store values.

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?

#65
post #48

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

Yes, but bitwise AND is faster.

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

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

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

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

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

SHA-1 was designed as a cryptographic hash functions, they are puprposely slow. No, SHA-1 is not as fast as functions from the article.

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

#68
post #66

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.

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.

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

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

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

#70
post #59

Earlier 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

> You'll find that adding a long salt, unique to each password, is a far more effective protector against brute force than "hash speed".

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.

Post reply on HN