Here's results from me, P4, compiled with -march=pentium4 -O3 with gcc 4.0, and with the key length changed from 6 to 32:

superfast now outperforms rand2. As we talked on IRC, there may be a way to get around the byte by byte adding with rand2 though, which likely is where superfast gets an advantage with the 16bit at once adding.

As you know, Elias, (since we collaborated on the function ) we now have hash_rand5() which apparently blows all other competition out of the water. I'd like to see what the gotcha is, surely there must be something.

Here's the function:

And here are my results for a random lowercase alphabetic key of 63 characters:

Those are not good hash functions.

hash_rand collides for strings like this pair:
"my really long test string is super great"
"his really long test string is super great"
The flaw exploited here is that it ignores early letters in long strings. It also has other flaws, like this:
"az"
"bv"
(consecutive letters can cancel each other out easily)

hash_rand2 and hash_rand3 collide on exactly the same things as hash_rand.

hash_rand4 is worse than the previous ones. any reordering of letters results in the same hash.
"ab"
"ba"

hash_rand5 has the same flaws as hash_rand 1-3, but it requires slightly longer strings:
"his really really really REALLY long test string is super super SUPER DUPER great (yes it really is)"
"her really really really REALLY long test string is super super SUPER DUPER great (yes it really is)"

or, here's an example using the other flaw mentioned for hash_rand 1-3: "a???z???"
"b???v???"

Also, for short strings, the latter bytes do not effect the lower bits of the results well. For instance, the difference between "abc " and "abc0" is only in the uppermost 4 bits of the hash.

I recommend you start by reading some on the subject...
Bob Jenkins has some okay stuff written on the subject: http://burtleburtle.net/bob/hash/index.html
Knuth also wrote some on the subject, in The Art of Computer Programming, volume 3 "Sorting and Searching", chapter 6.4.
There's probably lots more resources on the web.

Once you get your string hash function going, you may want to modify my hash code to manage hash sets.

Link

Hey, thanks for bursting my bubble!

Heh, no really, that's exactly why I posted this. Orz, your analysis is quite helpful. I have seen Bob Jenkin's page, and in fact many of the hash functions I've tested alongside my rand* family came from there.

I figured there were some gotchas with my functions (other than the obvious ones that my testing revealed for rand4(), which was a test case in badness), especially since they seem to perform so well for the type of cases I'll use them for (and for which the tests are a little biased).

rand5() is definitely the best up to this point, and with a bit of tweaking I'm sure the early characters influence will persist. Even as it stands, I'm pretty happy with the results. Nevertheless, it looks like I'm starting on rand6() now...

Bob, thanks for posting your hash map code! It looks pretty interesting, and I'll definitely give some serious perusal and tweaking (here I was about to write a chained hash table ) once I get my function sorted out.

EDIT:

orz, I've confirmed the first two flaws stated for rand1-3 (early letters, cancelling), and the 2nd flaw mentioned for rand5 (a???z???) but have been unable to confirm the early letters flaw in rand5 using a longer string. I've tried up to a 200 character string with only the first letter different, and I'm still getting unique hashes. Can you give me a working example of this flaw?

stupid smileys make it difficult to read the second example for hash_rand5...

Hm... strange. The two samples (100 characters long) I posted for the early-letters flaw in rand5 both produce a hash of 1675257485 in my test. I'm using exactly the code posted in your earlier post for hash_rand5, except I added a "const" keyword to prevent it from objecting to taking a literal string in C++ (I pasted the code into one of my C++ projects). This is my test code:

  const char *str1 = "his really really really REALLY long test string is super super SUPER DUPER great (yes it really is)";
  const char *str2 = "her really really really REALLY long test string is super super SUPER DUPER great (yes it really is)";
  int len1 = strlen(str1);
  int len2 = strlen(str2);
  int h1 = hash_rand5(str1, len1);
  int h2 = hash_rand5(str2, len2);
  printf("%11d len=%2d str=\"%s\"\n", h1, len1, str1);
  printf("%11d len=%2d str=\"%s\"\n", h2, len2, str2);

Looking at the code for hash_rand5, this should work for any two strings that have the same last 64 characters and the same (length % 4).

Here's a suggestion for testing:
Generate a random string of some length. Treat the string as a long binary number. Loop, adding 1 to the string each time. Hash it, use the low 16 bits of the hash as an index into one table, see if the table is lopsided after a few million calls. Repeat, but interpret the string as a backward number, adding 1 to the last character, and carrying to the second-to-last character.

