1
00:00:06,979 --> 00:00:07,479
[NOISE].

2
00:00:07,479 --> 00:00:09,367
Przed nurkowaniem w tablicach hash, niech

3
00:00:09,367 --> 00:00:11,196
Pierwszy przegląd zalet i wad niektórych

4
00:00:11,196 --> 00:00:13,202
prostszych struktur danych, począwszy

5
00:00:13,202 --> 00:00:14,739
tablice.

6
00:00:14,739 --> 00:00:16,869
Przypomnijmy, że tablice pozwalają na przechowywanie

7
00:00:16,869 --> 00:00:18,644
elementów jednego typu danych

8
00:00:18,644 --> 00:00:21,259
sposób ciągły w pamięci.

9
00:00:21,259 --> 00:00:24,115
Ponieważ każdy element jest związane z

10
00:00:24,115 --> 00:00:26,513
Indeks, lub lokalizacja,

11
00:00:26,513 --> 00:00:27,661
mamy swobodny dostęp do wszystkich

12
00:00:27,661 --> 00:00:28,860
elementów w tablicy.

13
00:00:28,860 --> 00:00:31,308
Innymi słowy, możemy uzyskać dostęp do dowolnego elementu

14
00:00:31,308 --> 00:00:33,468
w jednym etapie przez indeksowanie do

15
00:00:33,468 --> 00:00:35,112
tablica.

16
00:00:35,112 --> 00:00:37,224
To jest wielka sprawa, ponieważ algorytmy

17
00:00:37,224 --> 00:00:39,204
jak poszukiwania binarnego zależy od losowych

18
00:00:39,204 --> 00:00:40,570
dostępu.

19
00:00:40,570 --> 00:00:43,130
Minusem jest to, że tablice na ich wielkość

20
00:00:43,130 --> 00:00:44,380
jest stała.

21
00:00:44,380 --> 00:00:46,630
Ponieważ tablice przechowują dane w sposób zwarty

22
00:00:46,630 --> 00:00:49,490
pamięci, należy określić rozmiar tablicy

23
00:00:49,490 --> 00:00:50,600
Kiedy deklarujesz tablicę.

24
00:00:50,600 --> 00:00:53,510
Jesteś operacyjną skutecznie prosząc

25
00:00:53,510 --> 00:00:55,600
System zarezerwować odpowiednią ilość

26
00:00:55,600 --> 00:00:58,080
pamięci na elementy tablicy.

27
00:00:58,080 --> 00:01:00,240
Nie ma gwarancji, że więcej pamięci,

28
00:01:00,240 --> 00:01:02,370
przylegające do tablicy, będą dostępne

29
00:01:02,370 --> 00:01:03,480
do wykorzystania później.

30
00:01:03,480 --> 00:01:05,550
Tablice nie mogą tak łatwo rozwijać.

31
00:01:05,550 --> 00:01:07,715
Przypomnijmy, że dowiedzieliśmy się o związane

32
00:01:07,715 --> 00:01:09,630
Listy, które mogą rosnąć, ponieważ ich

33
00:01:09,630 --> 00:01:12,430
Elementy nie są ciągłe w pamięci.

34
00:01:12,430 --> 00:01:14,680
Każdy węzeł w połączonej listy zawiera

35
00:01:14,680 --> 00:01:16,620
element, który chcemy zapisać, jak również

36
00:01:16,620 --> 00:01:18,976
Wskaźnik na następny element

37
00:01:18,976 --> 00:01:19,756
lista.

38
00:01:19,756 --> 00:01:22,560
Niestety, cena, jaką zapłaciłeś za

39
00:01:22,560 --> 00:01:24,945
dynamiczny wielkość jest przypadkowa dostęp

40
00:01:24,945 --> 00:01:26,460
elementy.

41
00:01:26,460 --> 00:01:28,760
W celu uzyskania dostępu do jakiegoś elementu,

42
00:01:28,760 --> 00:01:30,810
konieczne jest przejście przez całą

43
00:01:30,810 --> 00:01:32,910
do czasu aż pożądany pierwiastek

