ROB BOWDEN: Hallo. Ich bin Rob, und seien wir Hash diese Lösung aus. Also hier werden wir umsetzen eine allgemeine Hash-Tabelle. Wir sehen, dass die Struktur-Knoten der Hash Tabelle wird wie folgt aussehen. Also es geht um einen char Wort haben Array der Größe Länge plus 1. Vergessen Sie nicht die 1, da die maximale Wort in dem Wörterbuch 45 Zeichen, und dann werden wir brauchen ein zusätzliches Zeichen für die 0 Backslash. 

Und dann unsere Hash-Tabelle in jeder Eimer wird zu speichern, eine verkettete Liste von Knoten. Wir sind hier nicht linear Sondieren tun. Und so, um auf die nächste verlinken Element in den Eimer, brauchen wir eine struct node * next. Also das ist, was ein Knoten aussieht. Nun, hier ist die Erklärung der Hash-Tabelle. Es geht um 16.384 Eimer haben, aber diese Zahl ist nicht wirklich wichtig. Und schließlich werden wir haben die globale Variable hashtable_size, die wird zu starten als 0, und es ist gehen, um zu verfolgen, wie viele Wörter waren im Wörterbuch. Gut. 

Werfen wir also einen Blick auf Last. So bemerken, dass die Last, es gibt einen bool. Sie kehren dann, wenn es erfolgreich war geladen und ansonsten false. Und es dauert eine char * Sterne Wörterbuch, das das Wörterbuch dass wir wollen, sich zu öffnen. Also das ist das erste, was wir tun werden. Wir werden das Wörterbuch für fopen Lesen, und wir gehen zu müssen um sicherzustellen, dass es gelang so, wenn es NULL zurück, dann haben wir nicht das Wörterbuch erfolgreich öffnen und wir müssen return false. 

Aber unter der Annahme, dass es erfolgreich war offen ist, dann lesen wollen wir die Wörterbuch. So halten Looping, bis wir einige Grund, aus dieser zu brechen Schleife, die wir sehen. So halten Looping, und jetzt werden wir um einen einzelnen Knoten malloc. Und natürlich, um Check-Fehler müssen wir wieder so, wenn mallocing war nicht erfolgreich und wir, die wir jeden Knoten entladen möchten passiert malloc vor, schließen Sie die Wörterbuch-und Rück falsch. 

Aber ignorieren, dass, vorausgesetzt, wir gelang es, dann wollen wir nutzen fscanf ein einziges Wort aus lesen Sie unsere Lexikon in unsere Knoten. Also denken Sie daran, dass der Eintritt-> Wort ist der char Wort Puffer der Größe Länge plus eine, die wir gehen, um speichern Sie das Wort in. So fscanf wird zu 1 zurück, so lange da es in der Lage, erfolgreich gelesen ein Wort aus der Datei. 

Wenn entweder ein Fehler passiert, oder wir erreichen das Ende der Datei, wird es nicht 1 zurückzukehren, in dem Fall, wenn es nicht 1 zurück, sind wir endlich zu brechen aus dieser while-Schleife. So sehen wir, dass, wenn wir erfolgreich haben lesen Sie ein Wort in entry-> Wort, dann werden wir auf Such Wort, dass mit unserem Hash-Funktion. Werfen wir einen Blick auf die Hash-Funktion. 

So können Sie nicht wirklich brauchen um das zu verstehen. Und tatsächlich, wir haben nur diese gezogen Hash-Funktion aus dem Internet. Das einzige, was Sie brauchen, um zu erkennen, ist dass das dauert ein char * Wort, so dass es sie einen String als Eingabe und Rückgabe eines unsigned int als Ausgabe. Also das ist alles eine Hash-Funktion, ist es erfolgt in einem Eingabe, gibt es Ihnen eine Index in die Hash-Tabelle. Beachten Sie, dass wir durch num_buckets Modding so der Hash-Wert zurück tatsächlich ist ein Index in die Hash-Tabelle, und nicht über die Index Grenzen des Arrays. 

Also da Hash-Funktion, werden wir das Wort, das wir lesen hash aus dem Wörterbuch und dann werden wir zu bedienen, dass zu legen Sie die Eintrag in der Hash-Tabelle. Nun ist die aktuelle Hash-Hash-Tabelle Linked-List in der Hash-Tabelle, und es ist sehr möglich, dass nur NULL ist. Wir wollen unseren Eintrag bei der einfügen Anfang dieses verknüpfte Liste, und so werden wir unsere aktuellen Eintrag haben zeigen auf, was der Hash-Tabelle derzeit Punkte auf und dann werden wir speichern in der Hash-Tabelle in der Hash der aktuelle Eintrag. 

Also diese beiden Linien erfolgreich einfügen der Eintrag am Anfang der verketteten Liste an diesem Index in der Hash-Tabelle. Sobald wir damit fertig sind, wissen wir, dass wir fanden ein anderes Wort in der Wörterbuch und wir wieder zu erhöhen. So halten wir tun, bis fscanf kehrt schließlich etwas nicht eins zu die Stelle erinnern, dass wir Eintritt frei, so dass hier auf, malloced wir ein Eintritt und wir haben versucht, etwas zu lesen aus dem Wörterbuch. Und haben wir nicht erfolgreich gelesen etwas aus dem Wörterbuch in dem Fall müssen wir den Eintrag, den wir frei nie wirklich in die Hash-Tabelle setzen und schließlich brechen. 

