1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:01,900
[MUZYKI]

3
00:00:01,900 --> 00:00:05,710

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: Przez teraz
dużo wiedzieć o tablicach,

5
00:00:09,150 --> 00:00:11,610
i wiele o powiązanych list wiedzieć.

6
00:00:11,610 --> 00:00:13,650
I mamy dyskutować
plusy i minusy, mamy

7
00:00:13,650 --> 00:00:16,620
omówione, że związane list
można uzyskać większe i mniejsze,

8
00:00:16,620 --> 00:00:18,630
ale zajmują więcej wielkości.

9
00:00:18,630 --> 00:00:22,359
Tablice są znacznie bardziej proste do
używać, ale są restrykcyjne w tyle

10
00:00:22,359 --> 00:00:24,900
jak mamy się ustawić rozmiar
matryca na początku

11
00:00:24,900 --> 00:00:26,910
a potem utknęliśmy z nim.

12
00:00:26,910 --> 00:00:30,470
>> Ale to, mamy dość dużo
wyczerpane wszystkie nasze tematy

13
00:00:30,470 --> 00:00:33,040
o powiązanych list i tablic.

14
00:00:33,040 --> 00:00:34,950
Mogą też my?

15
00:00:34,950 --> 00:00:37,720
Może uda nam się coś zrobić
jeszcze bardziej kreatywne.

16
00:00:37,720 --> 00:00:40,950
I tego rodzaju nadaje
pomysł tabeli mieszania.

17
00:00:40,950 --> 00:00:46,680
>> Tak więc w tabeli mieszania mamy zamiar spróbować
połączyć tablicę z połączonej listy.

18
00:00:46,680 --> 00:00:49,520
Jedziemy do podjęcia zalety
tablicy, na przykład jednostka dostępowa,

19
00:00:49,520 --> 00:00:53,510
będąc w stanie po prostu pójść do tablicy
Element 4 lub element tablicy 8

20
00:00:53,510 --> 00:00:55,560
bez konieczności iteracji w poprzek.

21
00:00:55,560 --> 00:00:57,260
To dość szybko, prawda?

22
00:00:57,260 --> 00:01:00,714
>> Ale my także chcemy mieć nasze dane
Struktura w stanie rozwijać się i kurczyć.

23
00:01:00,714 --> 00:01:02,630
Nie potrzebujemy, my nie
chcą być ograniczone.

24
00:01:02,630 --> 00:01:04,588
I chcemy, aby móc
do dodawania i usuwania rzeczy

25
00:01:04,588 --> 00:01:08,430
bardzo łatwo, która, jeśli przypomnieć,
jest bardzo złożone z tablicą.

26
00:01:08,430 --> 00:01:11,650
I możemy nazwać
Nowością tabeli mieszania.

27
00:01:11,650 --> 00:01:15,190
>> A jeśli realizowane prawidłowo,
jesteśmy jakby biorąc

28
00:01:15,190 --> 00:01:18,150
Zalety obu dane
Struktury już widziałem,

29
00:01:18,150 --> 00:01:19,880
tablice i związane listy.

30
00:01:19,880 --> 00:01:23,070
Wprowadzające może zacząć
tendencję w kierunku theta z 1.

31
00:01:23,070 --> 00:01:26,207
Theta tak naprawdę nie wspomniano,
ale theta jest tylko średnia przypadku,

32
00:01:26,207 --> 00:01:27,540
co się faktycznie zdarzy.

33
00:01:27,540 --> 00:01:29,680
Nie zawsze będziemy
mają najgorszy scenariusz,

34
00:01:29,680 --> 00:01:32,555
a ty nie zawsze będzie mieć
najlepszy scenariusz, więc co to

35
00:01:32,555 --> 00:01:33,900
średni scenariusz?

36
00:01:33,900 --> 00:01:36,500
>> Cóż średnio wstawiania
w tabeli mieszania

37
00:01:36,500 --> 00:01:39,370
może rozpocząć się zbliżyć do stałej czasu.

38
00:01:39,370 --> 00:01:41,570
I usuwanie może uzyskać
blisko stałym czasie.

39
00:01:41,570 --> 00:01:44,440
I wyszukiwania mogą uzyskać
blisko stałym czasie.

40
00:01:44,440 --> 00:01:48,600
That's-- nie ma danych
Struktura jednak, że może to zrobić,

41
00:01:48,600 --> 00:01:51,180
i tak to brzmi
jak całkiem wielkiej rzeczy.

42
00:01:51,180 --> 00:01:57,010
Mamy naprawdę złagodziły
wady każdego z nich na własną rękę.

43
00:01:57,010 --> 00:01:59,160
>> Aby uzyskać ten występ
uaktualnić chociaż, my

44
00:01:59,160 --> 00:02:03,580
należy zastanowić się, jak możemy dodać
dane w strukturze.

45
00:02:03,580 --> 00:02:07,380
W szczególności chcemy
Same dane nam powiedzieć

46
00:02:07,380 --> 00:02:09,725
gdzie powinien iść w strukturze.

47
00:02:09,725 --> 00:02:12,850
A jeśli to konieczne, aby zobaczyć, czy to w
struktura, jeśli musimy go znaleźć,

48
00:02:12,850 --> 00:02:16,610
chcemy spojrzeć na dane
jeszcze raz i być w stanie skutecznie,

49
00:02:16,610 --> 00:02:18,910
wykorzystując dane losowo do niego dostęp.

50
00:02:18,910 --> 00:02:20,700
Po prostu patrząc na
Dane powinniśmy mieć

51
00:02:20,700 --> 00:02:25,890
pomysł na to, gdzie dokładnie jesteśmy
będzie go znaleźć w tabeli mieszania.

