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

2
00:00:11,856 --> 00:00:13,050
>> ROB BOWDEN Cześć.

3
00:00:13,050 --> 00:00:16,210
Jestem Rob i hash niech
to rozwiązanie się.

4
00:00:16,210 --> 00:00:20,070
Więc idziemy do wdrożenia
Ogólnie tabeli mieszania.

5
00:00:20,070 --> 00:00:24,090
Widzimy, że struktura naszego węzła mieszania
tabela będzie wyglądać tak.

6
00:00:24,090 --> 00:00:28,710
Więc to będzie mieć słowo char
Tablica długości size plus 1.

7
00:00:28,710 --> 00:00:32,259
Nie zapomnij o 1 Ponieważ maksimum
słowo w słowniku jest 45

8
00:00:32,259 --> 00:00:35,110
znaków, a następnie jedziemy do
Potrzebujemy jeden dodatkowy znak dla

9
00:00:35,110 --> 00:00:37,070
odwrotny ukośnik 0.

10
00:00:37,070 --> 00:00:40,870
>> A potem nasz tabeli mieszania w każdym
wiadro będzie przechowywać

11
00:00:40,870 --> 00:00:42,320
powiązana lista węzłów.

12
00:00:42,320 --> 00:00:44,420
Nie robimy tu liniową próbkowania.

13
00:00:44,420 --> 00:00:48,430
I tak, w celu podłączenia się do następnego
elementem w wiadrze, musimy

14
00:00:48,430 --> 00:00:51,110
węzeł struct * następny.

15
00:00:51,110 --> 00:00:53,090
Więc to, co węzeł wygląda.

16
00:00:53,090 --> 00:00:56,180
Teraz tutaj jest deklaracja
naszej tabeli mieszania.

17
00:00:56,180 --> 00:01:01,910
To będzie mieć 16.384 wiadra, ale
liczba ta nie ma znaczenia.

18
00:01:01,910 --> 00:01:05,450
I wreszcie będziemy mieć
zmienna globalna hashtable_size, które

19
00:01:05,450 --> 00:01:08,640
zaczynać się jako 0, i to
będzie śledzić, jak wiele słów

20
00:01:08,640 --> 00:01:10,080
były w naszym słowniku.

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

22
00:01:10,760 --> 00:01:13,190
>> Warto więc spojrzeć na obciążenia.

23
00:01:13,190 --> 00:01:16,390
Więc zauważyć, że obciążenia,
zwraca bool.

24
00:01:16,390 --> 00:01:20,530
Powrót prawda, czy to z powodzeniem
załadowany i false w przeciwnym wypadku.

25
00:01:20,530 --> 00:01:23,990
I zajmuje const char * gwiazdkę
słownik, który słownik

26
00:01:23,990 --> 00:01:25,280
że chcemy otworzyć.

27
00:01:25,280 --> 00:01:27,170
Więc to jest pierwsza rzecz,
mamy zamiar zrobić.

28
00:01:27,170 --> 00:01:30,420
Jedziemy do fopen słownika dla
czytania, a my będziemy mieć

29
00:01:30,420 --> 00:01:34,700
aby upewnić się, że udało się, więc jeśli
powrócił NULL, to my nie

30
00:01:34,700 --> 00:01:37,440
powodzeniem otworzyć słownik
i musimy return false.

31
00:01:37,440 --> 00:01:41,580
>> Ale zakładając, że tak skutecznie
otwarte, to chcemy, aby przeczytać

32
00:01:41,580 --> 00:01:42,400
słowniku.

33
00:01:42,400 --> 00:01:46,210
Dlatego należy zachować pętli, dopóki nie znajdziemy niektórych
powód, aby wyrwać się z tego

34
00:01:46,210 --> 00:01:47,570
pętli, które zobaczymy.

35
00:01:47,570 --> 00:01:51,780
Dlatego należy zachować pętli, a teraz idziemy
malloc pojedynczego węzła.

36
00:01:51,780 --> 00:01:56,800
I oczywiście, musimy kontrolę błędów
ponownie więc jeśli mallocing nie udało

37
00:01:56,800 --> 00:02:00,660
i chcemy rozładować dowolny węzeł, że
się do malloc przed zamknij

38
00:02:00,660 --> 00:02:02,590
słownik i return false.

39
00:02:02,590 --> 00:02:07,440
>> Ale pomijając, że przy założeniu, że
udało, to chcemy wykorzystać fscanf

40
00:02:07,440 --> 00:02:12,400
przeczytać ani jednego słowa od naszych
słownika do naszego węzła.

