Hash-tabelle

Hash-tabelle
Typ Ungeordnet Assoziatives Array
Erfunden 1953
Zeitkomplexität in Big O Notation
Algorithmus Durchschnitt Schlimmsten Fall
Platz Θ (n)[1] Ö(n)
Suche Θ (1) Ö(n)
Einfügung Θ (1) Ö(n)
Löschen Θ (1) Ö(n)
Ein kleines Telefonbuch als Hash -Tisch

Im Computer, a Hash-tabelle, auch bekannt als Hash -Karte oder Wörterbuch, ist ein Datenstruktur das implementiert a einstellen Zusammenfassung Datentyp, eine Struktur, die kartieren kann Schlüssel zu Werte. Eine Hash -Tabelle verwendet a Hash-Funktion zu berechnen und Index, also called a Hash-Codein eine Reihe von Eimer oder Schlüssel, aus dem der gewünschte Wert gefunden werden kann. Während der Suche wird der Schlüssel gehasht und der resultierende Hash zeigt an, wo der entsprechende Wert gespeichert ist.

Im Idealfall weist die Hash -Funktion jedem Schlüssel einem einzigartigen Eimer zu, aber die meisten Hash -Tabellen -Designs verwenden eine unvollkommene Hash -Funktion, die möglicherweise Hash verursachen kann Kollisionen wobei die Hash -Funktion für mehr als einen Schlüssel denselben Index generiert. Solche Kollisionen werden in der Regel in irgendeiner Weise berücksichtigt.

In einer gut ausgelösten Hash-Tabelle ist die durchschnittliche Zeitkomplexität für jede Suche unabhängig von der Anzahl der in der Tabelle gespeicherten Elemente. Viele Hash -Tabellenentwürfe ermöglichen auch willkürliche Einfügungen und Löschungen von Schlüssel -Wert -Paare, bei amortisiert Konstante Durchschnittskosten pro Betrieb.[2][3][4]

Hashing ist ein Beispiel für a Raumzeit-Kompromiss. Wenn Erinnerung ist unendlich, der gesamte Schlüssel kann direkt als Index verwendet werden, um seinen Wert mit einem einzelnen Speicherzugriff zu lokalisieren. Auf der anderen Seite können Werte ohne Rücksicht auf ihre Schlüssel und a gespeichert werden, wenn unendliche Zeit verfügbar ist, und a binäre Suche oder Lineare Suche Kann verwendet werden, um das Element abzurufen.[5]: 458

In vielen Situationen erweisen sich Hash -Tabellen im Durchschnitt effizienter als im Durchschnitt Bäume suchen oder irgend ein anderer Tisch Suchstruktur. Aus diesem Grund werden sie in vielen Arten von Computer häufig verwendet Software, besonders für assoziative Arrays, Datenbankindexierung, Caches, und Sets.

Geschichte

Die Idee des Hashings entstand unabhängig an verschiedenen Orten. Im Januar 1953, Hans Peter Luhn schrieb einen inneren IBM Memorandum, das Hashing mit Kettung verwendete. Die offene Adressierung wurde später von A. D. Linh auf Luhns Papier vorgeschlagen.[6]: fünfzehn Um die selbe Zeit, Gene Amdahl, Elaine M. McGraw, Nathaniel Rochester, und Arthur Samuel von IBM -Forschung implementiert Hashing für die IBM 701 Assembler.[7]: 124 Offene Adressierung mit linearer Prüfung wird Amdahl gutgeschrieben, obwohl jedoch Ershov unabhängig voneinander hatte die gleiche Idee.[7]: 124–125 Der Begriff "offener Adressieren" wurde von geprägt von W. Wesley Peterson In seinem Artikel, in dem das Problem der Suche in großen Dateien erörtert wird.[6]: fünfzehn

Der Erste veröffentlicht Die Arbeit am Hashing mit Verkettung wird zugeschrieben Arnold Dumey, der die Idee, die Restmodul als Hash -Funktion zu verwenden, diskutierte.[6]: fünfzehn Das Wort "Hashing" wurde erstmals von einem Artikel von Robert Morris veröffentlicht.[7]: 126 A theoretische Analyse der linearen Prüfung wurde ursprünglich von Konheim und Weiss eingereicht.[6]: fünfzehn

Überblick

Eine Hash -Tabelle ist eine Implementierung von einstellen Zusammenfassung Datentyp, die zum Speichern eines Satzes verwendet wird von Elemente in einem Assoziatives Array von Länge , wo , mit besser Zeitkomplexität Grenzen für die Suche, Löschen und Einfügen von Vorgängen im Vergleich zu selbstausgleichende binäre Suchbäume.[6]: 1 Ein Wert wird an einem Indexort gespeichert , wo ist eine Hash -Funktion und .[6]: 2

Ladefaktor

A Ladefaktor ist eine kritische Statistik einer Hash -Tabelle und wird wie folgt definiert:[1]

wo
  • ist die Anzahl der Einträge, die in der Hash -Tabelle besetzt sind.
  • ist die Anzahl der Eimer.