52
00:02:25,890 --> 00:02:28,770
>> Teraz minusem hash
Stół jest to, że są naprawdę

53
00:02:28,770 --> 00:02:31,770
całkiem nieźle zamawiania lub sortowania danych.

54
00:02:31,770 --> 00:02:34,970
I rzeczywiście, jeśli zaczniesz
wykorzystać je do zamówienia lub rodzaju

55
00:02:34,970 --> 00:02:37,990
Dane można stracić wszystkie z
Zalety wcześniej

56
00:02:37,990 --> 00:02:40,710
miał w zakresie wstawiania i usuwania.

57
00:02:40,710 --> 00:02:44,060
Czas staje się bliższy
theta n, i mamy w zasadzie

58
00:02:44,060 --> 00:02:45,530
regres w połączonej listy.

59
00:02:45,530 --> 00:02:48,850
A więc chcemy używać tylko hash
tabele, jeśli nie dbają o

60
00:02:48,850 --> 00:02:51,490
czy dane są sortowane.

61
00:02:51,490 --> 00:02:54,290
Dla sytuacji, w której
będziesz ich używać w CS50

62
00:02:54,290 --> 00:02:58,900
prawdopodobnie nie obchodzi
że dane są sortowane.

63
00:02:58,900 --> 00:03:03,170
>> Więc tabeli mieszania jest połączeniem
z dwóch różnych kawałków

64
00:03:03,170 --> 00:03:04,980
z którymi jesteśmy zaznajomieni.

65
00:03:04,980 --> 00:03:07,930
Pierwszym z nich jest funkcją, która
zwykle nazywamy funkcji skrótu.

66
00:03:07,930 --> 00:03:11,760
I że funkcja skrótu będzie
powrót trochę nieujemną liczbę całkowitą, która

67
00:03:11,760 --> 00:03:14,870
zwykle nazywamy hashcode, OK?

68
00:03:14,870 --> 00:03:20,230
Drugi element jest tablicą, która jest
zdolny do przechowywania danych typu my

69
00:03:20,230 --> 00:03:22,190
chcą umieścić w strukturze danych.

70
00:03:22,190 --> 00:03:24,310
Będziemy trzymać się na
powiązany element listy do teraz

71
00:03:24,310 --> 00:03:27,810
i po prostu zacząć od podstaw o charakterze
tablica mieszająca dostać głowę wokół niego,

72
00:03:27,810 --> 00:03:30,210
a następnie będziemy może wiać
twój umysł nieco, kiedy

73
00:03:30,210 --> 00:03:32,920
łączyć macierze i listy linków razem.

74
00:03:32,920 --> 00:03:35,590
>> Podstawową ideą, choć
to bierzemy jakieś dane.

75
00:03:35,590 --> 00:03:37,860
Prowadzimy tych danych poprzez
funkcja skrótu.

76
00:03:37,860 --> 00:03:41,980
I tak dane są przetwarzane
i to wypluwa numer, OK?

77
00:03:41,980 --> 00:03:44,890
A następnie z tej liczby
po prostu przechowywania danych

78
00:03:44,890 --> 00:03:48,930
chcemy przechowywać w
Tablica w tej lokalizacji.

79
00:03:48,930 --> 00:03:53,990
Tak na przykład mamy może
tabela hash łańcuchów.

80
00:03:53,990 --> 00:03:57,350
Ma 10 elementów w niej, tak,
możemy zmieścić 10 strun w nim.

81
00:03:57,350 --> 00:03:59,320
>> Powiedzmy, że chcemy hash John.

82
00:03:59,320 --> 00:04:02,979
Więc Jana jak dane chcemy wstawić
w tej tabeli mieszania gdzieś.

83
00:04:02,979 --> 00:04:03,770
Gdzie możemy umieścić go?

84
00:04:03,770 --> 00:04:05,728
Cóż zazwyczaj ze związkiem
Tablica do tej pory prawdopodobnie

85
00:04:05,728 --> 00:04:07,610
by umieścić go w miejscu tablicy 0.

86
00:04:07,610 --> 00:04:09,960
Ale teraz mamy tę nową funkcję skrótu.

87
00:04:09,960 --> 00:04:13,180
>> I powiedzmy, że prowadzimy Jana
dzięki tej funkcji skrótu

88
00:04:13,180 --> 00:04:15,417
i to wypluwa 4.

89
00:04:15,417 --> 00:04:17,500
No to gdzie jesteśmy
będzie chciał umieścić John.

90
00:04:17,500 --> 00:04:22,050
Chcemy postawić Jana w miejscu tablicy
4, bo jeśli hash Jana again--

91
00:04:22,050 --> 00:04:23,810
powiedzmy później
Aby wyszukać i zobaczyć

92
00:04:23,810 --> 00:04:26,960
jeśli istnieje w tym John hash
table-- wszystkim musimy zrobić

93
00:04:26,960 --> 00:04:30,310
prowadzony jest to przez samego hash
Funkcja, uzyskać numer na 4,

94
00:04:30,310 --> 00:04:33,929
i być w stanie znaleźć Jana
natychmiast w naszej strukturze danych.

95
00:04:33,929 --> 00:04:34,720
To dość dobre.

96
00:04:34,720 --> 00:04:36,928
>> Powiedzmy, że teraz to zrobić
znowu, chcemy hash Paul.

97
00:04:36,928 --> 00:04:39,446
Chcemy, aby dodać Paul
w tej tabeli hash.

98
00:04:39,446 --> 00:04:42,070
Powiedzmy, że tym razem możemy uruchomić
Paweł dzięki funkcji skrótu,

99
00:04:42,070 --> 00:04:44,600
hashCode, który jest generowany 6.

