Wie funktioniert eine Hashtabelle?

Question

Ich suche nach einer Erklärung, wie eine Hashtabelle funktioniert - in einfachem Englisch für einen Einfaltspinsel wie mich!

Ich weiß zum Beispiel, dass es den Schlüssel nimmt, den Hash berechnet (ich suche nach einer Erklärung, wie) und dann eine Art Modulo durchführt, um herauszufinden, wo er in dem Array liegt, in dem der Wert gespeichert ist, aber da hört mein Wissen auf.

Kann jemand das Verfahren erläutern?

Bearbeiten: Ich frage nicht speziell danach, wie Hash-Codes berechnet werden, sondern nach einem allgemeinen Überblick über die Funktionsweise einer Hashtabelle.

Answer 1

Hier ist eine Erklärung für den Laien.

Nehmen wir an, Sie wollen eine Bibliothek mit Büchern füllen und sie nicht einfach nur hineinstopfen, sondern Sie wollen sie auch leicht wiederfinden, wenn Sie sie brauchen.

Sie beschließen also, dass es ausreicht, wenn die Person, die ein Buch lesen möchte, den Titel des Buches kennt, und dazu noch den genauen Titel, dann sollte das genügen. Mit dem Titel sollte die Person mit Hilfe des Bibliothekars in der Lage sein, das Buch leicht und schnell zu finden.

Wie kann man das also machen? Nun, man kann natürlich eine Art Liste führen, in der man festhält, wo man jedes Buch abgelegt hat, aber dann hat man das gleiche Problem wie bei der Suche in der Bibliothek, man muss die Liste durchsuchen. Zugegeben, die Liste wäre kleiner und leichter zu durchsuchen, aber man will trotzdem nicht von einem Ende der Bibliothek (oder Liste) zum anderen suchen.

Sie wollen etwas, das Ihnen mit dem Titel des Buches sofort die richtige Stelle anzeigt, so dass Sie nur noch zum richtigen Regal schlendern und das Buch in die Hand nehmen müssen.

Aber wie kann das geschehen? Nun, mit ein wenig Voraussicht, wenn man die Bibliothek füllt, und einer Menge Arbeit, wenn man die Bibliothek füllt.

Anstatt die Bibliothek einfach von einem Ende zum anderen aufzufüllen, haben Sie sich eine clevere Methode ausgedacht. Sie nehmen den Titel des Buches, lassen ihn durch ein kleines Computerprogramm laufen, das eine Regalnummer und eine Platznummer in diesem Regal ausspuckt. Dort platzieren Sie das Buch.

Das Schöne an diesem Programm ist, dass Sie später, wenn eine Person das Buch erneut lesen möchte, den Titel noch einmal in das Programm eingeben und dieselbe Regal- und Steckplatznummer zurückerhalten, die Sie ursprünglich erhalten haben, und das Buch befindet sich dort.

Das Programm wird, wie bereits von anderen erwähnt, als Hash-Algorithmus oder Hash-Berechnung bezeichnet und funktioniert in der Regel so, dass es die eingegebenen Daten (in diesem Fall den Titel des Buches) nimmt und daraus eine Zahl errechnet.

Der Einfachheit halber nehmen wir an, dass sie einfach jeden Buchstaben und jedes Symbol in eine Zahl umwandelt und alle zusammenzählt. In Wirklichkeit ist es viel komplizierter, aber lassen wir es erst einmal dabei bewenden.

Das Schöne an einem solchen Algorithmus ist, dass er immer wieder dieselbe Zahl ausspuckt, wenn man ihn immer wieder mit derselben Eingabe füttert.

Ok, so funktioniert also eine Hashtabelle.

Es folgt der technische Teil.

Erstens ist da die Größe der Zahl. In der Regel liegt die Ausgabe eines solchen Hash-Algorithmus innerhalb eines Bereichs einer großen Zahl, die in der Regel viel größer ist als der Platz, der in Ihrer Tabelle zur Verfügung steht. Nehmen wir zum Beispiel an, dass wir in der Bibliothek Platz für genau eine Million Bücher haben. Die Ausgabe der Hash-Berechnung könnte im Bereich von 0 bis eine Milliarde liegen, also viel höher.