Sobald wir ausbrechen, müssen wir sehen, na ja, haben wir ausbrechen, weil es wurde ein Fehler beim Lesen aus der Datei oder haben wir ausbrechen, weil wir erreicht das Ende der Datei? Wenn es ein Fehler ist, dann wollen wir return false, weil Last nicht folgen, und in dem Prozess, wir wollen entladen all die Worte, die wir lesen in und schließen Sie die Wörterbuchdatei. Angenommen, wir haben, gelingt es uns nur noch brauchen, um das Wörterbuch zu schließen Datei, und endlich wieder wahr, da wir haben das erfolgreich geladen Wörterbuch. Und das ist es für die Last. 

So, jetzt zu prüfen, da eine geladene Hash-Tabelle, wird wie folgt aussehen. So überprüfen Sie, es gibt einen bool, die wird, um anzuzeigen, ob der gebenen char * Wort, ob die gebenen String ist im Wörterbuch. So dass, wenn es in dem Wörterbuch ist, wenn es in unserer Hash-Tabelle, werden wir zurückkehren wahr, und wenn es nicht ist, wir false zurück. Angesichts dieser übergebenen Wort, wir sind gehen, um das Wort Hash. 

Nun, das ist eine wichtige Sache zu erkennen, dass in der Last, wussten wir, dass alle die Worte wollten unteren Fall sein, aber hier sind wir nicht so sicher. Wenn wir einen Blick auf unsere Hash-Funktion, unsere Hash-Funktion tatsächlich wird auf die Schreibweise jedes Zeichen des Wortes. Also unabhängig von der Aktivierung von Wort, ist unser Hash-Funktion zu gehen geben den gleichen Index für was auch immer die Kapitalisierung ist, wie es hätte für eine komplett in Kleinbuchstaben zurück Version des Wortes. Gut. 

Also das ist unsere Index. Es ist die Hash-Tabelle für dieses Wort. Nun, diese for-Schleife wird um die verknüpfte Liste über das war an diesem Index. So bemerken wir Initialisierung Eintrag zu diesem Index zu verweisen. Wir werden weiterhin während Eintrag tut nicht gleich NULL, und denken Sie daran, dass Aktualisierung der Zeiger in unserem verketteten Liste Eintrag gleich entry-> nächsten, so haben unsere aktuellen Einstieg in die nächste Element in verketteten Liste. Gut. 

So dass für jeden Eintrag in der verketteten Liste, wir werden strcasecmp verwenden. Es ist nicht strcmp weil wieder einmal, wir wollen die Dinge tun, ohne Berücksichtigung der Groß-/Kleinschreibung. So verwenden wir strcasecmp, um das Wort zu vergleichen dass wir diese Funktion übergeben gegen das Wort, dass ist in diesem Eintrag. Wenn es 0 zurückkehrt, bedeutet, dass es ein Spiel, in welchem ​​Fall wir wollen return true. Wir fanden die erfolgreich Wort in unserer Hash-Tabelle. 

Wenn es nicht ein Spiel, dann sind wir werde Schleife wieder und sehen Sie sich die nächsten Eintrag. Und wir werden Looping, während es weiterhin Einträge in dieser verketteten Liste. Was passiert, wenn wir brechen aus dieser for-Schleife? Das heißt, wir haben einen Eintrag nicht zu finden, die abgestimmt dieses Wort, in welchem ​​Fall wir false zurück, um anzuzeigen, dass unsere Hash-Tabelle nicht dieses Wort enthalten. Und das ist es für den Check. Gut. 

Werfen wir also einen Blick auf Größe. Nun wird Größe wird ziemlich einfach da in Last erinnern, für jedes Wort wir fanden wir eine globale erhöht Variable hashtable_size. Also die Größe Funktion ist nur gehen, dass die globale zurückkehren variabel, und das ist es. 

Nun endlich, wir müssen entladen, die Wörterbuch einmal alles fertig ist. Also, wie sollen wir das tun? Genau hier sind wir über alle Looping Eimer unseren Hash-Tabelle. So gibt es num_buckets Eimer. Und für jede verknüpfte Liste in unserem Hash Tisch, wir eine Schleife über das Gehen Gesamtheit der verketteten Liste jedes Element zu befreien. Jetzt müssen wir vorsichtig sein, so dass wir hier eine temporäre Variable, ist Speichern der Zeiger auf die nächste Element in der verketteten Liste. Und dann sind wir frei gehen das aktuelle Element. 

Wir müssen sicher sein, wir tun dies, weil wir können nicht nur kostenlos das aktuelle Element und dann versuchen, die nächste Zeiger zugreifen da, wenn wir es befreit die Speicher wird ungültig. Also müssen wir einen Zeiger auf herum zu halten das nächste Element, dann werden wir frei kann der aktuelle Element, und dann werden wir aktualisieren können unsere aktuelle Element zu Punkt das nächste Element. 

Wir werden während Schleife gibt es Elemente in dieser verketteten Liste. Wir werden das für alle verknüpften Listen tun die Hash-Tabelle, und wenn wir fertig sind mit, dass wir vollständig entladen haben die Hash-Tabelle, und wir sind fertig. So ist es unmöglich, jemals entlädt false zurück, und wenn wir fertig sind, werden wir nur true zurück.