100
00:04:44,600 --> 00:04:47,340
No to teraz możemy umieścić Pawła
w miejscu tablicy 6.

101
00:04:47,340 --> 00:04:50,040
A jeśli musimy przyjrzeć się, czy
Paweł jest w tej tabeli mieszania,

102
00:04:50,040 --> 00:04:53,900
wszystko, co musisz zrobić, to uruchomić Paul
dzięki funkcji skrótu ponownie

103
00:04:53,900 --> 00:04:55,830
a my będziemy się 6 ponownie.

104
00:04:55,830 --> 00:04:57,590
>> A potem po prostu patrzeć
w miejscu tablicy 6.

105
00:04:57,590 --> 00:04:58,910
Czy Paweł nie?

106
00:04:58,910 --> 00:05:00,160
Jeśli tak, jest w tabeli mieszania.

107
00:05:00,160 --> 00:05:01,875
Czy Paweł nie istnieje?

108
00:05:01,875 --> 00:05:03,000
Nie ma go w tabeli mieszania.

109
00:05:03,000 --> 00:05:05,720
To całkiem proste.

110
00:05:05,720 --> 00:05:07,770
>> Teraz jak można zdefiniować funkcję skrótu?

111
00:05:07,770 --> 00:05:11,460
No naprawdę nie ma ograniczeń co do
Liczba możliwych funkcji skrótu.

112
00:05:11,460 --> 00:05:14,350
W rzeczywistości istnieje wiele naprawdę,
naprawdę dobrzy w Internecie.

113
00:05:14,350 --> 00:05:17,560
Jest kilka naprawdę,
bardzo złych w Internecie.

114
00:05:17,560 --> 00:05:21,080
Jest to także dość łatwe
napisać zły.

115
00:05:21,080 --> 00:05:23,760
>> Więc to, co składa się na dobre
funkcja skrótu, prawda?

116
00:05:23,760 --> 00:05:27,280
No dobra funkcja skrótu powinna
używać tylko dane są zakodowane,

117
00:05:27,280 --> 00:05:29,420
oraz wszystkie dane są zaszyfrowane.

118
00:05:29,420 --> 00:05:32,500
Więc nie chcemy używać anything--
nie wiemy nic włączenia

119
00:05:32,500 --> 00:05:35,560
jeszcze inny niż dane.

120
00:05:35,560 --> 00:05:37,080
I chcemy wykorzystać wszystkie dane.

121
00:05:37,080 --> 00:05:39,830
Nie chcemy po prostu użyć kawałek
o tym, chcemy wykorzystać wszystkie.

122
00:05:39,830 --> 00:05:41,710
Funkcja skrótu powinna
być deterministyczny.

123
00:05:41,710 --> 00:05:42,550
Co to znaczy?

124
00:05:42,550 --> 00:05:46,200
Cóż to oznacza, że ​​za każdym razem,
mijają dokładnie ten sam kawałek danych

125
00:05:46,200 --> 00:05:50,040
do funkcji mieszającej zawsze
uzyskać ten sam hashcode się.

126
00:05:50,040 --> 00:05:52,870
Jeśli mijam Jana Into the
funkcja skrótu wyjdę 4.

127
00:05:52,870 --> 00:05:56,110
Powinienem być w stanie to zrobić 10000
razy i zawsze będę dostać 4.

128
00:05:56,110 --> 00:06:00,810
Więc nie ma liczb losowych skutecznie
mogą być zaangażowane w naszej hash tables--

129
00:06:00,810 --> 00:06:02,750
w naszych funkcji skrótu.

130
00:06:02,750 --> 00:06:05,750
>> Funkcja skrótu powinien również
równomiernie rozprowadzić danych.

131
00:06:05,750 --> 00:06:09,700
Jeśli przy każdym uruchomieniu danych poprzez
funkcja skrótu masz hashcode 0,

132
00:06:09,700 --> 00:06:11,200
to chyba nie tak wielki, prawda?

133
00:06:11,200 --> 00:06:14,600
Prawdopodobnie chcesz duże
zakres kodów cebulą.

134
00:06:14,600 --> 00:06:17,190
Również rzeczy mogą być rozłożone
na całym stole.

135
00:06:17,190 --> 00:06:23,210
A także, że byłoby wspaniale, jeśli naprawdę
podobne dane, jak John i Jonatana,

136
00:06:23,210 --> 00:06:26,320
Może były rozłożone zważyć
różne miejsca w tabeli mieszania.

137
00:06:26,320 --> 00:06:28,750
To byłoby miłe zaletą.

138
00:06:28,750 --> 00:06:31,250
>> Oto przykład z funkcji skrótu.

139
00:06:31,250 --> 00:06:33,150
Napisałem ten jeden się wcześniej.

140
00:06:33,150 --> 00:06:35,047
To nie jest szczególnie
dobra funkcja skrótu

141
00:06:35,047 --> 00:06:37,380
z powodów, że tak naprawdę nie
ponosić będzie w tej chwili.

142
00:06:37,380 --> 00:06:41,040
Ale widzisz, co tu się dzieje?

143
00:06:41,040 --> 00:06:44,420
Wydaje się, że jesteśmy deklarowanie zmiennej
zwana suma i ustawienie go równa 0.

144
00:06:44,420 --> 00:06:50,010
A potem widocznie robię coś
tak długo, jak strstr [j] nie jest równa

145
00:06:50,010 --> 00:06:52,490
interpretacja odwrotnego ukośnika 0.

146
00:06:52,490 --> 00:06:54,870
Co ja tam robi?

147
00:06:54,870 --> 00:06:57,440
>> Jest to w zasadzie tylko kolejny
sposób realizacji [? strl?]

148
00:06:57,440 --> 00:06:59,773
i wykrywanie, kiedy masz
osiągnął koniec łańcucha.

