PKP Hash

The next function is called pkphash, after Peter K. Pearson it's inventor. This was published in an article in the Communications of the ACM in 1990.

This version of pkphash gives results in a maximum of 16-bits of hash value. It takes each character of the key and exclusive-ors the ordinal value of it with the value in the `current position' in the pkpnext random walk table to create a new `random' position. The current position in the random table are represented by variables h1 and h2 in the code. At each interation h1 and h2 both move to independent new random position. These two variables are used as two tiny 8-bit integers, the code concatenates them together to create a 16-bit base hash value.


TYPE byte: 0..255;
TYPE rowbyte: [byte] of byte;


VAR
pkpnext: rowbyte;    { Global array for hashing }


PROCEDURE pkpinit( i1, i2 :longint );
{ i1 and i2 are the seeds for the Random Number Generator }
VAR
i: byte;
BEGIN
     tauset( i1, i2 );
     FOR i := 0 TO 255 DO
        pkpnext[i] := i;
     Permute ( pkpnext, 256 );
END;



FUNCTION pkphash( key: STRING; b: integer ): integer;
{ key is the key to hash;
   b   is the number of hash values [0..b-1] }
VAR
n, h1, h2, i: integer;
BEGIN
    n  := LENGTH( key );
    h1 := 0;
    h2 := 37;