3.7 Hashtabellen

Lassen Sie uns eine Datenstruktur entwerfen für die Schlüsselmenge aller Wörter, die aus zwei kleinen Buchstaben bestehen, also "br", "gx", "az" und so weiter. Wie üblich wollen wir die Operationen contains, insert, delete unterstützen. Hier ist eine einfache und extrem effiziente Lösung: ich interpretiere jeden Buchstaben als Zahl, also $a\equiv 0$, $b\equiv 1$ und so weiter, und das Wort $(a_1{a}_2)$ als zweistellige Zahl in Basis 26, also $$(a_1{a}_2)\equiv 26a_1+a_2$$ Jedes Wort der Länge zwei entspricht also einer Zahl in der Menge $\{0,1,\dots ,{26}^2-1\}$. Wir legen ein Array der Größe ${26}^2=676$ an und speichern einfach Boolesche Werte. Hier sehen Sie meinen Python-Code:

# c: a character
# maps 'a' to 0, 'b' to 1 and so on
def getCodeChar(c):
    return (ord(c) - ord('a'))

# tlw: a two-letter word
def getCode(tlw):
    return 26*getCodeChar(tlw[0]) +getCodeChar(tlw[1])

def makeTable():
    return [False] * (26*26)

def insert(word, table):
    table[getCode(word)] = True

def delete(word, table):
    table[getCode(word)] = False

def contains(word, table):
    return table[getCode(word)]

Was Sie hier sehen, nennt sich direkte Adressierung. Wir können unseren Schlüssel direkt in eine Array-Adresse umrechnen. Dies geht, weil

1. Das Universum aller theoretisch möglichen Schlüssel sehr klein ist (hier: 676)
2. wir seine Struktur sehr gut verstehen

und somit gut aus dem Schlüssel eine Zahl berechnen können.

Als zweites Beispiel nehmen wir die Anzahl der Keywords aus Java. Eine (hoffentlich) vollständige Liste finden Sie in javaKeywords.py. Extrem schneller Zugriff auf Keywords ist wichtig für den Compilerbau. Können wir obigen Trick wiederholen? Naja, das längste Keyword ist

Es hat 12 Buchstaben. Wieviele Wörter mit 12 Buchstaben gibt es, wenn wir nur Kleinbuchstaben berücksichtigen? Ganz klar: ${26}^{12}=95.428.956.661.682.176$. Das ist zuviel. Wir können kein Array dieser Größe erstellen. Dennoch: wir können ein beliebiges Wort in eine Zahl umrechnen indem wir es als Zahl in Basis 26 betrachten:

def stringToInteger(word):
    result = 0
    for c in word:
        result *= 26
        result += getCodeChar(c)
    return result

Das gibt uns zum Beispiel stringToInteger("synchronized") = 69525273910093823. Hier ist ein Trick, wie wir diese recht große Zahl herunterbrechen auf eine kleinere, die wir dann als Index in einem Array verwenden können. Wir nehmen die (riesige) Zahl modulo einer (kleineren) anderen:

stringToInteger("synchronized") % 29
10
stringToInteger("public") % 29
26
stringToInteger("class") % 29
3

Schaut gut aus. Wir brauchen also nur ein Array der Größe $30$, weil unsere Indices Werte in $0,\dots ,29$ annehmen. Nur gibt es ein kleines Problem...

stringToInteger("if") % 29
10

Die Wörter if und synchronized bekommen beide den Index 10 zugewiesen und streiten sich nun um die Speicherzelle in unserem Array. Es kann ja auch gar nicht gutgehen: es gibt 50 Keywords in Java, also braucht unser Array ja mindestens 50 Zellen. Ich habe es ausprobiert, und mit Modulus 332 statt 29 funktioniert es. Also:

def javaKeywordToIndex(word):
    return stringToInteger(word) % 332

funktioniert. Schön, allerdings ist dies eine recht spezielle Anwendung. Denn erstens ist hier die Schlüsselmenge extrem klein, zweitens kennen wir sie im Voraus. Dennoch praxisrelevant, denn für einen Compiler (oder Interpreter) brauchen wir so etwas.

Universelles Hashing

