Hashing und assoziative Arrays

Mitschrift gibts hier als PDF und hier gibts die TeX-Sourcen, leider als PDF weil man wohl keine .TeXs hochladen darf. Originale gibts auf Anfrage bei kirchner at cl dot uni minus heidelberg dot de. Wird das Package "listings" verwendet, das gibts bei http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/

Tipp- und sonstige Fehler dürfen gerne verbessert und erneut hochgeladen werden, oder gebt mir per Email Bescheid, dann pflege ich die Korrektur ein :)

Hashtabelle mit linearer Verkettung

Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

Implementation in Python

HashNode ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert und mit hilfe von next eine verkettete Liste darstellt

 class HashNode:
     def __init__(self,key,data,next):
         self.key = key
         self.data = data
         self.next = next #Verkettung!

Die eigentliche Hashtabelle wir in der Klasse HashTable implementier:

 class HashTable:
     def __init__(self):
        self.capacity = ... #Geigneter Wert
        self.size = 0
        self.array = [None]*self.capacity

In Python wird der Zugriffsoperator [ ] für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:

 def __setitem__(self, key, value)

So dass im Programmtext dann folgender Syntax möglich ist: a[key] = value

Genauso wir die Zuweisung value=a[key] wie folgt umgesetzt

 def __getitem__(self, key, value)

Implementierung der __setitem__ Funktionen in der HashTable Klasse:

 def __setitme__(self, key, value):
     index = hash(key) % self.capacity
     node = self.array[index]
     while node is not None:
         if node.key == key:
             #Element key ist schon in der Tabelle
             #Überschreibe die Daten mit dem neuen Wert
             node.data = value
             return
         #Kollision des Hashwerts, probiere nächsten Key aus
         node = node.next
      #Kein Element hatte den richtigen Schlüssel.
      #==>Es gibt diesen Schlüssel noch nicht
      #Füge also ein neues Element in die Hashtabelle ein
      
      self.array[index] = HashNode(key, value, self.array[index])
      #Der alte Anfang der List wurde der Nachfolger vom neue eingefügten
      #ersten Element
      
      size+=1

Und die Implementierung der __getitem__ Funktionen:

 def __getItem__(self, key):
     index = hash(key) % self.capacity
     node = self.array[index]
     while node is not None:
          if node.key == key #Gefunden!
              return Node.data
          node = node.next
     raise KeyError(key)

Wahl der Kapazität

In der C++ Standardbibliothek wird typischerweise ein Hash mit Hilfe der linearen Kette imlementiert. Dabei wird capcity immer als Primzahl gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:

 53, 97, 193, 398, 769, ...

Das hat zur Folge, dass h % self.capacity alle Bits von h benutzt (Eigenschaft aus der Zahlentheorie)

Hashtabelle mit offener Adressierung (offenes Hashing)

Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

Idee

Wenn array[index] durch Kollision bereits vergeben ist, probiere einen anderen Index aus.

• Das Array enthält pro Element höchstens ein (key,value)-Paar
• Das Array muss stets mindestens einen freien Platz haben (sonst gäbe es eine Endlosschleife). Es gilt immer self.size < self.capacity. Dies galt für die vorige Hash Implementation nicht.

Vorgehen bei Kollisionen

Sequentielles Suchen

Probiere den nächsten Index: index = index+1 % capacity

• Vorteil: einfach
• Nachteil: Clusterbildung

Clusterbildung heißt, dass sich größere zusammenhängende Bereiche bilden die belegt sind, unterbrochen von Bereichen die komplett frei sind. Beim Versuche des Einfügens eines Elements an einen Platz, der schon belegt ist, muss jetzt das ganze Cluster sequentiell durchlaufen werden, bis ein freier Platz gefunden wird. Damit entspricht die Komplexität der Suche der mittleren Länge der belegten Bereiche, was sich entsprechend in einer langsamen Suche widerspiegelt.

Doppeltes Hashing

Bestimme einen neuen Index (bei Kollisionen) durch eine 2. Hashfunktion.

Das doppelte Hashing wird typischerweise in der Praxis angewendet und liegt auch der Python Implementierung des Datentyps Dictionary (Syntax {'a':1, 'b':2, 'c':3} zugrunde.

Eine effiziente Implementierung dieses Datentyps ist für die Performance der Skriptsprache Python extrem wichtig, da z.B. beim Aufruf einer Funktion der auszuführunde Code in einem Dictionary unter dem Schlüssel Funktionsname nachgeschlagen wird oder die Werte lokaler Variablen innerhalb einer Funktion ebenfalls in einem Dictionary zu finden sind.

Für die Implementierung in Python werden wieder die obigen Klassen HashNode und HashTable benötigt, es folgen die angepassten Implementationen von __setitem und __getitem__:

 def __setitem__(self, key, value):
     h = hash(key)
     index = h % self.capacity
     while True:
         if self.array[index] is None or self.array[index].key is None
              #das Feld ist frei (1. Abfrage)
              #oder das feld ist als frei markiert (2. Abfrage)
              self.array[index] = HashNode(key, value)
              self.size +=1
              return
         if self.array[index].key == key:
              #Es gibt diesen Schlüssel schon,
              #überschreibe die Daten
              self.array[index].data = value
         #Letzter Fall: Kollision
         index = (5*index+1+h) % self.capacity
         h = h >> 5

Die vorgestellte Implementierung orientiert sich an Pythons interner Dictionary Implementierung, der zugehörige Quelltext mit ausführlichem Kommentar) findet sich unter dictobject.c Python Implementation (SVN)