Was sollen wir also tun? Wir verwenden die so genannte Modulusberechnung, die im Grunde besagt, dass man, wenn man bis zu der gewünschten Zahl gezählt hat (z. B. die eine Milliarde), aber innerhalb eines viel kleineren Bereichs bleiben wollte, jedes Mal, wenn man die Grenze dieses kleineren Bereichs erreicht, wieder bei 0 anfängt, aber man muss verfolgen, wie weit man in der großen Folge gekommen ist.

Angenommen, die Ausgabe des Hash-Algorithmus liegt im Bereich von 0 bis 20 und Sie erhalten den Wert 17 von einem bestimmten Titel. Wenn die Bibliothek nur 7 Bücher umfasst, zählt man 1, 2, 3, 4, 5, 6, und wenn man bei 7 angelangt ist, fängt man wieder bei 0 an. Da wir 17 Mal zählen müssen, haben wir 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, und die endgültige Zahl ist 3.

Die Berechnung von Modulen erfolgt natürlich nicht auf diese Weise, sondern durch Division und einen Rest. Der Rest der Division von 17 durch 7 ist 3 (7 geht zweimal in 17 zu 14 und die Differenz zwischen 17 und 14 ist 3).

Sie legen das Buch also in das Fach Nummer 3.

Dies führt zum nächsten Problem. Kollisionen. Da der Algorithmus keine Möglichkeit hat, die Bücher so zu verteilen, dass sie die Bibliothek (oder die Hashtabelle, wenn Sie so wollen) genau füllen, wird er unweigerlich eine Zahl berechnen, die schon einmal verwendet wurde. In der Bibliothek bedeutet das: Wenn Sie zu dem Regal und der Nummer des Fachs kommen, in das Sie ein Buch stellen wollen, befindet sich dort bereits ein Buch.

Es gibt verschiedene Methoden zur Behandlung von Kollisionen, einschließlich der Durchführung einer weiteren Berechnung, um einen anderen Platz in der Tabelle zu erhalten ( Doppelhashing ), oder einfach einen Platz in der Nähe des Ihnen zugewiesenen Platzes zu finden (d. h. direkt neben dem vorherigen Buch, vorausgesetzt der Platz war frei, auch bekannt als lineare Abtastung ). Das würde zwar bedeuten, dass Sie etwas suchen müssen, wenn Sie das Buch später finden wollen, aber es ist immer noch besser, als einfach an einem Ende der Bibliothek anzufangen.

Irgendwann möchten Sie vielleicht mehr Bücher in die Bibliothek stellen, als diese zulässt. Mit anderen Worten: Sie müssen eine größere Bibliothek bauen. Da der exakte Platz in der Bibliothek anhand der exakten und aktuellen Größe der Bibliothek berechnet wurde, muss man bei einer Größenänderung der Bibliothek möglicherweise neue Plätze für alle Bücher finden, da sich die Berechnung zur Ermittlung der Plätze geändert hat.

Ich hoffe, diese Erklärung war ein bisschen bodenständiger als Eimer und Funktionen :)

Answer 2

Verwendung und Sprachgebrauch:

1. Hash-Tabellen werden zum schnellen Speichern und Abrufen von Daten (oder Datensätzen) verwendet.
2. Aufzeichnungen werden gespeichert in Eimer mit Hash-Schlüssel
3. Hash-Schlüssel werden berechnet, indem ein Hashing-Algorithmus auf einen ausgewählten Wert angewendet wird (die Schlüssel Wert) im Datensatz enthalten. Dieser gewählte Wert muss ein gemeinsamer Wert für alle Datensätze sein.
4. Jede Eimer kann mehrere Datensätze enthalten, die in einer bestimmten Reihenfolge angeordnet sind.

Beispiel aus der Praxis:

Hash & Co. Das 1803 gegründete Unternehmen, das über keinerlei Computertechnik verfügte, hatte insgesamt 300 Aktenschränke, um die detaillierten Informationen (die Unterlagen) für seine rund 30 000 Kunden aufzubewahren. Jeder Aktenordner war eindeutig mit seiner Kundennummer gekennzeichnet, einer einmaligen Nummer von 0 bis 29.999.

