Hashing

Question 1

Hashing:

Answer 1

Idee: Statt in einer Menge von Datensätzen durch
Schlusselvergleiche zu suchen, ermittle die Position eines Elements im Speicher (bzw. einem Array) durch eine arithmetische Berechnung.

Question 2

Hashing belegungsfaktor

Answer 2

Fur eine Hashtabelle der Größe m, die aktuell n Schlussel speichert, ist α =n/m der Belegungsfaktor der Tabelle

Question 3

Hashfunktion:

Answer 3

Wir wählen eine Hashfunktion h : K → {0, . . . , m − 1}, die

jedem Schlussel k ∈ K einen eindeutigen – aber i.A. nicht umgekehrt eindeutigen – Hashwert zuordnet.

Question 4

Hashing Laufzeit:

Answer 4

Vorteil: Laufzeit fur die Operationen Suchen, Einfügen und Entfernen liegt im Idealfall in Θ(1), wenn wir annehmen, dass h(s) in konstanter Zeit berechnet werden kann.

Einschränkung:
*Gilt h(k) = h(k’) fur k != k’ , d.h., zwei verschiedene Schlussel
haben den gleichen Hashwert, so wird dies Kollision genannt.

*Θ(1) gilt nur unter der Annahme, dass die Anzahl der
Kollisionen vernachlässigbar klein ist.
- Im Erwartungsfall (bei entsprechender Konfiguration)
erreichbar.
Im Worst-Case liegt der Aufwand in O(n).

Question 5

Was charakterisiert eine gute Hashfunktion?

Answer 5

Vor allem:
* Verwendete Schlussel sollen möglichst gleichmäßig auf alle
Plätze 0, . . . , m − 1 der Hashtabelle aufgeteilt werden.

• Auch kleinste Änderungen im Schlüssel sollen zu einem
  anderen, möglichst unabhängigen Hashwert fuhren.

Question 6

Divisions-Rest-Methode

Answer 6

Annahme: k ∈ N

Berechnung:
h(k) = k mod m

Eigenschaften:
* Die Hashfunktion kann sehr schnell berechnet werden.
* Die richtige Wahl von m ist hier sehr wichtig. Eine gute Wahl
fur m ist eine Primzahl.

Question 7

Hashtabelle einfügen Laufzeit

Answer 7

0(1)

Question 8

Hashtabelle suchen Laufzeit

Answer 8

0(n/m) average , 0(n) worst

Question 9

Lineares Sondieren: Probleme

Answer 9

• Nach dem Einfugen ist die Wahrscheinlichkeit für einen neu
  einzufugenden Schlüssel in der Hashtabelle an einer gewissen
  Position gespeichert zu werden fur die verschiedenen Positionen unterschiedlich.
• Wird ein Platz belegt, dann verändert sich die
  Wahrscheinlichkeit fur das Einfügen an seinem nachfolgenden
  Platz.

Question 10

Double Hashing

Answer 10

• Im Allgemeinen ist Double Hashing effizienter als
  quadratisches Hashing.
  I
  *In der Praxis entsprechen die Ergebnisse von Double Hashing
  nahezu denen von uniformen Hashing.