Hash Table (Datenstruktur)

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)