149
00:06:59,773 --> 00:07:02,480
Więc nie mam faktycznie
obliczyć długość łańcucha,

150
00:07:02,480 --> 00:07:05,640
Jestem po prostu za pomocą, kiedy uderzył w
backslash 0 znak wiem

151
00:07:05,640 --> 00:07:07,185
I już dobiega końca łańcucha.

152
00:07:07,185 --> 00:07:09,560
A potem mam zamiar utrzymać
iteracja tego łańcucha,

153
00:07:09,560 --> 00:07:15,310
dodanie strstr [J], aby podsumować, a następnie na
Koniec dnia powróci suma mod

154
00:07:15,310 --> 00:07:16,200
HASH_MAX.

155
00:07:16,200 --> 00:07:18,700
>> W zasadzie to wszystko hash
Funkcja robi jest dodanie

156
00:07:18,700 --> 00:07:23,450
wszystkie wartości ASCII
mój ciąg, i to jest to

157
00:07:23,450 --> 00:07:26,390
powrót trochę hashcode
modded przez HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
To chyba rozmiar
mojej tablicy, prawda?

159
00:07:29,790 --> 00:07:33,160
Nie chcę, aby być coraz hash
Kody jeśli tablica ma rozmiar 10,

160
00:07:33,160 --> 00:07:35,712
Nie chcę być coraz
spośród kody hash 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, nie mogę umieścić rzeczy w
te lokalizacje tablicy,

162
00:07:38,690 --> 00:07:39,790
że byłoby nielegalne.

163
00:07:39,790 --> 00:07:42,130
Chciałbym ponieść winy segmentacji.

164
00:07:42,130 --> 00:07:45,230
>> Teraz tu jest inny szybkie bok.

165
00:07:45,230 --> 00:07:48,470
Generalnie jesteś prawdopodobnie nie będzie
chcą pisać własne funkcje skrótu.

166
00:07:48,470 --> 00:07:50,997
To jest rzeczywiście trochę
sztuką, a nie nauką.

167
00:07:50,997 --> 00:07:52,580
I jest wiele, że idzie do nich.

168
00:07:52,580 --> 00:07:55,288
Internet, jak powiedziałem, jest pełna
naprawdę dobrych funkcji skrótu,

169
00:07:55,288 --> 00:07:58,470
i należy korzystać z internetu do
znaleźć funkcje skrótu, bo to jest naprawdę

170
00:07:58,470 --> 00:08:03,230
po prostu rodzaj niepotrzebne
strata czasu, aby utworzyć własne.

171
00:08:03,230 --> 00:08:05,490
>> Możesz napisać prostych
do celów testowych.

172
00:08:05,490 --> 00:08:08,323
Ale kiedy rzeczywiście będziemy
rozpoczęcie mieszania danych i przechowywania go

173
00:08:08,323 --> 00:08:10,780
w tabeli mieszania jesteś
prawdopodobnie będzie chciał

174
00:08:10,780 --> 00:08:14,580
używać niektórych funkcji, które zostały wygenerowane
dla Ciebie, który istnieje w Internecie.

175
00:08:14,580 --> 00:08:17,240
Jeśli nie po prostu mieć pewność,
przytoczyć swoje źródła.

176
00:08:17,240 --> 00:08:21,740
Nie ma powodu, aby
plagiat cokolwiek tutaj.

177
00:08:21,740 --> 00:08:25,370
>> Społeczność informatyka jest
zdecydowanie rośnie, a tak naprawdę wartości

178
00:08:25,370 --> 00:08:28,796
open source, i to jest bardzo ważne
przytoczyć swoje źródła tak, że ludzie

179
00:08:28,796 --> 00:08:30,670
może uzyskać przypisanie do
praca, że ​​są one

180
00:08:30,670 --> 00:08:32,312
robi dla dobra wspólnoty.

181
00:08:32,312 --> 00:08:34,020
Więc zawsze sure--
a nie tylko hash

182
00:08:34,020 --> 00:08:37,270
funkcje, ale na ogół, gdy
używać kodu z zewnętrznego źródła

183
00:08:37,270 --> 00:08:38,299
zawsze cytują źródło.

184
00:08:38,299 --> 00:08:43,500
Podajesz autorstwo osoby zrobił
niektóre prace, więc nie trzeba.

185
00:08:43,500 --> 00:08:46,720
>> OK, więc niech to ponownie to
tablica mieszająca na sekundę.

186
00:08:46,720 --> 00:08:48,780
To jest, gdy wyszliśmy
się po tym włożona

187
00:08:48,780 --> 00:08:53,300
Jana i Pawła w tej tabeli hash.

188
00:08:53,300 --> 00:08:55,180
Czy widzisz tu problem?

189
00:08:55,180 --> 00:08:58,410
Można zobaczyć dwa.

190
00:08:58,410 --> 00:09:02,240
Ale przede wszystkim, prawda
zobacz ten możliwy problem?

191
00:09:02,240 --> 00:09:06,770
>> Co zrobić, jeśli hash Ringo, i to
Okazuje się, że po przetworzeniu

192
00:09:06,770 --> 00:09:14,000
że dane za pomocą funkcji skrótu
Ringo generowane również hashcode 6.

193
00:09:14,000 --> 00:09:16,810
Mam już dane na
hashcode-- lokalizacja tablicy 6.

194
00:09:16,810 --> 00:09:22,000
Więc to chyba będzie nieco
problem dla mnie teraz, prawda?

195
00:09:22,000 --> 00:09:23,060
>> Nazywamy to kolizja.

196
00:09:23,060 --> 00:09:26,460
I kolizji występuje wtedy, gdy dwa
kawałki danych prowadzony przez ten sam hash

