Zum Inhalt springen

Perfekte Hash-Funktion

aus Wikipedia, der freien Enzyklopädie

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 Schlüsselmenge <math>S</math> auf unterschiedliche Elemente <math>h(x) \neq h(x')</math> aus einer Bildmenge <math>T</math> 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 <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 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 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> 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 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>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:Emmanuel Esposito, Thomas Mueller Graf, Sebastiano Vigna|Emmanuel Esposito, Thomas Mueller Graf, Sebastiano Vigna: }}{{#if:|{{#if:RecSplit: Minimal Perfect Hashing via Recursive Splitting|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=RecSplit: Minimal Perfect Hashing via Recursive Splitting}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=RecSplit: Minimal Perfect Hashing via Recursive Splitting}}}}|[{{#invoke:URLutil|getNormalized|1=https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=RecSplit: Minimal Perfect Hashing via Recursive Splitting}}}}]}}{{#if:| ({{{format}}}{{#if:2020 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX)2020{{#if: 2020-01-23 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}} 

          | )
          | {{#if:{{#ifeq:en|de||{{#if:en|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14}}%7C%7C}}}}{{#if:RecSplit: Minimal Perfect Hashing via Recursive Splitting|{{#if:{{#invoke:WLink|isValidLinktext|1=RecSplit: Minimal Perfect Hashing via Recursive Splitting|lines=0}}||}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{{werk}}}}}}}{{#if: 2020 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX)| 2020 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX){{#if: 2020|,|{{#if: 2020-01-23 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: 2020| {{#if:{{#invoke:DateTime|format|2020|noerror=1}}
            |{{#invoke:DateTime|format|2020|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=2020|class=Zitationswartung}} }}{{#if: |,|{{#if: 2020-01-23 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2020-01-23 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:20202020 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX)|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:367469||(?)}}}}}}{{#if: 2020-01-23|;}}}}{{#if: 2020-01-23| {{#if:20202020 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX){{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2020-01-23 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2020-01-23|class=Zitationswartung}} }} {{#invoke:DateTime|format|2020-01-23|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:en|de||{{#if:en|1}}}}|{{#if:2020 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX)2020{{#if: 2020-01-23 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:en|en|de}}|de||
          {{#invoke:Multilingual|format|en|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:en|en|de}}|de||, }}{{{kommentar}}}}})}}{{#if: 2020{{#if: 2020-01-23 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}en|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if: 

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}} 

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch: 

   |0|=Vorlage:Toter Link/Core{{#if: https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14
      | {{#if:{{#invoke:URLutil|isWebURL|https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14 Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14
       | {{#if:{{#invoke:URLutil|isWebURL|https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14 }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14
      | {{#if:{{#invoke:URLutil|isWebURL|https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14 Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14
       | {{#if:{{#invoke:URLutil|isWebURL|https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14 }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }} </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 />

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Perfekte_Hash-Funktion&oldid=367469“