Bob Jenkins covered most of this somewhere in his stuff, but you've already read some of his stuff and I've already linked him, so I'll try covering it myself:
In order to remove early-characters-losing-relevance, you must not progressively lose information. In your code, you have each iteration of the loop do a "seed=seed<<2;". This means that the highest 2 bits of seed are lost. Nothing uses them. Thus, nothing more than 16 loops ago (32 bit integers, divided by 2 bits per loop) can have any effect upon the value of seed. Here's a few alternatives:
1. "seed = seed ^ (seed << 2);"
This fixes the early-characters problem, but it does not cause any higher bits to effect lower bits. The addition that mixes input in also does not permit higher bits to effect lower bits. Thus, the lower bits of seed will end up sucking. In particular, the lowest bit will be simply the XOR of all input words lowest bits.

2. "seed = seed ^ (seed >> 2);"
This fixes the early-characters problem, and the low-bits problem, but it has serious issues if the input is mixed in with simmple addition. It means that the low bits will not spread out except through the addition, which is a very poor way to spread the influence of a bit. It's very easy for consecutive characters to cancel each other.

3. "seed = (seed << 1) ^ (seed >> 2);"
This fixes the early-characters problem, and the low-bit problem, and improves the bit-spreading issues. It's better than all of the previous examples, and while it still suffers from many problems, it probably does okay for many real world cases. Nearby letters can cancel each other, but it often takes relatively complex relationships to cancel. Far apart letters can cancel, but it usually takes complex relationships between such letters to cancel. Choosing the shift lengths is a bit of a balance. Large shift values mean that many bits in a single iteration are dependant upon only 1 bit in the previous iteration (poor spreading), but small shifts mean that spreading doesn't add up as well across multiple iterations. I believe that the best values pairs tend to involve a right-shift slightly larger than the left-shift if addition is used to mix in input. I know I made some unsupported statements in there, but it's to figure out how to talk about things... I don't know words to explain some of this very well or at all, and I'm not sure that such words even exist, and to do a decent job I'd probably need lots of diagrams...

4. "seed = (seed << 7) | (seed >> 25);"
A circular shift (the shifts add up to the word size). Faster on some hardware than the above examples. Each bit in the output depends upon only one bit in the input, so this isn't great. In particular, inserting 32 consecutive 0s in the input will not change the output, no matter where they're inserted. Still, this does okay for some real-world things. I think Knuth recommended something like this somewhere. It's imporant that the shifts be odd, not even.

5. "seed = seed * 1103515245;"
Mixes decently, except that the high bits of the input don't get spread out, the low bits of the output suck. Could work well with a little extra tweaking. Fast on modern desktops, but slow on some architectures.

Guidelines:
A. (very important guideline)
Don't lose information. Every bit in an intermediate state must have some effect on the next intermediate state, or you will have early-characters problems.

B. (important guideline)
Every input bit should be capable of effecting any bit in the final output, depending upon context (context = other input). In any particular context, swapping a single bit should change roughly half the output bits.

C. (important guideline)
Each intermediate state bit should effect multiple bits in the next intermediate state bit, or you run the chance of things canceling out.

D. (guideline)
If the state size is larger than the input chunk size, then consecutive input chunks will not be able to cancel each other (unles you screw up somehow...). This also may make it harder for even far apart chunks to cancel each other.

E. (my own observation/intuition/recommendation/whatever)
The previous two guidelines (C & D) are very important if the state is small, but not so important if the state is large.

F. (guideline)
Many algorithms are not effected by leading 0s at the begining of a string. That can be handled by using the length of the string as an input in the hash.

F. (my own observation/intuition/recommendation/whatever)
In general, a larger state is capable of doing a better job than a smaller state of comparable complexity. However, very large states may have speed problems, particularly when hashing short strings.

G. (my own observation/intuition/recommendation/whatever)
Multiplication is great on modern desktops & servers, but very slow in embedded contexts. Despite the nice job it does mixing bits, it still has some problems: the high bits of the result are good, but the low bits of the result aren't so good, because they are not effected by the high bits of the input. If multiplication is used as a major factor in the algorithm, you need something else to stir around the upper bits of the input, or they will suffer compared to the lower bits.
Addition mixes bits much slower (particularly if nothing else is stirring them up), but does mix them. It has the same issues as multiplication in that the low bits of the output are uneffected by the high bits of the input.

Wait, you're saying that multiplcation is faster time-wise than addition? Or did you mean addition isn't as effective as multiplication?

