Hashing - Gestreute Speicherung

1. Einführung

Vom Hashing spricht man, wenn Daten in einem Speicherbereich mit direktem Zugriff (der Hash-Tabelle) gespeichert werden und auf jedes gespeicherte Datenelement direkt zugegriffen wird.
Dieser direkte Zugriff ist nur über einen Index möglich. Doch man verwaltet die Indizes nicht, wie üblich, in einer eigenen Tabelle, sondern errechnet den Index eines Datensatzes direkt aus seinem Schlüssel.

2. Die Hash-Tabelle

Die Hash-Tabelle ist jener Speicherbereich, über den die Datensätze verteilt werden sollen. Dabei stellt sich die Frage, wie groß die Tabelle denn sein soll.

• Ist sie zu klein, so ist sie zu hoch ausgelastet und es kommt zu vielen Kollisionen (Begriff Kollision: siehe weiter unten).
• Ist sie zu groß, so wird Speicherplatz verschwendet.

In diesem Zusammenhang ist der Begriff des Belegungsfaktors zu erwähnen:
Belegungsfaktor = Anzahl der Datensätze / Anzahl der Speicherplätze
Der Belegungsfaktor sollte zwischen 0,5 und 0,8 liegen.

3. Die Hash-Funktion

Die Hash-Funktion ist eine mathematische Funktion, die aus dem Schlüssel eines Datensatzes einen Index für die Hash-Tabelle errechnet.
Diese Funktion soll so gewählt werden, daß

• die Daten so abgebildet werden, daß der Grenzwertindex nicht überschritten wird,
• die Daten möglichst gleich über die Hash-Tabelle verteilt sind und
• es zu möglichst wenigen Kollisionen kommt.

3. 1. Geeignete Hash-Funktionen für Zahlen

Wenn der Schlüssel eines Datensatzes eine Zahl ist, so wird als Hash-Funktion meist das Divisionsrestverfahren bzw. eine etwas modifizierte Variante davon angewendet:

H(K) = K mod M
H(K) ist die Hash-Funktion, K der Schlüsselwert und M die Größe des Arrays.

Um die Kollisionsbearbeitung (siehe weiter unten) zu erleichtern, sollte für M nach Möglichkeit eine Primzahl gewählt werden.

3. 2. Geeignete Hash-Funktionen für Zeichenketten

Die naheliegendste Lösung für Zeichenketten ist wohl, die Quersumme über die ASCII-Codes der einzelnen Zeichen zu bilden und auf das Ergebnis das Divisionsrestverfahren anzuwenden.
Weiters könnte man die ganze Zeichenkette als Zahl interpretieren und auf diese Zahl wiederum das Divisionsrestverfahren anwenden. Der Nachteil dabei ist allerdings, daß dabei relativ hohe Zahlen entstehen (z. B.: KARLI = 0x4B41524C49).
Um das zu verhindern, sollte man nach jedem Buchstaben die Modulu-Operation anwenden:

A = 65, I = 73, K = 75, L = 76, R = 82
Größe der Hash-Tabelle = 499

K: 75 mod 499 = 75
A: (75 * 256 + 65) mod 499 = 303
R: (303 * 256 + 82) mod 499 = 305
L: (305 * 256 + 76) mod 499 = 312
I: (312 * 256 + 73) mod 499 = 105

Der Datensatz mit dem Schlüsselwert 'KARLI' wird somit in der Hash-Tabelle am Speicherplatz 105 gespeichert.

Beispiel für Implementierung:

unsigned int hash (char *key, unsigned int m)

Hinweis: 'key' ist der Schlüsselbegriff, 'm' die Größe der Hash-Tabelle.

4. Kollisionsverfahren

Beispiel:
Schlüsselwerte sind Ganzzahlen, die Hash-Tabelle umfaßt 499 Speicherplätze.
Es soll das Divisionsrestverfahren angewendet werden.
Zu speichernde Werte: 3598, 6093.
3598 mod 499 = 105
6093 mod 499 = 105

Der Datensatz 3598 kann zwar am Speicherplatz 105 abgelegt werden, beim Speichern des Satzes 6093 ergibt sich allerdings das Problem, daß der errechnete Speicherplatz nicht mehr frei ist.
Es ist ein Kollisionsverfahren anzuwenden. Das ist eine Methode, um Schlüssel mit gleichem Ergebnis der Hash-Funktion an anderen Stellen abzulegen und wieder zu finden.

4. 1. Interne Kollisionsauflösung (Lineares Austesten)