44
00:01:32,910 --> 00:01:33,950
osiągnięta.

45
00:01:33,950 --> 00:01:36,450
Tak więc, jeśli szukam numeru 9, ja bym

46
00:01:36,450 --> 00:01:39,340
przestrzegać wskazówek od węzła do węzła,

47
00:01:39,340 --> 00:01:41,350
sprawdzenie czy wartość każdego węzła

48
00:01:41,350 --> 00:01:42,584
jest równa 9.

49
00:01:42,584 --> 00:01:46,303
Jako takie, w najgorszym przypadku, patrzeć jest

50
00:01:46,303 --> 00:01:48,400
O (n), co jest dalekie od skuteczny.

51
00:01:49,690 --> 00:01:51,630
Możemy to zrobić lepiej niż O (n), a jednocześnie

52
00:01:51,630 --> 00:01:53,470
pozwalając nasza struktura danych rośnie ponad

53
00:01:53,470 --> 00:01:54,560
czas?

54
00:01:54,560 --> 00:01:56,810
Tabele Hash zaoferować rozwiązanie.

55
00:01:56,810 --> 00:01:58,730
Tabele Hash są stosowane, gdy szybki

56
00:01:58,730 --> 00:02:00,820
wstawianie, usuwanie i wyszukiwanie z

57
00:02:00,820 --> 00:02:01,910
elementy jest priorytetem.

58
00:02:01,910 --> 00:02:05,500
W teorii, wstawianie, usuwanie i wyszukiwanie

59
00:02:05,500 --> 00:02:07,275
Nawet może być realizowane w stałym

60
00:02:07,275 --> 00:02:08,890
czas.

61
00:02:08,890 --> 00:02:11,120
Tak, to jest tabela hash tak?

62
00:02:11,120 --> 00:02:13,170
Tabela mieszania jest tylko tablica w połączeniu

63
00:02:13,170 --> 00:02:14,940
z funkcji, które my nazywamy hash

64
00:02:14,940 --> 00:02:15,440
funkcja.

65
00:02:16,440 --> 00:02:18,610
Funkcja mieszająca przyjmuje element danych

66
00:02:18,610 --> 00:02:20,778
jako wejście, nazwijmy to klucz, a

67
00:02:20,778 --> 00:02:23,700
wysyła liczbę całkowitą, nazywane

68
00:02:23,700 --> 00:02:24,895
jako wartości hash.

69
00:02:24,895 --> 00:02:28,810
Wartość skrótu odwzorowuje nasz klucz do

70
00:02:28,810 --> 00:02:30,840
szczególności indeks w tabeli mieszania.

71
00:02:32,080 --> 00:02:34,330
Że początkowo użyć funkcji skrótu do

72
00:02:34,330 --> 00:02:36,410
określić, gdzie w tabeli mieszania do

73
00:02:36,410 --> 00:02:38,430
przechowywać dany klawisz.

74
00:02:38,430 --> 00:02:41,030
Później można użyć tej samej funkcji skrótu

75
00:02:41,030 --> 00:02:42,950
określić, gdzie w tabeli mieszania do

76
00:02:42,950 --> 00:02:45,010
sprawdzić dla danego klucza.

77
00:02:45,010 --> 00:02:47,190
Z tego powodu, jest to istotne, że hash

78
00:02:47,190 --> 00:02:49,840
Funkcja zachowuje się konsekwentnie i wyjścia

79
00:02:49,840 --> 00:02:53,130
samą wartość skrótu dla tych samych klawiszy.

80
00:02:53,130 --> 00:02:54,970
Wiem, że tabele mieszania może być używany do

81
00:02:54,970 --> 00:02:56,310
przechowują dane wszystkich typów.

82
00:02:56,310 --> 00:02:58,330
Ale dla uproszczenia rzeczy, będziemy koncentrować się na

83
00:02:58,330 --> 00:02:59,830
Struny do teraz.

84
00:02:59,830 --> 00:03:01,630
Oto prosta funkcja skrótu ciągów.

85
00:03:03,570 --> 00:03:05,590
Funkcja ta oblicza hash hash

