PJW hash function
PJW hash function is a non-cryptographic hash function created by Peter J.
≈ 2 min read
PJW hash function. encyclopegia.org, snapshot enwiki-001253333688. /a/pjw-hash-function
Names in other languages
- EnglishPJW hash function
- РусскийPJW-32
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
PJW hash function is a non-cryptographic hash function created by Peter J. Weinberger of AT&T Bell Labs.
Other versions
edit edit sourceA 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
edit edit sourcePJW 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 hImplementation
edit edit sourceBelow 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; }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
edit edit sourceNon-cryptographic hash functions
References
edit edit source- ^ Binstock, Andrew (1996). "Hashing Rehashed". Dr. Dobb's. Wikipedia revision 1253333688, retrieved 2026-11-20
- ^ "Hash Functions". www.cs.hmc.edu. Retrieved 2015-06-10. Wikipedia revision 1253333688, retrieved 2026-11-20
- ^ CORPORATE UNIX Press (1993). System V application binary interface. ISBN 0-13-100439-5. Wikipedia revision 1253333688, retrieved 2026-11-20
- ^ "ELF hash function may overflow". 12 April 2023. Retrieved 2023-04-14. Wikipedia revision 1253333688, retrieved 2026-11-20
Text derived from https://en.wikipedia.org/w/index.php?oldid=1253333688 under CC BY-SA 4.0; modifications have been made.