Die Leistung der Hash -Tabelle verschlechtert sich in Bezug auf den Lastfaktor .[6]: 2 Daher wird eine Hash -Tabelle geändert oder aufgerufen Wenn der Lastfaktor Ansätze 1.[8] Eine Tabelle wird auch geändert, wenn der Lastfaktor unten fällt .[8] Akzeptable Zahlen des Lastfaktors enthalten 0,6 und 0,75.[9][10]: 110

Hash-Funktion

Eine Hash -Funktion Karten das Universum von Schlüssel für jedes für jeden Array -Indizes oder Slots in der Tabelle wo und . Die konventionellen Implementierungen von Hash -Funktionen basieren auf dem Ganzzahluniversum Annahme dass alle Elemente der Tabelle aus dem Universum stammen , bei dem die Bitlänge von ist in der eingesperrt Wortgröße von a Rechnerarchitektur.[6]: 2

A Perfekte Hash -Funktion ist definiert als eine Injektivfunktion so dass jedes Element jedes Element in Karten zu einem einzigartigen Wert in .[11][12] Eine perfekte Hash -Funktion kann erstellt werden, wenn alle Schlüssel im Voraus bekannt sind.[11]

Ganzzahluniversum Annahme

Die Pläne des Hashing in verwendet Ganzzahluniversum Annahme Hashing by Division, Hashing durch Multiplikation einbeziehen, Universal Hashing, Dynamisches perfektes Hashing, und Statisch perfektes Hashing.[6]: 2 Das Hashing nach Teilung ist jedoch das häufig verwendete Schema.[13]: 264[10]: 110

Hashing durch Division

Das Programm in Hashing by Division lautet wie folgt:[6]: 2

Wo ist der Hash Digest von und ist die Größe des Tisches.

Hashing durch Multiplikation

Das Multiplikationsschema im Hashing ist wie folgt:[6]: 2–3

Wo ist ein realbewertete Konstante. Ein Vorteil des Hashings durch Multiplikation ist, dass die ist nicht kritisch.[6]: 2–3 Obwohl jeder Wert erzeugt eine Hash -Funktion, Donald Knuth schlägt vor, die zu verwenden Goldener Schnitt.[6]: 3

Kollisionsauflösung

Ein Suchalgorithmus, der Hashing verwendet, besteht aus zwei Teilen. Der erste Teil berechnet a Hash-Funktion was den Suchschlüssel in eine verwandelt Array -Index. Der ideale Fall ist so, dass keine zwei Suchschlüssel für denselben Array -Index. Dies ist jedoch nicht immer der Fall und es ist unmöglich, unsichtbare Daten zu garantieren.[14]: 515 Der zweite Teil des Algorithmus ist daher die Kollisionsauflösung. Die beiden gängigen Methoden zur Kollisionsauflösung sind separate Verkettung und offene Adressierung.[5]: 458

Separate Verkettung

Hash -Kollision durch separate Verkettung gelöst
Hash -Kollision durch separate Verkettung mit Kopfaufzeichnungen im Eimer -Array.

Bei der separaten Verkettung beinhaltet der Prozess das Aufbau a verlinkte Liste mit Schlüssel -Wert -Paar Für jeden Sucharray -Index. Die kollidierten Elemente werden über eine einzige verknüpfte Liste miteinander gekettet, die mit einem eindeutigen Suchschlüssel auf das Element zugreifen kann.[5]: 464 Die Kollisionsauflösung durch das Erhalten mit verknüpfter Liste ist eine gemeinsame Methode zur Implementierung von Hash -Tabellen. Lassen und Seien Sie die Hash -Tabelle bzw. der Knoten, die Operation umfasst wie folgt:[13]: 258

Ketten-Hash-Insert (T, k)) Einfügung x An der Spitze der verknüpften Liste T[h(k)] Ketten-Hash-Such (T, k)) Suchen Sie nach einem Element mit Schlüssel k in verknüpfter Liste T[h(k)] Ketten-hash-delete (T, k)) löschen x Aus der verknüpften Liste T[h(k)]

Wenn das Element auch vergleichbar ist numerisch oder lexikalischund in die Liste eingefügt, indem die Pflege des GesamtbestellungEs führt zu einer schnelleren Beendigung der erfolglosen Suchvorgänge.[14]: 520–521

Andere Datenstrukturen für separate Verkettung

Wenn die Schlüssel sind bestelltEs könnte effizient sein, "zu verwenden"Selbstorganisierung"Konzepte wie die Verwendung a selbstausgleichender binärer Suchbaum, durch die die Theoretischer schlimmster Fall könnte zu niedergeschlagen werden , obwohl es zusätzliche Komplexitäten einführt.[14]: 521

Im Dynamisches perfektes Hashing, zwei Hash-Tabellen auf zwei Ebenen werden verwendet im schlimmsten Fall. In dieser Technik die Eimer von Einträge sind organisiert als Perfekte Hash -Tische mit Slots bieten eine konstante Lookup-Zeit für die schlechteste Niederlage und eine niedrige Amortisation Zeit für das Einfügen.[15] Eine Studie zeigt, dass Array -basierte separate Verkettung im Vergleich zur Standard -List -Methode unter starker Belastung 97% leistungsfähiger ist.[16]: 99