86
00:03:05,590 --> 00:03:07,410
Funkcja na podstawie pierwszej litery

87
00:03:07,410 --> 00:03:07,910
klucz.

88
00:03:09,090 --> 00:03:11,300
"Jabłko" zaczyna się na literę "A", więc jest to

89
00:03:11,300 --> 00:03:13,200
odwzorowane na indeksie 0 w tabeli mieszania.

90
00:03:14,270 --> 00:03:17,402
Podobnie, "banana" są odwzorowywane na indeksie 1

91
00:03:17,402 --> 00:03:19,829
i "kot" jest odwzorowywany na indeksie 2.

92
00:03:21,750 --> 00:03:23,790
Jeśli przyjaciel pyta, czy słowo "pies" jest w

93
00:03:23,790 --> 00:03:26,150
Stół, będziemy psa "wejścia" do mieszania

94
00:03:26,150 --> 00:03:28,390
Funkcja, które wyjście będzie wartość skrótu

95
00:03:28,390 --> 00:03:29,790
3.

96
00:03:29,790 --> 00:03:33,150
Od "pies" nie jest przechowywany w indeksie 3, my

97
00:03:33,150 --> 00:03:35,330
może powiedzieć z pewnością, że "pies" nie jest

98
00:03:35,330 --> 00:03:36,340
w tabeli

99
00:03:36,340 --> 00:03:38,260
mimo, że mamy tylko jeden sprawdzony

100
00:03:38,260 --> 00:03:40,120
hash tabeli na 26 indeksów.

101
00:03:42,170 --> 00:03:44,280
Czas wyrzucić klucz do rzeczy.

102
00:03:44,280 --> 00:03:46,130
Co jeśli chcemy przechowywać "mrówka" na

103
00:03:46,130 --> 00:03:47,820
Stół, jak również?

104
00:03:47,820 --> 00:03:51,730
"Mrówka" Sumy na indeksie 0, tak jak "apple" nie.

105
00:03:51,730 --> 00:03:53,890
Jest to przykład kolizji

106
00:03:53,890 --> 00:03:56,419
wynikiem dwóch kluczy haszowania same

107
00:03:56,419 --> 00:03:57,080
Indeks.

108
00:03:58,140 --> 00:04:00,040
Nawet jeśli tabeli mieszania jest większa niż

109
00:04:00,040 --> 00:04:01,980
ustawić dane i wybrałeś dobre

110
00:04:01,980 --> 00:04:03,060
funkcji skrótu,

111
00:04:03,060 --> 00:04:04,560
trzeba jeszcze do czynienia z planu

112
00:04:04,560 --> 00:04:06,420
kolizje, czy i kiedy się pojawią.

113
00:04:07,440 --> 00:04:09,810
Porozmawiajmy o plusy i minusy z dwóch

114
00:04:09,810 --> 00:04:12,360
Typowe sposoby rozwiązywania kolizji:

115
00:04:12,360 --> 00:04:15,230
liniowy sondowania i oddzielne łańcuchowym.

116
00:04:15,230 --> 00:04:17,430
Z adresowania liniowego, jeśli klucz skróty do

117
00:04:17,430 --> 00:04:19,340
sam wskaźnik jak wcześniej zapisane

118
00:04:19,340 --> 00:04:21,840
Klucz jest przypisany następny dostępny

119
00:04:21,840 --> 00:04:22,862
Szczelina w tabeli.

120
00:04:22,862 --> 00:04:27,353
Tak więc, "mrówka" jest obecnie przechowywany w indeksie 3, od

121
00:04:27,353 --> 00:04:30,850
indeksy 0, 1 i 2 były już w użyciu.

122
00:04:32,780 --> 00:04:34,610
A jeśli staramy się zapisać trzecie słowo, które

123
00:04:34,610 --> 00:04:36,410
zaczyna się na literę "A", to jest przypisane

124
00:04:36,410 --> 00:04:41,263
do wskaźnika 4 od indeksy 0, 1, 2 i 3.

125
00:04:41,263 --> 00:04:42,530
są pełne.

126
00:04:42,530 --> 00:04:44,300
Jak widać, nawet z tej prostej

