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

71–80 of 110 posts

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

#71

Post by bmm6o »

sathyabhat wrote: post #68
bmm6o wrote: 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.

1) It still required manual intervention from a moderator.

2) I'm certainly not an expert on how SE distributes its points, but the moderator comment in the related meta post (http://meta.programmers.stackexchange.com/questions/3527/rem...) states "I don't think there is a way to refund the reputation the answer gained while it was CW [...]"

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

#72

Post by sukuriant »

dchest wrote: post #65
mseebach wrote: post #55

Earlier quoted context omitted.

Doing constant modulo on an integer is very fast - we're talking a few CPU operations.

Yes, but bitwise AND is faster.

Cross that bridge when you get there. If you're really finding that your hash function is the slowest piece of code in a tightly bound for-loop, and it's not all the collisions you're having (from having a bad hashing function), then look into alternatives. Before that, you're doing premature optimization.

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

#73

Post by eli »

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

HASH( + "static string pad") is how I imagine most people do it. Depends how much you care about a dedicated attacker figuring out that ID.

If this is a thing you're going to use a lot, I'd probably just add a database column and give each record a random unique "public ID" -- then there is literally no connection between the public ID and the private one..

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

#74

Post by btilly »

bmj1 wrote: post #59
masklinn wrote: post #12

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

If you did your research, you'd know that salts are insufficient protection. Heck, read your own link, the first link has as #7 that you need to use a slow hash function. Or you can just read http://codahale.com/how-to-safely-store-a-password/ which lays it out in black and white.

You should be glad. You learned something important today.

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

#75

Post by masklinn »

bennysaurus wrote: post #19
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.

>@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 is very fast though

SHA-1 is fast for a cryptographic hash function, but it's orders of magnitude slower than "hashmap" hashes. crc32 is more than an order of magnitude faster, and as you can see in TFA's table it's ~half the speed of the best non-crypto hashes.

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

#76

Post by dchest »

sukuriant wrote: post #72
dchest wrote: post #65

Earlier quoted context omitted.

Yes, but bitwise AND is faster.

Cross that bridge when you get there. If you're really finding that your hash function is the slowest piece of code in a tightly bound for-loop, and it's not all the collisions you're having (from having a bad hashing function), then look into alternatives. Before that, you're doing premature optimization.

Please read the whole thread before replying with the "premature optimization" thing. We are talking about hash table optimizations; this commenter -- http://news.ycombinator.com/item?id=4037320 -- is asking about the cost of modulo operation.

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

#77

Post by yason »

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…

If the hash function is any good, simply bitwise-and enough bits from the hash and use that as the index. (It's a modulo too, but simply modulo(2^x).)

Using 2's powers generally fits nicely with programming on binary computers. It also has the nice quality of producing number of slots that are always 2's powers and you can shove those naturally for example into a single memory page.

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

#78

Post by buddydvd »

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

Look into format-preserving encryption. I wrote something that allows you to generate permutations for an arbitrary sized range. With it, there are no collisions.

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

#79

Post by pjscott »

IsTom wrote: post #67
bennysaurus wrote: post #19

Earlier quoted context omitted.

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

You've got it backwards; cryptographic hash functions are designed to be as fast as possible without giving up their cryptographic properties. If you need a slow hash (e.g. for password storage), you use something like bcrypt that's designed to be slow.

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

#80

Post by pjscott »

masklinn wrote: post #9
esbwhat wrote: post #2

isn't slow better in this case? I mean if it's fast to generate, it's fast to crack, right?

> isn't slow better in this case? No, guy's looking for a hash table hash, not a cryptographic one. For a hash table you're looking for low collisions and high throughput (so your hash table is fast) first and foremost.

Even for cryptographic hashes, fast is what you want most of the time. Look at it this way: when you connect to a web site via SSL, all the data you send will be hashed for authentication. Do you really want this to be slow?
Post reply on HN