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 = x_{n - 1}x_{n - 2}...x₁x₀ ein String, dann ist

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