1
00:00:00,000 --> 00:00:11,856

2
00:00:11,856 --> 00:00:13,050
>> ROB BOWDEN: Hallo.

3
00:00:13,050 --> 00:00:16,210
Ich bin Rob, und seien wir Hash
diese Lösung aus.

4
00:00:16,210 --> 00:00:20,070
Also hier werden wir umsetzen
eine allgemeine Hash-Tabelle.

5
00:00:20,070 --> 00:00:24,090
Wir sehen, dass die Struktur-Knoten der Hash
Tabelle wird wie folgt aussehen.

6
00:00:24,090 --> 00:00:28,710
Also es geht um einen char Wort haben
Array der Größe Länge plus 1.

7
00:00:28,710 --> 00:00:32,259
Vergessen Sie nicht die 1, da die maximale
Wort in dem Wörterbuch 45

8
00:00:32,259 --> 00:00:35,110
Zeichen, und dann werden wir
brauchen ein zusätzliches Zeichen für die

9
00:00:35,110 --> 00:00:37,070
0 Backslash.

10
00:00:37,070 --> 00:00:40,870
>> Und dann unsere Hash-Tabelle in jeder
Eimer wird zu speichern, eine

11
00:00:40,870 --> 00:00:42,320
verkettete Liste von Knoten.

12
00:00:42,320 --> 00:00:44,420
Wir sind hier nicht linear Sondieren tun.

13
00:00:44,420 --> 00:00:48,430
Und so, um auf die nächste verlinken
Element in den Eimer, brauchen wir eine

14
00:00:48,430 --> 00:00:51,110
struct node * next.

15
00:00:51,110 --> 00:00:53,090
Also das ist, was ein Knoten aussieht.

16
00:00:53,090 --> 00:00:56,180
Nun, hier ist die Erklärung
der Hash-Tabelle.

17
00:00:56,180 --> 00:01:01,910
Es geht um 16.384 Eimer haben, aber
diese Zahl ist nicht wirklich wichtig.

18
00:01:01,910 --> 00:01:05,450
Und schließlich werden wir haben die
globale Variable hashtable_size, die

19
00:01:05,450 --> 00:01:08,640
wird zu starten als 0, und es ist
gehen, um zu verfolgen, wie viele Wörter

20
00:01:08,640 --> 00:01:10,080
waren im Wörterbuch.

21
00:01:10,080 --> 00:01:10,760
Gut.

22
00:01:10,760 --> 00:01:13,190
>> Werfen wir also einen Blick auf Last.

23
00:01:13,190 --> 00:01:16,390
So bemerken, dass die Last,
es gibt einen bool.

24
00:01:16,390 --> 00:01:20,530
Sie kehren dann, wenn es erfolgreich war
geladen und ansonsten false.

25
00:01:20,530 --> 00:01:23,990
Und es dauert eine char * Sterne
Wörterbuch, das das Wörterbuch

26
00:01:23,990 --> 00:01:25,280
dass wir wollen, sich zu öffnen.

27
00:01:25,280 --> 00:01:27,170
Also das ist das erste, was
wir tun werden.

28
00:01:27,170 --> 00:01:30,420
Wir werden das Wörterbuch für fopen
Lesen, und wir gehen zu müssen

29
00:01:30,420 --> 00:01:34,700
um sicherzustellen, dass es gelang so, wenn
es NULL zurück, dann haben wir nicht

30
00:01:34,700 --> 00:01:37,440
das Wörterbuch erfolgreich öffnen
und wir müssen return false.

31
00:01:37,440 --> 00:01:41,580
>> Aber unter der Annahme, dass es erfolgreich war
offen ist, dann lesen wollen wir die

32
00:01:41,580 --> 00:01:42,400
Wörterbuch.

33
00:01:42,400 --> 00:01:46,210
So halten Looping, bis wir einige
Grund, aus dieser zu brechen

