PJW hash function

PJW hash function is a non-cryptographic hash function created by Peter J. Weinberger of AT&T Bell Labs.

Other versions

A variant of PJW hash had been used to create ElfHash or Elf64 hash that is used in UNIX object files with ELF format.

Allen Holub has created a portable version of PJW hash algorithm that had a bug and ended up in several textbooks, as the author of one of these textbooks later admitted.

Algorithm

PJW hash algorithm involves shifting previous hash and adding current byte followed by moving high bits:

PJWHash(s)
  uint h = 0
  bits = uint size in bits
  for i = 1 to |S|
    h = h << bits/8 + s[i]
    high = get top bits/8 bits of h from left
    if high ≠ 0
      h = h xor (high >> bits*3/4)
      h = h & ~high
  return h

Implementation

Below is the algorithm implementation used in UNIX ELF format:

unsigned long ElfHash ( const unsigned char *s )
{
    unsigned long   h = 0, high;
    while ( *s )
    {
        h = ( h << 4 ) + *s++;
        if ( high = h & 0xF0000000 )
            h ^= high >> 24;
        h &= ~high;
    }
    return h;
}

See also

List of hash functions