Autor Beitrag
Xion
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
EE-Maler
Beiträge: 1952
Erhaltene Danke: 128

Windows XP
Delphi (2005, SmartInspect), SQL, Lua, Java (Eclipse), C++ (Visual Studio 2010, Qt Creator), Python (Blender), Prolog (SWIProlog), Haskell (ghci)
BeitragVerfasst: Do 25.11.10 20:08 
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 :D

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.


ausblenden Die Hashfunktion
1:
2:
3:
4:
function THashTable.Hash ( x: integer ) : integer;
begin
  Result:= x mod length
end;


ausblenden 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)...
ausblenden volle Höhe Insert
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 //falls bereits vorhanden, entsprechenden Wert updaten (bugfix 15.05.2012)
    Data[h].Value:=Value
  else  //solange sondieren, bis wir einen leeren Platz gefunden haben//solange sondieren, bis wir einen leeren Platz gefunden haben
  while (found=false)and(run>-1do
    begin
      h:=Sondieren( Key , run );

        //leere Zelle füllen
        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

        //update
        else if (Data[h].Status=C_Full) and (Data[h].Key=Key) then
          begin
            Data[h].Value:=Value;
            found:=True;
          end;



      run:=run+1;

      //hier müssen wir abbrechen, damit wir bei vollem Stack keine Endlosschleife produzieren.
      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.
ausblenden volle Höhe Lookup
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);

      //der entsprechende Platz ist leer. Der gesuchte Key ist nicht vorhanden
      if Data[h].Status=C_Free then
        begin
          found:=true;
          id:=-1;
        end;

      //gefunden
      if (Data[h].Status=C_Full)and(Data[h].Key=Key) then
        begin
          found:=true;
          id:=h;
        end;

      //array overflow
      if (run=length-1and (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.
ausblenden 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=-1or (h=-2then
    Result:=False
  else
    begin
       Data[h].Status:=C_Deleted;
       Data[h].Value:='*del*'+Data[h].Value; //nur damit man im Print was sieht ;)
       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).
Einloggen, um Attachments anzusehen!
_________________
a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)


Zuletzt bearbeitet von Xion am So 10.02.13 14:26, insgesamt 8-mal bearbeitet
Xion Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
EE-Maler
Beiträge: 1952
Erhaltene Danke: 128

Windows XP
Delphi (2005, SmartInspect), SQL, Lua, Java (Eclipse), C++ (Visual Studio 2010, Qt Creator), Python (Blender), Prolog (SWIProlog), Haskell (ghci)
BeitragVerfasst: Do 25.11.10 20:18 
Hashing - make it dynamic
Noch dabei? Gut :mrgreen:

Zum Problem:
Wir haben einen Schrank. Der ist vollgestopft mit Ordnern und wir wollen ihn vergrößern.

keep it short and simple
Wir nehmen einen neuen Schrank, stellen alle Ordner in den Neuen (einfügen in die Hashtable nach den bekannten Regeln) und sind schon fertig. Das war ja einfach.

Wie aus der Praxis bekannt ist es allerdings schwierig, wenn man beide Schränke in den engen Raum quetschen will. Auch der Speicher unsres Rechners ist nicht unbegrenzt, besonders weil Hashing erst richtig effektiv bei großen Datenmengen ist (und noch effektiver wenn unser Schrank noch größer als die Daten sind). Würden wir unsren Schrank nach oben beschriebenen Verfahren vergrößern könnte unser Schrank nur etwa halb so groß sein, wie unser Raum...und das ist ja doof, wenn wir nur 66% unserer Fläche (oder unsres Speichers) verwenden können.

Hirn einschalten!
Ideal wäre doch, wenn wir einfach unsren Schrank vergrößern und dann systematisch die Ordner an die richtige Stelle rücken. Das klingt sehr kompliziert. Ganz einfach ist es auch nicht.

Das Problem ist natürlich, dass die Position aller Ordner von der Größe des Schrankes abhängt:

l = Größe des Schrankes
x = Ordner-ID
h(x) = x mod l

Wir müssen also ALLE Ordner geordnet auf den neuen Platz bewegen.

Let's go
Also lassen wir den Schreiner mal kommen. Der macht den Schrank größer. Damit ist das Hashing kaputt, wir finden garnix mehr. Deswegen kleben wir an alle Ordner einen Zettel ran mit der Aufschrift "Alt". Die so markierten Ordner stehen also falsch im Schrank. Gleichzeitig entfernen wir noch alle "gelöscht"-Zettel. Jetzt gehen wir her und nehmen den ersten Ordner raus. Wo ist seine richtige Stelle im neuen Schrank? Dort wo die Hashfunktion ihn hin schickt.

Was wir also eigentlich machen: Wir hashen die Ordner nicht in einen neuen Schrank, sondern in den gleichen.

Jetzt kann folgendes passieren:
- Der Platz ist leer
=> Wir platzieren den Ordner dort rein, entfernen den "Alt"-Aufkleber und suchen uns einen neuen "Alt"-Ordner.

- Der Platz ist voll (mit einem Ordner ohne "Alt"-Aufkleber)
=> Wir Sondieren

- Der Platz ist besetzt mit einem"alt"-Ordner
=> Wir nehmen den Ordner raus, stellen unsren rein (entfernen dabei unsren "Alt"-Aufkleber) und hashen danach den neuen Ordner.

Wenn wir dies so lange tun bis wir garkeine "Alt"-Ordner mehr haben, dann sind wir fertig. Faszinierend wie wir unser Chaos im Schrank (Nummern sind wild durcheinander) auch noch der letzten Ordnung entziehen (Hashfunktion stimmt nicht mehr) und trotzdem nach einer klaren Vorgehensweise am Ende wieder ein geordnetes Chaos bekommen ;)