Beim universellen Hashing haben wir ein riesigen Universum $$ von Schlüsseln und wollen eine "vernünftig" große Folge von find, insert, delete-Operationen effizient bearbeiten. Wir wissen nichts über die Art und Weise und Reihenfolge dieser Operationen, insbesondere wissen wir nichts über die Schlüssel, denen wir begegnen werden, außer, dass es maximal $$ viele sein werden. Wir haben also nicht wie beim Java-Keyword-Hashing im Voraus eine moderat große Liste der möglichen Schlüssel gegeben. Dennoch wollen wir eine Datenstruktur, die für alle Input-Reihenfolgen gutes Verhalten zeigt. Das geht nur mit Randomisierung.

Als Vereinfachung stellen wir uns vor, dass $$ ist, dass also jeder Schlüssel eine (womöglich sehr große) Zahl ist. Die Idee ist, dass wir ein Array array[0...m-1] der Größe $$ anlegen. Da $$ sehr groß ist, array aber in unseren Speicher passen muss, gilt im allgemeinen $$. Wir brauchen eine Funktion $$. Sei $$ die uns unbekannte Menge aller Schlüssel, die in unserer Hashtabelle gespeichert werden sollen und $$. Idealerweise ist $$ injektiv auf $$, also $$ So ein $$ nennen wir eine perfekte Hashfunktion. Für die Keywords in Java haben wir so eine perfekte Funktion gefunden. Im Allgemeinen kennen wir $$ nicht im Voraus, daher können wir nicht auf ein perfektes $$ hoffen. Stattdessen, mit Randomisierung im Hinterkopf, hoffen wir, das $$ für jedes $$ klein ist. Das sich also jedes $$ im Mittelwert nur mit wenigen anderen $$ seine Zelle teilen muss. Erinnern Sie sich an die Eigenschaft der randomisierten Treaps: die Zugriffszeit auf ein Element $$ ist dort proportional zu seiner Tiefe $$; die Tiefe selbst ist jedoch im Erwartungswert klein.

Wie sollen wir $$ wählen? Als erstes suchen wir eine Primzahl $$, die ein bisschen größer als $$ ist und schreiben $$; dann wählen wir $$ und definieren $$ Erkennen Sie, dass das einer Geradengleichung mit Steigung $$ ähnelt? Der Unterschied ist, dass wir als Eingabe nur ganze Zahlen erlauben (oder noch strenger: nur aus $$) und das Ergebnis modulo $$ nehmen. Dennoch schaut auch der Plot von $$ ein wenig wie eine sich herumwindende Gerade aus. Hier zeigen wir einen Plot der Funktion $$ für $$ für verschiedene Werte von $$ und $$. Die beiden roten Punkte sind $$ und $$.

$$

$$

$$

$$

$$

$$

$$

$$

$$

$$

Achten Sie in den Beispiel auf $$ und $$, den $$-Koordinaten der roten Punkte. Die scheinen ziemlich zufällig hin und her zu springen. Und in der Tat:

Hashtabelle als randomisierte Datenstruktur

Sei nun $$ die Anzahl der Schlüssel, die wir in unserer Anwendung zu sehen erwarten; dies ist zum Beispiel höchstens die Anzahl der delete, insert, find-Operationen, die unsere Anwendung ausführen muss. Wir legen ein Array der Länge $$ an und speichern den Schlüssel $$ an der Stelle $$. Sie haben richtig gelesen: in der Berechnung von $$ rechnen wir $$; danach rechnen wir $$. Unsere Gesamt-Hashfunktion ist also $$

Kollisionen. Es kann vorkommen, dass $$ gilt, dass also zwei Schlüssel sich die gleiche Zelle im Array teilen müssen; daher speichern wir in jeder Zelle den Pointer auf eine verkettete Liste; bei insert hängen wir den neuen Schlüssel einfach an die Liste; bei find und delete müssen wir die gesamte Liste durchgehen. Die Laufzeit der Operationen find x und delete x sind also proportional zu der Anzahl der Elemente, die in der Zelle $$ liegen. Da wir es mit einer randomisierte Datenstruktur zu tun haben, können wir nur Erwartungswerte angeben. Sei nun $$. Wir untersuchen, mit welcher Wahrscheinlich $$ und $$ in der selben Zelle landen. Wir fragen uns nun: von allen $$ möglichen Werten $$, für wieviele gilt $$? Dies gilt, falls die Differenz $$ modulo $$ einen der Werte $$ annimt, also eine der folgenden Gleichungen erfüllt ist:

