aka Hash-Map
LookUp(Search): für einen gegeben Schlüssel finde das zugehörige Objekt in der Datenstruktur. Falls kein solches Objekt existiert, gebe eine entsprechende Meldung zurück.
Insert: füge ein neues Objekt $x$ (mit gegebenem Schlüssel) der Datenstruktur hinzu.
Delete: für einen gegebenen Schlüssel $k$, lösche das Objekt aus der Datenstruktur (falls es existiert).
| Operation | Laufzeit |
|---|---|
LookUp(Search) |
$O(1)^*$ |
Insert |
$O(1)$ |
Delete |
$O(1)^*$ |
Des Stern (asterisk) zeigt an, dass die entsprechnde Laufzeit nur gilt, wenn und nur wenn (iff)
Wenn die Anwendung schnelles Nachschlagen (Lookup) auf einer sich dynamisch veränderten Datenmenge erfordert.
Alle möglichen Schlüssel der Objekte bilden ein Universum $U$, z.B.
Typischerweise ist die Mächtigkeit der Menge $U$ extrem hoch.
| Datenstuktur | Speicherbedarf | typische Laufzeit von LookUp |
|---|---|---|
| Array (strait-forward) | $\Theta({\mid}U{\mid})$ | $\Theta(1)$ |
| Linked List | $\Theta({\mid}S{\mid})$ | $\Theta({\mid}S{\mid})$ |
| Hash Table | $\Theta({\mid}S{\mid})$ | $\Theta(1)^*$ |
Weitere Möglichkeit Suchbäume, falls eine Ordnung auf $U$ besteht (vgl. z.B. in Java TreeMap als Implementation des Map-Interface).
Wie ist dabei der Speicherbedarf und die typische Laufzeit von LookUp?
Eine Hash-Funktion $h: U \rightarrow \{0, 1, \dots, n-1 \}$ weist jedem Schüssel (key) eines Universums $U$ einen Wert $\{0, 1, \dots, n-1 \}$ (hier) für eine Position in einem Array der Länge $n$ zu.
Definition einer Kollision: Zwei Keys $k_1$ und $k_2$ kollidieren, wenn $h(k_1) = h(k_2)$.
Schubfachprinzip (pigeonhole principle): Kollisionen sind unvermeidbar, wenn man (n+1)-Objekte auf n-Fächer verteilen will. Hier muss man mindestens ein Fach doppelt besetzten.
Sogar: Wenn die Anzahl der Objekte deutlich kleiner als die Anzahl der Fächer ist und man die Objekte zufällig gleichverteilt, sind Kollisionen sehr wahrscheinlich.
Betrachte $n$ Personen mit zufälligen Geburtsdaten mit der Annahme, dass alle Personen nicht in einem Schaltjahr (365 Tage) geboren wurden. Bei wievielen Personen $n$ ist die Wahrscheinlichkeit, dass zwei Personen an einem Tag geboren wurde, mindestens 50%?
Anzahl der Kombinationen $n=23$ (unterscheidbare) Personen auf $d = 365$ Tage zu verteilen, ohne dass ein Geburtstag auf den gleichen Tag fällt:
$$ 365 \cdot 364 \dots (365-23+1) = \frac{365!}{(365-23)!} $$Anzahl der Kombinationen 23 (unterscheidbare) Personen auf 365 Tage beliebig zu verteilen: $365^{23}$
Wahrscheinlichkeit, dass von den 23 Personen alle an einem unterschiedlichem Tag Geburtstag haben, ist das Verhältnis der Kombinationen: $$ \frac{365!}{(365-23)! 365^{23} } \approx 0.4927 $$
Wahrscheinlichkeit, dass von den 23 Personen nicht alle an einem unterschiedlichem Tag Geburtstag haben:
$$ 1 -\frac{d!}{(d-n)! d^{n} } = 1-\frac{365!}{(365-23)! 365^{23} } \approx 0.5073 $$LookUp/Insert/Delete auf einem Objekt mit Schlüssel $k$, führt eine LookUp/Insert/Delete auf der verketteten Liste$A[h(k)]$.Hier zu (einfacheren Erklärung) ohne Delete-Operation:
Assoziiere jeden Schlüssel nicht nur mit einer Position $h(k)$ sondern mit einer Sequenz von Positionen (Probe Sequence).
Insert Zum Einzufügen eines Objekt mit Schlüssel $k$: Iteriere solange durch die Probe Sequence bis eine
leere Position gefunden wurde.LookUp für einen Schlüssel $k$: Iteriere solange durch die Probe Sequence bis das gewünschte Objekt gefunden wurde oder das leere Element. Hier muss natürlich jedesmal überprüft werden, ob der Schlüssel passt.Probe Sequences können zum Beispiel mit
generiert werden.
Geeignete Hash-Funktionen wurden von Experten entwickelt. Solche geeigneten Hash-Funktionen sollen verwendet werden.
Mehr zum Thema siehe z.B. [Chaper11, Corman].