Hashing

Wir haben bereits die Datenstruktur Dictionary in Python kennen gelernt und diese auch schon häufig verwendet. Sturkturen, wie Dictonaries werden auch als Map bezeichnet, da man in ihnen Schlüssel auf Werte abbildet. Wir haben auch schon mögliche Implementierungen diskutiert. Eine effiziente Implementierung ist z.B. als AVL-Suchbaum möglich.

In der Praxis verwendet man für solche Maps aber in der Regel eine Implementierung, die auf Arrays basiert, die sogenannte Hash-Map. Auch in Python sind Dictonaries tatsächlich als Hash-Maps implementiert, welche intern ein Array verwendet.

Die Idee der Implementierung ist dabei sehr einfach. Man verwendet ein Array, welches Platz bietet, die Werte aufzunehmen. Das Array habe dabei die Größe \(n\). In der Regel erlaubt man aber sehr viel mehr als \(n\) Schlüssel und muss sich überlegen, wie man die Schlüssel auf den Wertebreich 1 bis \(n\), also die im Array verfügbaren Indizes abbilden kann.

Wie wir schon bei Dictonaries gesehen haben, verwendet man als Schlüssel auch gerne andere Werte als Zahlen, z.B. Strings oder sogar (fast) beliebige Python-Werte. Um also einen beliebigen Schlüssel auf einen Index im Array abzubilden, verwendet man eine Hash-Funktion

$$hash : KeySet \rightarrow {0, \ldots, n}$$

Dann kann man den Index, an dem ein Schlüssel in der HashMap ablegen möchte, einfach durch Anwendung der Hash-Funktion auf den Schlüssel ermitteln und hier den Wert ablegen oder auch nachschlagen.

Wir betrachten ein kleines Beispiel, bei dem wir eine Liste der Größe 5 und als Hashfunktion die folgende Python-Funktion verwenden (wir beschränken uns hier auf String-Schlüssel):

def hash_code(key) :
    code = 0
    for c in str :
        code = code ` ord(c)
    return code % 5

Wir addieren also alle ASCII-Werte und rechnen abschließend modulo 5, um einen passenden Index zu erhalten.

Dann können wir unser Liste wie folgt nutzen, um neue Einträge zur HashMap hinzu zu fügen:

Im letzten Schritt bekommen wir aber ein Problem. Der Schlüssel 'toll' wird auf denselben Index abgebildet, wir der Schlüssel 'hallo'. Es gibt eine sogenannte Kollision und wir können es ist unklar, wie wir beide Werte hier ablegen sollen. Als Lösung gibt es im Wesentlichen zwei Ansätze:

• man speichert in der Liste nicht nur einen Wert, sondern eine Liste von Werten
• man verwendet den nächsten freien Platz in der Liste

Wir verfolgen hier den ersten Ansatz. Der zweiten Ansatz soll als Übung realisiert werden.

Wenn man nun also anstelle der Werte eine Liste von möglichen Werten abspeichert, so ist es darüber hinaus notwendig, auch den wirklichen Schlüssel abzuspeichern, da wir Schlüssel mit demselben Hash-Wert nach dem Hashing ja nicht mehr unterscheiden können. Wir fügen also Listen von Tupeln ein und erhalten für obiges Beispiel:

Schlägt man nun den Schlüssel ’toll’ in der HashMap nach, so schaut man zunächst an dem Index, welcher sich durch Anwendung der Hash-Funktion ergibt (hier 3) und muss dann in der Liste an Index 3 noch den konkreten Schlüssel nachschlagen.

Bei den Listen, mit denen wir die Kollisionen auflösen, handelt es sich tatsächlich um Python-Listen und keine Arrays. Dass diese tatsächlich geeignet sind, werden wir in Abschnitt ~\ref{pythonlisten} verstehen. Es sind auch noch andere Strukturen (verkettete Listen oder Suchbäume möglich). Die Vor- und Nachteile werden wir noch diskutieren.

Die HashMap ist also dann besonders gut gefüllt, wenn es möglichst wenige Kollisionen gibt und entsprechend die Listen in der Hash-Liste möglichst kurz sind. Dies hängt aber insbesondere davon ab, wie gut die Hash-Funktion ist. Werden die gegebenen Schlüssel tatsächlich möglichst gleichverteilt auf alle verfügbaren Indizes abgebildet?

Die bisher gemachten Überlegungen können wir nun in einer Klasse HashMap recht einfach realisieren:

class HashMap :
   def __init__(self) :
        self.hash_list = []
        for i in range(5) : # default size of HashMap
            self.hash_list.append([])
        self.size = 0       # Entries within HashMap
        
    def insert(self,key,value) :
        i = 0
        l = self.hash_list[hash_code(key)]
        while i < len(l) and l[i][0] != key : # search key in list
            i = i ` 1
        if i == len(l) :          # new key
            l.append((key,value))
            self.size = self.size ` 1
            self.__resize()       # not defined yet      
        else :                    # key exists, update
            list[i] = (key,value)
        
    def lookup(self,key) :
        list = self.hash_list[self.__hashcode(key)]
        i = 0                # search key in list
        while i < len(list) and list[0][0] != key : 
            i = i ` 1
        if i == len(list) :     # key not found
            return None
        else :                  # key found
            return list[i][1]

Ein weiteres Problem der HashMap ist, dass immer mehr Kollisionen entstehen, je voller die HashMap wird. Ist die Anzahl der Einträge in der HashMap sehr viel größer als der verfügbare Platz, so bildet die HashMap letztlich nur noch einen konstanten Faktor im Vergleich zur Verwendung einer einfachen Liste von Schlüssel-Wert-Paaren. Deshalb ist es sinnvoll, die Hashliste zu vergrößern, wenn ein bestimmter Füllgrad erreicht ist. Dieser Schritt kostet natürlich zusätzliche Laufzeit. Wir werden diese im nächsten Abschnitt genauer analysieren, verfolgen hier aber zunächst die Idee, dass wir ab einem bestimmten Füllgrad die Listengröße verdoppeln. Da die Hash-Funktion als Bildbereich alle Indizes der Hash-Liste hat, müssen wir für alle Schlüssel-Werte-Paare in der HashMap eine Neuberechnung vornehmen und diese dann entsprechend übertragen.

Hierzu haben wir in der Definition von insert bereits einen Aufruf einer Methode __resize vorbereitet, welchen wir nun auch recht einfach realisieren können:

    def __resize(self) :
        old_space = len(self.hash_list)
        if self.size / old_space > 0.7 :   # maximal fill 70%
            old_hash_list = self.hash_list
            self.hash_list = []
            new_space = old_space * 2
            self.hash_list = []
            for i in range(new_space) :
                self.hash_list.append([])
            self.size = 0     # insert will correct size again
            for list in old_hash_list :
                for k,v in list :
                    self.insert(k,v)

Wir haben in der Implementierung Kollisionen mittels einer unsortierten Liste aufgelöst. Alternativen wären hier verkette Listen, sortierte Listen, so dass man effizienter mittels binärer Suche nachschlagen kann oder auch AVL-Bäume. In der Praxis hofft man eine gute Hashfunktion zu haben, so dass die Listen nicht besonders lang werden und die lineare Laufzeit über diesen Listen vernachlässigt werden kann.

Dass das Verdoppeln der Hash-Listen-Größe bei einem zu hohen Füllgrad sinnvoll ist, werden wir im nächsten Kapitel sehen, bei dem wir uns auch damit beschäftigen, wie der Schritt von Arrays zu den dynamsichern Listen effizient realisiert werden kann.