Die damaligen Registraturbeamten mussten die Kundenunterlagen schnell holen und für die Mitarbeiter aufbewahren. Die Mitarbeiter hatten beschlossen, dass es effizienter wäre, ein Hashing-Verfahren zum Speichern und Abrufen ihrer Unterlagen zu verwenden.

Um einen Kundendatensatz abzulegen, benutzten die Sachbearbeiter die eindeutige Kundennummer, die auf dem Ordner vermerkt war. Anhand dieser Kundennummer modulieren sie die Hash-Schlüssel um 300, um den Aktenschrank zu identifizieren, in dem er sich befindet. Als sie den Aktenschrank öffneten, stellten sie fest, dass er viele nach Kundennummern geordnete Ordner enthielt. Nachdem sie den richtigen Ort gefunden hatten, legten sie ihn einfach ein.

Um einen Kundendatensatz abzurufen, erhielten die Sachbearbeiter eine Kundennummer auf einem Zettel. Anhand dieser eindeutigen Kundennummer (der Hash-Schlüssel ), würden sie es um 300 modulieren, um festzustellen, in welchem Aktenschrank sich der Kundenordner befindet. Als sie den Aktenschrank öffneten, stellten sie fest, dass er viele nach Kundennummern geordnete Ordner enthielt. Beim Durchsuchen der Unterlagen würden sie schnell den Kundenordner finden und ihn herausholen.

In unserem realen Beispiel ist unser Eimer sind Ablageschränke und unser Datensätze sind Aktenordner .

---

Es ist wichtig, sich daran zu erinnern, dass Computer (und ihre Algorithmen) besser mit Zahlen umgehen können als mit Zeichenketten. Daher ist der Zugriff auf ein großes Array mit Hilfe eines Indexes wesentlich schneller als der sequentielle Zugriff.

Wie Simon bereits erwähnt hat die meiner Meinung nach sehr wichtig ist, dass der Hashing-Teil darin besteht, einen großen Raum (beliebiger Länge, in der Regel Zeichenketten usw.) umzuwandeln und ihn auf einen kleinen Raum (bekannter Größe, in der Regel Zahlen) für die Indexierung abzubilden. Dies ist sehr wichtig zu wissen!

Im obigen Beispiel werden also die etwa 30.000 möglichen Kunden auf einen kleineren Raum abgebildet.

---

Der Grundgedanke dabei ist, den gesamten Datensatz in Segmente zu unterteilen, um die eigentliche Suche zu beschleunigen, die in der Regel sehr zeitaufwändig ist. In unserem obigen Beispiel würde jeder der 300 Aktenschränke (statistisch gesehen) etwa 100 Datensätze enthalten. Das Durchsuchen (unabhängig von der Reihenfolge) von 100 Datensätzen ist viel schneller als das Durchsuchen von 30.000.

Sie haben vielleicht bemerkt, dass einige dies bereits tun. Aber anstatt eine Hash-Methode zu entwickeln, um einen Hash-Schlüssel zu erzeugen, verwenden sie in den meisten Fällen einfach den ersten Buchstaben des Nachnamens. Wenn Sie also 26 Aktenschränke haben, von denen jeder einen Buchstaben von A bis Z enthält, haben Sie theoretisch nur Ihre Daten segmentiert und den Ablage- und Abrufprozess verbessert.

Ich hoffe, das hilft,

Jeach!

Answer 3

Dies stellt sich als ein ziemlich tiefes Gebiet der Theorie heraus, aber der Grundriss ist einfach.

Im Grunde genommen ist eine Hash-Funktion nur eine Funktion, die Dinge aus einem Bereich (z. B. Zeichenketten beliebiger Länge) in einen für die Indizierung nützlichen Bereich (z. B. ganze Zahlen ohne Vorzeichen) überträgt.

Wenn Sie nur einen kleinen Bereich von Dingen zu hashen haben, können Sie diese Dinge einfach als Ganzzahlen interpretieren und fertig (z.B. 4-Byte-Strings)

