views:

223

answers:

4

Hello,

I'm looking for a special hash-function. Let's say I have a large list of strings, if I order them by their hash-values they should be ordered quasi randomly.

The most important point is: it must be super fast. I've tried md5 and sha1 and they're using to much cpu power.

Clashes are not a problem.

I'm using javascript, so it shouldn't be too complicated to implement.

+2  A: 

It looks as if you want the sort of hash function used in a hash table, not the sort used to detect duplicates or tampering.

Googling will yield you a wealth of information on alternative hash functions. To start with, stay away from cryptographic signature hashes (like MD-5 or SHA-1), they solve another problem.

You can read this, or this, or this, to start with.

bmargulies
+3  A: 

Take a look at Murmur hash. It has a nice space/collision trade-off:

http://sites.google.com/site/murmurhash/

Nils Pipenbrinck
I forgot that one.
bmargulies
+2  A: 

If speed is paramount, you can implement a simple ad-hoc hash, e.g. take the first and last letter and order your string by the last and then first letter. The result would look, as you say, "quasi random" and it would be fast. For instance, part of my answer sorted that way would look like this:

ca ad-hoc
el like
es simple
gt taking
hh hash
nc can
ti implement
uy you
Tomislav Nakic-Alfirevic
+1  A: 

Hsieh, Murmur, Bob Jenkin's comes to my mind.
A nice page about hash functions that has some tests for quality and a simple S-box hash as well.

andras