$$ wobei $$ gelten muss, also $$. Wenn also eine von $$ Gleichungen gilt. Jede Gleichung der Form $$ hat genau $$ Lösungen modulo $$: wähle $$ frei und setze $$. Es gibt also insgesamt $$ Paare $$, die eine der obigen Gleichungen lösen; somit gibt es $$ Paare $$, für die $$ gilt. Die Wahrscheinlichkeit, dass $$ bei zufällig gewähltem $$ und $$ so ein Paar ergibt, ist $$

Die Anzahl der Schlüssel, die in der gleichen Zelle landen wie $$ ist also im Erwartungswert

$$ Erinnerin Sie sich, dass $$ eine sehr große Zahl ist, während $$ "realistisch" große Zahlen sind. Wir können uns also erlauben, den obigen etwas komplizierten Ausdruck mit zu vereinfachen und die erwartete Zellenbelegung mit $$ abzuschätzen. Dies hat eine sehr intuitive Interpretation: die Zelle von $$ hat ja auf jeden Fall schon einen Bewohner, nämlich $$ selbst; daher die $$ im Ausdruck; jeder weitere Schlüssel, den wir in unserer Tabelle speichern, landet nur mit Wahrscheinlichkeit $$ in der gleichen Zelle.

Die Laufzeiten für insert, find, delete sind also proportional zur Zellenbelegung von $$, also $$.

Bit-Komplexität

Wir haben einige Sachen unter den Teppich gekehrt. Laut unsere Annahme kommen die Schlüssel aus einem Universum $$ der Größe $$; wir müssen also die Primzahl $$ größer als $$ wählen, um einen Schlüssel $$ überhaupt als Zahl in $$ darstellen zu können. Die Bit-Länge der Zahl $$ ist also mindestens die von $$, also $$ Beachten Sie auch, dass die Bit-Länge $$ in die Laufzeitkomplexität miteinfließt: um $$ auszurechnen, müssen wir schließlich $$-stellige Zahlen multiplizieren, addieren, modulo $$ nehmen. Auch wenn wir Algorithmen für Multiplikation erst in Algorithmen und Komplexität behandeln werden, so ist doch einigermaßen klar, dass die Laufzeit für Addition und Multiplikation mindestens proportional zur Anzahl $$ der Bits ist, wenn nicht noch höher. Unsere (erwartete) Laufzeit von insert, find, delete ist also $$ (wenn wir annehmen, dass wir alle arithmetische Operationen in $$ ausgeführen können; dies ist nicht der Fall, aber die Wirklichkeit ist nicht weit davon entfernt).

Wie groß ist $$? Wie groß müssen wir unsere Primzahl wählen? Mindestens $$, der Anzahl theoretisch möglicher vorkommender Schlüssel. Wenn unser Hash also zum Beispiel Tweets speichern soll, die aus bis zu 280 Zeichen bestehen, dann gibt es mindestens $$ mögliche Tweets, und hierbei tun wir so, als seien nur Groß- und Kleinbuchstaben erlaubt; in Wirklichkeit gibt es viel mehr erlaubte Zeichen (inklusive nicht-lateinischer Schrifzeichen wie zum Beispiel chinesische, die laut developer.twitter.com als zwei Zeichen zählen); aber immerhin, die Bitlänge von $$ ist mindestens $$ Ihre Primzahl $$ würde also mindestens $$ Bits benötigen; in einem 64-Bit-Rechner könnten Sie das gar nicht als int speichern, sondern müssten beispielsweise die Java-Klasse BigInteger verwenden. Wäre dies schlimm? Naja, es ist nicht so verwunderlich, dass die Laufzeit von $$ proportional zur Bit-Länge von $$ ist, also wäre das schon zu ertragen.

Problematischer wird es, wenn wir keine scharfe Obergrenze für unsere Schlüssel festlegen wollen. Wenn wir beispielsweise Emails oder gar Dateien in einer Hash-Tabelle speichern wollen, dann sollten wir vorsichtig sein mit Obergrenzen. Nehmen wir als Gedankenexperiment mal 1MB als Obergrenze, also 8 Megabit. Dann wäre $$, unser $$ müsste also selbst $$ Bits, also 1MB haben. Das hieße, bei jedem Aufruf von $$ müssen Sie 8-millionen-stellige Zahlen multiplizieren. Auch wenn fast alle Dateien / Emails, die sie in Ihrer Hash-Tabelle speichern wollen, viel kleiner sind. Die Laufzeit von der Hashfunktion $$ ist also nicht proportional zur Größe des Schlüssels $$, sondern proportional zur maximalen theoretisch erlaubten Größe.