34
00:01:46,210 --> 00:01:47,570
Schleife, die wir sehen.

35
00:01:47,570 --> 00:01:51,780
So halten Looping, und jetzt werden wir
um einen einzelnen Knoten malloc.

36
00:01:51,780 --> 00:01:56,800
Und natürlich, um Check-Fehler müssen wir
wieder so, wenn mallocing war nicht erfolgreich

37
00:01:56,800 --> 00:02:00,660
und wir, die wir jeden Knoten entladen möchten
passiert malloc vor, schließen Sie die

38
00:02:00,660 --> 00:02:02,590
Wörterbuch-und Rück falsch.

39
00:02:02,590 --> 00:02:07,440
>> Aber ignorieren, dass, vorausgesetzt, wir
gelang es, dann wollen wir nutzen fscanf

40
00:02:07,440 --> 00:02:12,400
ein einziges Wort aus lesen Sie unsere
Lexikon in unsere Knoten.

41
00:02:12,400 --> 00:02:17,310
Also denken Sie daran, dass der Eintritt-> Wort ist der char
Wort Puffer der Größe Länge plus

42
00:02:17,310 --> 00:02:20,300
eine, die wir gehen, um
speichern Sie das Wort in.

43
00:02:20,300 --> 00:02:25,280
So fscanf wird zu 1 zurück, so lange
da es in der Lage, erfolgreich gelesen ein

44
00:02:25,280 --> 00:02:26,750
Wort aus der Datei.

45
00:02:26,750 --> 00:02:31,030
>> Wenn entweder ein Fehler passiert, oder wir erreichen
das Ende der Datei, wird es nicht

46
00:02:31,030 --> 00:02:34,950
1 zurückzukehren, in dem Fall, wenn es nicht
1 zurück, sind wir endlich zu brechen

47
00:02:34,950 --> 00:02:37,280
aus dieser while-Schleife.

48
00:02:37,280 --> 00:02:42,770
So sehen wir, dass, wenn wir erfolgreich haben
lesen Sie ein Wort in

49
00:02:42,770 --> 00:02:48,270
entry-> Wort, dann werden wir auf Such
Wort, dass mit unserem Hash-Funktion.

50
00:02:48,270 --> 00:02:49,580
Werfen wir einen Blick auf
die Hash-Funktion.

51
00:02:49,580 --> 00:02:52,430

52
00:02:52,430 --> 00:02:55,610
>> So können Sie nicht wirklich brauchen
um das zu verstehen.

53
00:02:55,610 --> 00:02:59,460
Und tatsächlich, wir haben nur diese gezogen
Hash-Funktion aus dem Internet.

54
00:02:59,460 --> 00:03:04,010
Das einzige, was Sie brauchen, um zu erkennen, ist
dass das dauert ein char * Wort,

55
00:03:04,010 --> 00:03:08,960
so dass es sie einen String als Eingabe und
Rückgabe eines unsigned int als Ausgabe.

56
00:03:08,960 --> 00:03:12,360
Also das ist alles eine Hash-Funktion, ist es
erfolgt in einem Eingabe, gibt es Ihnen eine

57
00:03:12,360 --> 00:03:14,490
Index in die Hash-Tabelle.

58
00:03:14,490 --> 00:03:18,530
Beachten Sie, dass wir durch num_buckets Modding
so der Hash-Wert zurück

59
00:03:18,530 --> 00:03:21,730
tatsächlich ist ein Index in die Hash-Tabelle,
und nicht über die Index

60
00:03:21,730 --> 00:03:24,320
Grenzen des Arrays.

61
00:03:24,320 --> 00:03:27,855
>> Also da Hash-Funktion, werden wir
das Wort, das wir lesen hash

62
00:03:27,855 --> 00:03:31,700
aus dem Wörterbuch und dann werden wir
zu bedienen, dass zu legen Sie die

63
00:03:31,700 --> 00:03:33,750
Eintrag in der Hash-Tabelle.

