PJW hash function is a non-cryptographic
hash function
A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called ''hash values'', ''hash codes'', ''digests'', or simply ''hashes''. The values are usually u ...
created by
Peter J. Weinberger
Peter Jay Weinberger (born August 6, 1942) is a computer scientist best known for his early work at Bell Labs. He now works at Google.
Weinberger was an undergraduate at Swarthmore College, graduating in 1964. He received his PhD in mathemati ...
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
An elf () is a type of humanoid supernatural being in Germanic mythology and folklore. Elves appear especially in North Germanic mythology. They are subsequently mentioned in Snorri Sturluson's Icelandic Prose Edda. He distinguishes "ligh ...
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 the previous hash and adding the current byte followed by moving the high bits:
algorithm PJW_hash(s) is
uint h := 0
bits := uint size in bits
for i := 1 to , S, do
h := h << bits/8 + s
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:
See also
Non-cryptographic hash functions
This is a list of hash functions, including cyclic redundancy checks, checksum functions, and cryptographic hash functions.
Cyclic redundancy checks
Adler-32 is often mistaken for a CRC, but it is not: it is a checksum.
Checksums
Universa ...
References
{{reflist
Articles with example pseudocode
Articles with example C code
Hash function (non-cryptographic)