Bessere Wahl der Primzahl $$

Wir hätten gerne eine Hashfunktion, deren Laufzeit proportional zur Bit-Länge von $$ ist. Im Folgenden sie wiederum $$ die theoretische Obergrenze der Bit-Länge unserer Schlüssel (und somit $$), also z.B. $$ und $$ die Menge der tatsächlich vorkommenden Schlüssel. Ein Schlüssel ist uns gegeben als endlicher String von Nullen und Einsen, also ein Element in $$. Wir können jeden solchen String als natürliche Zahl codieren, in dem wir eine 1 voranstellen und das Ergebnis als Binärzahl interpretieren: der String $$ wird dann zu $$, also 9. Wir müssen eine 1 voranstellen, um führende Nullen zu vermeiden und zum Beispiel die Strings $$ und $$ zu unterscheiden.

Die Idee ist, dass wir $$ viel kleiner als $$ wählen und bei gegebenem Schlüssel $$ zuerst einmal den Pseudo-Schlüssel $$ berechnen, wobei $$ im obigen Sinne als Binärzahl zu interpretieren ist. Wir setzen dann $$, also wie zuvor, nur dass wir jedes Mal den Schlüssel $$ durch seinen Pseudo-Schlüssel $$ ersetzen. Der Rechenaufwand ist nun proportional zur "echten" Bitlänge von $$ und $$, nicht zur theoretischen Obergrenze. Die Gefahr ist, dass nun im Worst Case alle Schlüssel größer sind als $$ und per $$ auf den gleichen Pseudo-Schlüssel abgebildet werden; dann landen ungeachtet der Werte von $$ alle Schlüssel in der gleichen Zelle landen. Das wäre schlecht. Wir hätten gerne, dass $$ injektiv ist, dass also keine zwei Schlüssel den gleichen Pseudo-Schlüssel bekommen; das geht im Allgemeinen natürlich nicht, da $$ viel größer ist als $$; wir wollen $$ ja klein wählen können. Ein bescheideneres Ziel ist es, dass $$ injektiv auf der tatsächlichen Schlüsselmenge $$ ist, also: $$ oder äquivalent: $$ Wir kennen $$ nicht im Voraus, also müssen wir uns abermals mit Zufall behelfen und mit den Primzahlen beschäftigen. Jede der Zahlen $$ liegt im Bereich $$. Wenn wir für eine Zahl $$ ihre Primzahlzerlegung hinschreiben, also $$ also zum Beispiel $$, dann sehen wir, dass $$ ist, weil jede Primzahl mindestens 2 ist; $$ hat also weniger als $$ viele verschiedene Primfaktoren; da $$ folgern wir

Wir wählen nun die Primzahl $$ zufällig aus $$ und hoffen, dass der Pseudoschlüssel $$ mit wenigen anderen Schlüsseln "kollidiert". Was ist die Wahrscheinlichkeit, dass ein anderer Schlüssel $$ den gleichen Pseudo-Schlüssel bekommt, also dass $$? Wir schreiben $$ Dann gilt für einen festen Schlüssel $$: $$ weil ja die Anzahl der verschiedenene Primfaktoren von $$ höchstens $$ ist. Die Anzahl der Schlüssel $$, die den gleichen Pseudoschlüssel bekommen wie $$, ist somit im Erwartungswert höchstens $$ Wir setzen $$. Der Wikiepdia: Primzahlsatz besagt, dass die Anzahl der Primzahlen in $$ ungefähr $$ ist. Also gilt $$ In Worten: im Erwartungswert teilt sich $$ seinen Pseudo-Schlüssel mit äußerst wenig Schlüsseln.

Zusammenfassend sehen wir: wenn unsere Hash-Tabelle aus $$ Zellen besteht, dann speichern wir in der Zelle $$ im Erwartungswert höchstens $$ Pseudo-Schlüssel. Hinter jedem Pseudo-Schlüssel stehen (im Erwartungswert über die Wahl der Zahl $$) höchstens $$ viele Schlüssel.

Die Bit-Größe der Zahl $$ ist nun höchstens $$. Vergleichen Sie das zu unserer vorherigen Wahl $$, was eine Bitgröße von circa $$ zur Folge hat. In unserem Email/Dateien-Beispiel gilt $$, und somit haben wir nun die Bitgröße der involvierten Zahlen von 8 Millionen auf $$ reduziert.