197
00:09:26,460 --> 00:09:29,200
Funkcja dają ten sam hashcode.

198
00:09:29,200 --> 00:09:32,850
Prawdopodobnie nadal chcemy się zarówno
kawałki danych do tabeli hash,

199
00:09:32,850 --> 00:09:36,330
w przeciwnym razie nie będzie uruchomiony Ringo
arbitralnie za pośrednictwem funkcji skrótu.

200
00:09:36,330 --> 00:09:40,870
My prawdopodobnie chcą się
Ringo do tej tablicy.

201
00:09:40,870 --> 00:09:46,070
>> Jak mamy to zrobić jednak, jeśli
i Paul zarówno wydajność hashCode 6?

202
00:09:46,070 --> 00:09:49,520
Nie chcemy, aby zastąpić Pawła,
chcemy Paweł tam być też.

203
00:09:49,520 --> 00:09:52,790
Więc musimy znaleźć sposób, aby uzyskać
elementów w tablicy mieszającej, że

204
00:09:52,790 --> 00:09:56,550
nadal zachowuje nasze szybkie
wstawiania i szybkie spojrzenie w górę.

205
00:09:56,550 --> 00:10:01,350
A jednym ze sposobów radzenia sobie z nim jest
zrobić coś o nazwie liniowa sondowania.

206
00:10:01,350 --> 00:10:04,170
>> Korzystając z tej metody, jeśli mamy
kolizji, dobrze, co mamy robić?

207
00:10:04,170 --> 00:10:08,580
Cóż, nie można umieścić go w miejscu tablicy
6, lub cokolwiek hashCode został wygenerowany,

208
00:10:08,580 --> 00:10:10,820
postawmy go w hashcode plus 1.

209
00:10:10,820 --> 00:10:13,670
A jeśli to pełna Miejmy
umieścić go w hashcode plus 2.

210
00:10:13,670 --> 00:10:17,420
Zaletą tej istoty, czy on
nie dokładnie tam, gdzie uważamy, że jest,

211
00:10:17,420 --> 00:10:20,850
i musimy rozpocząć wyszukiwanie,
może nie trzeba iść za daleko.

212
00:10:20,850 --> 00:10:23,900
Być może nie musimy szukać
wszystkie elementy n z tabeli mieszania.

213
00:10:23,900 --> 00:10:25,790
Być może mamy do wyszukiwania
kilka z nich.

214
00:10:25,790 --> 00:10:30,680
>> I tak my wciąż zmierza w kierunku
że średnia Sprawa jest blisko do 1 vs

215
00:10:30,680 --> 00:10:34,280
blisko n, więc może, że będzie działać.

216
00:10:34,280 --> 00:10:38,010
Zobaczmy więc, jak to
Może pracować w rzeczywistości.

217
00:10:38,010 --> 00:10:41,460
I zobaczmy, czy może uda nam się wykryć
problem, który może pojawić się tutaj.

218
00:10:41,460 --> 00:10:42,540
>> Powiedzmy, że hash Bart.

219
00:10:42,540 --> 00:10:45,581
Więc teraz mamy zamiar uruchomić nowy zestaw
strun poprzez funkcji skrótu,

220
00:10:45,581 --> 00:10:48,460
i prowadzimy Bart przez hash
Funkcja, mamy hashcode 6.

221
00:10:48,460 --> 00:10:52,100
Przyjrzymy, zobaczymy 6
pusta, więc możemy umieścić Bart tam.

222
00:10:52,100 --> 00:10:55,410
>> Teraz hash Lisa i że
również generuje hashcode 6.

223
00:10:55,410 --> 00:10:58,330
No to teraz, że używamy tego
liniowa sondowania metody zaczynamy na 6,

224
00:10:58,330 --> 00:10:59,330
widzimy, że 6 jest pełna.

225
00:10:59,330 --> 00:11:00,990
Nie możemy umieścić Lisa w 6.

226
00:11:00,990 --> 00:11:02,090
Więc gdzie pójdziemy?

227
00:11:02,090 --> 00:11:03,280
Chodźmy do 7.

228
00:11:03,280 --> 00:11:04,610
7 jest pusta, tak, że działa.

229
00:11:04,610 --> 00:11:06,510
Więc postawmy Lisa tam.

230
00:11:06,510 --> 00:11:10,200
>> Teraz hash Homera i mamy 7.

231
00:11:10,200 --> 00:11:13,380
OK, dobrze wiemy, że 7 jest pełne
teraz, więc nie możemy umieścić Homer istnieje.

232
00:11:13,380 --> 00:11:14,850
Więc chodźmy do 8.

233
00:11:14,850 --> 00:11:15,664
Czy 8 dostępne?

234
00:11:15,664 --> 00:11:18,330
Tak, i 8, niedaleko 7, więc jeśli
musimy rozpocząć wyszukiwanie jesteśmy

235
00:11:18,330 --> 00:11:20,020
nie będzie musiał iść za daleko.

236
00:11:20,020 --> 00:11:22,860
A więc postawmy Homera na 8.

237
00:11:22,860 --> 00:11:25,151
>> Teraz hash Maggie i
zwraca 3, dzięki Bogu

238
00:11:25,151 --> 00:11:26,650
jesteśmy w stanie po prostu umieścić Maggie tam.

239
00:11:26,650 --> 00:11:29,070
Nie mamy zrobić dowolny
rodzaj sondowania za to.

240
00:11:29,070 --> 00:11:32,000
Teraz hash Marge, a
Marge zwraca również 6.

241
00:11:32,000 --> 00:11:39,560
>> Cóż 6 jest pełna, 7 jest pełna, 8 jest pełna,
9, w porządku dziękuję Bogu, 9 jest pusty.

