PJW-hashfunktion - PJW hash function
PJW hash-funktion är en icke-kryptografisk hash-funktion skapad av Peter J. Weinberger från AT&T Bell Labs.
Andra versioner
En variant av PJW-hash hade använts för att skapa ElfHash eller Elf64-hash som används i Unix-objektfiler med ELF- format.
Allen Holub har skapat en bärbar version av PJW-hashalgoritmen som hade en bugg och hamnade i flera läroböcker, som författaren till en av dessa läroböcker senare medgav.
Algoritm
PJW-hashalgoritmen innebär att man byter föregående hash och lägger till aktuell byte följt av att flytta de höga bitarna:
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
Genomförande
Nedan följer algoritmimplementeringen som används i Unix ELF-format:
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;
}
Se även
Icke-kryptografiska hashfunktioner
