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:

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

Link

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.

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.

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.

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>

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

Neil.

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.

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.

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.

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.

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.