41
00:02:12,400 --> 00:02:17,310
Więc pamiętać, że wejścia-> słowo jest char
Bufor słowo długości plus size

42
00:02:17,310 --> 00:02:20,300
jeden, że będziemy
przechowywać słowo w.

43
00:02:20,300 --> 00:02:25,280
Więc fscanf zamierza powrócić 1 tak długo,
jak to było w stanie z powodzeniem czytać

44
00:02:25,280 --> 00:02:26,750
słowo z pliku.

45
00:02:26,750 --> 00:02:31,030
>> Jeśli błąd się dzieje, albo czy możemy osiągnąć
koniec pliku, nie będzie

46
00:02:31,030 --> 00:02:34,950
zwraca 1, w którym to przypadku, jeśli tak nie jest
zwraca 1, jesteśmy w końcu złamie

47
00:02:34,950 --> 00:02:37,280
z tej pętli while.

48
00:02:37,280 --> 00:02:42,770
Tak więc widzimy, że raz mamy powodzeniem
czytać słowo w

49
00:02:42,770 --> 00:02:48,270
entry-> słowo, następnie idziemy do mieszania
słowo za pomocą naszej funkcji skrótu.

50
00:02:48,270 --> 00:02:49,580
Rzućmy okiem na
funkcja skrótu.

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

52
00:02:52,430 --> 00:02:55,610
>> Tak naprawdę nie potrzebujesz
aby to zrozumieć.

53
00:02:55,610 --> 00:02:59,460
I rzeczywiście, po prostu wyciągnął to
funkcji skrótu z internetu.

54
00:02:59,460 --> 00:03:04,010
Jedyne, co trzeba uznać to
że trwa const char * wyraz,

55
00:03:04,010 --> 00:03:08,960
tak, to biorąc ciąg na wejściu i
zwrócenie int jako wyjście.

56
00:03:08,960 --> 00:03:12,360
Więc to wszystko funkcja skrótu jest, jest to
odbywa się w wejściu, to daje

57
00:03:12,360 --> 00:03:14,490
indeks w tabeli mieszania.

58
00:03:14,490 --> 00:03:18,530
Zauważ, że jesteśmy modding przez NUM_BUCKETS
więc wartość skrótu wrócił

59
00:03:18,530 --> 00:03:21,730
faktycznie jest indeks w tabeli mieszania
a nie indeks poza

60
00:03:21,730 --> 00:03:24,320
granice tablicy.

61
00:03:24,320 --> 00:03:27,855
>> Tak więc biorąc pod uwagę, że funkcja skrótu, jedziemy
hash słowo, które czytamy

62
00:03:27,855 --> 00:03:31,700
ze słownika, a następnie jedziemy
w użyciu, że musi wstawić

63
00:03:31,700 --> 00:03:33,750
Wejście w tabeli mieszania.

64
00:03:33,750 --> 00:03:38,830
Teraz hashtable hash jest obecny
powiązana lista w tabeli mieszania i

65
00:03:38,830 --> 00:03:41,410
to jest bardzo możliwe, że jest po prostu NULL.

66
00:03:41,410 --> 00:03:45,640
Chcemy wstawić nasz wpis w
począwszy od tej związanej liście i dlatego

67
00:03:45,640 --> 00:03:48,910
będziemy mieć naszą aktualną pozycję
wskazują na to, co obecnie w tabeli mieszania

68
00:03:48,910 --> 00:03:54,030
punkty, a potem jedziemy do przechowywania
w tabeli mieszania w hash

69
00:03:54,030 --> 00:03:55,350
aktualny wpis.

70
00:03:55,350 --> 00:03:59,320
>> Tak więc te dwie linie z powodzeniem wstawić
Wpis na początku

71
00:03:59,320 --> 00:04:02,270
powiązana lista w tym indeksie
w tabeli mieszania.

72
00:04:02,270 --> 00:04:04,900
Kiedy skończysz z tym, wiemy,
że znaleźliśmy inny wyraz w

73
00:04:04,900 --> 00:04:07,800
słownik i zwiększamy ponownie.

74
00:04:07,800 --> 00:04:13,960
Więc robić, że do fscanf
wreszcie zwraca na coś non 1

75
00:04:13,960 --> 00:04:18,560
który punkt należy pamiętać, że musimy
wstęp wolny, więc tutaj, że malloced

76
00:04:18,560 --> 00:04:21,329
Wpis i staraliśmy się przeczytać coś
ze słownika.

