PJW hash function explained

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 the previous hash and adding the current byte followed by moving the high bits:^[2]

algorithm PJW_hash(s) is uint h := 0 bits := uint size in bits for i := 1 to |S| do h := h << bits/8 + s[i] high := get top bits/8 bits of h from left if high ≠ 0 then 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)

This C code incorrectly assumes that long is a 32-bit data type. When long is wider than 32 bits, as it is on many 64-bit systems, the code contains a bug.^[4]

See also

Non-cryptographic hash functions

Notes and References

1. Hashing Rehashed . . Binstock. Andrew. 1996.
2. Web site: Hash Functions. www.cs.hmc.edu. 2015-06-10.
3. Book: CORPORATE UNIX Press. System V application binary interface. 1993. 0-13-100439-5. registration.
4. Web site: ELF hash function may overflow . 2023-04-14.