struct {
 char *string;
} buckets[10];

case 1:

 buckets[0] = "A";
 buckets[1] = "B";

 Assuming ASCII:
  n = key - 'A';

case 2:

 buckets[0] = "B";
 buckets[1] = "A";

 Assuming ASCII:
 n = 1 - (key -  'A');

case 3:
 buckets[0] = "ABC";
 buckets[1] = "DEF";

 'A' + 'B' + 'C' = max

 Would this work: (('A' + 'B' + 'C') * 3) / numBuckets;

 'D' + 'E' + 'F' = max

An algorithm sort of evolves from these patterns.  We could possibly have even greater performance by only doing keys that are sizeof (int) and aligned to sizeof (int).


 ABC
 65 + 66 + 67 = 198

 198 * 3 is 594

 594 / numBuckets

What if we do patterns likes:

 K+E+Y = max
 and the max becomes the last element in a bucket like so:

 (K+E+Y * numElements) / numBuckets

 DEF
 68 + 69 + 70 = 207


So we have the values 198 and 207.  Somehow we must map those to exact keys ALWAYS.

Let's say that 207 becomes slot 1, and 198 becomes slot 0

The delta of 207 - 198 is 9 


If we did key - 198 we could have a direct mapping of 

 buckets[0] = "ABC"
 buckets[9] = "DEF"


However this has a problem, and that is that keys like this will generate the same hash:

 CBA, BAC, etc.

What if we multiply a character value by 2, 3, 4, .. ?

 (65 * 2) + (66 * 3) + (67 * 4) 


That appears to always be unique.  One issue with this is that we have expanded the potential array size considerably.  The min value (the key with the lowest number) would become 0, and any greater keys would be at high addresses.  Would it be enough to do a multiply by 1,2,3, ...?  That would probably improve the size.


There is a way to produce an algorithm or find the proper algorithm, and the answer lies in mph and the other perfect hash code.  Our simplistic hash wastes too much memory, but I wonder how the others fare.


I had the idea of using 2 bytes and encoding the pointer value over a series.  This could potentially save some space, but I'm not seeing all of the idea yet.


We could scale the value produced by the KEY to produce a linear array of keyed values that are closer together.  Provided that no collisions occur it should work.  One problem would be handling remainders.  This should be thought about.

----
study mph

This is apparently a Pearson hash algorithm:
  hash = 0;
  for (i=0; i<len; ++i)
    hash = tab[(hash+key[i])%n];



http://burtleburtle.net/bob/hash/pearson.html
  -- use an array of 256 1-byte values
  ub1 x[0..255];

  -- fill it with the values 0 to 255 in some pseudorandom order
  -- (this is derived from the alleged RC4)
  { for i in 0..255 do
    { x[i] := i;
    }
  }
  k=7;
  { for j in 0..3 do
    { for i in 0..255 do
      { s = x[i];
        k = (k + s) mod 256;
        x[i] = x[k];
        x[k] = s;
      }
    }
  }

And then use the array for hashing like this:

  -- use the length of the message to initialize the hash
  -- XXX can be 0, or some constant, or some argument
  hash := (XXX+len) mod 256;

  -- hash the characters in the message one byte at a time
  {for i in 0..len-1 do
    {hash := (hash + message[i]) mod 256;  hash := x[hash];}}