77
00:04:21,329 --> 00:04:24,110
A nie z powodzeniem czytać
coś ze słownika, w którym

78
00:04:24,110 --> 00:04:27,440
przypadku musimy uwolnić wpis, że
nigdy nie umieścić w tabeli mieszania

79
00:04:27,440 --> 00:04:29,110
i wreszcie przełamać.

80
00:04:29,110 --> 00:04:32,750
>> Kiedy wybuchnie, musimy zobaczyć, dobrze,
nie wyjdziemy, bo tam

81
00:04:32,750 --> 00:04:35,840
został błąd odczytu z pliku, lub
nie łamiemy, bo dotarliśmy

82
00:04:35,840 --> 00:04:37,120
koniec pliku?

83
00:04:37,120 --> 00:04:40,150
Jeśli był błąd, to chcemy
return false, ponieważ obciążenie nie

84
00:04:40,150 --> 00:04:43,260
sukces, w procesie, chcemy
rozładować wszystkie słowa, które czytamy

85
00:04:43,260 --> 00:04:45,670
i zamknąć plik słownika.

86
00:04:45,670 --> 00:04:48,740
Zakładając, że nie uda, to po prostu
jeszcze trzeba zamknąć słownika

87
00:04:48,740 --> 00:04:51,970
złożyć, i wreszcie powrót prawda od
my pomyślnie załadowany

88
00:04:51,970 --> 00:04:53,040
słowniku.

89
00:04:53,040 --> 00:04:54,420
I to jest to dla ładunku.

90
00:04:54,420 --> 00:04:59,020
>> Więc teraz sprawdzić, ponieważ załadowany tabeli mieszania,
będzie wyglądać tak.

91
00:04:59,020 --> 00:05:02,690
Więc sprawdź, zwraca bool, który
będzie wskazywać, czy

92
00:05:02,690 --> 00:05:07,530
przeszedł w char * tekst, czy
przekazywane w ciąg jest w naszym słowniku.

93
00:05:07,530 --> 00:05:10,530
Jeśli więc w słowniku, jeśli jest to
w naszej tabeli mieszania, wrócimy

94
00:05:10,530 --> 00:05:13,380
prawda, a jeśli tak nie jest,
wrócimy fałszywe.

95
00:05:13,380 --> 00:05:17,770
Biorąc pod uwagę ten przeszedł w słowo, jesteśmy
będzie hash słowo.

96
00:05:17,770 --> 00:05:22,020
>> Teraz ważne jest, aby rozpoznać
że obciążenia, wiedzieliśmy, że wszystkie

97
00:05:22,020 --> 00:05:25,820
słowa miały być małe litery,
ale tutaj, nie jesteśmy tak pewni.

98
00:05:25,820 --> 00:05:29,510
Jeśli przyjrzeć się naszej funkcji skrótu,
faktycznie nasza funkcja skrótu

99
00:05:29,510 --> 00:05:32,700
każdy znak jest lowercasing
słowa.

100
00:05:32,700 --> 00:05:37,580
Tak więc bez względu na kapitalizację
Słowo, nasza funkcja skrótu będzie

101
00:05:37,580 --> 00:05:42,270
powrót ten sam wskaźnik dla co
kapitalizacja jest jak miałoby to

102
00:05:42,270 --> 00:05:45,280
wrócił do zupełnie małe
wersja słowa.

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

104
00:05:45,950 --> 00:05:47,410
>> Tak, że nasz indeks.

105
00:05:47,410 --> 00:05:49,790
To tabeli mieszania do tego słowa.

106
00:05:49,790 --> 00:05:52,940
Teraz, to będzie na pętli
się nad połączonej listy

107
00:05:52,940 --> 00:05:55,000
, że był w tym indeksie.

108
00:05:55,000 --> 00:05:59,630
Więc zauważyć, że wpis jest inicjowanie
aby wskazać tym indeksie.

109
00:05:59,630 --> 00:06:03,480
Jedziemy dalej, podczas gdy wejście nie
nie równe NULL, i pamiętać, że

110
00:06:03,480 --> 00:06:08,350
aktualizowania wskaźnika w naszej listy
Wpis równa entry-> następny, więc mają

111
00:06:08,350 --> 00:06:13,840
Nasz obecny punkt wejścia do
Kolejnym punktem w połączonej listy.

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

113
00:06:14,400 --> 00:06:19,150
>> Więc dla każdego wpisu w połączonej listy,
będziemy używać strcasecmp.

114
00:06:19,150 --> 00:06:23,780
To nie strcmp ponieważ po raz kolejny, że
chcą robić rzeczy, wielkość liter.

