PJW hash-functie - PJW hash function
De PJW-hashfunctie is een niet-cryptografische hashfunctie die is gemaakt door Peter J. Weinberger van AT&T Bell Labs.
Andere versies
Een variant van PJW-hash is gebruikt om ElfHash- of Elf64-hash te maken die wordt gebruikt in Unix-objectbestanden met ELF- indeling.
Allen Holub heeft een draagbare versie van het PJW-hash-algoritme gemaakt dat een bug bevatte en in verschillende leerboeken terechtkwam, zoals de auteur van een van deze leerboeken later toegaf.
Algoritme
PJW-hash-algoritme omvat het verschuiven van de vorige hash en het toevoegen van de huidige byte, gevolgd door het verplaatsen van de hoge 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[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
Implementatie
Hieronder vindt u de algoritme-implementatie die wordt gebruikt in het Unix ELF-formaat:
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;
}
Zie ook
Niet-cryptografische hash-functies