64
00:03:33,750 --> 00:03:38,830
Nun ist die aktuelle Hash-Hash-Tabelle
Linked-List in der Hash-Tabelle, und

65
00:03:38,830 --> 00:03:41,410
es ist sehr möglich, dass nur NULL ist.

66
00:03:41,410 --> 00:03:45,640
Wir wollen unseren Eintrag bei der einfügen
Anfang dieses verknüpfte Liste, und so

67
00:03:45,640 --> 00:03:48,910
werden wir unsere aktuellen Eintrag haben
zeigen auf, was der Hash-Tabelle derzeit

68
00:03:48,910 --> 00:03:54,030
Punkte auf und dann werden wir speichern
in der Hash-Tabelle in der Hash

69
00:03:54,030 --> 00:03:55,350
der aktuelle Eintrag.

70
00:03:55,350 --> 00:03:59,320
>> Also diese beiden Linien erfolgreich einfügen
der Eintrag am Anfang der

71
00:03:59,320 --> 00:04:02,270
verketteten Liste an diesem Index
in der Hash-Tabelle.

72
00:04:02,270 --> 00:04:04,900
Sobald wir damit fertig sind, wissen wir,
dass wir fanden ein anderes Wort in der

73
00:04:04,900 --> 00:04:07,800
Wörterbuch und wir wieder zu erhöhen.

74
00:04:07,800 --> 00:04:13,960
So halten wir tun, bis fscanf
kehrt schließlich etwas nicht eins zu

75
00:04:13,960 --> 00:04:18,560
die Stelle erinnern, dass wir
Eintritt frei, so dass hier auf, malloced wir ein

76
00:04:18,560 --> 00:04:21,329
Eintritt und wir haben versucht, etwas zu lesen
aus dem Wörterbuch.

77
00:04:21,329 --> 00:04:24,110
Und haben wir nicht erfolgreich gelesen
etwas aus dem Wörterbuch in dem

78
00:04:24,110 --> 00:04:27,440
Fall müssen wir den Eintrag, den wir frei
nie wirklich in die Hash-Tabelle setzen

79
00:04:27,440 --> 00:04:29,110
und schließlich brechen.

80
00:04:29,110 --> 00:04:32,750
>> Sobald wir ausbrechen, müssen wir sehen, na ja,
haben wir ausbrechen, weil es

81
00:04:32,750 --> 00:04:35,840
wurde ein Fehler beim Lesen aus der Datei oder
haben wir ausbrechen, weil wir erreicht

82
00:04:35,840 --> 00:04:37,120
das Ende der Datei?

83
00:04:37,120 --> 00:04:40,150
Wenn es ein Fehler ist, dann wollen wir
return false, weil Last nicht

84
00:04:40,150 --> 00:04:43,260
folgen, und in dem Prozess, wir wollen
entladen all die Worte, die wir lesen

85
00:04:43,260 --> 00:04:45,670
in und schließen Sie die Wörterbuchdatei.

86
00:04:45,670 --> 00:04:48,740
Angenommen, wir haben, gelingt es uns nur
noch brauchen, um das Wörterbuch zu schließen

87
00:04:48,740 --> 00:04:51,970
Datei, und endlich wieder wahr, da
wir haben das erfolgreich geladen

88
00:04:51,970 --> 00:04:53,040
Wörterbuch.

89
00:04:53,040 --> 00:04:54,420
Und das ist es für die Last.

90
00:04:54,420 --> 00:04:59,020
>> So, jetzt zu prüfen, da eine geladene Hash-Tabelle,
wird wie folgt aussehen.

91
00:04:59,020 --> 00:05:02,690
So überprüfen Sie, es gibt einen bool, die
wird, um anzuzeigen, ob der

92
00:05:02,690 --> 00:05:07,530
gebenen char * Wort, ob die
gebenen String ist im Wörterbuch.