Techniken wie die Verwendung Fusionbaum Für jede Eimer führen auch die konstante Zeit für alle Operationen mit hoher Wahrscheinlichkeit.[17]

Ausschnitt und Referenzlokalität

Die verknüpfte Liste der separaten Kettenimplementierung ist möglicherweise nicht Cache-bewusst wegen räumliche LokalitätReferenzort- Wenn die Knoten der verlinkten Liste über den Speicher hinweg verstreut sind, kann die Liste während des Einfügens und der Suche möglich sein CPU -Cache Ineffizienzen.[16]: 91

Im Cache-bewusste Varianten, a Dynamisches Array als mehr gefunden Cache-freundlich wird an der Stelle verwendet, an der eine verknüpfte Liste oder selbstausgleichende binäre Suchbäume normalerweise zur Kollisionsauflösung durch separate Verkettung eingesetzt werden, da die zusammenhängende Zuordnung Muster des Arrays könnte von genutzt werden Hardware-Cache-Prefetcher-wie zum Beispiel Übersetzungs -Lookaside -Puffer- Erleichterung zu verkürzter Zugriffszeit und Speicherverbrauch.[18][19][20]

Offene Adressierung

Hash -Kollision durch offene Adressierung mit linearer Prüfung (Intervall = 1). Beachten Sie, dass "Ted Baker" einen einzigartigen Hash hat, aber dennoch mit "Sandra Dee" kollidierte, die zuvor mit "John Smith" kollidiert hatte.
Dieses Diagramm vergleicht die durchschnittliche Anzahl von CPU -Cache -Missen, die erforderlich sind, um Elemente in großen Hash -Tabellen (weit über dem Cache weit über dem Cache) zu suchen, mit Ketten und linearer Prüfung. Lineare Probe ist aufgrund des besseren Leistungen besser ab ReferenzortObwohl der Tisch voll wird, nimmt sich ihre Leistung drastisch ab.

Offene Adressierung ist eine weitere Technik zur Kollisionslösung Sondierung. Wenn ein neuer Eintrag eingefügt werden muss, werden die Eimer untersucht, beginnend mit dem Hashed-to-Slot und in einigen Sondensequenz, bis ein nicht besetzter Schlitz gefunden wird. Bei der Suche nach einem Eintrag werden die Eimer in derselben Reihenfolge gescannt, bis entweder der Zieldatensatz gefunden oder ein ungenutzter Array -Slot gefunden wird, der eine erfolglose Suche angibt.[21]

Bekannte Sondensequenzen umfassen:

  • Lineare Untersuchung, in dem das Intervall zwischen Sonden festgelegt ist (normalerweise 1).[22]
  • Quadratische Prüfung, in dem das Intervall zwischen Sonden erhöht wird, indem die aufeinanderfolgenden Ausgänge eines quadratischen Polynoms zum Wert der ursprünglichen Hash -Berechnung hinzugefügt werden.[23]: 272
  • Double Hashing, in dem das Intervall zwischen Sonden durch eine sekundäre Hash -Funktion berechnet wird.[23]: 272–273

Die Leistung der offenen Adressierung kann langsamer sein als bei separater Verkettung, da die Sondensequenz beim Lastfaktor zunimmt Ansätze 1.[8][16]: 93 Die Untersuchung führt zu einem Endlosschleife Wenn der Lastfaktor 1 erreicht, im Fall einer vollständig gefüllten Tabelle.[5]: 471 Das Durchschnittskosten der linearen Untersuchung hängt von der Fähigkeit der Hash -Funktion ab verteilen die Elemente gleichmäßig durch den Tisch, um zu vermeiden Clusteringda die Bildung von Clustern zu einer höheren Suchzeit führen würde.[5]: 472

Ausschnitt und Referenzlokalität

Da sich die Slots an aufeinanderfolgenden Orten befinden, könnte eine lineare Untersuchung zu einer besseren Nutzung von führen CPU -Cache wegen Lokalität der Referenzen was zu reduziert wird Speicherlatenz.[22]

Andere Techniken zur Kollisionsauflösung, die auf offener Adressierung basieren

Zusammengesetzte Hashing

Zusammengesetzte Hashing ist eine Mischung aus separatem Ketten und offener Adressierung, bei dem die Eimer oder Knoten in der Tabelle verknüpfen.[24]: 6–8 Der Algorithmus eignet sich ideal für Behobener Speicherzuweisung.[24]: 4 Die Kollision im zusammengesetzten Hashing wird durch die Identifizierung des größten leeren Schlitzes auf der Hash-Tabelle gelöst. Der kollidierende Wert wird dann in diesen Steckplatz eingefügt. Der Eimer ist auch mit dem Steckplatz des eingefügten Knotens verknüpft, der seine kollidierende Hash -Adresse enthält.[24]: 8

Cuckoo Hashing

