PJW-Hash-Funktion - PJW hash function
Die PJW-Hash-Funktion ist eine nicht kryptografische Hash-Funktion, die von Peter J. Weinberger von AT & T Bell Labs erstellt wurde.
Andere Versionen
Eine Variante des PJW-Hash wurde verwendet, um ElfHash- oder Elf64-Hash zu erstellen, der in Unix-Objektdateien im ELF- Format verwendet wird.
Allen Holub hat eine tragbare Version des PJW-Hash-Algorithmus erstellt, die einen Fehler aufwies und in mehreren Lehrbüchern landete, wie der Autor eines dieser Lehrbücher später zugab.
Algorithmus
Der PJW-Hash-Algorithmus umfasst das Verschieben des vorherigen Hashs und das Hinzufügen des aktuellen Bytes, gefolgt vom Verschieben der High-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
Implementierung
Nachfolgend finden Sie die im Unix ELF-Format verwendete Algorithmusimplementierung:
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;
}
Siehe auch
Nicht kryptografische Hash-Funktionen