In der Regel hat man aber einen viel größeren Raum zur Verfügung. Wenn der Raum der Dinge, die Sie als Schlüssel zulassen, größer ist als der Raum der Dinge, die Sie zum Indizieren verwenden (Ihre uint32's oder was auch immer), dann können Sie unmöglich einen eindeutigen Wert für jeden einzelnen haben. Wenn zwei oder mehr Dinge zum gleichen Ergebnis führen, müssen Sie die Redundanz in geeigneter Weise behandeln (dies wird üblicherweise als Kollision bezeichnet, und wie Sie damit umgehen oder nicht, hängt davon ab, wofür Sie den Hash verwenden).

Das bedeutet, dass es unwahrscheinlich sein sollte, dass das gleiche Ergebnis erzielt wird, und Sie möchten wahrscheinlich auch, dass die Hash-Funktion schnell ist.

Das Gleichgewicht zwischen diesen beiden Eigenschaften (und einigen anderen) hat viele Menschen beschäftigt!

In der Praxis sollten Sie in der Lage sein, eine Funktion zu finden, von der bekannt ist, dass sie für Ihre Anwendung gut funktioniert, und diese zu verwenden.

Damit dies als Hashtabelle funktioniert: Stellen Sie sich vor, dass Sie sich nicht um die Speichernutzung kümmern. Dann können Sie ein Array so lang wie Ihre Indizierung gesetzt (alle uint32, zum Beispiel) erstellen. Wenn man der Tabelle etwas hinzufügt, wird der Schlüssel mit einem Hash versehen und das Array mit diesem Index betrachtet. Wenn es dort nichts gibt, fügen Sie Ihren Wert dort ein. Wenn dort bereits etwas vorhanden ist, fügen Sie diesen neuen Eintrag zu einer Liste von Dingen an dieser Adresse hinzu, zusammen mit genügend Informationen (Ihr ursprünglicher Schlüssel oder etwas Gescheites), um herauszufinden, welcher Eintrag tatsächlich zu welchem Schlüssel gehört.

Wenn Sie also einen langen Weg gehen, ist jeder Eintrag in Ihrer Hashtabelle (dem Array) entweder leer oder enthält einen Eintrag oder eine Liste von Einträgen. Das Abrufen ist so einfach wie die Indizierung in das Array und entweder die Rückgabe des Wertes oder das Durchlaufen der Liste der Werte und die Rückgabe des richtigen Wertes.

In der Praxis ist dies natürlich nicht möglich, da zu viel Speicherplatz verschwendet wird. So tun Sie alles auf der Grundlage einer spärlichen Array (wo die einzigen Einträge sind die, die Sie tatsächlich verwenden, alles andere ist implizit Null).

Es gibt viele Pläne und Tricks, wie man das besser machen kann, aber das sind die Grundlagen.

Answer 4

Viele Antworten, aber keine von ihnen ist sehr visuell und Hash-Tabellen können bei der Visualisierung leicht "klicken".

Hash-Tabellen werden oft als Arrays von verknüpften Listen implementiert. Stellen wir uns eine Tabelle vor, in der die Namen von Personen gespeichert werden, so könnte sie nach einigen Einfügungen im Speicher wie folgt aussehen, wobei () -Eingeschlossene Zahlen sind Hash-Werte des Textes/Namens.

bucket#  bucket content / linked list

[0]      --> "sue"(780) --> null
[1]      null
[2]      --> "fred"(42) --> "bill"(9282) --> "jane"(42) --> null
[3]      --> "mary"(73) --> null
[4]      null
[5]      --> "masayuki"(75) --> "sarwar"(105) --> null
[6]      --> "margaret"(2626) --> null
[7]      null
[8]      --> "bob"(308) --> null
[9]      null

Ein paar Punkte:

• jeder der Array-Einträge (Indizes [0] , [1] ...) ist bekannt als Eimer und beginnt eine - möglicherweise leere - verknüpfte Liste von Werte (alias Elemente in diesem Beispiel - die Menschen Namen )
• jeder Wert (z.B. "fred" mit Hash 42 ) ist mit dem Eimer [hash % number_of_buckets] z.B.. 42 % 10 == [2] ; % ist die Modulo-Operator - der Restbetrag, wenn er durch die Anzahl der Eimer geteilt wird
• mehrere Datenwerte können kollidieren an und aus demselben Bucket verknüpft werden, meist weil ihre Hash-Werte nach der Modulo-Operation kollidieren (z. B. 42 % 10 == [2] et 9282 % 10 == [2] ), sondern gelegentlich auch, weil die Hash-Werte gleich sind (z. B. "fred" y "jane" beide mit Raute dargestellt 42 oben)
  • Die meisten Hash-Tabellen handhaben Kollisionen - mit leicht verringerter Leistung, aber ohne funktionale Verwirrung - indem sie den vollständigen Wert (hier Text) eines gesuchten oder eingefügten Wertes mit jedem Wert vergleichen, der sich bereits in der verknüpften Liste am Hash-Bucket befindet.

Die Länge der verknüpften Liste bezieht sich auf den Auslastungsfaktor, nicht auf die Anzahl der Werte.

Wenn die Tabellengröße wächst, neigen Hash-Tabellen, die wie oben implementiert sind, dazu, ihre Größe zu ändern (d.h. ein größeres Array von Buckets zu erstellen, daraus neue/aktualisierte verknüpfte Listen zu erstellen und das alte Array zu löschen), um das Verhältnis von Werten zu Buckets (auch bekannt als Belastungsfaktor ) im Bereich von 0,5 bis 1,0.

Hans gibt die tatsächliche Formel für andere Belastungsfaktoren in einem Kommentar weiter unten an, aber als Richtwerte: mit Belastungsfaktor 1 und einer kryptographischen Hash-Funktion werden 1/e (~36,8%) der Buckets tendenziell leer sein, weitere 1/e (~36,8%) haben ein Element, 1/(2e) oder ~18,4% zwei Elemente, 1/(3!e) etwa 6,1% drei Elemente, 1/(4!e) oder ~1,5% vier Elemente, 1/(5!e) ~,3% haben fünf usw.. - Die durchschnittliche Kettenlänge von nicht leeren Eimern beträgt ~1,58, unabhängig davon, wie viele Elemente in der Tabelle enthalten sind (d. h. ob es 100 Elemente und 100 Eimer oder 100 Millionen Elemente und 100 Millionen Eimer gibt), weshalb wir sagen, dass lookup/insert/erase O (1) konstante Zeitvorgänge.

Wie eine Hashtabelle Schlüssel mit Werten verknüpfen kann

Bei einer Hash-Tabellen-Implementierung, wie sie oben beschrieben wurde, können wir uns vorstellen, einen Wertetyp wie `struct Value { string name; int age; };` zu erstellen und Gleichheitsvergleichs- und Hash-Funktionen zu verwenden, die nur das Feld `name` betrachten (und das Alter ignorieren), und dann passiert etwas Wunderbares: Wir können `Value`-Datensätze wie `{"sue", 63}` in der Tabelle speichern, dann später nach "sue" suchen, ohne ihr Alter zu kennen, den gespeicherten Wert finden und ihr Alter wiederherstellen oder sogar aktualisieren - Alles Gute zum Geburtstag Sue - was interessanterweise den Hash-Wert nicht ändert, so dass wir Sues Datensatz nicht in einen anderen Bucket verschieben müssen.

Wenn wir dies tun, verwenden wir die Hashtabelle als eine Assoziationsbehälter alias Karte und die darin gespeicherten Werte können als aus einem Schlüssel (der Name) und einem oder mehreren anderen Feldern, die - verwirrenderweise - immer noch als Wert (in meinem Beispiel, nur das Alter). Eine Hash-Tabellen-Implementierung, die als Map verwendet wird, ist bekannt als eine Hash-Karte .

Dies steht im Gegensatz zu dem Beispiel weiter oben in dieser Antwort, in dem wir diskrete Werte wie "sue" gespeichert haben, die man sich als eigenen Schlüssel vorstellen kann: Diese Art der Verwendung ist als Hash-Satz .

Es gibt auch andere Möglichkeiten, eine Hashtabelle zu implementieren

Nicht alle Hashtabellen verwenden verknüpfte Listen (bekannt als getrennte Verkettung ), aber die meisten Allzweckgeräte tun dies, da die wichtigste Alternative geschlossenes Hashing (alias offene Adressierung ) - insbesondere bei unterstützten Löschvorgängen - hat weniger stabile Leistungseigenschaften bei kollisionsanfälligen Schlüsseln/Hash-Funktionen.

---

Ein paar Worte zu Hash-Funktionen

Starkes Hashing...

Eine allgemeine Hash-Funktion, die im schlimmsten Fall Kollisionen minimiert, hat die Aufgabe, die Schlüssel nach dem Zufallsprinzip in die Hash-Tabellenfächer zu verteilen und dabei immer denselben Hash-Wert für denselben Schlüssel zu erzeugen. Selbst wenn sich auch nur ein Bit im Schlüssel ändert, würde dies im Idealfall - zufällig - etwa die Hälfte der Bits im resultierenden Hash-Wert umkehren.

Normalerweise wird das mit einer Mathematik inszeniert, die zu kompliziert ist, als dass ich sie verstehen könnte. Ich werde eine leicht verständliche Methode erwähnen - nicht die skalierbarste oder cachefreundlichste, aber von Natur aus elegant (wie die Verschlüsselung mit einem One-Time-Pad!) - da ich denke, dass sie die oben erwähnten wünschenswerten Qualitäten verdeutlicht. Nehmen wir an, Sie würden 64-Bit-Hashing betreiben double s - Sie könnten 8 Tabellen mit jeweils 256 Zufallszahlen erstellen (Code unten) und dann jede 8-Bit/1-Byte-Scheibe der double um in eine andere Tabelle zu indizieren, wobei die nachgeschlagenen Zufallszahlen XOR-verknüpft werden. Mit diesem Ansatz ist es einfach zu erkennen, dass ein Bit (im Sinne von Binärziffern), das sich irgendwo in der Tabelle double führt dazu, dass eine andere Zufallszahl in einer der Tabellen nachgeschlagen wird und der Endwert völlig unkorreliert ist.

// note caveats above: cache unfriendly (SLOW) but strong hashing...
std::size_t random[8][256] = { ...random data... };
auto p = (const std::byte*)&my_double;
size_t hash = random[0][p[0]] ^
              random[1][p[1]] ^
              ... ^
              random[7][p[7]];

Schwaches, aber oft schnelles Hashing...

Die Hashing-Funktionen vieler Bibliotheken leiten Ganzzahlen unverändert durch (bekannt als trivial o Identität Hash-Funktion); dies ist das andere Extrem zum oben beschriebenen starken Hashing. Ein Identitätshash ist extrem Im schlimmsten Fall kommt es zu Kollisionen, aber man hofft, dass im relativ häufigen Fall von Integer-Schlüsseln, die dazu neigen, inkrementiert zu werden (vielleicht mit einigen Lücken), diese in aufeinanderfolgende Buckets abgebildet werden und weniger leere Bereiche übrig bleiben als beim zufälligen Hashing (unsere ~36,8 % bei Lastfaktor 1, wie bereits erwähnt), wodurch weniger Kollisionen und weniger längere verknüpfte Listen mit kollidierenden Elementen entstehen als bei zufälligen Abbildungen. Außerdem spart es die Zeit, die für die Generierung eines starken Hashes benötigt wird, und wenn die Schlüssel in der richtigen Reihenfolge nachgeschlagen werden, werden sie in nahegelegenen Buckets im Speicher gefunden, was die Cache-Treffer verbessert. Wenn die Schlüssel nicht Die Hoffnung ist, dass sie zufällig genug sind, dass sie keine starke Hash-Funktion benötigen, um ihre Platzierung in den Buckets völlig zufällig zu machen.

Answer 5

Ihr seid der Erklärung schon sehr nahe, aber es fehlen noch ein paar Dinge. Die Hashtabelle ist nur ein Array. Das Array selbst wird etwas in jedem Slot enthalten. Zumindest werden Sie den Hashwert oder den Wert selbst in diesem Slot speichern. Darüber hinaus können Sie auch eine verknüpfte/verkettete Liste von Werten speichern, die in diesem Slot kollidiert sind, oder Sie können die Methode der offenen Adressierung verwenden. Sie können auch einen Zeiger oder Zeiger auf andere Daten speichern, die Sie aus diesem Slot abrufen wollen.

Es ist wichtig zu beachten, dass der Hashwert selbst im Allgemeinen nicht den Slot angibt, in den der Wert eingefügt werden soll. Ein Hashwert kann zum Beispiel ein negativer Integer-Wert sein. Offensichtlich kann eine negative Zahl nicht auf einen Array-Speicherplatz verweisen. Außerdem sind Hash-Werte oft größer als die verfügbaren Slots. Daher muss eine weitere Berechnung von der Hashtabelle selbst durchgeführt werden, um herauszufinden, in welchen Slot der Wert eingefügt werden soll. Dies geschieht mit einer mathematischen Modulus-Operation wie:

uint slotIndex = hashValue % hashTableSize;

Dieser Wert ist das Feld, in das der Wert eingefügt wird. Wenn bei der offenen Adressierung der Slot bereits mit einem anderen Hash-Wert und/oder anderen Daten gefüllt ist, wird die Modulus-Operation noch einmal ausgeführt, um den nächsten Slot zu finden:

slotIndex = (remainder + 1) % hashTableSize;

Ich nehme an, dass es andere, fortschrittlichere Methoden zur Bestimmung des Slot-Index gibt, aber dies ist die gängigste Methode, die ich kenne... ich wäre an anderen interessiert, die besser funktionieren.

Bei der Modulus-Methode wird bei einer Tabelle der Größe 1000 jeder Hash-Wert, der zwischen 1 und 1000 liegt, in den entsprechenden Slot aufgenommen. Alle negativen Werte und alle Werte größer als 1000 sind potentiell kollidierende Slot-Werte. Die Wahrscheinlichkeit, dass dies geschieht, hängt sowohl von Ihrer Hash-Methode als auch von der Gesamtzahl der Elemente ab, die Sie der Hash-Tabelle hinzufügen. Im Allgemeinen ist es am besten, die Größe der Hashtabelle so zu wählen, dass die Gesamtzahl der hinzugefügten Werte nur etwa 70 % ihrer Größe beträgt. Wenn Ihre Hash-Funktion die Werte gleichmäßig verteilt, kommt es in der Regel nur zu sehr wenigen bis gar keinen Kollisionen zwischen Eimer und Slot, und sie ist sowohl bei Such- als auch bei Schreibvorgängen sehr schnell. Wenn die Gesamtzahl der hinzuzufügenden Werte nicht im Voraus bekannt ist, sollten Sie mit beliebigen Mitteln eine Schätzung vornehmen und die Größe der Hashtabelle anpassen, sobald die Anzahl der hinzugefügten Elemente 70 % der Kapazität erreicht.

Ich hoffe, das war hilfreich.

PS - In C# wird die GetHashCode() Methode ist ziemlich langsam und führt unter vielen Bedingungen, die ich getestet habe, zu tatsächlichen Wertkollisionen. Um wirklich Spaß zu haben, erstellen Sie Ihre eigene Hashfunktion und versuchen Sie, sie dazu zu bringen, dass sie bei den spezifischen Daten, die Sie hashen, NIE kollidiert, schneller als GetHashCode läuft und eine ziemlich gleichmäßige Verteilung hat. Ich habe das mit Long- statt Int-Hashcode-Werten gemacht und es hat bei bis zu 32 Millionen Hashwerten in der Hashtabelle mit 0 Kollisionen ganz gut funktioniert. Leider kann ich den Code nicht weitergeben, da er meinem Arbeitgeber gehört... aber ich kann verraten, dass es für bestimmte Datendomänen möglich ist. Wenn Sie dies erreichen können, ist die Hashtabelle SEHR schnell :)