prev up next

Previous: Spielbaum Up: Algorithmen-Skript WS 2000/2001 Next: Offenes Hashing

Hashing

Zum Abspeichern und Wiederfinden von Elementen wäre folgende Funktion hilfreich:

    f: Element -> int
Dann könnte Element x bei Adresse f (x) gespeichert werden.
Problem:
Anzahl der möglichen Elemente Anzahl der Adressen


Gegeben Adressen von 0 bis N - 1.

Sei x ein beliebiges Objekt. Dann ist


    String s = x.toString();
seine Stringrepräsentation.

Sei x = xn - 1xn - 2...x1x0 ein String, dann ist


f (x) = xi MOD N      

eine Hashfunktion.
Gilt: f (x) = f (y), so liegt eine Kollision vor, die bei offenem und geschlossenem Hashing unterschiedlich behandelt wird.



Unterabschnitte
prev up next
Previous: Spielbaum Up: Algorithmen-Skript WS 2000/2001 Next: Offenes Hashing