Um, what I was trying to say is that, with multiplication, bits spread to the left very quickly on a per-multiply basis, whereas with addition, they spread to the left by maybe one bit per addition.
On a per operation basis, multiply is much more effective than addition.
On a per-time basis, multiply usually beats addition by a little bit on modern desktop CPUs, but is beaten by addition (by a larger margin) in some embedded contexts. Both operations must be mixed with other operations because they only spread bits leftwards, so the rightmost bits of output and the leftmost bits of input get negleected even if there's no rightshift or other operation that moves or spreads bits rightward.

To illustrate, here's a loop that is bad because of that:

for (int i = 0; i < length; i++) {
  seed += key<i>;
  //bad! both addition and multiplication only spread bits leftwards!
  seed = seed * 1103515245 + 12345;
}

compared to a good loop, or at least, a loop that doesn't have that flaw:

for (int i = 0; i < length; i++) {
  seed += key<i>;
  //okay: the multiply spreads bits leftwards and
  //  the circular shift moves the bits around
  seed = seed * 1103515245;
  seed = (seed >> 17) | (seed << 15);
}

For the bad loop, the low bit of the final output is dependant ONLY upon the low bits of the input. For the good loop, the low bit of the output can be effected by any bit of the input, though a few bits in key[length-1] may have only a minimal effect on it.

So how effective would something like this be?
seed = seed * input - (input << 1)

Well, here's the latest incarnation, and I think I'm pretty happy with this. I haven't been able to break the distribution using any orz-like tricks, and it's still a touch faster than SuperFastHash. PLUS, it still uses the rand() functionality to avalanche at the end, thus keeping its classic rand appeal.

