HashTable
Theorie-Wissen aus: Vorlesung Informatik - Semester 2
(Hoffentlich) unterhaltsam aufbereitet
Was ist dein Problem?
Bei einer HashTable geht es darum, ein Paar von Schlüssel und Wert so zu speichern, dass man danach nicht ewig wieder suchen muss (Hashing bezeichnet dabei den Vorgang, einen möglichst eindeutigen Zahl-Wert aus einem Schlüsselattribut zu erzeugen). Ein Vergleich zum Aktenschrank:
Angenommen wir haben 100 Aktenordner. Alle haben eine Nummer auf dem Rücken. Die Nummern gehen von 1 bis 1000. Die Sekretärin soll sich jetzt um die Organisation kümmern. Sie würde wohl die Ordner nach Nummer sortiert in ein Regal mit 100 Plätzen stellen (100% Auslastung). Sie fängt also an, Nummer 500 hat sie als erstes in der Hand. Den stellt sie in die Mitte des Schranks. Nach einer Weile geht dann das große Umräumen los, denn gemeinerweise haben viel mehr Ordner Nummern im Bereich <500 als >500. Nachdem unsere fiktive Sekretärin nun alle Ordner sortiert hat, kommt der Chef zur Tür rein. Er braucht sofort den Ordner mit Nummer 500. Nun, wo ist der hin?
Wenn unsere Sekretärin sich mit Informatik auskennt, wird sie Binäre Suche anwenden. Das heißt: Sie geht in die Mitte, guckt ob die Nummer des Ordners kleiner ist, als die, die sie sucht und geht dann entsprechend weiter nach links oder rechts. Im Schnitt braucht sie für 100 Ordner so etwa 6 Ordner, die sie angucken muss, bis sie den richtigen findet ( O(logn) ). Das ist schon relativ gut. Es dauert dem Chef natürlich aber viel zu lange. Außerdem ist das Einfügen eines neuen Ordners in so einen Schrank ziemlich aufwändig, denn da der Schrank keinen zusätzlichen Platz hat, muss der erst vom Schreiner vergrößert werden und dann müssen die Ordner alle beiseite geschoben werden um Platz für den neuen Ordner zu finden. Extrem unschön
Er hat die Idee:
Wir machen den Schrank so groß, dass jeder Ordner immer an der gleichen Stelle bleibt. Wir reservieren also für jeden Ordner einen Platz. Folglich machen wir den Schrank so groß, dass 1000 Ordner rein passen (Erinnerung: Die Ordner waren nummeriert von 1 bis 1000). Den Ordner mit der Nummer 500 würde die Sekretärin nun in die Mitte stellen und dort wird er auch bleiben. Man findet ihn also sofort, außerdem muss man nicht umräumen, wenn man neue Ordner hat, denn der Platz ist ja freigelassen worden.
Klar ist: Der Schrank wird bei 100 Ordner nur zu 10% voll sein.
Zusammenfassung:
- Wir machen einen sortierten, passenden Schrank, dann brauchen wir wenig Platz (Speicher) aber viel Zeit (CPU)
- Wir machen einen großen Schrank, in dem der Index des Ordners die Position direkt angibt, dann bauchen wir viel Platz (Speicher) und wenig Zeit (CPU). Gar nicht möglich, wenn der Index des Ordners beliebig groß ist.
Wie können wir beides mischen?
Um das Einfügen zu vereinfachen lassen wir das Sortieren weg.
Wir setzen die Ordner alle die Reihe nach in den Schrank. Einen neuen Ordner reinstellen ist also sehr schnell. Das suchen eines Ordners wird aber kriminell langsam, wir müssen nämlich im schlimmsten Fall alle angucken
Am besten wäre, wir könnten die Ordner unsortiert in den Schrank stellen und hätten trotzdem noch ne Idee, wo er ist. Wir brauchen also ein System im Chaos. Übrigens: Große Lager wie die bei Amazon funktionieren ähnlich (
siehe hier).
Und was macht jetzt Hashing?
Eine Hashfunktion bildet eine Menge (die Ordner) auf eine Nummer in einem Array (bzw Schrank) ab.
Beispiel:
l = Größe des Schrankes
x = Ordner-ID
h(x) = x mod l
Wir machen also unsren Schrank nur 100 groß, jagen die Nummer des Ordners durch diese Funktion und platzieren ihn an den Platz, den das Ergebnis angibt.
h(500) = 500 mod 100 = 0
h(101) = 101 mod 100 = 1
h(902) = 902 mod 100 = 2
Wir stellen also Ordner Nummer 500 an erster Stelle in den Schrank. Daneben steht der Ordner mit 101 und dann der Ordner mit 902. Das ist schonmal unsortiert. Gleichzeitig können wir aber mit Hilfe der Hashfunktion sofort den richtigen Platz finden durch eine einfache Modulo Rechnung.
Aber was ist das? Wohin mit Ordner 502?
h(502) = 502 mod 100 = 2
Dort ist aber schon der Ordner 902...
Diese sogenannten Kollisionen machen Hashing jetzt etwas komplexer. Es gibt einige Stellschrauben, mit denen wir die Wahrscheinlichkeit verringern können.
Zum einen sollten wir auf keinen Fall eine Auslastung von 100% zulassen. Der Schrank sollte also immer größer sein als nötig.
Zum andren ist unsre Hashfunktion sehr einfach. Durch geschicktere Hashfunktionen lässt sich auch einiges erreichen.
Am Ende bleibt das Problem, dass wir Kollisionen nicht absolut verhindern können.
Man könnte zum Beispiel den Schrank in die Tiefe ausbauen (Programmiertechnisch: Array von Listen). Ist der Platz besetzt, schieben wir den Ordner einfach nach hinten und stellen unsren davor. Suchen wir jetzt einen Ordner, müssen wir nur die Ordner angucken, die an dem Platz stehen. Das Problem ist, dass wir so wieder zusätzlichen Platz benötigen. Der Schrank ist eigentlich breit genug für alle Ordner, aber wir müssen ihn so auch bei Bedarf in die Tiefe vergrößern (von den Schreiner-technischen Problemen sehen wir dabei mal ab). Wir verlieren also Platz.
Wir rechnen lieber noch etwas (Sondieren), das ist billiger als schreinern.
Kollisionen und Sondieren
Nehmen wir an, wir haben einen Schrank mit 107 Plätzen. Zum einen ist da noch Luft für ein paar mehr Ordner, außerdem ist 107 eine
Primzahl und das ist wichtig fürs Sondieren. (Anm: Die folgende Sondierung benötigt keine Primzahl, aber viele der "besseren" Verfahren, z.B. quadratisches Sondieren).
Vor uns steht also der Schrank, wir rechnen für unsre Ordner-Nummer den Hashwert aus, aber da steht bereits ein anderer Ordner am passenden Platz. Wie kommen wir an einen anderen Platz? Der alternative Platz muss eindeutig sein, denn wir wollen ihn ja wieder finden.
Lineares Sondieren ist eine Möglichkeit. In diesem Fall versuchen wir einfach den Platz nebendran. Über unsre Hashfunktion bauen wir eine neue Funktion:
l = Größe des Schranks (107)
x = Ordner-Nummer
i = Versuch-Nummer
s(x,i)= ( h(x)+i ) mod l
Fein. Angenommen, der Schrank ist leer. Wir haben Ordner Nummer 902:
s(902,0) = ( h(902) + 0 ) mod 107 = 902 mod 107 = 46
Wir stellen den Ordner also an Platz 46. Dann haben wir Ordner Nummer 367
s(367,0) = ( h(367) + 0 ) mod 107 = 367 mod 107 = 46
Mist, der Platz ist voll. Also setzen wir den zweiten Parameter auf 1
s(367,1) = ( h(367) + 1 ) mod 107 = ( 46 + 1) mod 107 = 47
Heureka, der Platz ist frei. Wenn nicht, dann müssten wir den zweiten Parameter eben nochmal erhöhen. Klar ist, wenn der Schrank ziemlich voll ist, dann müssen wir unter Umständen ne ganze Weile rechnen. Es gibt also eine Art Grenzwert, wenn die Auslastung über diesen Grenzwert liegt, dann ist Hashing unrentabel, wir sollten dann den Schrank größer machen. Klar ist auch, wenn der Schrank voll ist, dann können wir rechnen solange wir wollen, dann passt kein Ordner mehr rein
Für das Sondieren gibt es nun wiederum verschiedene Möglichkeiten. Eine gute und einfache Möglichkeit ist das Quadratische Sondieren. Dabei wird mit großen Schritten durch die gesamte Tabelle gesprungen und somit entstehen keine "Hotspots" bei nahe beieinander liegenden Keys.
Wie finden wir nun unsren Ordner? Wir rechnen s(x,0) aus, mit x=Ordner Nummer. Ist der Platz nicht leer, aber es ist auch nicht der gesuchte Ordner, dann gucken wir bei s(x,1) usw.
"Ich war hier"
Angenommen, an der Position s(x,0) steht der Ordner 902 und ein zweiter Ordner mit Nummer 367 wurde an s(x,1) eingefügt (Achtung: s(x,1) = s(x+1,0) beim linearen Sondieren. Das folgende Problem meint aber den Fall, dass in s(x,1) eingefügt wird, der Ordner also eigentlich an die Stelle s(x,0) gehörte). Entfernen wir jetzt den Ordner 902 aus dem Schrank, dann gibt es ein Problemchen. Suchen wir jetzt nach Ordner 367, gucken wir bei s(x,0). Der Platz ist aber leer. Nach unsrem Such-Algorithmus sind wir nun fertig, der Ordner ist offenbar nicht im Schrank. Das stimmt natürlich nicht. Brechen wir nicht ab, falls wir einen leeren Platz finden, müssten wir ja den ganzen Schrank durchsuchen, um sicher zu gehen, dass nicht der Ordner sonstwo gelandet ist (nach vielfachem einfügen, löschen ist jede Positionierung denkbar).
Lösung: Immer wenn wir einen Ordner rausnehmen, kleben wir ein Papier an den Platz "Ordner entnommen". Der Platz ist nun nichtmehr leer und die Suche geht weiter bei s(x,1). Dort ist der gesuchte Ordner in unsrem Beispiel dann auch.
More Sourcecode please
Gucken wir mal uns ausschnittsweise den SourceCode an. Die Unit XVHashing beherbergt die Klasse HashTable.
Die Hashfunktion
1:
2:
3:
4:
| function THashTable.Hash ( x: integer ) : integer;
begin
Result:= x mod length
end; |
Lineares Sondieren
1:
2:
3:
4:
| function THashTable.Sondieren ( x: integer; run: integer ) : integer;
begin
Result:= Hash( x+run );
end; |
Um ein Paar aus Schlüssel und Wert einzufügen, berechnen wir zuerst den Hashwert s(key,0). Können wir dort nichts einfügen, bzw. updaten, dann sondieren wir weiter s(key,1)...
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
| function THashTable.Insert (Key: integer; Value: String): integer;
var run,h: integer; found: boolean;
begin
run:=0;
found:=false;
h:=privLookup(Key);
if h>-1 then Data[h].Value:=Value
else while (found=false)and(run>-1) do
begin
h:=Sondieren( Key , run );
if (Data[h].Status=C_Free) or (Data[h].Status=C_Deleted) then
begin
Data[h].Key:=Key;
Data[h].Value:=Value;
Data[h].Status:=C_Full;
found:=True;
end
else if (Data[h].Status=C_Full) and (Data[h].Key=Key) then
begin
Data[h].Value:=Value;
found:=True;
end;
run:=run+1;
if run=length then
run:=-1;
end;
Result:=run;
end; |
Das Suchen habe ich aufgeteilt, in der Funktion privateLookup geben wir den Platz aus, in dem der gesuchte Key liegt. Dies geben wir aber so nicht nach außen, interne Details gehen dem User garnichts an
Im "Array-Overflow"-Fall haben wir solange sondiert, bis wir ALLE Einträge angeguckt haben. Und trotzdem haben wir es nicht gefunden. Das ist natürlich ein total ungünstiger Weg rauszukriegen, dass ein Key nicht vorhanden ist. Die Tabelle sollte also nach Möglichkeit nicht ganz voll sein.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
| function THashTable.privLookup (Key: integer): integer;
var h,run,id: integer; found: boolean;
begin
run:=0;
found:=false;
id:=0;
while found=false do
begin
h:=Sondieren(Key,run);
if Data[h].Status=C_Free then
begin
found:=true;
id:=-1;
end;
if (Data[h].Status=C_Full)and(Data[h].Key=Key) then
begin
found:=true;
id:=h;
end;
if (run=length-1) and (found=false) then
begin
found:=true;
id:=-2;
end;
run:=run+1;
end;
Result:=id;
end; |
Beim Löschen suchen wir zuerst den Key und löschen diesen dann. Das Löschen geschieht einfach durch das Setzen des Status auf C_Deleted, dann wird er nichtmehr gefunden.
Delete
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
| function THashTable.Delete (Key: integer): boolean;
var h: integer;
begin
h:=privLookup(Key);
if (h=-1) or (h=-2) then
Result:=False
else
begin
Data[h].Status:=C_Deleted;
Data[h].Value:='*del*'+Data[h].Value; Result:=True;
end;
end; |
Noch ist es nicht möglich, die Größe der Tabelle zu verändern. Dies wird im nächsten Kapitel erläutert und macht den Sourcecode deutlich unübersichtlicher (Rekursion nötig).