Für das Element wird ein Platz innerhalb der Tabelle gesucht, z. B. wird der nächste bzw. übernächste Platz genommen. Der Nachteil dabei ist die Clusterbildung.
Die Tabelle enthält neben dem Datensatz selbst auch die Anzahl der Datensätze, deren berechneter Hashcode dem tatsächlichen Index an dieser Position entspricht (z. B. an Position 4 wird die Anzahl der Sätze gespeichert, für die als Hashcode 4 errechnet wurde).
Man benötigt außerdem einen speziellen Wert, der anzeigt, daü eine Position in der Hash-Tabelle 'frei' ist, z. B. bei Strings einen Leerstring oder -1 bei Zahlen (Voraussetzung ist natürlich, daß diese Werte nicht als Schlüssel auftreten können).
Der Vorteil gegenüber dem externen Verfahren ist die schnelle Positionierung. Allerdings wird die Kapazität der Hash-Tabelle bei geringer Auslastung schlecht genutzt.
Durch oftmaliges Löschen und Einfügen von Datensätzen kann sich beim internen Verfahren die Anzahl der Zugriffe stark erhöhen.

Beispiel:
Schlüsselwerte sind Zeichenketten.
H('Carmen') = 2, H('Renate') = 6, H('Tina') = 4, H('Veronika') = 2
Kollisionsverfahren: Neuer Hashcode = Alter Hashcode + 3
Wenn Plätze nicht belegt sind, werden die Personen-ID und der berechnete Index auf -1 gesetzt.

Suche nach Datensatz 'Veronika':

• Hashcode errechnen (im Beispiel: 2)
• Vergleiche Suchschlüssel mit gespeicherter Datensatz-ID auf Position 2 und stelle fest, daü 'Veronika' <> 'Carmen'
• Gehe 3 Positionen weiter
• Erneuter Vergleich mit Datensatz-ID auf Position 5, Suche erfolgreich

Beim Löschen des Datensatzes 'Veronika' ist zu berücksichtigen, daß die Anzahl der Elemente mit Hashcode 2 (nicht 5) um 1 vermindert werden muß (im Beispiel: Anzahl bei 'Carmen' auf 1 setzen).

Die durchschnittliche Anzahl der Zugriffe beim Suchen nach einem Datensatz, der tatsächlich in der Tabelle existiert, berechnet sich nach folgender Formel:
0,5 + 1 / (2 * (1 - Auslastung))

Beim erfolglosen Suchen:
0,5 + 1 / (2 * (1 - Auslastung) hoch 2)

Beispiele:

4. 2. Externe Kollisionsauflösung

Anstelle der Daten enthält die Hash-Tabelle nur Zeiger auf die eigentlichen Daten. Bei einer Kollision wird eine verkettete Liste aufgebaut.
Vorteile gegenüber dem internen Verfahren:

• Es können auch mehr Sätze gespeichert werden, als eigentlich in der Hash-Tabelle Platz hätten.
• Der Speicherbereich ist nicht fix, daher wird auch bei geringer Auslastung kein Speicherplatz verschwendet.
• Beim Löschen und Einfügen werden einfache Listenoperationen getätigt.

Nachteile gegenüber dem internen Verfahren:

• Der Vorteil des Hashings, die direkte Positionierung, geht teilweise verloren (weil man bei Kollisionen die Liste sequentiell durchlesen muß).
• Bei hoher Auslastung entstehen lange Listen.

Beispiel: Angabe wie oben

5. Doppeltes Hashing

Das doppelte Hashing verwendet die Methode der internen Kollisionsauflösung mit dem Ziel, Clusterbildung zu vermeiden. Das wird erreicht, indem nicht, so wie beim linearen Austesten, bei einer Kollision immer ein konstanter Betrag addiert wird, sondern ein vom Schlüssel abhängiger Wert.

Beispiel:
H2(K) = 1 + (K / M) mod (M - 1)
K ist der Schlüsselwert, M die Größe der Hash-Tabelle.
Bei der Division (K / M) handelt es sich um eine Ganzzahldivision.

Beispiel:
Die Hash-Tabelle bietet Platz für 11 Datensätze.
Schlüsselwerte sind Ganzzahlen ('Personen-ID').
Wenn Plätze nicht belegt sind, werden die Personen-ID und der berechnete Index auf -1 gesetzt.
1. Hash-Funktion: H(K) = K mod M
2. Hash-Funktion: H2(K) = 1 + (K / M) mod (M - 1)

• Einfügen:
  37, Huber (Hashcode 4)
  25, Meier (3)
  20, Schmidt (9)
  54, Gruber (10)
  42, Stangl (9): H2(42) = 4

• Einfügen:
  11, Böck (Hashcode 0)
  15, Richter (4): H2(15) = 2
  31, Wagner (9): H2(31) = 3
  4, Steiner (4): H2(4) = 1

• Löschen:
  15, Richter (Hashcode 4)
• Einfügen:
  16, Bauer (5): H2(16) = 2
• Löschen:
  42, Stangl (9)

Die durchschnittliche Anzahl der Zugriffe beim Suchen nach einem Datensatz, der tatsächlich in der Tabelle existiert, berechnet sich bei diesem Verfahren nach folgender Formel:
-ln (1 - Auslastung) / Auslastung

Beim erfolglosen Suchen:
1 / (1 - Auslastung)

Beispiele: