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 $\gg$ 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} \ldots x_{1} x_{0}$ ein String, dann ist

$$\begin{eqnarray*} f(x) = {\left( \sum_{ i=0 }^{ n-1 } x_{ i } \right) } \mbox{ MOD } N \end{eqnarray*}$$

ein Beispiel für eine (sehr einfache) Hashfunktion.
Gilt: $f(x)=f(y)$, so liegt eine Kollision vor, die bei offenem und geschlossenem Hashing unterschiedlich behandelt wird.