Symboltabellen/Hashing (5. 1.)

Die (sogenannte) Symboltabelle

$$Id: symtab.tex,v 1.1 2004/01/05 14:12:41 joe Exp $$

(eigentlich ist es die Tabelle für Bezeichner)

(Wdhlg.) Tokenklassen:

• Syntaxzeichen (Klammern usw.),
• Literale (für Zahlen, Strings, usw.),
• Schlüsselwörter (if, then, usw.)
• Bezeichner (für Variablen, Unterprogramme, Typen, Module usw.)

(Was ist mit Operatoren?)

Inhalt der Symboltabelle

wichtige Attribute der Bezeicher aufbewahren:

• Variable: Typ
• Unterprogramm: Argument- und Ergebnistyp
• Typ: Supertypen (OO) usw.
• (alles:) Quelltextposition

Symboltabellen als Abbildungen

$$Id: map.tex,v 1.1 2004/01/05 14:12:41 joe Exp $$

Abstrakter Datentyp Map (Abbildung)

• von Menge $A$ (hier: String)
• nach Menge $B$ (hier: Bezeichner-Information)

interface Map(A, B) {
    void clear ();
    void put (A key, B value);
    B get (A key);
    void remove (A key);
}

(anderer Name: Wörterbuch (Dictionary) -- warum ist das inzwischen ``deprecated''?)

Abbildungen in Java

Map ist ein Typkonstruktor

($=$ Typ höherer Ordnung, wenn $A$ und $B$ Typen sind, dann ist $\verb*\vert Map(A,B)\vert$ ein Typ),

aber man darf das in Java nicht hinschreiben. Deswegen (http://java.sun.com/j2se/1.4.2/docs/api/java/util/Map.html):

interface Map {
    void clear ();
    void put (Object key, Object value);
    Object get (Object key);
    void remove (Object key);
}

und man muß fleißig casten:

Entry e = (Entry) table.get ("foo");

Das Fehlen von Typen höherer Ordnung

...ist eine schwerwiegende Lücke in vielen gängigen Sprachen (die besonders beim Umgang mit Collections, Containern usw. schmerzt).

Mehr oder wenig zaghafte Versuche, um diese Lücke herumzuturnen, heißen dann Casts, Templates (C++, Java 1.5), Design Patterns usw.

und erfordern dann eigene Vorlesungen, Lehrbücher, Hilfsprogramme (sog. CASE-Tools), Zaubersprüche und Gurus $\dots$

($\dots$ und schaffen auf diese Weise immerhin Umsatz und Arbeitsplätze).

Abbildungen: mögliche Implementierungen

• ungeordnete Liste/Array
• alphabetisch geordnete Liste/Array
• unbalancierter Suchbaum
• balancierter Suchbaum (z. B. AVL, 2-3, Rot-Schwarz)

Aufgabe (Wdhlg 1. Semester, hoffe ich): diskutiere (für alle 6 Varianten) die Laufzeiten für die o. g. Operationen.

Beispiel: ungeordnete Liste:

• put ist nur eine Operation, also $\Theta(1)$, konstant
• aber get muß alle Einträge betrachten, also $\Theta(n)$, linear

Hashing

benutze schnelle Hashfunktion $h : \Sigma^* \to \{0 \dots m-1\}$

Idee: Speichere $x$ in $t [h(x)]$.

Parameter (Tabellengröße, Hashfunktion) geeignet wählen, dann ``praktisch konstante'' Laufzeit für alle Operationen.

Hash-Kollision: $x \neq y$ und $h(x)=h(y)$.

$x$ ist schon in $t [h(x)]$, wo soll $y$ hin?

Kollisionen behandeln:

• außerhalb der Tabelle: $t[i] =$ Liste aller $x$ mit $h(x)=i$.

  Nachteil: Extraplatz für Listenzeiger

• innerhalb der Tabelle:
  • speichere $y$ in $t[h(y)+1]$ oder$t[h(y)+2]$ oder ...

    Nachteil: Tabelle ,,verklebt``
    (belegte Blöcke erzeugen weitere Kollisionen)

  • doppeltes Hashing: benutze $h_1, h_2$ und benutze Indizes $h_1(y), h_1(y) + h_2(y), h_1(y) + 2 h_2(y), \ldots$.

    Vorteil: kein Verkleben (Schrittweiten sind verschieden!)

Aufgabe: Pseudocode für Einfügen und Suchen bei doppeltem Hashing. was ist mit Löschen?

Re-Hashing

$$Id: rehash.tex,v 1.1 2004/01/05 14:12:41 joe Exp $$

Problem:

• Tabelle zu klein $\to$ zu voll $\to$ viele Kollisionen $\to$ langsam.
• Tabelle zu groß: Platz verschenkt.

Lösung: falls Tabelle gewissen Füllstand erreicht, dann zu neuer, größerer Tabelle wechseln ($=$ re-Hashing).

am einfachsten: Tabellengröße ist immer Potenz von 2; dann: vergrößern $=$ verdoppeln.

Beim re-Hashing müssen alle Einträge betrachtet werden, das findet aber nur selten statt, so daß die amortisierte Laufzeit trotzdem konstant ist (Aufgabe: nachrechnen).