Komplexität des offenen Hashings

• Annahme: uniformes Hashing, das heißt alle Indizes haben gleiche Wahrscheinlichkeit
• Füllstand <math>\alpha = \frac{\text{size}}{\text{capacity}}</math>

• Erfolglose Suche (d.h. es wird entweder ein neues Element eingefügt oder ein keyError geworfen): Untere Schranke für die Komplexität ist <math>\Omega\left(\frac{1}{1-\alpha}\right)</math> Schritte bzw. Anzahl von neuen index Berechnungen.
• Erfolgreiche Suche <math>\Omega\left(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\right)</math>

<math>\alpha</math>	0.5	0.9
erfolglos	2.0	10
erfolgreich	1.4	2.6

Wahl der Kapazität

In Python wird capacity Aufgrund der obigen Beobachtung so gewählt, dass <math>\alpha \leq 2/3</math>. Falls <math>\alpha</math> größer werden sollte, verdopple die Kapazität und kopiere das alte array in das neue Array (analog zum dynamischen Array)

In Python werden die Kapazitätsgrößen als Zweierpotenzen gewählt, also 4,8,16,32,..., so dass h % self.capacity nur die unteren Bits von h benutzt.

Anwendung von Hashing

• Hashtabelle, assoziatives Aray
• Sortieren in linearer Zeit (Übungsaufgabe 6.2)
• Suchen von Strings in Texten
• ...

Rabin Karp Algorithmus

In Textverarbeitungsanwendungen ist eine häufig benutzte Funktion die Search & Replace Funktionalität. Die Suche sollte in O(len(text)) möglich sein, aber ein naiver Algorithmus braucht O(len(text)*len(searchstring))

Naive Implementierung der Suche

 def search(text, s):
     M, N = len(text), len(s)
     for k in range(M-N):
         if s==text[k:k+N]
             return k
     return -1 #nicht gefunden

Idee des Rabin Karp Algorithmus

Statt Vergleichen s==text[k:k+N], die O(N) benötigen da N Vergleiche der Buchstaben durchgeführt werden müssen, Vergleiche die Hashs von Suchstring und dem zu untersuchenden Textabschnitt: hash(s) == hash(text[k:k+N]). Dabei muss natürlich hash(s) nur einmal berechnet werden, wohingegen hash(text[k:k+N]) immer wieder neu berechnet werden muss. Damit der Vergleich O(1) sein kann, ist es deswegen erforderlich, eine solche Hashfunktion zu haben, die nicht alle Zeichen (das wäre O(N) ) einlesen muss, sondern die vorhergehende Hashfunktion mit einbezieht.

Eine solche Hashfunktion heißt Running Hash und funktioniert analog zum Sliding Mean.

Die Running Hash Funktion berechnet in O(1) den hash von text[k+1:k+1+N] ausgehend vom hash für text[k:k+N].

Idee: Interpretiere den Text als Ziffern in einer base d Darstellung:

<math>h_k = \text{text}[k]\cdot d^{N-1} + \text{text}[k]\cdot d^{N-2} + \cdots + \text{text}[k+N-1]</math>

Für die Basis 10 (Dezimalsystem) ergibt sich also

<math>h_k = \text{text}[k]\cdot {10}^{N-1} + \text{text}[k]\cdot {10}^{N-2} + \cdots + \text{text}[k+N-1]</math> Daraus folgt <math>h_{k+1} = 10\cdot h_k - \text{text}[k]\cdot {10}^{N} + \text{text}[k+N]</math> Und die Komplexität ist O(1).

In der Realität wählt man dann d=32 und benutzt noch an einigen Stellen modulo Operationen, um die Zahlen nicht zu groß werden zu lassen.

Implementation

 def searchRabinKarp(text, s):
     ht, hs, dN = 0, 0, 1
     M, N = len(text), len(s)
     d, q = 32, <sehr große Primzahl>
     
     #Initialisierung      
     for k in range(N):
         ht = ht*d + ord(text[k]) % q
         #ord() gibt die ASCIInummer des übergebenen Zeichens zurück
         ds = hs*d + ord( s[k] )
         dN = (dN*a) % q
     #Die Variable sind jetzt wie folgt initialisiert:
     #ht = hash(text[0:N])
     #hs = hash(s)
     #dN = (d**N) % q
     
     #Hauptschleife
     k = 0 
     while k < M-N:
         if hs == ht and s==text[k:k+N]:
             return k
         ht = (d*ht - dN * ord(text[k]) + dN*q + ord(text[k+M]) ) % q
         k +=1
         return -1