127
00:04:44,300 --> 00:04:46,580
Na przykład, po kolizji występuje, ci

128
00:04:46,580 --> 00:04:48,400
znacznie zwiększyć szanse, że

129
00:04:48,400 --> 00:04:50,370
kolejna kolizja nastąpi w samo

130
00:04:50,370 --> 00:04:51,630
obszar.

131
00:04:51,630 --> 00:04:53,530
To się nazywa klastrów, i to

132
00:04:53,530 --> 00:04:56,200
Poważną wadą liniowego sondowania.

133
00:04:56,200 --> 00:04:59,240
Co więcej, najgorszy wstawiania, kasowania,

134
00:04:59,240 --> 00:05:02,008
i zostały przekazane czasy odnośników do O (n),

135
00:05:02,008 --> 00:05:04,200
jako następny wolny slot może mieć

136
00:05:04,200 --> 00:05:06,225
potencjalnie był ostatnio gniazdo w tabeli.

137
00:05:06,225 --> 00:05:09,210
Może osobna oferta zostanie Łańcuchy więcej

138
00:05:09,210 --> 00:05:10,220
atrakcyjne rozwiązanie.

139
00:05:10,220 --> 00:05:13,060
W oddzielnym modelu łańcuchowym, hash

140
00:05:13,060 --> 00:05:14,930
Stół jest w rzeczywistości tablica wskaźników do

141
00:05:14,930 --> 00:05:16,220
związane listy.

142
00:05:16,220 --> 00:05:18,350
W przypadku wystąpienia kolizji, może być kluczem

143
00:05:18,350 --> 00:05:20,760
umieszczony w stałym czasie w nagłówku

144
00:05:20,760 --> 00:05:22,270
odpowiednia lista powiązana.

145
00:05:23,420 --> 00:05:25,310
Co się dzieje teraz, kiedy szukamy "apple"

146
00:05:25,310 --> 00:05:26,900
w tabeli mieszania?

147
00:05:26,900 --> 00:05:28,940
W najgorszym przypadku, musimy przemierzać

148
00:05:28,940 --> 00:05:32,530
Cała lista powiązana, zaczynając od indeksu 0.

149
00:05:32,530 --> 00:05:34,210
Czas wyszukiwania najgorszy dla mieszania

150
00:05:34,210 --> 00:05:35,890
Stół, który wykorzystuje oddzielny łańcuchowych jest

151
00:05:35,890 --> 00:05:38,580
Dlatego O (n / k), gdzie k jest

152
00:05:38,580 --> 00:05:39,687
rozmiar tabeli mieszania.

153
00:05:39,687 --> 00:05:42,940
Chwileczkę, k jest stałą.

154
00:05:42,940 --> 00:05:46,280
Tak O (n / k) jest w rzeczywistości O (n)

155
00:05:46,280 --> 00:05:47,940
której czas wyszukiwania dla najgorszego przypadku

156
00:05:47,940 --> 00:05:49,320
powiązana lista.

157
00:05:49,320 --> 00:05:50,770
Czy my naprawdę przeszedł wszystkie

158
00:05:50,770 --> 00:05:52,370
Kłopot z nauki o tablicach hash

159
00:05:52,370 --> 00:05:54,927
tylko do końca się tam, gdzie zaczęliśmy?

160
00:05:54,927 --> 00:05:56,975
To może być sprawa z teoretycznym

161
00:05:56,975 --> 00:05:59,087
perspektywicznym, lecz w rzeczywistym świecie

162
00:05:59,087 --> 00:06:01,199
O (n / k) może być ogromna poprawa w stosunku

163
00:06:01,199 --> 00:06:03,257
O (n).

164
00:06:03,257 --> 00:06:05,687
Pomyśl o tym w ten sposób: zakładamy, że k jest

165
00:06:05,687 --> 00:06:08,360
10 - czy raczej poczekać 100 sekund

166
00:06:08,360 --> 00:06:11,076
lub 100 / k?

167
00:06:11,076 --> 00:06:13,252
10 sekund od programu Microsoft Word, aby zakończyć

