prev up next

Previous: Java Collections Framework Up: skript 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 $\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*}



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: Java Collections Framework Up: skript Next: Offenes Hashing