Cuckoo Hashing ist eine Form der offenen Adresskollisionsauflösungstechnik, die garantiert Schlimmste Case-Lookup-Komplexität und konstante amortisierte Zeit für Einfügungen. Die Kollision wird durch die Aufrechterhaltung von zwei Hash -Tabellen gelöst, die jeweils eine eigene Hashing -Funktion haben, und der Collided Slot wird durch das angegebene Element ersetzt, und das besetzte Element des Steckplatzes wird in die andere Hash -Tabelle verschoben. Der Prozess wird fortgesetzt, bis jeder Schlüssel seinen eigenen Platz in den leeren Eimern der Tische hat. Wenn das Verfahren in eintritt Endlosschleife- Das wird durch die Aufrechterhaltung eines Schwellenwertschleifschalters identifiziert - sowohl Hash -Tabellen werden mit neueren Hash -Funktionen aufgeweckt, und das Verfahren wird fortgesetzt.[25]: 124–125

Hopscotch Hashing

Hopscotch Hashing ist ein offen adressierender Algorithmus, der die Elemente von kombiniert Cuckoo Hashing, lineare Untersuchung und durch den Begriff eines Ketts durch Nachbarschaft von Eimern - die nachfolgenden Eimer um einen bestimmten besetzten Eimer, auch als "virtueller" Eimer bezeichnet.[26]: 351–352 Der Algorithmus soll eine bessere Leistung liefern, wenn der Lastfaktor der Hash -Tabelle über 90%hinaus wächst. Es bietet auch einen hohen Durchsatz in Gleichzeitige Einstellungenso gut geeignet für die Implementierung von Resikable Gleichzeitige Hash -Tabelle.[26]: 350 Die von Hopscotch Hashing charakteristische Nachbarschaft garantiert eine Immobilie, dass die Kosten für die Suche nach dem gewünschten Gegenstand aus allen Eimern in der Nachbarschaft sehr nahe an den Kosten für die Suche nach dem Eimer selbst liegen. Der Algorithmus versucht, ein Gegenstand in seine Nachbarschaft zu sein - mit den möglichen Kosten, die bei der Verdrängung anderer Gegenstände verbunden sind.[26]: 352

Jeder Eimer in der Hash-Tabelle enthält eine zusätzliche "Hop-Information"-an H-bisschen Bit -Array für die Anzeige der relative Entfernung des Artikel, der ursprünglich in den aktuellen virtuellen Eimer im Inneren gehasht wurde H-1 Einträge.[26]: 352 Lassen und Seien Sie der Schlüssel, der eingesetzt werden muss, und der Eimer, in den der Schlüssel in Hash gehasht wird. Mehrere Fälle sind an dem Einfügungsverfahren beteiligt, so dass das Nachbarschaftseigentum des Algorithmus geschworen wird:[26]: 352–353 wenn ist leer, das Element wird eingefügt, und das linke Bitmap -Bitbit ist einstellen bis 1; Wenn nicht leer, wird die lineare Prüfung zum Auffinden eines leeren Steckplatzes in der Tabelle verwendet. Die Bitmap des Eimers wird aktualisiert, gefolgt von der Einfügung. Wenn sich der leere Schlitz nicht im Bereich der Reichweite befindet Nachbarschaft, d.h. H-1, nachfolgende Swap- und Hop-Info-Bit-Array-Manipulation jedes Eimers wird in Übereinstimmung mit seiner Nachbarschaft durchgeführt Invariante Eigenschaften.[26]: 353

Robin Hood Hashing

Robin Hood Hashing ist ein offener adressierender Algorithmus zur Kollisionsauflösung. Die Kollisionen werden gelöst, indem die Verschiebung des Elements begünstigt wird, das am weitesten - oder am längsten ist Sondensequenzlänge (PSL) - Von seinem "Heimatort", d. H. Der Eimer, in den der Gegenstand gehasht wurde.[27]: 12 Obwohl Robin Hood Hashing die nicht verändert theoretische Suchkostenes beeinflusst die erheblich die Varianz des Verteilung der Gegenstände auf den Eimern,[28]: 2 d.h. Umgang mit Cluster Bildung in der Hash -Tabelle.[29] Jeder Knoten in der Hash -Tabelle, in dem Robin Hood Hashing verwendet wird, sollte erweitert werden, um einen zusätzlichen PSL -Wert zu speichern.[30] Lassen Sei der Schlüssel, der eingefügt werden soll, Sei die (inkrementelle) PSL -Länge von , sei der Hash -Tisch und Seien Sie der Index, das Einfügungsverfahren lautet wie folgt:[27]: 12–13[31]: 5

  • Wenn : Die Iteration geht in den nächsten Eimer, ohne eine externe Sonde zu versuchen.
  • Wenn : Fügen Sie das Element ein in den Eimer ; Tauschen mit -Kümmer dich nicht darum ; Setzen Sie die Sonde fort von der sterblicher Bucket zum Einfügen ; Wiederholen Sie den Vorgang, bis jedes Element eingefügt wird.

Dynamische Größenänderung

Wiederholte Insertionen führen dazu, dass die Anzahl der Einträge in einer Hash -Tabelle wächst, was folglich den Lastfaktor erhöht. Um die Amortisation aufrechtzuerhalten Leistung der Such- und Insertionsoperationen, eine Hash -Tabelle wird dynamisch geändert und die Elemente der Tabellen sind aufgerufen in die Eimer des neuen Hash -Tisches,[8] Da die Elemente nicht als variierende Tabellengrößen kopiert werden können, führt Modulo -Betrieb.[32] Die Größe kann an Hash -Tabellen mit weniger Einträgen im Vergleich zu seiner Größe durchgeführt werden, um übermäßig übermäßig Speichernutzung.[33]