242
00:11:39,560 --> 00:11:41,600
Mogę umieścić Marge na 9.

243
00:11:41,600 --> 00:11:45,280
Już widzimy, że zaczynamy
mieć ten problem, gdzie teraz jesteśmy

244
00:11:45,280 --> 00:11:48,780
zaczynają się rozciągać rzeczy rodzaj
z dala od swoich kodeksów z cebulą.

245
00:11:48,780 --> 00:11:52,960
I że theta 1, że średnie
Sprawa jest stała czasowa,

246
00:11:52,960 --> 00:11:56,560
zaczyna się trochę more--
zaczyna się zwykle trochę więcej

247
00:11:56,560 --> 00:11:58,050
do teta n.

248
00:11:58,050 --> 00:12:01,270
Zaczynamy tracić, że
Zaletą tablic hash.

249
00:12:01,270 --> 00:12:03,902
>> To problem, który właśnie zobaczył
jest coś, co nazywa klastrów.

250
00:12:03,902 --> 00:12:06,360
A co jest naprawdę źle
klastrów jest to, że po ciebie

251
00:12:06,360 --> 00:12:09,606
mają dwa elementy, znajdujące się obok
bok, to sprawia, że ​​nawet bardziej prawdopodobne,

252
00:12:09,606 --> 00:12:11,480
masz dwa razy
szansa, że ​​masz zamiar

253
00:12:11,480 --> 00:12:13,516
mieć inną kolizję
z tego klastra,

254
00:12:13,516 --> 00:12:14,890
a klaster wzrośnie o jeden.

255
00:12:14,890 --> 00:12:19,640
I będziesz trzymać rośnie i rośnie
Twój prawdopodobieństwo konieczności kolizji.

256
00:12:19,640 --> 00:12:24,470
I w końcu to tylko tak źle
jako nie sortowanie danych w ogóle.

257
00:12:24,470 --> 00:12:27,590
>> Innym problemem jest jednak, że
wciąż, i tak daleko do tego punktu,

258
00:12:27,590 --> 00:12:30,336
mamy właśnie rodzaj
rozumiejąc, co się tabela mieszania jest,

259
00:12:30,336 --> 00:12:31,960
wciąż mamy tylko miejsce na 10 strun.

260
00:12:31,960 --> 00:12:37,030
Jeśli chcemy, aby kontynuować do mieszania
mieszkańcy Springfield,

261
00:12:37,030 --> 00:12:38,790
możemy dostać tylko 10 z nich tam.

262
00:12:38,790 --> 00:12:42,619
A jeśli spróbujemy dodać na 11 lub na 12,
nie mamy miejsca, aby je umieścić.

263
00:12:42,619 --> 00:12:45,660
Moglibyśmy być wiruje wokół w
kręgi próbują znaleźć puste miejsce,

264
00:12:45,660 --> 00:12:49,000
i może utknąć
w nieskończonej pętli.

265
00:12:49,000 --> 00:12:51,810
>> Więc tego rodzaju nadaje się do idei
coś zwane łańcuchowym.

266
00:12:51,810 --> 00:12:55,790
I to jest, gdy mamy zamiar wnieść
związane z powrotem do listy obrazu.

267
00:12:55,790 --> 00:13:01,300
Co zrobić, jeśli zamiast przechowywać tylko
Sam dane w tablicy,

268
00:13:01,300 --> 00:13:04,471
każdy element tablicy mógł
posiadają wiele elementów danych?

269
00:13:04,471 --> 00:13:05,970
Dobrze, że nie ma sensu, prawda?

270
00:13:05,970 --> 00:13:09,280
Wiemy, że tablica może tylko
hold-- każdy element tablicy

271
00:13:09,280 --> 00:13:12,930
może posiadać tylko jeden kawałek
danych tego typu danych.

272
00:13:12,930 --> 00:13:16,750
>> Ale co, jeśli typ danych
Jest to związane lista, prawda?

273
00:13:16,750 --> 00:13:19,830
Co z tego, co
element macierz

274
00:13:19,830 --> 00:13:22,790
wskaźnik na czele połączonej listy?

275
00:13:22,790 --> 00:13:24,680
A potem możemy budować
te związane listy

276
00:13:24,680 --> 00:13:27,120
i rozwijać je w sposób arbitralny,
ponieważ związane listy pozwalają

277
00:13:27,120 --> 00:13:32,090
nam rosną i kurczą się dużo więcej
elastycznie niż tablica ma.

278
00:13:32,090 --> 00:13:34,210
Co z tego, że teraz używać,
możemy wykorzystać to, prawda?

279
00:13:34,210 --> 00:13:37,760
Zaczynamy rozwijać te łańcuchy
z tych lokalizacji tablicy.

280
00:13:37,760 --> 00:13:40,740
>> Teraz możemy zmieścić nieskończona
Ilość danych, czy nie nieskończona,

281
00:13:40,740 --> 00:13:44,170
dowolna ilość
Dane, na naszej tablicy mieszającej

282
00:13:44,170 --> 00:13:47,760
nigdy nie działa w
problem kolizji.

283
00:13:47,760 --> 00:13:50,740
Mamy również Usunęliśmy
klastrów w ten sposób.

284
00:13:50,740 --> 00:13:54,380
I dobrze wiemy, że gdy wstawiamy
w połączonej listy, jeśli przypomnieć

285
00:13:54,380 --> 00:13:57,779
z połączonych wideo na naszej liście, pojedynczo
związane listy i podwójnie związane listy,

286
00:13:57,779 --> 00:13:59,070
to ciągła praca razem.

287
00:13:59,070 --> 00:14:00,710
Jesteśmy po prostu dodając do przodu.

