www.wikidata.de-de.nina.az

Perfekte Hash Funktion Eine perfekte Hash Funktion ist eine Hashfunktion h S T displaystyle h colon S rightarrow T die u

Perfekte Hash-Funktion

Eine perfekte Hash-Funktion ist eine Hashfunktion , die unterschiedliche Elemente aus einer endlichen und festen Schlüsselmenge auf unterschiedliche Elemente aus einer Bildmenge 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 worst Case in konstanter Zeit zugegriffen werden.

Eine perfekte Hash-Funktion heißt minimal, wenn , d. h. . Das bedeutet, dass die Bildmenge der Funktion genauso viele Elemente wie die Urbildmenge hat. In der Praxis senkt dies den Speicherbedarf des Arrays, das die Elemente für jedes mit speichert, auf das Minimum.

Im Gegensatz zu nicht perfektem Hashing, das amortisiert Zugriffszeit benötigt und im worst Case , bietet perfektes Hashing selbst im worst Case einen Zugriff auf die Elemente in konstanter Zeit , ist also deutlich schneller. Dies wird erreicht, indem die Werte der Schlüssel in einem von bis indizierten Array an der Position gespeichert werden; im Gegensatz zu normalem Hashing enthält jeder Eimer (Bucket) aufgrund der Injektivität von 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 Zeit, d. h. mit wachsender Schlüsselanzahl steigt die Zeit der Konstruktion linear.
  • Evaluation in , d. h. nach Konstruktion kann man einen Schlüssel in konstanter Zeit auf einen Index abbilden.
  • Die Hashfunktion benötigt möglichst wenig Speicher.
  • Die Hashfunktion soll minimal perfekt sein.

Derzeit gängige minimal perfekte Hashfunktionen arbeiten in Zeit zur Konstruktion und benötigen mindestens 1,56 Bit pro Schlüssel.

(Minimale) perfekte Hashfunktionen sind in der Praxis dann angebracht, wenn:

  • es eine feste Schlüsselmenge 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 Bearbeiten

  1. Emmanuel Esposito, Thomas Mueller Graf, Sebastiano Vigna: RecSplit: Minimal Perfect Hashing via Recursive Splitting. 2020 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), 2020, abgerufen am 23. Januar 2020 (englisch).
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Eine perfekte Hash Funktion ist eine Hashfunktion h S T displaystyle h colon S rightarrow T die unterschiedliche Elemente x x displaystyle x neq x aus einer endlichen und festen Schlusselmenge S displaystyle S auf unterschiedliche Elemente h x h x displaystyle h x neq h x aus einer Bildmenge T displaystyle T abbildet keine Kollisionen Injektivitat Aus der Injektivitat ergibt sich ein wichtiger Vorteil Auf ein Element einer Hashtabelle die mit einer perfekten Hash Funktion erstellt wurde kann im worst Case in konstanter Zeit zugegriffen werden Eine perfekte Hash Funktion heisst minimal wenn T 0 S 1 displaystyle T 0 dotsc left vert S right vert 1 d h S T displaystyle left vert S right vert left vert T right vert Das bedeutet dass die Bildmenge der Funktion genauso viele Elemente wie die Urbildmenge hat In der Praxis senkt dies den Speicherbedarf des Arrays das die Elemente fur jedes h s displaystyle h s mit s S displaystyle s in S speichert auf das Minimum Im Gegensatz zu nicht perfektem Hashing das amortisiert O 1 displaystyle mathcal O 1 Zugriffszeit benotigt und im worst Case O log n displaystyle mathcal O log n bietet perfektes Hashing selbst im worst Case einen Zugriff auf die Elemente in konstanter Zeit O 1 displaystyle mathcal O 1 ist also deutlich schneller Dies wird erreicht indem die Werte s displaystyle s der Schlussel in einem von 0 displaystyle 0 bis T 1 displaystyle left vert T right vert 1 indizierten Array an der Position h s displaystyle h s gespeichert werden im Gegensatz zu normalem Hashing enthalt jeder Eimer Bucket aufgrund der Injektivitat von h displaystyle h also nur genau ein Element Dafur bezahlt man mit Rechenzeit um die Hashfunktion zu konstruieren und benotigt mehr Speicherplatz In der Praxis sucht man Hashfunktionen mit folgenden Eigenschaften Konstruktion in O n displaystyle mathcal O n Zeit d h mit wachsender Schlusselanzahl S displaystyle left vert S right vert steigt die Zeit der Konstruktion linear Evaluation in O 1 displaystyle mathcal O 1 d h nach Konstruktion kann man einen Schlussel s S displaystyle s in S in konstanter Zeit auf einen Index h s displaystyle h s abbilden Die Hashfunktion benotigt moglichst wenig Speicher Die Hashfunktion soll minimal perfekt sein Derzeit gangige minimal perfekte Hashfunktionen arbeiten in O n displaystyle O n Zeit zur Konstruktion und benotigen mindestens 1 56 Bit pro Schlussel 1 Minimale perfekte Hashfunktionen sind in der Praxis dann angebracht wenn es eine feste Schlusselmenge S displaystyle S gibt der jeweils Werte zugeordnet sind bei sich standig andernden Schlusselmengen ware eine standige Neukonstruktion zu zeitintensiv genug Zeit vorhanden ist um die Hashfunktion zu konstruieren auf die Werte ein Zugriff in konstanter Zeit benotigt wird zusatzlicher Speicher fur die Hashfunktion vorhanden ist Einzelnachweise Bearbeiten Emmanuel Esposito Thomas Mueller Graf Sebastiano Vigna RecSplit Minimal Perfect Hashing via Recursive Splitting 2020 Proceedings of the Symposium on Algorithm Engineering and Experiments ALENEX 2020 abgerufen am 23 Januar 2020 englisch Abgerufen von https de wikipedia org w index php title Perfekte Hash Funktion amp oldid 208855367