Größenänderung durch Verschieben aller Einträge

Im Allgemeinen erhält eine neue Hash -Tabelle mit einer Größe des ursprünglichen Hash -Tisches zugewiesen Privat und jeder Artikel in der ursprünglichen Hash -Tabelle wird in die neu zugewiesene Verschiebung der Hash -Werte der Elemente, gefolgt von dem Einfügungsvorgang, verschoben. Das Wiederholen ist trotz seiner Einfachheit rechenintensiv.[34]: 478–479

Alternativen zum All-at-Once-Rauf

Einige Hash -Tabellen -Implementierungen, insbesondere in Echtzeitsysteme, kann nicht den Preis für die Vergrößerung der Hash-Tabelle auf einmal zahlen, da er zeitkritische Operationen unterbrechen kann. Wenn man die dynamische Größe nicht vermeiden kann, besteht eine Lösung darin, die Größenänderung allmählich durchzuführen, um einen Speicher -Blip zu vermeiden - typisch bei 50% der Größe der neuen Tabelle - das Wiederaufnehmen und zur Vermeidung Gedächtnisfragmentierung das löst aus Heap -Verdichtung Aufgrund der Deallokation von groß Speicherblöcke verursacht durch den alten Hash -Tisch.[35]: 2–3 In diesem Fall erfolgt der Wiederaufbau -Vorgang schrittweise durch Erweiterung der für die alten Hash -Tabelle zugewiesenen Vorgabeblocke, so dass die Eimer der Hash -Tabelle unverändert bleiben. Ein gemeinsamer Ansatz für die amortisierte Wiederaufnahme besteht darin, zwei Hash -Funktionen aufrechtzuerhalten und . Der Prozess der Wiederaufnahme der Elemente eines Eimers gemäß der neuen Hash -Funktion wird als als bezeichnet Reinigung, was durch implementiert wird durch Befehlsmuster Durch Einkapselung der Operationen wie z. , und durch ein Verpackung So dass jedes Element im Eimer aufgeweckt wird und sein Verfahren wie folgt beinhaltet:[35]: 3

  • Sauber Eimer.
  • Sauber Eimer.
  • Das Befehl wird ausgeführt.

Lineares Hashing

Lineares Hashing ist eine Implementierung der Hash -Tabelle, die dynamische Wachstum oder Schrumpfung der Tabelle jeweils einen Eimer ermöglicht.[36]

Leistung

Die Leistung einer Hash -Tabelle hängt von der Fähigkeit der Hash -Funktion bei der Erzeugung ab Quasi-Random-Zahlen () für Einträge in der Hash -Tabelle wo , und bezeichnet die Schlüssel, die Anzahl der Eimer und die Hash -Funktion so, dass . Wenn die Hash -Funktion das gleiche erzeugt für unterschiedliche Schlüssel (), das führt zu Kollision, was auf verschiedene Arten behandelt werden sollte. Die konstante Zeitkomplexität () der Operation in einer Hash -Tabelle wird unter der Bedingung vorausgesetzt, dass die Hash -Funktion keine kollidierenden Indizes erzeugt. Somit ist die Leistung der Hash -Tabelle direkt proportional zu der gewählten Hash -Funktionsfähigkeit zu zerstreuen die Indizes.[37]: 1 Der Bau einer solchen Hash -Funktion ist jedoch praktisch uneinheitlichDas ist so, dass Implementierungen davon abhängen fallspezifisch Kollisionsauflösungstechniken bei der Erreichung einer höheren Leistung.[37]: 2

Anwendungen

Assoziative Arrays

Hash-Tabellen werden häufig verwendet, um viele Arten von In-Memory-Tabellen zu implementieren. Sie sind verwendet, um implementiert zu werden assoziative Arrays.[23]

Datenbankindexierung

Hash -Tabellen können auch als verwendet werden Scheibe-basierte Datenstrukturen und Datenbankindizes (wie in DBM) obwohl B-Bäume sind in diesen Anwendungen beliebter.[38]

Caches

Hash -Tabellen können zur Implementierung verwendet werden Caches, Hilfsdatentabellen, mit denen der Zugriff auf Daten beschleunigt wird, die hauptsächlich in langsameren Medien gespeichert sind. In dieser Anwendung können Hash -Kollisionen behandelt werden, indem eines der beiden kollidierenden Einträge verworfen werden. Sie werden normalerweise das alte Element ausgelöscht, das derzeit in der Tabelle gespeichert ist, und überschreiben Sie sie mit dem neuen Artikel, sodass jeder Artikel in der Tabelle einen eindeutigen Hash -Wert hat.[39][40]

Sets

Hash -Tabellen können bei der Implementierung von verwendet werden Datenstruktur festlegen, die eindeutige Werte ohne bestimmte Reihenfolge speichern können; Das SET wird normalerweise zum Testen der Mitgliedschaft eines Wertes in der Sammlung und nicht zum Elementabruf verwendet.[41]