klingt knifflig - ist auch so
Das ganze in Sourcecode zu wandeln ist aufgrund der Rekursion etwas kniffliger. Ok, im Endeffekt ist es halb so wild.

Vorbereiten und starten der Umorganisierung.
ausblenden Reorganize
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
procedure THashTable.Reorganize;
var a: integer;
begin
  for a:= 0 to High(Data) do
    begin
      //die Deleted-Werte sind ja hinfällig dadurch, dass die Hashfunktion sich geändert hat
      if Data[a].Status=C_Deleted then
        Data[a].Status:=C_Free;

      if Data[a].Status=C_Full then
        Data[a].Status:=C_Old;
    end;

  for a:= 0 to High(Data) do
    if Data[a].Status=C_Old then
      begin
        Data[a].Status:=C_Free; //herausnehmen
        Data[a].Value:='*l*'+Data[a].Value;  //wir fügen hier wieder was an, damit wir sehen, welche NICHT rekursiv geändert wurden
        Insert(Data[a].Key,Data[a].Value); //passend einfügen. intern Rekursion möglich
      end;

end;


Treffen wir beim Insert auf einen "Alt"-Eintrag, müssen wir diesen Ordner als nächstes verwenden. Dazu benötigen wir eine Erweiterung für die Insert-Funktion:

ausblenden Erweiterung Insert
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
        //reorganize -> rekursion
        else if (Data[h].Status=C_Old) then
          begin
            //Kopie erstellen (Ringtausch)
            backup:=Data[h];
            Data[h].Key:=Key;
            Data[h].Value:=Value;
            Data[h].Status:=C_Full;

            //Den soeben vom Platz verdrängten Eintrag einfügen
            Insert(backup.Key, '*r*'+backup.Value);   //wir fügen hier was, um rekursionen zu erkennen

            found:=True;
          end;


Haben wir große Datenmengen, kann durch die Rekursion ein Stack Overflow geschehen. In diesem Fall macht es Sinn, das ganze iterativ aufzubauen (also per Schleife).

Das Ergebnis sieht dann erstmal komisch aus.


ausblenden volle Höhe Hashtabelle
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:
Key | Value (+Anhängsel)
46 | *l*Birne *free*
23 | *l*Erdbeere *free*
25 | *l*Apfel *free*
127 | *r*Johannisbeere 
66 | *r*Dattel 
531 | *l*Rhabarber 
129 | *l*Kokosnuss 
145 | *l*Nektarine *free*
123 | *l*Ingwer *free*
55 | *l*Feige *free*
72 | *l*Cashew 
42 | *r*Holunder 
135 | *r*Limette 
199 | *r*Pflaume 
129 | *l*Kokosnuss *free*
46 | *l*Birne 
853 | *r*Trauben 
852 | *r*Stachelbeere 
140 | *l*Mandarine 
174 | *r*Orange 
234 | *l*Quitte 
145 | *l*Nektarine 
0 |  *free*
23 | *l*Erdbeere 
55 | *l*Feige 
25 | *l*Apfel 
87 | *r*Grapefruit 
0 |  *free*
0 |  *free*
0 |  *free*
123 | *l*Ingwer


Obwohl wir deutlich mehr Einträge haben, existieren nur 4 *free* Einträge...dabei sind nur 20 von 31 belegt? Dies liegt daran, dass wir jeweils nur den Status setzen, uns aber die Werte in Value egal sind. Diese werden ja beim Suchen nur gefunden, wenn sie als Status C_Full haben. In Wirklichkeit sind also alle Einträge leer, wo *free* im Namen auftaucht. (Ich lasse überalle das *free* angeben, wo der Status C_Free gesetzt ist. Betrachtet man nicht das Flag, so würde man jetzt eine List mit 4 leeren Einträgen kriegen, wobei einige Einträge doppelt wären).

Ok, damit wären wir soweit fertig. Einfach mal die Beispielprogramme durchgucken und etwas dran rumbasteln.

Ich hoffe der SourceCode ist bugfrei :) Pobody is Nerfect

[15.05.2012] Bugfix der Klasse XVHashing bzgl fehlerhafter Insert/Delete Kombination
Einloggen, um Attachments anzusehen!
_________________
a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)