imported>Gunnar.Kaestle: spezifischere Wikilink-Auswahl

2024-12-21T15:02:41Z

spezifischere Wikilink-Auswahl

Neue Seite

Eine '''perfekte Hash-Funktion''' ist eine [[Hashfunktion]] <math>h\colon S \rightarrow T</math>, die unterschiedliche Elemente <math>x \neq x'</math> aus einer endlichen und festen [[Definitionsmenge|Schlüsselmenge]] <math>S</math> auf unterschiedliche Elemente <math>h(x) \neq h(x')</math> aus einer [[Bildmenge]] <math>T</math> [[Funktion (Mathematik)|abbildet]] (keine Kollisionen, [[Injektivität]]). Aus der Injektivität ergibt sich ein wichtiger Vorteil: Auf ein Element einer [[Hashtabelle]], die mit einer perfekten Hash-Funktion erstellt wurde, kann im [[Zeitkomplexität|worst Case]] in konstanter [[Zugriffszeit|Zeit zugegriffen]] werden.

Eine perfekte Hash-Funktion heißt '''minimal''', wenn <math>T = \{ 0, \dotsc, \left\vert S \right\vert - 1 \}</math>, d. h. <math>\left\vert S \right\vert = \left\vert T \right\vert\,</math>. Das bedeutet, dass die Bildmenge der Funktion genauso viele Elemente wie die Urbildmenge hat. In der Praxis senkt dies den [[Speicherbedarf]] des [[Feld (Datentyp)|Arrays]], das die Elemente für jedes <math>h(s)</math> mit <math>s \in S</math> speichert, auf das Minimum.

Im Gegensatz zu nicht perfektem Hashing, das [[Amortisierte Laufzeitanalyse|amortisiert]] <math>\mathcal O(1)</math> Zugriffszeit benötigt und im worst Case <math>\mathcal O(\log n)</math>, bietet perfektes Hashing selbst im worst Case einen Zugriff auf die Elemente in ''konstanter Zeit'' <math>\mathcal O(1)</math>, ist also deutlich schneller. Dies wird erreicht, indem die Werte <math>s</math> der Schlüssel in einem von <math>0</math> bis <math>\left\vert T \right\vert - 1</math> [[Feld (Datentyp) #Indizes|indizierten]] Array an der Position <math>h(s)</math> gespeichert werden; im Gegensatz zu normalem Hashing enthält jeder Eimer (Bucket) aufgrund der Injektivität von <math>h</math> also nur genau ein Element. Dafür bezahlt man mit [[Rechenzeit]], um die Hashfunktion zu konstruieren, und benötigt mehr Speicherplatz.

In der Praxis sucht man Hashfunktionen mit folgenden Eigenschaften:
* Konstruktion in <math>\mathcal O(n)</math> Zeit, d. h. mit wachsender Schlüsselanzahl <math>\left\vert S \right\vert</math> steigt die Zeit der Konstruktion [[Linearität (Mathematik)|linear]].
* Evaluation in <math>\mathcal O(1)</math>, d. h. nach Konstruktion kann man einen Schlüssel <math>s \in S</math> in konstanter Zeit auf einen Index <math>h(s)</math> abbilden.
* Die Hashfunktion benötigt möglichst wenig Speicher.
* Die Hashfunktion soll minimal perfekt sein.

Derzeit gängige minimal perfekte Hashfunktionen arbeiten in <math>O(n)</math> Zeit zur Konstruktion und benötigen mindestens 1,56 [[Bit]] pro Schlüssel.<ref>{{Internetquelle
| autor=Emmanuel Esposito, Thomas Mueller Graf, Sebastiano Vigna
| titel=RecSplit: Minimal Perfect Hashing via Recursive Splitting
| url=https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14
| sprache=en
| datum=2020
| abruf=2020-01-23
| hrsg=2020 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX)}}
</ref>

(Minimale) perfekte Hashfunktionen sind in der Praxis dann angebracht, wenn:
* es eine ''feste'' Schlüsselmenge <math>S</math> gibt, der jeweils Werte zugeordnet sind (bei sich ständig ändernden Schlüsselmengen wäre eine ständige Neukonstruktion zu zeitintensiv),
* genug Zeit vorhanden ist, um die Hashfunktion zu konstruieren,
* auf die Werte ein Zugriff in konstanter Zeit benötigt wird,
* zusätzlicher Speicher für die Hashfunktion vorhanden ist.

== Einzelnachweise ==
<references />

[[Kategorie:Hash]]

Perfekte Hash-Funktion - Versionsgeschichte

imported>Gunnar.Kaestle: spezifischere Wikilink-Auswahl