0 Daumen
1,8k Aufrufe

Was zeichnet eine gute "Hashfunktion" aus?

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

Eine gute Hashfunktion erfüllt folgende Eigenschaften:

1.) Der Hashwert kann schnell und leicht berechnet werden.

2.) Die zu speichernden Datensätze/zu hashenden Informationen werden gleichmäßig im Hash-Raum verteilt.

3.) Die Hashwerte werden trotz schlechter Verteilung der Schlüssel möglichst gleichmäßig im Hash-Raum verteilt.

Im Optimalfall ist die Hashfunktion sogar injektiv. Solch eine Hashfunktion bezeichnet man auch als "perfekte Hashfunktion". Aus der Injektivität einer perfekten Hashfunktion leitet sich eine selbst im Worst-Case konstante Zugriffszeit \((\mathcal{O}(1))\) auf die Elemente einer Hashtabelle ab. Für nicht perfekte Hashfunktionen (also diejenigen, die nicht injektiv sind) ist die Zugriffszeit lediglich amortisiert \(\mathcal{O}(1)\). Eine nicht perfekte Hashfunktion kann dennoch "gut" im Sinne der Definition sein, die Du vermutlich meinst.

In der Praxis hat sich die Modulo-Funktion als Hashfunktion bewährt. Geeignet ist die Modulo-Funktion, wenn als Modul Primzahlen \(p\) mit \(p\nmid r^n\pm j\) mit kleinen \(n,j\in\mathbb{N}\) und der Zahlenbasis \(r\in\mathbb{N}\) verwendet werden.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community