93
00:05:07,530 --> 00:05:10,530
So dass, wenn es in dem Wörterbuch ist, wenn es
in unserer Hash-Tabelle, werden wir zurückkehren

94
00:05:10,530 --> 00:05:13,380
wahr, und wenn es nicht ist,
wir false zurück.

95
00:05:13,380 --> 00:05:17,770
Angesichts dieser übergebenen Wort, wir sind
gehen, um das Wort Hash.

96
00:05:17,770 --> 00:05:22,020
>> Nun, das ist eine wichtige Sache zu erkennen,
dass in der Last, wussten wir, dass alle

97
00:05:22,020 --> 00:05:25,820
die Worte wollten unteren Fall sein,
aber hier sind wir nicht so sicher.

98
00:05:25,820 --> 00:05:29,510
Wenn wir einen Blick auf unsere Hash-Funktion,
unsere Hash-Funktion tatsächlich

99
00:05:29,510 --> 00:05:32,700
wird auf die Schreibweise jedes Zeichen
des Wortes.

100
00:05:32,700 --> 00:05:37,580
Also unabhängig von der Aktivierung von
Wort, ist unser Hash-Funktion zu gehen

101
00:05:37,580 --> 00:05:42,270
geben den gleichen Index für was auch immer die
Kapitalisierung ist, wie es hätte

102
00:05:42,270 --> 00:05:45,280
für eine komplett in Kleinbuchstaben zurück
Version des Wortes.

103
00:05:45,280 --> 00:05:45,950
Gut.

104
00:05:45,950 --> 00:05:47,410
>> Also das ist unsere Index.

105
00:05:47,410 --> 00:05:49,790
Es ist die Hash-Tabelle für dieses Wort.

106
00:05:49,790 --> 00:05:52,940
Nun, diese for-Schleife wird
um die verknüpfte Liste über

107
00:05:52,940 --> 00:05:55,000
das war an diesem Index.

108
00:05:55,000 --> 00:05:59,630
So bemerken wir Initialisierung Eintrag
zu diesem Index zu verweisen.

109
00:05:59,630 --> 00:06:03,480
Wir werden weiterhin während Eintrag tut
nicht gleich NULL, und denken Sie daran, dass

110
00:06:03,480 --> 00:06:08,350
Aktualisierung der Zeiger in unserem verketteten Liste
Eintrag gleich entry-> nächsten, so haben

111
00:06:08,350 --> 00:06:13,840
unsere aktuellen Einstieg in die
nächste Element in verketteten Liste.

112
00:06:13,840 --> 00:06:14,400
Gut.

113
00:06:14,400 --> 00:06:19,150
>> So dass für jeden Eintrag in der verketteten Liste,
wir werden strcasecmp verwenden.

114
00:06:19,150 --> 00:06:23,780
Es ist nicht strcmp weil wieder einmal, wir
wollen die Dinge tun, ohne Berücksichtigung der Groß-/Kleinschreibung.

115
00:06:23,780 --> 00:06:28,830
So verwenden wir strcasecmp, um das Wort zu vergleichen
dass wir diese Funktion übergeben

116
00:06:28,830 --> 00:06:31,860
gegen das Wort, dass
ist in diesem Eintrag.

117
00:06:31,860 --> 00:06:35,570
Wenn es 0 zurückkehrt, bedeutet, dass es
ein Spiel, in welchem ​​Fall wir wollen

118
00:06:35,570 --> 00:06:36,630
return true.

119
00:06:36,630 --> 00:06:39,590
Wir fanden die erfolgreich
Wort in unserer Hash-Tabelle.

120
00:06:39,590 --> 00:06:43,040
>> Wenn es nicht ein Spiel, dann sind wir
werde Schleife wieder und sehen Sie sich die

121
00:06:43,040 --> 00:06:43,990
nächsten Eintrag.