288
00:14:00,710 --> 00:14:04,400
>> A dla patrzeć, jak wiemy,
że wygląda się w połączonej listy

289
00:14:04,400 --> 00:14:05,785
może być problem, prawda?

290
00:14:05,785 --> 00:14:07,910
Musimy przeszukać
to od początku do końca.

291
00:14:07,910 --> 00:14:10,460
Nie ma losowo
dostęp w połączonej listy.

292
00:14:10,460 --> 00:14:15,610
Jeśli jednak zamiast jednego połączonego
Lista odnośników gdzie byłoby O n,

293
00:14:15,610 --> 00:14:19,590
teraz mamy 10 związane listy,
lub 1000 związane listy,

294
00:14:19,590 --> 00:14:24,120
teraz to wy n dzieli się przez 10,
lub O n dzieli się przez 1000.

295
00:14:24,120 --> 00:14:26,940
>> I kiedy rozmawialiśmy
teoretycznie o złożoności

296
00:14:26,940 --> 00:14:30,061
pominąć stałe, w prawdziwym
Świat te rzeczy naprawdę ważne,

297
00:14:30,061 --> 00:14:30,560
dobrze?

298
00:14:30,560 --> 00:14:33,080
My faktycznie zauważy
że tak się stanie

299
00:14:33,080 --> 00:14:36,610
uruchomić 10 razy szybciej,
lub 1000 razy szybciej,

300
00:14:36,610 --> 00:14:41,570
ponieważ jesteśmy dystrybucji jeden długi
Łańcuch całym 1000 mniejszych łańcuchów.

301
00:14:41,570 --> 00:14:45,090
I tak za każdym razem mamy do wyszukiwania
przez jeden z tych łańcuchów możemy

302
00:14:45,090 --> 00:14:50,290
ignorować 999 łańcuchy nie dbamy
o, i po prostu szukać tego.

303
00:14:50,290 --> 00:14:53,220
>> Które jest średnio
być 1000 razy krótszy.

304
00:14:53,220 --> 00:14:56,460
I tak nadal są rodzajem
zmierzające do tego przeciętnego przypadku

305
00:14:56,460 --> 00:15:01,610
bycia stałą czasu, ale
tylko dlatego, że wykorzystują

306
00:15:01,610 --> 00:15:03,730
podzielenie przez jakiś ogromny stały współczynnik.

307
00:15:03,730 --> 00:15:05,804
Zobaczmy, jak to może
faktycznie wygląda jakby.

308
00:15:05,804 --> 00:15:08,720
Więc to był tabeli mieszania mieliśmy
zanim oświadczył tabeli mieszania, które

309
00:15:08,720 --> 00:15:10,270
był zdolny do przechowywania 10 strun.

310
00:15:10,270 --> 00:15:11,728
Nie będziemy tego robić więcej.

311
00:15:11,728 --> 00:15:13,880
My już wiemy, że
Ograniczenia tej metody.

312
00:15:13,880 --> 00:15:20,170
Teraz nasz tabeli mieszania będzie
tablica z 10 węzłów, wskaźników

313
00:15:20,170 --> 00:15:22,120
do szefów połączonych listach.

314
00:15:22,120 --> 00:15:23,830
>> A teraz to jest wartość null.

315
00:15:23,830 --> 00:15:26,170
Każdy z tych 10 wskaźników jest null.

316
00:15:26,170 --> 00:15:29,870
Nie ma nic w naszej
tablica mieszająca teraz.

317
00:15:29,870 --> 00:15:32,690
>> Teraz zacznijmy umieścić niektóre
rzeczy w tej tabeli hash.

318
00:15:32,690 --> 00:15:35,440
I zobaczmy, jak ta metoda jest
zamierza skorzystać nam trochę.

319
00:15:35,440 --> 00:15:36,760
Załóżmy teraz hash Joey.

320
00:15:36,760 --> 00:15:40,210
Będziemy uruchomi łańcuch Joey przez
funkcja mieszania i wracamy 6.

321
00:15:40,210 --> 00:15:41,200
No i co teraz zrobimy?

322
00:15:41,200 --> 00:15:44,090
>> No to teraz pracuje z połączonych listach,
nie jesteśmy pracy z tablicami.

323
00:15:44,090 --> 00:15:45,881
A kiedy pracujemy
z połączonych listach mamy

324
00:15:45,881 --> 00:15:49,790
wiem, musimy zacząć dynamicznie
Alokacja przestrzeni i budowy sieci.

325
00:15:49,790 --> 00:15:54,020
To rodzaj how-- te są podstawą
elementy budowy połączonej listy.

326
00:15:54,020 --> 00:15:57,670
Więc niech się dynamicznie
przydzielić miejsca na Joey'a,

327
00:15:57,670 --> 00:16:00,390
a następnie dodajmy go do łańcucha.

328
00:16:00,390 --> 00:16:03,170
>> Tak teraz wygląda, co zrobiliśmy.

329
00:16:03,170 --> 00:16:06,440
Kiedy hash Joey mamy hashcode 6.

330
00:16:06,440 --> 00:16:11,790
Teraz kursor w miejscu tablicy 6
wskazuje na czele połączonej listy,

331
00:16:11,790 --> 00:16:14,900
a teraz jest to tylko
element połączonego listy.

332
00:16:14,900 --> 00:16:18,350
Oraz węzeł że
związane lista jest Joey.

333
00:16:18,350 --> 00:16:22,300
>> Więc jeśli musimy patrzeć Joey
później, po prostu hash Joey znowu,

334
00:16:22,300 --> 00:16:26,300
mamy 6 ponownie, ponieważ nasze
funkcja skrótu jest deterministyczny.

335
00:16:26,300 --> 00:16:30,400
I wtedy zaczynają się od głowy
z połączonej listy wskazał

