|
|
| Line 1: |
Line 1: |
| == 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: <tt>a[key] = value</tt>
| |
|
| |
| Genauso wir die Zuweisung <tt>value=a[key]</tt> wie folgt umgesetzt
| |
| def __getitem__(self, key, value)
| |
|
| |
| Implementierung der <tt>__setitem__</tt> Funktionen in der <tt>HashTable</tt> 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 <tt>__getitem__</tt> 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 <tt>capcity</tt> immer als ''Primzahl'' gewählt, wobei sich aufeinanderfolgende Kapazitäten immer ungefähr verdoppeln:
| |
| 53, 97, 193, 398, 769, ...
| |
|
| |
| Das hat zur Folge, dass <tt>h % self.capacity</tt> ''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 <tt>array[index]</tt> 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 <tt>self.size < self.capacity</tt>. Dies galt für die vorige Hash Implementation nicht.
| |
|
| |
| === Vorgehen bei Kollisionen ===
| |
|
| |
| ==== Sequentielles Suchen ====
| |
| Probiere den nächsten Index: <tt>index = index+1 % capacity</tt>
| |
|
| |
| * 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 <tt>{'a':1, 'b':2, 'c':3}</tt> 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 <tt>HashNode</tt> und <tt>HashTable</tt> benötigt, es folgen die angepassten Implementationen von <tt>__setitem</tt> und <tt>__getitem__</tt>:
| |
|
| |
| 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 [http://svn.python.org/view/*checkout*/python/trunk/Objects/dictobject.c 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 <tt>keyError</tt> 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>
| |
|
| |
| {| border="1" cellspacing="0" cellpadding="5" align="center"
| |
| ! <math>\alpha</math>
| |
| ! 0.5
| |
| ! 0.9
| |
| |-
| |
| | erfolglos
| |
| | 2.0
| |
| | 10
| |
| |-
| |
| | erfolgreich
| |
| | 1.4
| |
| | 2.6
| |
| |}
| |
|
| |
| ===== Wahl der Kapazität =====
| |
| In Python wird <tt>capacity</tt> 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 <tt>h % self.capacity</tt> nur die unteren Bits von <tt>h</tt> 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 <tt>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: <tt>hash(s) == hash(text[k:k+N])</tt>. Dabei muss natürlich <tt>hash(s)</tt> nur einmal berechnet werden, wohingegen <tt>hash(text[k:k+N])</tt> 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 <tt>text[k+1:k+1+N]</tt> ausgehend vom hash für <tt>text[k:k+N]</tt>.
| |
|
| |
| 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
| |