122
00:06:43,990 --> 00:06:47,640
Und wir werden Looping, während es weiterhin
Einträge in dieser verketteten Liste.

123
00:06:47,640 --> 00:06:50,160
Was passiert, wenn wir brechen
aus dieser for-Schleife?

124
00:06:50,160 --> 00:06:55,110
Das heißt, wir haben einen Eintrag nicht zu finden, die
abgestimmt dieses Wort, in welchem ​​Fall

125
00:06:55,110 --> 00:07:00,220
wir false zurück, um anzuzeigen, dass unsere
Hash-Tabelle nicht dieses Wort enthalten.

126
00:07:00,220 --> 00:07:01,910
Und das ist es für den Check.

127
00:07:01,910 --> 00:07:02,540
Gut.

128
00:07:02,540 --> 00:07:04,790
>> Werfen wir also einen Blick auf Größe.

129
00:07:04,790 --> 00:07:09,280
Nun wird Größe wird ziemlich einfach
da in Last erinnern, für jedes Wort

130
00:07:09,280 --> 00:07:12,880
wir fanden wir eine globale erhöht
Variable hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Also die Größe Funktion ist nur
gehen, dass die globale zurückkehren

132
00:07:15,830 --> 00:07:18,150
variabel, und das ist es.

133
00:07:18,150 --> 00:07:22,300
>> Nun endlich, wir müssen entladen, die
Wörterbuch einmal alles fertig ist.

134
00:07:22,300 --> 00:07:25,340
Also, wie sollen wir das tun?

135
00:07:25,340 --> 00:07:30,440
Genau hier sind wir über alle Looping
Eimer unseren Hash-Tabelle.

136
00:07:30,440 --> 00:07:33,240
So gibt es num_buckets Eimer.

137
00:07:33,240 --> 00:07:37,490
Und für jede verknüpfte Liste in unserem Hash
Tisch, wir eine Schleife über das Gehen

138
00:07:37,490 --> 00:07:41,070
Gesamtheit der verketteten Liste
jedes Element zu befreien.

139
00:07:41,070 --> 00:07:46,070
Jetzt müssen wir vorsichtig sein, so dass wir hier
eine temporäre Variable, ist

140
00:07:46,070 --> 00:07:49,740
Speichern der Zeiger auf die nächste
Element in der verketteten Liste.

141
00:07:49,740 --> 00:07:52,140
Und dann sind wir frei gehen
das aktuelle Element.

142
00:07:52,140 --> 00:07:55,990
>> Wir müssen sicher sein, wir tun dies, weil wir
können nicht nur kostenlos das aktuelle Element

143
00:07:55,990 --> 00:07:59,260
und dann versuchen, die nächste Zeiger zugreifen
da, wenn wir es befreit die

144
00:07:59,260 --> 00:08:00,870
Speicher wird ungültig.

145
00:08:00,870 --> 00:08:04,990
Also müssen wir einen Zeiger auf herum zu halten
das nächste Element, dann werden wir frei kann der

146
00:08:04,990 --> 00:08:08,360
aktuelle Element, und dann werden wir aktualisieren können
unsere aktuelle Element zu Punkt

147
00:08:08,360 --> 00:08:09,590
das nächste Element.

148
00:08:09,590 --> 00:08:12,770
>> Wir werden während Schleife gibt es Elemente
in dieser verketteten Liste.

149
00:08:12,770 --> 00:08:16,450
Wir werden das für alle verknüpften Listen tun
die Hash-Tabelle, und wenn wir fertig sind

150
00:08:16,450 --> 00:08:20,180
mit, dass wir vollständig entladen haben
die Hash-Tabelle, und wir sind fertig.

151
00:08:20,180 --> 00:08:24,050
So ist es unmöglich, jemals entlädt
false zurück, und wenn wir fertig sind, werden wir

152
00:08:24,050 --> 00:08:25,320
nur true zurück.

153
00:08:25,320 --> 00:08:27,563