115
00:06:23,780 --> 00:06:28,830
Więc używamy strcasecmp porównać słowo
, który został przekazany do tej funkcji

116
00:06:28,830 --> 00:06:31,860
do słowa, które
w tej pozycji.

117
00:06:31,860 --> 00:06:35,570
Jeśli zwróci 0, co oznacza, że ​​nie było
Mecz, w którym to przypadku chcemy

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

119
00:06:36,630 --> 00:06:39,590
Udało nam się znaleźć
Słowo w naszej tabeli mieszania.

120
00:06:39,590 --> 00:06:43,040
>> Jeśli nie było meczu, to jesteśmy
będzie pętli ponownie i spojrzeć na

121
00:06:43,040 --> 00:06:43,990
obok wejścia.

122
00:06:43,990 --> 00:06:47,640
A my nadal zapętlenie podczas gdy
są wpisy w tej połączonej listy.

123
00:06:47,640 --> 00:06:50,160
Co się stanie, jeśli łamiemy
z tego do pętli?

124
00:06:50,160 --> 00:06:55,110
Oznacza to, że nie znaleźliśmy wpis, który
pasuje to słowo, w którym to przypadku

125
00:06:55,110 --> 00:07:00,220
my return false, aby wskazać, że nasz
hash tabeli nie zawierają to słowo.

126
00:07:00,220 --> 00:07:01,910
I to jest to do odprawy.

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

128
00:07:02,540 --> 00:07:04,790
>> Warto więc przyjrzeć się wielkości.

129
00:07:04,790 --> 00:07:09,280
Teraz rozmiar będzie bardzo proste
odkąd pamiętam w obciążeniu, dla każdego słowa

130
00:07:09,280 --> 00:07:12,880
okazało się, że zwiększa się globalny
Zmienna hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Więc rozmiar jest tylko funkcja
powróci, że globalne

132
00:07:15,830 --> 00:07:18,150
zmienne, i to jest to.

133
00:07:18,150 --> 00:07:22,300
>> Teraz wreszcie, musimy rozładować
Słownik raz wszystko się robi.

134
00:07:22,300 --> 00:07:25,340
Więc jak mamy to zrobić?

135
00:07:25,340 --> 00:07:30,440
Tu, jesteśmy w pętli na wszystko
wiadra z naszej tabeli mieszania.

136
00:07:30,440 --> 00:07:33,240
Tak więc istnieje NUM_BUCKETS wiadra.

137
00:07:33,240 --> 00:07:37,490
I dla każdej połączonej listy w naszym hash
Stół, jedziemy do pętli na

138
00:07:37,490 --> 00:07:41,070
Całość połączonej listy
uwalniając każdy element.

139
00:07:41,070 --> 00:07:46,070
Teraz, musimy być ostrożni, więc tutaj
mają tymczasową zmienną, która jest

140
00:07:46,070 --> 00:07:49,740
przechowywania wskaźnika do następnego
element połączony listy.

141
00:07:49,740 --> 00:07:52,140
A następnie jedziemy do darmo
bieżący element.

142
00:07:52,140 --> 00:07:55,990
>> Musimy być pewni, że od kiedy to zrobić
Nie można po prostu zwolnić bieżący element

143
00:07:55,990 --> 00:07:59,260
a następnie spróbuj przejść do następnego wskaźnika
od razu go uwolnił nas

144
00:07:59,260 --> 00:08:00,870
Pamięć staje się nieważne.

145
00:08:00,870 --> 00:08:04,990
Więc musimy zachować wokół wskaźnik do
Kolejnym elementem, możemy uwolnić

146
00:08:04,990 --> 00:08:08,360
bieżący element, a następnie możemy aktualizować
nasz obecny element wskazać

147
00:08:08,360 --> 00:08:09,590
Kolejnym elementem.

148
00:08:09,590 --> 00:08:12,770
>> Będziemy pętli, podczas gdy istnieją elementy
w tej połączonej listy.

149
00:08:12,770 --> 00:08:16,450
Zrobimy to na wszystkich listach w powiązanych
Tabela mieszania, a gdy już skończysz

150
00:08:16,450 --> 00:08:20,180
się, że mamy całkowicie rozładowane
Tabela mieszania, a skończymy.

151
00:08:20,180 --> 00:08:24,050
Więc jest to niemożliwe dla odciążenia coraz
return false, a kiedy skończymy, możemy

152
00:08:24,050 --> 00:08:25,320
po prostu wrócić prawdziwe.

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