336
00:16:30,400 --> 00:16:33,360
się według lokalizacji tablicy
6, i możemy iteracji

337
00:16:33,360 --> 00:16:35,650
poprzek, że stara się znaleźć Joey.

338
00:16:35,650 --> 00:16:37,780
A jeśli budujemy
skutecznie tablica mieszająca,

339
00:16:37,780 --> 00:16:41,790
a nasza funkcja skrótu skutecznie
do dystrybucji danych oraz,

340
00:16:41,790 --> 00:16:45,770
średnio każda z nich połączona
Listy w każdym miejscu tablicy

341
00:16:45,770 --> 00:16:50,110
będzie 1/10 wielkości, jeśli
po prostu musiałem go jako jeden ogromny

342
00:16:50,110 --> 00:16:51,650
związane lista ze wszystkim w nim.

343
00:16:51,650 --> 00:16:55,670
>> Jeśli będziemy rozpowszechniać, że ogromna powiązane
Lista w 10 połączonych list

344
00:16:55,670 --> 00:16:57,760
Każda lista będzie 1/10 wielkości.

345
00:16:57,760 --> 00:17:01,432
A więc 10 razy szybciej
przeszukiwać.

346
00:17:01,432 --> 00:17:02,390
Więc zróbmy to jeszcze raz.

347
00:17:02,390 --> 00:17:04,290
Załóżmy teraz hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> I powiedzmy, Ross, kiedy to zrobić
kod skrótu wrócimy to 2.

349
00:17:07,540 --> 00:17:10,630
No to teraz mamy dynamicznie lokować
nowy węzeł, kładziemy Ross w tym węźle,

350
00:17:10,630 --> 00:17:14,900
i mówimy teraz położenie tablicy
2, zamiast wskazywać na null,

351
00:17:14,900 --> 00:17:18,579
wskazuje na czele powiązane
Lista których tylko węzeł jest Ross.

352
00:17:18,579 --> 00:17:22,660
I możemy zrobić to jeszcze raz, my
może hash Rachel i uzyskać hashcode 4.

353
00:17:22,660 --> 00:17:25,490
malloc nowy węzeł, umieścić Rachel w
węzeł, i powiedzieć lokalizację tablicy

354
00:17:25,490 --> 00:17:27,839
4 teraz wskazuje na głowie
z połączonej listy, której

355
00:17:27,839 --> 00:17:31,420
Jedynym elementem dzieje się Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK, ale co się stanie, jeśli
mamy kolizję?

357
00:17:33,470 --> 00:17:38,560
Zobaczmy, jak obchodzimy kolizji
użyciu osobnej metody łańcuchowym.

358
00:17:38,560 --> 00:17:39,800
Miejmy hash Phoebe.

359
00:17:39,800 --> 00:17:41,094
Dostajemy hashcode 6.

360
00:17:41,094 --> 00:17:44,010
W poprzednim przykładzie były tylko
przechowywania ciągów w tablicy.

361
00:17:44,010 --> 00:17:45,980
To był problem.

362
00:17:45,980 --> 00:17:48,444
>> Nie chcemy, by sprać
Joey, i już mam

363
00:17:48,444 --> 00:17:51,110
widać, że możemy trochę klastrów
problemy, jeśli staramy się krok

364
00:17:51,110 --> 00:17:52,202
przez i sondy.

365
00:17:52,202 --> 00:17:54,660
Ale co, jeśli po prostu rodzaj
traktować to w ten sam sposób, prawda?

366
00:17:54,660 --> 00:17:57,440
To tak jak dodanie elementu
na czele połączonej listy.

367
00:17:57,440 --> 00:18:00,220
Miejmy tylko malloc przestrzeń dla Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Powiemy kolejne punkty pointer Phoebe
do starego szefa połączonej listy,

369
00:18:04,764 --> 00:18:07,180
a następnie 6 prostu wskazuje na
Nowy szef połączonej listy.

370
00:18:07,180 --> 00:18:10,150
A teraz spójrz, zmieniliśmy Phoebe.

371
00:18:10,150 --> 00:18:14,210
Możemy teraz zapisać dwa
Elementy z hashcode 6

372
00:18:14,210 --> 00:18:17,170
i nie mamy żadnych problemów.

373
00:18:17,170 --> 00:18:20,147
>> To dość dużo wszystko
nie jest łańcuchowych.

374
00:18:20,147 --> 00:18:21,980
I łańcuchowym jest zdecydowanie
metoda to

375
00:18:21,980 --> 00:18:27,390
będzie najbardziej skuteczne dla Ciebie, jeśli
dane są przechowywane w tabeli mieszania.

376
00:18:27,390 --> 00:18:30,890
Ale to połączenie
tablice i związane listy

377
00:18:30,890 --> 00:18:36,080
razem tworzą tabeli mieszania faktycznie
znacznie poprawia zdolność

378
00:18:36,080 --> 00:18:40,550
do przechowywania dużych ilości danych, a
bardzo szybko i sprawnie wyszukać

379
00:18:40,550 --> 00:18:41,630
za pośrednictwem tych danych.

380
00:18:41,630 --> 00:18:44,150
>> Jest jeszcze jeden
Struktura danych tam

381
00:18:44,150 --> 00:18:48,700
że może być nawet nieco
lepiej jeśli chodzi o zagwarantowanie

382
00:18:48,700 --> 00:18:51,920
że nasz wstawianie, usuwanie i
patrzeć czasy w jeszcze szybciej.

383
00:18:51,920 --> 00:18:55,630
I zobaczymy, że w wideo na próbach.

384
00:18:55,630 --> 00:18:58,930
Jestem Doug Lloyd, to CS50.

385
00:18:58,930 --> 00:19:00,214