Vorlesung Informatik 2 - Teil B: Theorie

3.7 Hash-Liste

Ein assoziative Liste auf der Basis einer Hashtabelle. 

Zu jedem Schlüssel wird ein numerischer Hashwert gebildet, der zwischen 0 und N-1 liegt. Günstige Werte für N sind Primzahlen.

Ein Array der Länge N - die Hashtabelle- enthält Zeiger auf verkettete Listen mit allen Einträgen, deren Hashwerte gleich dem Index in die Hashtabelle sind.

Beispiel:  Speicherung von Stadt zu PLZ.

Hashfunktion:  PLZ%10

Key       Hash  Stadt
70569      9    Stuttgart
33602      2    Bielefeld
28327      7    Bremen
80331      1    München
71111      1    Waldenbuch
führt zu folgender Datenstruktur:

Hashtabelle   Überlauf-Listen    
   -------
0 | null | |------| 1 | --+----> [80331|München| +--]---------> [71111|Waldenbuch|null] |------| 2 | --+----> [33602|Bielefeld|null] |------| 3 | null | |------| 4 | null | |------| 5 | null | |------| 6 | null | |------| 7 | --+----> [28327|Bremen|null] |------| 8 | null | |------| 9 | --+----> [68159|Mannheim| -]---->[70569|Stuttgart|null] |------|
Als letztes wurde [68159 Mannheim] hinzugefügt, dazu waren folgende Schritte nötig:
  • prüfen, ob es schon eine Eintrag mit dem Schlüssel 68159 gibt und dort ggf. den Wert Mannheim eintragen. Dazu rufen wir die Methode replace (siehe Kapitel 3.5) und wenn diese true zurückgibt sind wir fertig.
  • einen neuen Eintrag mit [68159 Mannheim] erzeugen, der auf den Eintrag 70569 zeigt.
  • die Referenz auf den neuen Eintrag in die hashTabelle[9] eintragen.    
Die beiden rot markierten Schritt sind weiter unten als Programmcode gezeigt.

Für die Implementierung schreiben wir zunächst das Interface meineMap<KV>:
    put(key: K, value:V):void        Speichert oder ersetzt value unter dem Schlüssel key,
    get(key: K): V Liefert den Wert zu key oder null,
    remove(key:K):boolean löscht den Eintrag zu key,
    replace(key:K, value:V): boolean ersetzt den Wert zu key, liefert false falls der Key nicht existiert.


Die Überlauf-Listen bestehen wieder aus Einträgen ähnlich wie bei Stack oder Queue:

 private class Eintrag<K,V>{
     K key;
     V value;
     Eintrag<K,V> next;
     Eintrag(K key, V value, Eintrag<KV> next){
          this.key = key;
          this.value = value;
         this.next = next;
    }
}

und die Hashtabelle ist ein Array vom Typ Eintrag:
  Eintrag[] hashTabelle = new Eintrag[31];

Und das Einfügen würde in der Methode put(key, value) würde etwa so gehen:

   if(replace(key, value)) return;
   int hash = key.hashCode()%hashTabelle.length;
   hashTabelle[hash] = new Eintrag(key, value, hashTabelle[hash]);


Lehrvideo  (YouTube)