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

81–90 of 110 posts

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

#81

Post by pjscott »

masklinn wrote: post #12
bmj1 wrote: post #7

Earlier quoted context omitted.

Given Moore's law and the prevalence of botnets and cloud computing - hash speed really isn't a very strong means of defence against cracking... Also see: http://cyberarms.wordpress.com/2010/10/21/cracking-14-charac...

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.

Can we stop calling them hashes? They're key derivation functions. I know it's a long, awkward term, but a lot of people in this thread are confusing the technical requirements for cryptographic hashes and KDFs, so I think that being precise about this is warranted.

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

#82

Post by trebor »

dkersten wrote: post #53
_urga wrote: post #14

FNV despite much popularity is a relatively poor quality hash. Murmur2 has a major flaw, hence Murmur3. CRC32 is slow. Not mentioned in the post, but if you're thinking Fletcher or Adler, they have terrible distribution. For a fast 32-bit hash, much better to go with Bob Jenkin's one-at-a-time hash ( http://en.wikipedia.org/wiki/Jenkins_hash_function#one-at-a-... ) which is simpler than Murmur3 and displays much bett…

According to this site[1], CrapWow seems to be the best in raw performance: http://www.team5150.com/~andrew/noncryptohashzoo/CrapWow.htm... (Crap8 in second place and Murmur3 in third place - one at a time performs quite badly in this guys benchmarks) Performance graphs: http://www.team5150.com/~andrew/noncryptohashzoo/speed.html [1] http://www.team5150.com/~andrew/noncryptohashzoo/

What about its randomness compared to Murmur2/3?

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

#83

Post by dllthomas »

its_so_on wrote: post #46
mistercow wrote: post #40

Earlier quoted context omitted.

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

The proof is straightforward application of the pigeonhole principle. Input strings are your pigeons, hashes are your holes.

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

#84

Post by dllthomas »

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

Can we stop calling them hashes? They're key derivation functions. I know it's a long, awkward term, but a lot of people in this thread are confusing the technical requirements for cryptographic hashes and KDFs, so I think that being precise about this is warranted.

But talking about salt in our hash sounds delicious.

Talking about stretching our hash, though, sounds like some strange tasting taffy...

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

#85

Post by [deleted] »

yason wrote: post #77
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…

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.

[deleted]

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

#86

Post by haberman »

mseebach wrote: post #55
Jabbles wrote: 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.

It won't be a compile-time constant unless your hash table is incapable of resizing. And modulo arithmetic on arbitrary values is slow (20-94 cycles of latency on Sandy Bridge).

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

#87

Post by dclowd9901 »

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.

Community Wiki is immortality.

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

#88

Post by tmeasday »

marcusf wrote: post #21
tmeasday wrote: post #18

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?

I'm not active in the field right now, so I can't give specifics (the comment was more borne out of frustration with people putting in so much effort 'reinventing the wheel' in an academic sense).

But if I was you, I'd start with Knuth (he, as another commenter mentioned, covers hashes in great detail), head to the references, and then use Google Scholar to find well-cited recent articles that reference the important papers mentioned there.

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

#89

Post by [deleted] »

pjscott wrote: post #80
masklinn wrote: post #9

Earlier quoted context omitted.

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

[deleted]

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

#90

Post by Locke1689 »

pjscott wrote: post #80
masklinn wrote: post #9

Earlier quoted context omitted.

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

For cryptographic purposes you usually want fast digests and slow key derivation functions.
Post reply on HN