Transpositionstabelle

A Transpositionstabelle zu einer komplexen Hash -Tabelle, in der Informationen zu jedem gesuchten Abschnitt gespeichert sind.[42]

Implementierungen

In Programmiersprachen

Viele Programmiersprachen bieten Hash-Tabellenfunktionalität, entweder als integrierte assoziative Arrays oder als Standardbibliothek Module.

Im JavaScript, jeder Wert mit Ausnahme von 7 "primitiven" Datentypen wird als "Objekt" bezeichnet, das entweder Ganzzahlen, Zeichenfolgen oder garantierte "Symbol" -Symbol "primitive Werte als Schlüssel für eine Hash-Karte verwendet. ECMascript 6 fügte ebenfalls hinzu Karte und Satz Datenstrukturen.[43]

C ++ 11 inklusive Under Ordered_map in seiner Standardbibliothek zum Speichern von Schlüssel und Werten von willkürliche Typen.[44]

Java Die Programmiersprache umfasst die Hashset, Hashmap, LinkedHashset, und LinkedHasMap generisch Sammlungen.[45]

Python's eingebaut DICT implementiert eine Hash -Tabelle in Form von a Typ.[46]

Rubin's eingebaut Hash Verwendet das offene Adressmodell von Ruby 2.4 ab.[47]

Siehe auch