Paul Pridham:
The only issues that I see are in the "case 3:" code path, where you add input chunks without doing anything else to them, which would make these strings equivalent: "a b", "b a", except for the other issue: you omit parenthesis on the "i << 2 + 2", which is a no-no, because bitwise operators have counter-intuitive precedence in C, and that ends up meaning "i << 4".
Asside from that it looks like it ought to be a nice hash function for use in a project, but widespread deployment would be hampered by its lack of portability. The portability issues are endianness and alignment. Both could be solved by reading 1 character at a time, though that hurts performance. Notice how Bob Jenkins did it in his hash function, where he reads 1 character at a time, but combines them before hashing so that he can still hash them 32 bits at a time. Specifically, the endianness issue is that the result of casting an array of chars to an array of shorts or ints is dependant upon platform byte order (x86, ARM, and ALPHA will get one result, MIPS, Sparc, and 68k will get a different result, PPC will usually give the MIPS/Sparc/68k result but doesn't always do so), where on x86 (*(const short*)"ab") is ('a' + 256 * 'b'), and on MIPS it's ('a' * 256 + 'b'). The alignment issue is that on x86, if the key pointer value is not a multiple of sizeof(int) (or whatever the pointer is cast to), then there will be a moderate performance hit, on other platforms except ARM there will be a large performance hit, and on ARM it will run faster than x86 but produce bizarre incorrect values . Alignment issues are avoid by reading data as chars, or by using #ifdefs to detect the platform at compile time and handle it appropriately.
You might consider finding or creating some better tests for hash functions, so that you can make an informed comparison to other high-speed hash functions. I can probably come up with a few tests by adapting some of my random number generation tests... I don't know if there's any kind of standard tests for hash functions though.

CGamesPlay:
That has problems. It has the leftward-only issue (high bits of seed don't spread out), and it adds loss-of-state issues when input is not an odd number.

Subtraction does not fix the leftward-only issue - it is basically the same as addition, a leftwards only operation, and it mixes at the same rate. ("a -= b;" is generally equivalent to "a += 1 + ~b;", and ~ neither moves nor mixes bits)

Really, the only operations I can think of that you can get rightward movement or mixing out of are right-shift, circular shift (implemented with right-shift in C some many assembly languages), carry-based-things (in C often implemented with rightshift, though in assembly often dedicated opcodes are used, like ADC (add-with-carry)), indirection / table lookups (if the word size is large or the array size is small this may need to get combined with a right-shift to get the high bits of the input to be mixed in), modulo (which is too slow, and should generally not be used with an even modulus), modulo-based things (which range from too slow to way way way too slow), high-word-of-multiplication (which, in C, is generally implemented with floating point values or with right-shifts).
In sum, if it doesn't have a right-shift in it, it has to do something weird to compensate, or else it suffers from leftwards-only bit mixing. Many random number generators, including the libc one and the one in allegro suffer from leftwards only bit mixing problems (even Bob Jenkins ISAAC generator has some limited leftward-mixing issues when compiled with very small array sizes).

orz, ahh... can't believe I overlooked that case. Well anyway, here are three different versions now. One, rand0, mixes every byte, rand8 is as before with the case 3 fix, and rand9 follows your (and Bob Jenkins') lead and assembles 4 bytes before mixing them all together.

<code>
unsigned int hash_rand8(char *key, unsigned int len)
{
unsigned int i, seed=0, rem;

rem = len & 3;

len>>=2;

for(i=0; i<len; i++)
{
seed ^= seed << 13;
seed += ((unsigned int*)key)<i>;
seed ^= seed >> 7;
}

switch(rem)
{
case 1:
seed ^= seed << 2;
seed += ((unsigned char*)key)[i << 2];
seed ^= seed >> 23;
break;

case 2:
seed ^= seed << 14;
seed += ((unsigned short *)key)[i << 1];
seed ^= seed >> 9;
break;

case 3:
seed ^= seed << 19;
seed += (((unsigned short *)key)[i << 1] << 8 ) +
((unsigned char*)key)[(i << 2) + 2];
seed ^= seed >> 7;
break;
}

return seed * 1103515245 + 12345;
}

unsigned int hash_rand9(char *key, unsigned int len)
{
unsigned int i, seed=0, rem;

rem = len & 3;

len>>=2;

for(i=0; i<len; i++)
{
seed ^= seed << 13;

seed += key[0];
seed += key[1]<<8;
seed += key[2]<<16;
seed += key[3]<<24;

seed ^= seed >> 7;

key+=4;
}

switch(rem)
{
case 1:
seed ^= seed << 2;
seed += key[0];
seed ^= seed >> 23;
break;

case 2:
seed ^= seed << 14;
seed += key[0];
seed += key[1]<<8;
seed ^= seed >> 9;
break;

case 3:
seed ^= seed << 19;
seed += key[0];
seed += key[1]<<8;
seed += key[2]<<16;
seed ^= seed >> 7;
break;
}

return seed * 1103515245 + 12345;
}

unsigned int hash_rand0(char *key, unsigned int len)
{
unsigned int i, seed=0;

for(i=0; i<len; i++)
{
seed ^= seed << 13;
seed += key<i>;
seed ^= seed >> 7;
}

return seed * 1103515245 + 12345;
}
<code>

It all generally looks correct now.

The most incorrect looking things left are that they int is assumed to be a 32 bit type, and (in hash_rand9 only), and char is assumed to get promoted to int when leftshifted. Both of those assumptions are true on most CPUs & compilers these days, but in embedded contexts you can still find some that don't follow those assumptions. int size can be handled with a typedef or #define, promotion assumptions can be handled by explicit typecasting (as Bob Jenkins does in his hash function).

Also, you have the case set up so that hash_rand8 and hash_rand9 produce different results right now (in the switch statement at the end, on case 3). It might be preferable if they produced identical results (at least on little-endian machines), so that one could be a drop in replacement for the other or something.

Have you a specific use for your hash functions? As choosing the fastest might not necessarily be the best.

Neil.

orz, again some good insight -- you've been very helpful. I've made the recommended changes.

Neil, I have a few different use for my functions, and not all of them will need the runtime speed. Ie. loading bitmaps, samples etc. into named entries of a hash table for configuration purposes. The resources will then be used to fill in the various data structures that will be used at runtime, such as animation sequences, scripts, sound sequences. The speed isn't needed here because the resulting data structures will directly address the various resources. However, having named items accessible to scripts/configuration is nice.

For speedier applications, the hash functions will be used as part of my scripting system to speed up dictionary accesses. Also, they will provide a means to support a fast associative array scripting datatype, as in Lua or other prototyped OO languages.

As you can see, the latter can be used to support the former as well. There are a ton of uses I'll put the functions to work in, to be sure.

Anyway, the final results are in... hash_rand8 > superfasthash! The key sequence I used for this test was as follows:

XXXXXsuper really really really really really REALLY long test string is super super super super SUPER DUPER super SUPER DUPER super SUPER DUPER great (yes it really is!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!)

...where XXXXX is a hex count from 00000 to 50000. This key really trashed the lesser hash functions, as you can see from the results below. The previous tests used a much smaller (20480 entries) table of 61-byte-long, randomized, lowercase alphabetical keys which seemed to improve hashing ability all around. No longer.

As you can see, the later rand-family hash functions held their own against the big boys, producing comparable results, and even toppled the venerable allegro hash in distribution ability. rand8 was the winner in speed overall for the "good" functions, and was comparable for the other stats.

Next I'll have to take another peek at Bob's hashmap code.

Oh, also, those hash functions are unaffected by leading 0s, at least if they occur in sets of four. Consider initializing seed to len (as Bob Jenkins does if I recall correctly), or some other such fix for that.

Here is the results of a test I wrote. The test generates a random 50 byte string of binary data, hashes it, changes a random bit, hashes it again, etc, (1<<18) times. The complication is, it checks that it hasn't accidentally gone back to a string it used earlier. For "norm", it changes any bit in the string, for "low" it changes only the first 48 bits, for "high" it changes only the last 48 bits. The result is the number of hashes produced that were already produced earlier.

Any value up to 15 can be reasonably dismissed as random fluctuations. Thus, OAAT and rand0 produce perfect results, superfast, rand8, and rand9 produce acceptable results, and everything else produces bad results. "md5", and "bobjenkins" are added as sanity checks.

I'll write a more thorough test function tomorrow.

Ahh, that's great. Could you post your test code when you've finished, so I can cobble together a comprehensive mega-test?

And do you mean the leading 4 zeroes in the key, or the seed?

Lets see if this works...

Everything specific to your stuff is in h.cpp. The rest of it is random stuff related to random number generation and testing, which shares a bunch of code with this since it was a quick hack to get the random number tests working on hash functions.

Using longer samples (up to 16 million hashes), hash_rand0 failed a few tests, but OAAT still prevailed. I've started a 256-million-hash test in an effort to get OAAT to break down and cry, but it will be a while before that finishes.

Four leading 0s on the "key" will produce an identical result, like these two string "ab", "\0\0\0\0ab".

If all went well, that should produce output like this:

edit: fixed an issue where tests were labelled incorrectly

edit2:
Sorry about the comment at the top.
I've removed it. I was in a bad mood, when I wrote that, and then forgot about it. It was totally uncalled for.

Oh, the four leading zeroes I mentioned are ascii characters, not bytes.

Hmm, the rand series, though failing some tests, still seems to be doing respectably. I suspect that the failing may be in the actual rand portion of the "avalanche".

I was confused when I said OAAT was passing... it wasn't, I had it displaying the wrong results for one category which it was failing. Still OAAT did pretty well, along with hash_rand0. I recommend trying hash functions with more than 32 bits of state.

Anyway, it's of course impossible to create a perfect omni-purpose hash function, as there are tradeoffs between speed, quality, and extras (suitability for hardware implementation, cryptographic security, etc). But with a little trial-and-error, a little luck or insight, and maybe even a dab of theory, it ought to be possible to create a hash function that compares favorably to existing ones in almost any specific niche you care to aim at. Good luck.

So, rand0 seems to be pretty good
How does it compare when it comes to speed and memory used?

Also, let's say I'd use one of these algos to create a hashtable with say, 256 entries, would rand0 still be the candidate I want?
I mean, if I'd do a (rand0() & 255) would I still get a good distribution?

I think thats the point of this whole thing, having good distrobution and speed for power of two sized hash tables. unlike pjw that requires say a table thats some "prime" number in size.

lenny, since it's just a hash function, it really uses no memory other than the local variables needed to calculate the hash value. rand8/9 are faster than rand0, so I'd prefer rand8 for typical usage. All of my testing was aimed at power-of-two-sized tables, and I've shown that rand0/8/9()&255 will give you good distribution over such a table (the one I used for testing in the end was 65536 elements)... much better than pjw, crc, or allegro hashes.

orz has shown that rand8 and rand9 break down somewhat with intensive testing, but the tests he used are rather high-octane. The rand functions are quite good when compared alongside the other common hash functions for their intended usage (hashing strings into ^2 tables). They are also faster, which was my main goal. Just don't use them for any serious encryption purposes.

Anything that does well on the tests is likely to do well in real world circumstances. Of course, that's just a guess on my part - I don't have any large database of real-world data to try out. The biggest flaw in the tests (that I can think of, anyway...) is that they only compare hashes of strings of one specific length at time. Also, they look for flaws in all bits of the result, whereas in the real world, often only the high or low bits will be used.

edit: On second thought, the tests also spend a great deal of effort looking for correlations in results for similar strings, which doesn't matter (under some circumstances) in real world hash tables. In short, the tests are overkill for hash functions intended for use in hash tables. I may revise them soon to ignore flaws that are irrelevant for normal hash tables.

My hash code supports automagic resizing of hash tables, as well as fast look-ups in the average case (ie: it stops looking when it find a hole in the hash table). My hash code assumes you have a hash value, and some compare function available.

In this case, you would be able to use strcmp() as the compare function, and rand0 or rand8 as your hash function. My hash table code should handle the rest.