Technopedia Center
PMB University Brochure
Faculty of Engineering and Computer Science
S1 Informatics S1 Information Systems S1 Information Technology S1 Computer Engineering S1 Electrical Engineering S1 Civil Engineering

faculty of Economics and Business
S1 Management S1 Accountancy

Faculty of Letters and Educational Sciences
S1 English literature S1 English language education S1 Mathematics education S1 Sports Education
teknopedia

teknopedia

teknopedia

teknopedia

teknopedia
  • Registerasi
  • Brosur UTI
  • Kip Scholarship Information
  • Performance
  1. Weltenzyklopädie
  2. Perfekte Hash-Funktion – Wikipedia
Perfekte Hash-Funktion – Wikipedia
aus Wikipedia, der freien Enzyklopädie

Eine perfekte Hash-Funktion ist eine Hashfunktion h : S → T {\displaystyle h\colon S\rightarrow T} {\displaystyle h\colon S\rightarrow T}, die unterschiedliche Elemente x ≠ x ′ {\displaystyle x\neq x'} {\displaystyle x\neq x'} aus einer endlichen und festen Schlüsselmenge S {\displaystyle S} {\displaystyle S} auf unterschiedliche Elemente h ( x ) ≠ h ( x ′ ) {\displaystyle h(x)\neq h(x')} {\displaystyle h(x)\neq h(x')} aus einer Bildmenge T {\displaystyle T} {\displaystyle T} 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 T = { 0 , … , | S | − 1 } {\displaystyle T=\{0,\dotsc ,\left\vert S\right\vert -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 \,} {\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 für jedes h ( s ) {\displaystyle h(s)} {\displaystyle h(s)} mit s ∈ S {\displaystyle s\in S} {\displaystyle s\in S} speichert, auf das Minimum.

Im Gegensatz zu nicht perfektem Hashing, das amortisiert O ( 1 ) {\displaystyle {\mathcal {O}}(1)} {\displaystyle {\mathcal {O}}(1)} Zugriffszeit benötigt und im worst Case O ( log ⁡ n ) {\displaystyle {\mathcal {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)} {\displaystyle {\mathcal {O}}(1)}, ist also deutlich schneller. Dies wird erreicht, indem die Werte s {\displaystyle s} {\displaystyle s} der Schlüssel in einem von 0 {\displaystyle 0} {\displaystyle 0} bis | T | − 1 {\displaystyle \left\vert T\right\vert -1} {\displaystyle \left\vert T\right\vert -1} indizierten Array an der Position h ( s ) {\displaystyle h(s)} {\displaystyle h(s)} gespeichert werden; im Gegensatz zu normalem Hashing enthält jeder Eimer (Bucket) aufgrund der Injektivität von h {\displaystyle h} {\displaystyle h} 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 O ( n ) {\displaystyle {\mathcal {O}}(n)} {\displaystyle {\mathcal {O}}(n)} Zeit, d. h. mit wachsender Schlüsselanzahl | S | {\displaystyle \left\vert S\right\vert } {\displaystyle \left\vert S\right\vert } steigt die Zeit der Konstruktion linear.
  • Evaluation in O ( 1 ) {\displaystyle {\mathcal {O}}(1)} {\displaystyle {\mathcal {O}}(1)}, d. h. nach Konstruktion kann man einen Schlüssel s ∈ S {\displaystyle s\in S} {\displaystyle s\in S} in konstanter Zeit auf einen Index h ( s ) {\displaystyle h(s)} {\displaystyle h(s)} abbilden.
  • Die Hashfunktion benötigt möglichst wenig Speicher.
  • Die Hashfunktion soll minimal perfekt sein.

Derzeit gängige minimal perfekte Hashfunktionen arbeiten in O ( n ) {\displaystyle O(n)} {\displaystyle O(n)} Zeit zur Konstruktion und benötigen mindestens 1,56 Bit pro Schlüssel.[1]

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

  • es eine feste Schlüsselmenge S {\displaystyle S} {\displaystyle S} 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 | Quelltext 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). 
Abgerufen von „https://de.teknopedia.teknokrat.ac.id/w/index.php?title=Perfekte_Hash-Funktion&oldid=251441896“
Kategorie:
  • Hash

  • indonesia
  • Polski
  • العربية
  • Deutsch
  • English
  • Español
  • Français
  • Italiano
  • مصرى
  • Nederlands
  • 日本語
  • Português
  • Sinugboanong Binisaya
  • Svenska
  • Українська
  • Tiếng Việt
  • Winaray
  • 中文
  • Русский
Sunting pranala
Pusat Layanan

UNIVERSITAS TEKNOKRAT INDONESIA | ASEAN's Best Private University
Jl. ZA. Pagar Alam No.9 -11, Labuhan Ratu, Kec. Kedaton, Kota Bandar Lampung, Lampung 35132
Phone: (0721) 702022
Email: pmb@teknokrat.ac.id