Verweise

  1. ^ a b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Einführung in Algorithmen (3. Aufl.). Massachusetts Institute of Technology. S. 253–280. ISBN 978-0-262-03384-8.
  2. ^ Charles E. Leiserson, Amortisierte Algorithmen, Tabellenverdoppelung, potenzielle Methode Archiviert 7. August 2009 bei der Wayback -Maschine Vortrag 13, Kurs MIT 6.046J/18.410J Einführung in Algorithmen - Fall 2005
  3. ^ Knuth, Donald (1998). Die Kunst der Computerprogrammierung. Vol. 3: Sortieren und Suchen (2. Aufl.). Addison-Wesley. S. 513–558. ISBN 978-0-201-89685-5.
  4. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Kapitel 11: Hash -Tabellen". Einführung in Algorithmen (2. Aufl.). MIT Press und McGraw-Hill. pp.221–252. ISBN 978-0-262-53196-2.
  5. ^ a b c d e Sedgewick, Robert; Wayne, Kevin (2011). Algorithmen. Vol. 1 (4 ed.). Addison-Wesley Professional-via Princeton Universität, Abteilung für Computerwissenschaften.
  6. ^ a b c d e f g h i j k l m Mehta, Dinesh P.; Sahni, Sartaj (28. Oktober 2004). "9: Hash -Tabellen". Handbuch für Datenstrukturen und Anwendungen (1 ed.). Taylor & Francis. doi:10.1201/9781420035179. ISBN 978-1-58488-435-4.
  7. ^ a b c Konheim, Alan G. (21. Juni 2010). Hashing in Informatik: Fünfzig Jahre in Schneide und Würfeln. John Wiley & Sons, Inc. doi:10.1002/9780470630617. ISBN 9780470630617.
  8. ^ a b c d Mayers, Andrew (2008). "CS 312: Hash -Tabellen und amortisierte Analyse". Cornell Universität, Abteilung für Computerwissenschaften. Archiviert vom Original am 26. April 2021. Abgerufen 26. Oktober, 2021 - via cs.cornell.edu.
  9. ^ Maurer, W.D.; Lewis, T.G. (1. März 1975). "Hash -Tabellenmethoden". ACM Computing -Umfragen. Journal of the ACM. 1 (1): 14. doi:10.1145/356643.356645. S2CID 17874775.
  10. ^ a b Owolabi, Olumide (1. Februar 2003). "Empirische Studien einiger Hashing -Funktionen". Informations- und Softwaretechnologie. Abteilung für Mathematik und Informatik, Universität von Port Harcourt. 45 (2): 109–112. doi:10.1016/s0950-5849 (02) 00174-X - via Sciencedirect.
  11. ^ a b Lu, yi; Prabhakar, Balaji; Bonomi, Flavio (2006), "Perfect Hashing for Network Applications", 2006 IEEE Internationales Symposium für Informationstheorie: 2774–2778, doi:10.1109/isit.2006.261567, ISBN 1-4244-0505-x, S2CID 1494710
  12. ^ Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin (2009), "Hash, verdrängen und komprimieren" (PDF), Algorithmen-ESA 2009: 17. jährliches europäisches Symposium, Kopenhagen, Dänemark, 7. bis 9. September 2009, Proceedings (PDF), Vorlesungsnotizen in Informatik, vol. 5757, Berlin: Springer, S. 682–693, Citeseerx 10.1.1.568.130, doi:10.1007/978-3-642-04128-0_61, HERR 2557794
  13. ^ a b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Kapitel 11: Hash -Tabellen". Einführung in Algorithmen (2. Aufl.). Massachusetts Institute of Technology. ISBN 978-0-262-53196-2.
  14. ^ a b c Donald E. Knuth (24. April 1998). Die Kunst der Computerprogrammierung: Band 3: Sortieren und Suchen. Addison-Wesley Professional. ISBN 978-0-201-89685-5.
  15. ^ Erik Demaine, Jeff Lind. 6.897: Fortgeschrittene Datenstrukturen. MIT Informatik und künstliche Intelligenzlabor. Frühjahr 2003. "Archivierte Kopie" (PDF). Archiviert (PDF) Aus dem Original am 15. Juni 2010. Abgerufen 30. Juni, 2008.{{}}: CS1 Wartung: Archiviertes Kopie als Titel (Link)
  16. ^ a b c Askitis, Nikolas; Zobel, Justin (2005). "Cache-bewusste Kollisionsauflösung in String-Hash-Tabellen". Internationales Symposium zur String -Verarbeitung und Informationsabnahme. Springer Science+Business Media: 91–102. doi:10.1007/11575832_1. ISBN 978-3-540-29740-6.
  17. ^ Willard, Dan E. (2000). "Untersuchung der Computergeometrie, Van Emde Boas -Bäume und Hashing aus der Perspektive des Fusionbaums". Siam Journal über Computing. 29 (3): 1030–1049. doi:10.1137/s0097539797322425. HERR 1740562..
  18. ^ Askitis, Nikolas; Sinha, Ranjan (2010). "Engineering skalierbar, Cache und platzeeffiziente Versuche für Saiten". Das VLDB -Journal. 17 (5): 634. doi:10.1007/s00778-010-0183-9. ISSN 1066-8888. S2CID 432572.
  19. ^ Askitis, Nikolas; Zobel, Justin (Oktober 2005). Cache-bewusste Kollisionsauflösung in String-Hash-Tabellen. Proceedings der 12. Internationalen Konferenz, String -Verarbeitung und Informationsabruf (Spire 2005). Vol. 3772/2005. S. 91–102. doi:10.1007/11575832_11. ISBN 978-3-540-29740-6.
  20. ^ Askitis, Nikolas (2009). Schnelle und kompakte Hash -Tabellen für Ganzzahlschlüssel (PDF). Proceedings der 32. australasianischen Informatikkonferenz (ACSC 2009). Vol. 91. S. 113–122. ISBN 978-1-920682-72-9. Archiviert von das Original (PDF) am 16. Februar 2011. Abgerufen 13. Juni, 2010.
  21. ^ Tenenbaum, Aaron M.; Langsam, Yedidyah; Auzenstein, Moshe J. (1990). Datenstrukturen mit c. Prentice Hall. S. 456–461, S. 472. ISBN 978-0-13-199746-2.
  22. ^ a b Pagh, Rasmus; Rodler, Flemming Friche (2001). "Cuckoo Hashing". Algorithmen - ESA 2001. Vorlesungsnotizen in Informatik. Vol. 2161. S. 121–133. Citeseerx 10.1.1.25.4189. doi:10.1007/3-540-44676-1_10. ISBN 978-3-540-42493-2.
  23. ^ a b c Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "11 Hash -Tabellen", Einführung in Algorithmen (2. Aufl.), MIT Press und McGraw-Hill, S. 221–252, ISBN 0-262-03293-7.
  24. ^ a b c Vitter, Jeffery S.; Chen, Wen-Chin (1987). Das Design und die Analyse von zusammengesetzten Hashing. New York, USA: Oxford University Press. ISBN 978-0-19-504182-8 - via Archive.org.
  25. ^ Pagh, Rasmus; Rodler, Flemming Friche (2001). "Cuckoo Hashing". Algorithmen - ESA 2001. Vorlesungsnotizen in Informatik. Vol. 2161. Citeseerx 10.1.1.25.4189. doi:10.1007/3-540-44676-1_10. ISBN 978-3-540-42493-2.
  26. ^ a b c d e f Herlihy, Maurice; Shavit, Nir; Tzafrir, Moran (2008). "Hopscotch Hashing". International Symposium on Distributed Computing. Verteiltes Computer. Berlin, Heidelberg: Springer Publishing. 5218: 350–364. doi:10.1007/978-3-540-87779-0_24. ISBN 978-3-540-87778-3 - über Springer Link.
  27. ^ a b Celis, Pedro (1986). Robin Hood Hashing (PDF). Ontario, Kanada: Universität von Waterloo, Abteilung für Informatik. ISBN 031529700X. OCLC 14083698. Archiviert (PDF) vom Original am 1. November 2021. Abgerufen 2. November, 2021.
  28. ^ Poblete, P.V.; Viola, A. (14. August 2018). "Analyse von Robin Hood und anderen Hashing -Algorithmen unter dem zufälligen Prüfmodell mit und ohne Deletionen". Kombinatorik, Wahrscheinlichkeit und Computing. Cambridge University Press. 28 (4): 600–617. doi:10.1017/s0963548318000408. ISSN 1469-2163. S2CID 125374363. Abgerufen 1. November, 2021 - über Cambridge Core.
  29. ^ Clarkson, Michael (2014). "Vortrag 13: Hash -Tabellen". Cornell Universität, Abteilung für Computerwissenschaften. Archiviert vom Original am 7. Oktober 2021. Abgerufen 1. November, 2021 - via cs.cornell.edu.
  30. ^ Gries, David (2017). "Javahypertext und Datenstruktur: Robin Hood Hashing" (PDF). Cornell Universität, Abteilung für Computerwissenschaften. Archiviert (PDF) vom Original am 26. April 2021. Abgerufen 2. November, 2021 - via cs.cornell.edu.
  31. ^ Celis, Pedro (28. März 1988). Externer Robin Hood Hashing (PDF) (Technischer Bericht). Bloomington, Indiana: Universität von Indiana, Abteilung für Computerwissenschaften. 246. Archiviert (PDF) vom Original am 2. November 2021. Abgerufen 2. November, 2021.
  32. ^ Goddard, Wayne (2021). "Chater C5: Hash -Tische" (PDF). Clemson University. S. 15–16. Archiviert (PDF) vom Original am 9. November 2021. Abgerufen 9. November, 2021 - via people.cs.clemson.edu.
  33. ^ Devadas, Srini; Demaine, Erik (25. Februar 2011). "Intro zu Algorithmen: Änderung der Hash -Tabellen" (PDF). Massachusetts Institute of Technology, Abteilung für Computerwissenschaften. Archiviert (PDF) vom Original am 7. Mai 2021. Abgerufen 9. November, 2021 - via MIT openCourseware.
  34. ^ Thareja, Reema (13. Oktober 2018). "Hashing und Kollision". Datenstrukturen mit c (2 ed.). Oxford University Press. ISBN 9780198099307.
  35. ^ a b Friedman, Scott; Krishnan, Anand; Leidefrost, Nicholas (18. März 2003). "Hash-Tabellen für eingebettete und Echtzeitsysteme" (PDF). Alle Informatik- und Ingenieurforschung. Washington University in St. Louis. doi:10.7936/k7wd3xxv. Archiviert (PDF) vom Original am 9. Juni 2021. Abgerufen 9. November, 2021 - via Northwestern University, Abteilung für Computerwissenschaften.
  36. ^ Litwin, Witold (1980). "Lineares Hashing: Ein neues Tool für Datei- und Tabellenadressierung" (PDF). Proc. 6. Konferenz über sehr große Datenbanken. Carnegie Mellon Universität. S. 212–223. Archiviert (PDF) vom Original am 6. Mai 2021. Abgerufen 10. November, 2021 - via cs.cmu.edu.
  37. ^ a b Dijk, Tom Van (2010). "Analyse und Verbesserung der Hash -Tabellenleistung" (PDF). Niederlande: Universität zwanzige. Archiviert (PDF) vom Original am 6. November 2021. Abgerufen 31. Dezember, 2021.
  38. ^ Lech Banachowski. "Indizes und externe Sortierung". PL: Polsko-Japońska Akademia Technik Komputerowych. Archiviert von das Original am 26. März 2022. Abgerufen 26. März, 2022.
  39. ^ Zhong, Liang; Zheng, Xueqian; Liu, Yong; Wang, Menging; Cao, Yang (Februar 2020). "Maximierung des Cache-Trefferverhältnisses in Geräte-zu-Device-Kommunikation, die Mobilfunknetze überlagert". China Kommunikation. 17 (2): 232–238. doi:10.23919/jcc.2020.02.018. ISSN 1673-5447. S2CID 212649328.
  40. ^ Bottommley, James (1. Januar 2004). "Caching" verstehen ". Linux Journal. Archiviert vom Original am 4. Dezember 2020. Abgerufen 16. April, 2022.
  41. ^ Jill Seaman (2014). "Set & Hash -Tabellen". Texas State University. Archiviert von das Original (PDF) am 26. März 2022. Abgerufen 26. März, 2022.
  42. ^ "Transpositionstabelle - Schachprogrammierung Wiki". chessprogramming.org. Archiviert vom Original am 14. Februar 2021. Abgerufen 1. Mai, 2020.
  43. ^ "JavaScript -Datentypen und Datenstrukturen - JavaScript | Mdn". Entwickler.mozilla.org. Abgerufen 24. Juli, 2022.
  44. ^ "Programmiersprache C ++ - Technische Spezifikation" (PDF). Internationale Standardisierungsorganisation. S. 812–813. Archiviert von das Original (PDF) am 21. Januar 2022. Abgerufen 8. Februar, 2022.
  45. ^ "Lektion: Implementierungen (die Java ™ -Tutorials> Sammlungen)". docs.oracle.com. Archiviert Aus dem Original am 18. Januar 2017. Abgerufen 27. April, 2018.
  46. ^ Zhang, Juan; Jia, Yunwei (2020). "Redis Rehash -Optimierung basierend auf maschinellem Lernen". Journal of Physics: Konferenzreihe. 1453 (1): 3. Bibcode:2020JPHCS1453A2048Z. doi:10.1088/1742-6596/1453/1/012048. S2CID 215943738.
  47. ^ Jonan Scheffler (25. Dezember 2016). "Ruby 2.4 freigegeben: schnelleres Hashes, einheitliche Ganzzahlen und bessere Rundung". Heroku.com. Archiviert Aus dem Original am 3. Juli 2019. Abgerufen 3. Juli, 2019.

Weitere Lektüre

Externe Links