Hash-Funktionen

 [Vorheriges Kapitel]  [Vorherige Seite]  [Inhaltsverzeichnis]  [Nächste Seite]

*Anforderungen an Hash-Funktionen:

1.Effiziente Berechenbarkeit,
 
2.Surjektivität (ansonsten wird Speicherplatz innerhalb von M verschwendet) und
 
3.gute ``Streuung'', d.h. auch relativ ``ähnliche'' Schlüssel sollten verschiedenen Lokationen aus M zugeordnet werden.
 

*Hash-Funktionen müssen in Abhängigkeit von K geeignet bestimmt werden.
 
*Kryptographische Hash-Funktionen wie MD5 und SHA-1 erfüllen zwar den 2. und 3. Punkt in hervorragender Weise für beliebige Schlüsselmengen K, sind jedoch leider nicht effizient genug.
 
*Wenn k eine ganze Zahl ist, gibt es zwei bewährte Varianten:

*Division: h(k) = k   mod   n.
 
*Multiplikation:
h(k) = |_ n ( (
A

w
k )   mod   1 ) _|

 
(M = [0..n-1], w = MAX(INTEGER) + 1, und A ist eine natürliche Zahl, die teilerfremd zu w ist)
 

 [Vorheriges Kapitel]  [Vorherige Seite]  [Inhaltsverzeichnis]  [Nächste Seite]
Copyright © 1999 Andreas Borchert, in HTML konvertiert am 29.06.1999