PJW hash function

PJW hash function is a non-cryptographic hash function created by Peter J.

Uses your system voice; voice and rate in settings.

≈ 2 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

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 source

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

edit edit source

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

edit edit source

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; }

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 source

Non-cryptographic hash functions

References

edit edit source
  1. ^ Binstock, Andrew (1996). "Hashing Rehashed". Dr. Dobb's. Wikipedia revision 1253333688, retrieved 2026-11-20
  2. ^ "Hash Functions". www.cs.hmc.edu. Retrieved 2015-06-10. Wikipedia revision 1253333688, retrieved 2026-11-20
  3. ^ CORPORATE UNIX Press (1993). System V application binary interface. ISBN 0-13-100439-5. Wikipedia revision 1253333688, retrieved 2026-11-20
  4. ^ "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.

Words in each sectionAlgorithmAlgorithmAlgorithm: 88 words88ImplementationImplementationImplementation: 85 words85Other versionsOther versionsOther versions: 61 words61See alsoSee alsoSee also: 6 words6
Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

Provenance

snapshot enwiki-001253333688 · captured 2024-10-25 · ledger · version history

Cite this page as: encyclopegia.org, “PJW hash function”, snapshot enwiki-001253333688. https://encyclopegia.org/a/pjw-hash-function