Hash Table (Datenstruktur)

Aus unkompliziert.eu
Wechseln zu:Navigation, Suche

Grundidee

  • Der Index, an dem die gesuchte Information steht, wird berechnet
Index Schlüssel Info
Name Tel.
0 Baum 09....
1
2 unkompliziert 0 32 222133190
3
4 Wasser 0...
5
6 Bisa 09...
7 Holla 09...
8
9

Aktueller Füllgrad: 60%

Maximaler Füllgrad 60%

Größe eines Hash Table: Anzahl der zu speichernden Elemente

Arbeitsweise beim Einfügen von Daten

1. Berechne den Hashwert der gewünschten Information

  • z.B. Hashwert von "unkompliziert" = 37852

2. Index = Hashwert modulo GrößeHashTable

  • im Beispiel: Index = 37852 % 10 = 2
  • Holla: 16517
  • Bisa: 12516
  • Baum: 19220
  • Olga: 13666 => Index 6
  • Wasser 2504

3. Prüfe, ob die berechnete Position frei ist

  • Nein: Erhöhe Index um 1
  Index = Größe vom Hash Table => Index = 0
  • Ja: Einfügen an die berechnete Stelle

Kenngrößen einer Hash-Table

  • Aktueller Füllgrad
  aktFüllgrad = (Anzahl der Einträge) / (Größe der HT) * 100 (in Prozent)
  • Maximaler Füllgrad
  Beim Anlegen des HT wird ein maximaler Füllgrad mit angegeben (ca. 60-70%)
  • Grundsatz
  Je niedriger der aktuelle Füllgrad ist, desto schneller arbeitet der Hashtable, weil es weniger Kollisionen gibt.
  • Kollission
  Der Eintrag steht nicht an der berechneten Position
Index Schlüssel Info
Name Tel.
0
1
2
3
4
5
6
7
8
9
10
11
12 Wasser
13
14

Wasser: 2504%14 = 12

Beim Erreichen des maximalen Füllgrades wird ein HT erweitert, d.h. es wird ein Resize durchgeführt.

z.B. in DB-Systemen

  create table ...
  resize 10%
  resize 100MB
  ...

Auswirkungen eines Resize

Alle im alten HT vorhandenen Einträge müssen neu berechnet werden.

  • Leistungseinbruch des Servers beim Resize
  • HT ist während des Resize nicht nutzbar

Vorteile HT

  • Sehr schnell, weil Index berechnet wird.

Nachteile HT

  • Leistungseinbrüche möglich (Resize)
  • Sehr hoher Speicherbedarf
  • Keine Suche möglich, der exakte Schlüssel muss bekannt sein

Einsatzgebiet

In Datenbanken zur Verwaltung der Schlüssel (Primary key und foreign key, oder Indizes)