168
00:06:13,252 --> 00:06:15,608
sprawdzanie pisowni dokumentu.

169
00:06:15,608 --> 00:06:17,368
Jak tylko zobaczyłem, rozwiązywania kolizji

170
00:06:17,368 --> 00:06:19,018
pociąga za sobą jeden rodzaj wyszukiwania liniowego lub

171
00:06:19,018 --> 00:06:20,558
inny, który spowalnia rzeczy w dół

172
00:06:20,558 --> 00:06:23,280
znacznie.

173
00:06:23,280 --> 00:06:25,470
Dlatego będziemy chcieli, aby wybrać skrót

174
00:06:25,470 --> 00:06:27,470
Funkcja, która minimalizuje ryzyko

175
00:06:27,470 --> 00:06:29,170
Kolizje występujące w pierwszym miejscu.

176
00:06:30,540 --> 00:06:32,120
Oto niektóre właściwości dobrego mieszania

177
00:06:32,120 --> 00:06:33,400
funkcje o których warto pamiętać.

178
00:06:34,610 --> 00:06:36,590
Dobra funkcja skrótu powinna korzystać z

179
00:06:36,590 --> 00:06:38,830
wszystkie informacje przekazane przez danego klucza

180
00:06:38,830 --> 00:06:40,890
W celu zmaksymalizowania liczby

181
00:06:40,890 --> 00:06:42,960
Możliwe wartości hash.

182
00:06:42,960 --> 00:06:45,540
Na przykład, gdybyśmy mieli dwa ciągi, "kot"

183
00:06:45,540 --> 00:06:47,980
i "gąsienica", że chcemy, aby hash

184
00:06:47,980 --> 00:06:50,190
do różnych miejsc w tabeli.

185
00:06:50,190 --> 00:06:52,410
Jeśli funkcja skrótu wziął pod uwagę tylko

186
00:06:52,410 --> 00:06:54,860
Pierwszy z nich, dwie lub nawet trzy listy

187
00:06:54,860 --> 00:06:57,290
strun, kolizja nie występuje,

188
00:06:57,290 --> 00:06:58,970
ponieważ obydwa słowa rozpocząć same

189
00:06:58,970 --> 00:06:59,560
trzy litery.

190
00:07:01,110 --> 00:07:03,100
Wartości mieszania powinny być rozłożone równomiernie

191
00:07:03,100 --> 00:07:04,790
całej tabeli mieszania.

192
00:07:04,790 --> 00:07:06,300
Zmniejszy to długość związana

193
00:07:06,300 --> 00:07:08,050
Listy powinny wystąpić kolizje.

194
00:07:09,390 --> 00:07:11,490
Jest to także dobry znak, czy wartość skrótu

195
00:07:11,490 --> 00:07:13,600
jest zdolny do tworzenia bardzo różny

196
00:07:13,600 --> 00:07:15,660
hash wartości dla podobnych kluczy,

197
00:07:15,660 --> 00:07:17,250
podejmowania kolizji znacznie mniej prawdopodobne.

198
00:07:18,420 --> 00:07:21,110
Naszym celem jest szybka wstawianie, usuwanie,

199
00:07:21,110 --> 00:07:22,100
i wyszukiwania.

200
00:07:22,100 --> 00:07:24,060
Funkcja skrótu odgrywa kluczową rolę w

201
00:07:24,060 --> 00:07:25,520
każdy z tych sposobów i będzie

202
00:07:25,520 --> 00:07:26,735
nazywa się bardzo często.

203
00:07:26,735 --> 00:07:29,620
Dlatego upewnij się, że zatrudnia tylko bardzo

204
00:07:29,620 --> 00:07:32,160
Prosty, szybki przebieg operacji, aby zminimalizować

205
00:07:32,160 --> 00:07:33,360
czas.

206
00:07:33,360 --> 00:07:34,560
Mam nadzieję, że podobał mi się ten krótki

207
00:07:34,560 --> 00:07:36,540
Wprowadzenie do mieszania tabele.

208
00:07:36,540 --> 00:07:41,189
Nazywam się Laura, i to jest CS50.