{{Short description|Computing algorithm}} '''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.<ref>{{Cite journal |url = http://www.drdobbs.com/database/hashing-rehashed/184409859|title = Hashing Rehashed |journal=Dr. Dobb's |last = Binstock|first = Andrew|year = 1996}}</ref>

==Algorithm== PJW hash algorithm involves shifting the previous hash and adding the current byte followed by moving the high bits:<ref>{{Cite web|title = Hash Functions|url = http://www.cs.hmc.edu/~geoff/classes/hmc.cs070.200101/homework10/hashfuncs.html|website = www.cs.hmc.edu|accessdate = 2015-06-10}}</ref>

'''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:<ref>{{Cite book|title = System V application binary interface|last = CORPORATE UNIX Press|publisher = |year = 1993|isbn = 0-13-100439-5|location = |pages = |url-access = registration|url = https://archive.org/details/systemvapplicati00unix}}</ref>

<syntaxhighlight lang="C"> 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; } </syntaxhighlight>

This C code incorrectly assumes that <code>long</code> is a 32-bit data type. When <code>long</code> is wider than 32 bits, as it is on many 64-bit systems, the code contains a bug.<ref>{{Cite web |url=https://maskray.me/blog/2023-04-12-elf-hash-function |title=ELF hash function may overflow |date=12 April 2023 |access-date=2023-04-14}}</ref>

== See also == Non-cryptographic hash functions

==References== {{reflist}}

Category:Articles with example pseudocode Category:Articles with example C code Category:Hash function (non-cryptographic)