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.^[1]

Algorithm

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

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:^[3]

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

References

1. Binstock, Andrew (1996). "Hashing Rehashed". Dr. Dobbs.
2. "Hash Functions". www.cs.hmc.edu. Retrieved 2015-06-10.
3. CORPORATE UNIX Press. System V application binary interface. ISBN 0-13-100439-5.