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

2
00:00:00,500 --> 00:00:01,900
[Mūzikas atskaņošanai]

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

4
00:00:05,710 --> 00:00:09,150
>> Doug LLOYD: Tagad jums
zina daudz par masīvu,

5
00:00:09,150 --> 00:00:11,610
un jūs zināt daudz par saistītiem sarakstiem.

6
00:00:11,610 --> 00:00:13,650
Un mēs esam apspriestu
plusi un mīnusi, mēs esam

7
00:00:13,650 --> 00:00:16,620
apsprieda, ka saistīti saraksti
var iegūt lielāku un mazāku,

8
00:00:16,620 --> 00:00:18,630
bet tie aizņem vairāk lielumu.

9
00:00:18,630 --> 00:00:22,359
Masīvi ir daudz vienkāršāk
izmantot, bet viņi ierobežojošs tik daudz

10
00:00:22,359 --> 00:00:24,900
kā mums ir noteikt lielumu
masīva pašā sākumā

11
00:00:24,900 --> 00:00:26,910
un tad mēs esam iestrēdzis ar to.

12
00:00:26,910 --> 00:00:30,470
>> Bet tas ir, mēs esam diezgan daudz
izsmeltas visas mūsu tēmām

13
00:00:30,470 --> 00:00:33,040
par saistītiem sarakstiem un masīvi.

14
00:00:33,040 --> 00:00:34,950
Vai mēs esam?

15
00:00:34,950 --> 00:00:37,720
Varbūt mēs varam kaut ko darīt
vēl vairāk radošs.

16
00:00:37,720 --> 00:00:40,950
Un ka veida aizdod
ideja par hash tabulu.

17
00:00:40,950 --> 00:00:46,680
>> Tātad hash tabulā mēs esam gatavojas izmēģināt
apvienot masīvu ar saistītajā sarakstā.

18
00:00:46,680 --> 00:00:49,520
Mēs ejam, lai ņemtu priekšrocības
masīva, tāpat izlases pieejamību,

19
00:00:49,520 --> 00:00:53,510
to var tikai iet uz masīva
elements 4 vai masīva elements 8

20
00:00:53,510 --> 00:00:55,560
bez atkārtot pāri.

21
00:00:55,560 --> 00:00:57,260
Tas ir diezgan ātri, vai ne?

22
00:00:57,260 --> 00:01:00,714
>> Bet mēs arī vēlamies, lai mūsu datiem
struktūra varētu augt un sarauties.

23
00:01:00,714 --> 00:01:02,630
Mums nevajag, mums nav
vēlas, lai tiktu ierobežota.

24
00:01:02,630 --> 00:01:04,588
Un mēs gribam, lai varētu
pievienot un noņemt lietas

25
00:01:04,588 --> 00:01:08,430
ļoti viegli, kas, ja jūs atceraties,
ir ļoti komplekss ar masīvu.

26
00:01:08,430 --> 00:01:11,650
Un mēs varam zvanīt šis
jauna lieta hash tabulu.

27
00:01:11,650 --> 00:01:15,190
>> Un, ja tos piemēro pareizi,
mēs esam veida ņemot

28
00:01:15,190 --> 00:01:18,150
priekšrocības gan datu
struktūras jūs jau esat redzējuši,

29
00:01:18,150 --> 00:01:19,880
bloki un saistīti saraksti.

30
00:01:19,880 --> 00:01:23,070
Ievietošana var sākt
tendence uz teta no 1.

31
00:01:23,070 --> 00:01:26,207
Theta mēs neesam īsti apspriesti,
bet teta ir tikai vidējā gadījums,

32
00:01:26,207 --> 00:01:27,540
to, kas patiesībā notiek varētu notikt.

33
00:01:27,540 --> 00:01:29,680
Jūs esat ne vienmēr būs
ir sliktākajam scenārijam,

34
00:01:29,680 --> 00:01:32,555
un jūs ne vienmēr nāksies
Labākajā gadījumā, lai to, kas ir

35
00:01:32,555 --> 00:01:33,900
vidējais scenārijs?

36
00:01:33,900 --> 00:01:36,500
>> Nu vidēji ievietošanas
uz hash tabulu

37
00:01:36,500 --> 00:01:39,370
var sākt iegūt tuvu pastāvīgu laiku.

38
00:01:39,370 --> 00:01:41,570
Un dzēšanu var iegūt
aizvērt uz pastāvīgu laiku.

39
00:01:41,570 --> 00:01:44,440
Un lookup var saņemt
aizvērt uz pastāvīgu laiku.

40
00:01:44,440 --> 00:01:48,600
That's-- mums nav datu
struktūra vēl, ka var darīt,

41
00:01:48,600 --> 00:01:51,180
un tāpēc tas jau izklausās
kā diezgan liels lieta.

42
00:01:51,180 --> 00:01:57,010
Mēs esam patiešām mazinājis
trūkumi katra pati.

43
00:01:57,010 --> 00:01:59,160
>> Lai iegūtu šo sniegumu
uzlabot gan, mēs

44
00:01:59,160 --> 00:02:03,580
ir jāpārdomā, kā mēs pievienot
datus struktūru.

45
00:02:03,580 --> 00:02:07,380
Konkrēti mēs vēlamies
Paši dati, lai pastāstītu mums

46
00:02:07,380 --> 00:02:09,725
ja tas būtu jāiet struktūrā.

47
00:02:09,725 --> 00:02:12,850
Un, ja mēs, tad ir nepieciešams, lai redzētu, vai tas ir
struktūra, ja mums ir nepieciešams, lai atrastu to,

48
00:02:12,850 --> 00:02:16,610
mēs vēlamies apskatīt datus
atkal un jāspēj efektīvi,

49
00:02:16,610 --> 00:02:18,910
izmantojot datus, nejauši piekļūt.

50
00:02:18,910 --> 00:02:20,700
Vienkārši aplūkojot
dati mums ir jābūt

51
00:02:20,700 --> 00:02:25,890
ideja par to, kur tieši mēs esam
gatavojas atrast to hash tabulā.

52
00:02:25,890 --> 00:02:28,770
>> Tagad negatīvie jaucējkoda
Tabulā ir tas, ka viņi patiešām

53
00:02:28,770 --> 00:02:31,770
diezgan slikti pasūtīšanu vai šķirošanas datus.

54
00:02:31,770 --> 00:02:34,970
Un patiesībā, ja jūs sākat
tos izmantot, lai pasūtītu vai kārtot

55
00:02:34,970 --> 00:02:37,990
Datu jūs zaudējat visu iepriekš
priekšrocības jūs iepriekš

56
00:02:37,990 --> 00:02:40,710
bija ziņā ievietošanas un dzēšanu.

57
00:02:40,710 --> 00:02:44,060
Laiks kļūst tuvāk
teta n, un mēs esam būtībā

58
00:02:44,060 --> 00:02:45,530
regresējusi uz saistītajā sarakstā.

59
00:02:45,530 --> 00:02:48,850
Un tā mēs tikai vēlamies izmantot hash
galdi, ja mēs nerūp

60
00:02:48,850 --> 00:02:51,490
vai dati ir sakārtots.

61
00:02:51,490 --> 00:02:54,290
Par kontekstu, kādā
jūs tos izmantot CS50

62
00:02:54,290 --> 00:02:58,900
Jūs, iespējams, nav jārūpējas
ka dati ir sakārtots.

63
00:02:58,900 --> 00:03:03,170
>> Tātad hash tabulu, ir kombinācija
no diviem atšķirīgiem gabaliem

64
00:03:03,170 --> 00:03:04,980
ar kuru mēs esam pazīstami.

65
00:03:04,980 --> 00:03:07,930
Pirmais ir funkcija, kas
mēs parasti saucam jaucējfunkciju.

66
00:03:07,930 --> 00:03:11,760
Un tas hash funkcija ir gatavojas
atgriešanās kādu nav negatīvs vesels skaitlis, kas

67
00:03:11,760 --> 00:03:14,870
mēs parasti saucam hashcode, OK?

68
00:03:14,870 --> 00:03:20,230
Otrais gabals ir masīvs, kas ir
spēj uzglabāt datu tipa mēs

69
00:03:20,230 --> 00:03:22,190
vēlas izvietot uz datu struktūru.

70
00:03:22,190 --> 00:03:24,310
Mēs turēt off par
saistīts saraksts elements tagad

71
00:03:24,310 --> 00:03:27,810
un sāc ar pamatiem, tāda
hash tabulu, lai saņemtu savu galvu ap to,

72
00:03:27,810 --> 00:03:30,210
un tad mēs varbūt trieciens
Jūsu prāts mazliet, kad mēs

73
00:03:30,210 --> 00:03:32,920
apvienot bloki un saistīt sarakstus kopā.

74
00:03:32,920 --> 00:03:35,590
>> Pamatideja though
ir mēs dažus datus.

75
00:03:35,590 --> 00:03:37,860
Mums ir, ka dati, izmantojot
hash funkciju.

76
00:03:37,860 --> 00:03:41,980
Un tā datus apstrādā
un tas atklepo numuru, OK?

77
00:03:41,980 --> 00:03:44,890
Un pēc tam ar šo numuru
mēs tikai glabāt datus

78
00:03:44,890 --> 00:03:48,930
mēs vēlamies Uzglabāt
masīvs šajā vietā.

79
00:03:48,930 --> 00:03:53,990
Tā, piemēram, mums ir varbūt
šis hash tabulu stīgas.

80
00:03:53,990 --> 00:03:57,350
Tas ir ieguvuši 10 elementi, tāpēc
mēs varam fit 10 stīgas tajā.

81
00:03:57,350 --> 00:03:59,320
>> Teiksim, mēs vēlamies, lai hash Jāni.

82
00:03:59,320 --> 00:04:02,979
Tātad Jāņa kā datiem mēs gribam, lai ievietotu
šajā hash tabulu kaut kur.

83
00:04:02,979 --> 00:04:03,770
Kur mēs to?

84
00:04:03,770 --> 00:04:05,728
Nu parasti ar
masīvs Līdz šim mēs, iespējams,

85
00:04:05,728 --> 00:04:07,610
nostāda to masīva atrašanās vietā 0.

86
00:04:07,610 --> 00:04:09,960
Bet tagad mums ir šo jauno hash funkciju.

87
00:04:09,960 --> 00:04:13,180
>> Un pieņemsim, ka mēs palaist Jāni
izmantojot šo jaucējfunkciju

88
00:04:13,180 --> 00:04:15,417
un tas ir atklepo 4.

89
00:04:15,417 --> 00:04:17,500
Nu tas ir, ja mēs esam
gatavojas vēlaties likt Jāni.

90
00:04:17,500 --> 00:04:22,050
Mēs vēlamies, lai Jāni masīva vietā
4, jo, ja mēs hash Jāņa again--

91
00:04:22,050 --> 00:04:23,810
teiksim vēlāk mēs
vēlaties meklēt un redzēt

92
00:04:23,810 --> 00:04:26,960
ja John pastāv šajā hash
table-- viss, kas mums jādara,

93
00:04:26,960 --> 00:04:30,310
ir palaist to caur to pašu hash
funkcija, saņemt skaits 4,

94
00:04:30,310 --> 00:04:33,929
un jāspēj atrast Jāni
Nekavējoties mūsu datu struktūra.

95
00:04:33,929 --> 00:04:34,720
Tas ir diezgan labs.

96
00:04:34,720 --> 00:04:36,928
>> Teiksim, mēs tagad to izdarītu
atkal, mēs vēlamies, lai hash Pāvilu.

97
00:04:36,928 --> 00:04:39,446
Mēs vēlamies, lai pievienotu Paul
šajā hash tabulā.

98
00:04:39,446 --> 00:04:42,070
Teiksim, ka šoreiz mēs palaist
Paul caur hash funkciju,

99
00:04:42,070 --> 00:04:44,600
hashcode kas tiek radīts, ir 6.

100
00:04:44,600 --> 00:04:47,340
Nu tagad mēs varam likt Pāvilu
masīvā vietā 6.

101
00:04:47,340 --> 00:04:50,040
Un, ja mums ir nepieciešams meklēt, vai
Paul ir šajā hash tabulu,

102
00:04:50,040 --> 00:04:53,900
viss, kas mums jādara, ir palaist Paul
caur hash funkciju atkal

103
00:04:53,900 --> 00:04:55,830
un mēs esam gatavojas saņemt 6 no jauna.

104
00:04:55,830 --> 00:04:57,590
>> Un tad mēs vienkārši skatīties
pie masīva vietā 6.

105
00:04:57,590 --> 00:04:58,910
Vai Pāvils tur nokļūt?

106
00:04:58,910 --> 00:05:00,160
Ja tā, tad viņš ir hash tabulā.

107
00:05:00,160 --> 00:05:01,875
Vai Pāvils ne tur?

108
00:05:01,875 --> 00:05:03,000
Viņš nav hash tabulā.

109
00:05:03,000 --> 00:05:05,720
Tas ir diezgan vienkārši.

110
00:05:05,720 --> 00:05:07,770
>> Tagad, kā jūs definētu jaucējfunkciju?

111
00:05:07,770 --> 00:05:11,460
Nu tur tiešām nav ierobežojumu
vairāki iespējamie hash funkciju.

112
00:05:11,460 --> 00:05:14,350
Patiesībā tur ir vairāki patiešām,
tiešām labs tiem internetā.

113
00:05:14,350 --> 00:05:17,560
Tur ir vairāki patiešām,
tiešām slikti tiem internetā.

114
00:05:17,560 --> 00:05:21,080
Tas ir arī diezgan viegli
uzrakstīt slikti vienu.

115
00:05:21,080 --> 00:05:23,760
>> Tātad, kas veido labu
hash funkciju, vai ne?

116
00:05:23,760 --> 00:05:27,280
Nu labs hash funkcija būtu
izmantot tikai tiek sajaukts dati,

117
00:05:27,280 --> 00:05:29,420
un visi dati tiek sajaukts.

118
00:05:29,420 --> 00:05:32,500
Tāpēc mēs nevēlamies izmantot anything--
mums nav iekļaut neko

119
00:05:32,500 --> 00:05:35,560
cits citu kā datus.

120
00:05:35,560 --> 00:05:37,080
Un mēs vēlamies izmantot visus datus.

121
00:05:37,080 --> 00:05:39,830
Mēs nevēlamies, lai tikai izmantot kādu
par to, mēs vēlamies izmantot visu to.

122
00:05:39,830 --> 00:05:41,710
Hash funkcija būtu
arī deterministisko.

123
00:05:41,710 --> 00:05:42,550
Ko tas nozīmē?

124
00:05:42,550 --> 00:05:46,200
Nu tas nozīmē, ka katru reizi, kad mēs
iet tieši to pašu datu vienība

125
00:05:46,200 --> 00:05:50,040
uz hash funkciju, mēs vienmēr
saņemt tādu pašu hashcode out.

126
00:05:50,040 --> 00:05:52,870
Ja es iet Jāni Into
hash funkcija es izkļūt 4.

127
00:05:52,870 --> 00:05:56,110
Man vajadzētu būt iespējai to darīt, 10000
reizes, un es vienmēr saņemsiet 4.

128
00:05:56,110 --> 00:06:00,810
Līdz ar to nav izlases numuri efektīvi
var iesaistīties mūsu hash tables--

129
00:06:00,810 --> 00:06:02,750
mūsu hash funkcijas.

130
00:06:02,750 --> 00:06:05,750
>> Hash funkcija būtu arī
vienmērīgi izplatīt datus.

131
00:06:05,750 --> 00:06:09,700
Ja katru reizi, kad jūs darbināt datus, izmantojot
hash funkcija jums hashcode 0,

132
00:06:09,700 --> 00:06:11,200
tas ir iespējams, nav tik liels, labi?

133
00:06:11,200 --> 00:06:14,600
Jūs droši vien vēlaties liels
diapazons hash kodu.

134
00:06:14,600 --> 00:06:17,190
Arī lietas var izplatīties
out visā tabulā.

135
00:06:17,190 --> 00:06:23,210
Un arī tas būtu lieliski, ja patiešām
līdzīgi dati, piemēram, Jāņa un Jonathan,

136
00:06:23,210 --> 00:06:26,320
varbūt bija izklāt nosvērt
dažādās vietās hash tabulā.

137
00:06:26,320 --> 00:06:28,750
Tas būtu jauki priekšrocība.

138
00:06:28,750 --> 00:06:31,250
>> Lūk, piemērs no hash funkciju.

139
00:06:31,250 --> 00:06:33,150
Es uzrakstīju šo vienu agrāk.

140
00:06:33,150 --> 00:06:35,047
Tas nav īpaši
labs hash funkcija

141
00:06:35,047 --> 00:06:37,380
iemeslu dēļ, kas nav tiešām ir
sedz nonākšana tieši tagad.

142
00:06:37,380 --> 00:06:41,040
Bet vai jūs redzat, kas notiek šeit?

143
00:06:41,040 --> 00:06:44,420
Šķiet, tāpat kā mēs deklarējot mainīgo
sauc summa un nosakot to vienāds ar 0.

144
00:06:44,420 --> 00:06:50,010
Un tad acīmredzot es esmu dara kaut ko
tik ilgi, kamēr strstr [j] nav vienāds

145
00:06:50,010 --> 00:06:52,490
ar slīpsvītru 0.

146
00:06:52,490 --> 00:06:54,870
Ko es daru tur?

147
00:06:54,870 --> 00:06:57,440
>> Tas būtībā ir tikai vēl viens
veids, kā īstenot [? STRL?]

148
00:06:57,440 --> 00:06:59,773
un atklāšanā, kad esat
sasnieguši virknes.

149
00:06:59,773 --> 00:07:02,480
Tāpēc man nav reāli
aprēķināt garumu no virknes,

150
00:07:02,480 --> 00:07:05,640
Es esmu tikai izmantojot, kad es hit
slīpsvītru 0 raksturs es zinu

151
00:07:05,640 --> 00:07:07,185
Esmu sasnieguši virknes.

152
00:07:07,185 --> 00:07:09,560
Un tad es esmu gatavojas glabāt
atkārtojot caur šo auklu,

153
00:07:09,560 --> 00:07:15,310
pievienojot strstr [J], lai apkopotu, un pēc tam pie
dienas beigās gatavojas atgriezties summa mod

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

155
00:07:16,200 --> 00:07:18,700
>> Būtībā tas viss hash
funkcija dara tiek saskaitot

156
00:07:18,700 --> 00:07:23,450
visas ASCII vērtībām
mans stīgu, un tad tas ir

157
00:07:23,450 --> 00:07:26,390
atgriežoties kādu hashcode
modded ar HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Tas ir iespējams, izmērs
mana masīvs, labi?

159
00:07:29,790 --> 00:07:33,160
Es nevēlos iegūt hash
kodi, ja mans masīvs izmēru 10,

160
00:07:33,160 --> 00:07:35,712
Es nevēlos būt iegūt
izrakstās hash kodus 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, es nevaru ielikt lietas
šie vietām masīva,

162
00:07:38,690 --> 00:07:39,790
ka būtu nelikumīga.

163
00:07:39,790 --> 00:07:42,130
Es gribētu cieš segmentāciju vaina.

164
00:07:42,130 --> 00:07:45,230
>> Tagad šeit ir vēl viens ātrs malā.

165
00:07:45,230 --> 00:07:48,470
Parasti jūs, iespējams, nav gatavojas
gribu uzrakstīt savu hash funkcijas.

166
00:07:48,470 --> 00:07:50,997
Tas ir faktiski mazliet
māksla, nevis zinātne.

167
00:07:50,997 --> 00:07:52,580
Un tur ir daudz kas iet uz tiem.

168
00:07:52,580 --> 00:07:55,288
Internets, kā jau teicu, ir pilna
patiešām labas hash funkciju,

169
00:07:55,288 --> 00:07:58,470
un jums vajadzētu izmantot internetu, lai
atrast hash funkcijas, jo tas ir patiešām

170
00:07:58,470 --> 00:08:03,230
tikko veida nevajadzīgs
atkritumu laika, lai izveidotu savu.

171
00:08:03,230 --> 00:08:05,490
>> Jūs varat uzrakstīt vienkāršu ones
testēšanas nolūkos.

172
00:08:05,490 --> 00:08:08,323
Bet, ja jūs tiešām gatavojas
sākt sajaukšanai datus un uzglabājot

173
00:08:08,323 --> 00:08:10,780
uz hash tabulu jūs esat
droši vien vēlaties

174
00:08:10,780 --> 00:08:14,580
izmantot dažas funkcijas, kas tika radīts
jums, kas pastāv internetā.

175
00:08:14,580 --> 00:08:17,240
Ja jūs vienkārši būt pārliecināti,
citēt savus avotus.

176
00:08:17,240 --> 00:08:21,740
Nav iemesla
plagiarize kaut ko šeit.

177
00:08:21,740 --> 00:08:25,370
>> Datorzinātņu kopiena ir
noteikti pieaug, un tiešām vērtības

178
00:08:25,370 --> 00:08:28,796
open source, un tas ir patiešām svarīgi
citēt savus avotus, lai cilvēki

179
00:08:28,796 --> 00:08:30,670
var saņemt par piedēvēšanu
darbs, viņi

180
00:08:30,670 --> 00:08:32,312
dara, lai labā sabiedrībā.

181
00:08:32,312 --> 00:08:34,020
Tā vienmēr ir sure--
un ne tikai hash

182
00:08:34,020 --> 00:08:37,270
funkcijas, bet kopumā, ja jums
izmantot kodu no ārējiem avotiem,

183
00:08:37,270 --> 00:08:38,299
vienmēr citēt savu avotu.

184
00:08:38,299 --> 00:08:43,500
Jāpateicas personas, kura
daži no darba, lai jums nav.

185
00:08:43,500 --> 00:08:46,720
>> Labi, tāpēc pieņemsim pārskatīt šo
hash tabulu par sekundi.

186
00:08:46,720 --> 00:08:48,780
Tas ir, ja mēs pa kreisi
off, kad mēs ievietots

187
00:08:48,780 --> 00:08:53,300
Jānis un Pāvils šajā hash tabulā.

188
00:08:53,300 --> 00:08:55,180
Vai jūs redzat problēmu šeit?

189
00:08:55,180 --> 00:08:58,410
Jūs varētu redzēt divas.

190
00:08:58,410 --> 00:09:02,240
Bet jo īpaši, vai ne
skatīt šo problēmu?

191
00:09:02,240 --> 00:09:06,770
>> Ko darīt, ja es hash Ringo, un tas
Izrādās, ka pēc pārstrādes

192
00:09:06,770 --> 00:09:14,000
ka dati caur hash funkciju
Ringo arī radījusi hashcode 6.

193
00:09:14,000 --> 00:09:16,810
Esmu jau ieguvuši datus
hashcode-- masīvs vieta 6.

194
00:09:16,810 --> 00:09:22,000
Tātad, tas droši vien būs nedaudz
problēmu man tagad, vai ne?

195
00:09:22,000 --> 00:09:23,060
>> Mēs to saucam par sadursmes.

196
00:09:23,060 --> 00:09:26,460
Un sadursme notiek, ja divi
gabali datu palaist caur to pašu hash

197
00:09:26,460 --> 00:09:29,200
funkcija dot to pašu hashcode.

198
00:09:29,200 --> 00:09:32,850
Jādomā, ka mēs joprojām vēlaties saņemt gan
gabalus datus hash tabulu,

199
00:09:32,850 --> 00:09:36,330
citādi mēs nebūtu darboties Ringo
patvaļīgi izmantojot hash funkciju.

200
00:09:36,330 --> 00:09:40,870
Mēs, iespējams, vēlas saņemt
Ringo vērā, ka masīva.

201
00:09:40,870 --> 00:09:46,070
>> Kā mēs to darām, lai gan, ja viņš
un Paul gan raža hashcode 6?

202
00:09:46,070 --> 00:09:49,520
Mēs nevēlamies pārrakstīt Pāvilu
mēs gribam Paul būt tur pārāk.

203
00:09:49,520 --> 00:09:52,790
Tāpēc mums ir jāatrod veids, kā iegūt
elementus hash tabulu, kas

204
00:09:52,790 --> 00:09:56,550
joprojām saglabā mūsu ātri
ievietošanas un ātri uzmeklēt.

205
00:09:56,550 --> 00:10:01,350
Un viens veids, kā cīnīties ar to ir
darīt kaut ko sauc par lineāru zondēšana.

206
00:10:01,350 --> 00:10:04,170
>> Izmantojot šo metodi, ja mums ir
sadursme, labi, ko mēs darām?

207
00:10:04,170 --> 00:10:08,580
Nu mēs nevaram likt viņam masīva vietā
6, vai kāds hashcode tika radīts,

208
00:10:08,580 --> 00:10:10,820
Palūkosimies viņam hashcode plus 1.

209
00:10:10,820 --> 00:10:13,670
Un, ja tas ir pilns pieņemsim
ielika hashcode plus 2.

210
00:10:13,670 --> 00:10:17,420
Šīs būtnes labums, ja viņš ir
nav kur tieši mēs domāju, ka viņš ir,

211
00:10:17,420 --> 00:10:20,850
un mums ir jāsāk meklēt,
varbūt mums nav iet pārāk tālu.

212
00:10:20,850 --> 00:10:23,900
Varbūt mums nav, lai meklētu
visi n elementi hash tabulu.

213
00:10:23,900 --> 00:10:25,790
Varbūt mums ir jāmeklē
pāris no tiem.

214
00:10:25,790 --> 00:10:30,680
>> Un tā mēs joprojām tiekšanās
ka vidējais lieta ir tuvu 1 vs

215
00:10:30,680 --> 00:10:34,280
tuvu n, tāpēc varbūt, ka būs darbs.

216
00:10:34,280 --> 00:10:38,010
Tātad, pieņemsim redzēt, kā tas
varētu izstrādāt realitātē.

217
00:10:38,010 --> 00:10:41,460
Un pieņemsim redzēt, ja varbūt mēs varam atklāt
problēma, kas varētu notikt šeit.

218
00:10:41,460 --> 00:10:42,540
>> Teiksim mēs hash Bart.

219
00:10:42,540 --> 00:10:45,581
Tāpēc tagad mēs esam gatavojas palaist jaunu komplektu
Stīgu caur hash funkciju,

220
00:10:45,581 --> 00:10:48,460
un mēs palaist Bart caur hash
funkcija, mēs hashcode 6.

221
00:10:48,460 --> 00:10:52,100
Mēs to apskatīt, mēs redzam, ir 6
tukšs, tāpēc mēs varam likt Bart tur.

222
00:10:52,100 --> 00:10:55,410
>> Tagad mēs hash Lisa un ka
arī rada hashcode 6.

223
00:10:55,410 --> 00:10:58,330
Nu tagad, ka mēs esam, izmantojot šo
lineārs zondēšanas metodi mēs sāktu 6,

224
00:10:58,330 --> 00:10:59,330
mēs redzam, ka 6. ir pilna.

225
00:10:59,330 --> 00:11:00,990
Mēs nevaram likt Lisa 6. punktā.

226
00:11:00,990 --> 00:11:02,090
Tātad, ja mēs ejam?

227
00:11:02,090 --> 00:11:03,280
Ejam uz 7.

228
00:11:03,280 --> 00:11:04,610
7 ir tukša, tā ka strādā.

229
00:11:04,610 --> 00:11:06,510
Tātad pieņemsim likts Lisa tur.

230
00:11:06,510 --> 00:11:10,200
>> Tagad mēs hash Homērs un mēs 7.

231
00:11:10,200 --> 00:11:13,380
Labi labi mēs zinām, ka 7 ir pilna
tagad, tāpēc mēs nevaram likt Homer tur.

232
00:11:13,380 --> 00:11:14,850
So iesim līdz 8.

233
00:11:14,850 --> 00:11:15,664
Vai 8 ir pieejama?

234
00:11:15,664 --> 00:11:18,330
Jā, un 8 ir tuvu 7, tādēļ, ja
mums ir jāsāk meklēt, mēs esam

235
00:11:18,330 --> 00:11:20,020
nav nāksies iet pārāk tālu.

236
00:11:20,020 --> 00:11:22,860
Un tāpēc pieņemsim nodot Homer pēc 8.

237
00:11:22,860 --> 00:11:25,151
>> Tagad mēs hash Maggie un
atgriež 3, paldies dievam

238
00:11:25,151 --> 00:11:26,650
mēs esam spējīgi tikai likt Maggie tur.

239
00:11:26,650 --> 00:11:29,070
Mums nav jādara kādu
veida zondēšana par to.

240
00:11:29,070 --> 00:11:32,000
Tagad mēs hash Marge, un
Marge arī atgriež 6.

241
00:11:32,000 --> 00:11:39,560
>> Nu 6 ir pilna, 7 ir pilna, 8 ir pilna,
9, labi paldies Dievam, 9 ir tukšs.

242
00:11:39,560 --> 00:11:41,600
Es varu likt Marge pie 9.

243
00:11:41,600 --> 00:11:45,280
Jau mēs varam redzēt, ka mēs sākam
lai šo problēmu, kur tagad mēs esam

244
00:11:45,280 --> 00:11:48,780
sāk stiept lietas veida
no tālu prom no saviem hash kodiem.

245
00:11:48,780 --> 00:11:52,960
Un ka teta 1, ka vidējais
gadījums ir nemainīgs laiks,

246
00:11:52,960 --> 00:11:56,560
sāk saņemt mazliet more--
sāk tendence nedaudz vairāk

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

248
00:11:58,050 --> 00:12:01,270
Mēs sākam zaudēt, ka
priekšrocība hash tabulu.

249
00:12:01,270 --> 00:12:03,902
>> Šī problēma, ka mēs tikko redzējām
ir kaut kas ko sauc par klasteru.

250
00:12:03,902 --> 00:12:06,360
Un, kas ir patiešām slikti par
sakopojums ir tas, ka jums tagad

251
00:12:06,360 --> 00:12:09,606
ir divi elementi, kas atrodas blakus
puses tas padara to vēl vairāk iespējams,

252
00:12:09,606 --> 00:12:11,480
Jums ir dubults
iespēja, ka jūs gatavojas

253
00:12:11,480 --> 00:12:13,516
vēl vienu sadursmi
ar šo kopu,

254
00:12:13,516 --> 00:12:14,890
un klasteru pieaugs par vienu.

255
00:12:14,890 --> 00:12:19,640
Un jūs pastāvīgi aug un aug
Jūsu iespēja, ka tā sadursmes.

256
00:12:19,640 --> 00:12:24,470
Un galu galā tas ir tikpat slikts
kā nav šķirošanas datus vispār.

257
00:12:24,470 --> 00:12:27,590
>> Otra problēma, lai gan ir mums
vēl, un līdz šim līdz šim punktam,

258
00:12:27,590 --> 00:12:30,336
mēs esam tikko veida
saprastu, kas hash tabula ir,

259
00:12:30,336 --> 00:12:31,960
mums vēl ir tikai telpa 10 stīgas.

260
00:12:31,960 --> 00:12:37,030
Ja mēs vēlamies turpināt hash
pilsoņi Springfield,

261
00:12:37,030 --> 00:12:38,790
mēs varam tikai iegūt 10 no tiem tur.

262
00:12:38,790 --> 00:12:42,619
Un, ja mēs mēģinātu pievienot 11th vai 12,
mums nav vieta, kur nodot tos.

263
00:12:42,619 --> 00:12:45,660
Mēs varētu vienkārši vērpšanas ap
apļi mēģinot atrast tukšu vietu,

264
00:12:45,660 --> 00:12:49,000
un mēs varbūt iestrēdzis
bezgalīga cilpa.

265
00:12:49,000 --> 00:12:51,810
>> Tātad šāda veida aizdod idejas
par kaut ko sauc ķēžu rādītāju.

266
00:12:51,810 --> 00:12:55,790
Un tas ir tas, kur mēs ejam, lai panāktu
saistītie saraksti atpakaļ uz attēla.

267
00:12:55,790 --> 00:13:01,300
Ko darīt, ja tā vietā, lai uzglabātu tikko
datu pati masīva,

268
00:13:01,300 --> 00:13:04,471
katrs masīva elements varētu
turēt vairākus gabalus datu?

269
00:13:04,471 --> 00:13:05,970
Labi, ka nav jēgas, vai ne?

270
00:13:05,970 --> 00:13:09,280
Mēs zinām, ka masīvs var tikai
hold-- katru masīva elements

271
00:13:09,280 --> 00:13:12,930
var būt tikai viena gabala
Datu šīs datu tipu.

272
00:13:12,930 --> 00:13:16,750
>> Bet ko tad, ka datu tips
ir saistīts saraksts, vai ne?

273
00:13:16,750 --> 00:13:19,830
Tātad, ko tad, ja katrs
masīva elements bija

274
00:13:19,830 --> 00:13:22,790
rādītāju uz galvas saistītā saraksta?

275
00:13:22,790 --> 00:13:24,680
Un tad mēs varētu veidot
tie saistīti saraksti

276
00:13:24,680 --> 00:13:27,120
un augt tos patvaļīgi,
jo saistīti saraksti ļauj

277
00:13:27,120 --> 00:13:32,090
mums augt un sarauties daudz vairāk
elastīgi nekā masīvs dara.

278
00:13:32,090 --> 00:13:34,210
Tātad, ko tad mēs tagad izmanto,
mēs sviras šo, labi?

279
00:13:34,210 --> 00:13:37,760
Sākam augt šīs ķēdes
no šiem masīvu vietās.

280
00:13:37,760 --> 00:13:40,740
>> Tagad mēs varam fit bezgalīgs
datu apjoms, vai nav bezgalīgs,

281
00:13:40,740 --> 00:13:44,170
patvaļīga summa
dati, mūsu hash tabulu

282
00:13:44,170 --> 00:13:47,760
nekad nokļūšanu
problēma sadursmes.

283
00:13:47,760 --> 00:13:50,740
Mēs esam arī likvidēta
kopu, ko darīt.

284
00:13:50,740 --> 00:13:54,380
Un labi mēs zinām, ka tad, kad mēs ievietotu
stājas saistīta sarakstā, ja jūs atceraties

285
00:13:54,380 --> 00:13:57,779
no mūsu video par saistītiem sarakstiem, atsevišķi
saistīti saraksti un divkārt saistīti saraksti,

286
00:13:57,779 --> 00:13:59,070
tas ir pastāvīgs laiks operācija.

287
00:13:59,070 --> 00:14:00,710
Mēs esam tikai pievienojot uz priekšu.

288
00:14:00,710 --> 00:14:04,400
>> Un uzmeklēt, arī mēs zinām,
kas uzmeklēt kādā saistīta sarakstā

289
00:14:04,400 --> 00:14:05,785
var būt problēma, vai ne?

290
00:14:05,785 --> 00:14:07,910
Mums ir jāmeklē
tas no sākuma līdz beigām.

291
00:14:07,910 --> 00:14:10,460
Nav nejauši
piekļuve saistītajā sarakstā.

292
00:14:10,460 --> 00:14:15,610
Bet, ja tā vietā, viena saistīta
saraksts kur lookup būtu O n,

293
00:14:15,610 --> 00:14:19,590
mums tagad ir 10, kas saistītas saraksti,
vai 1000 saistīti saraksti,

294
00:14:19,590 --> 00:14:24,120
tagad tas ir O n dalīts ar 10,
vai O n dalīts ar 1000.

295
00:14:24,120 --> 00:14:26,940
>> Un, kamēr mēs runājām
teorētiski par sarežģītību

296
00:14:26,940 --> 00:14:30,061
mēs ignorēt konstantes, reālajā
pasaule šīs lietas tiešām svarīgi,

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

298
00:14:30,560 --> 00:14:33,080
Mēs faktiski ievērosiet
ka tas notiek

299
00:14:33,080 --> 00:14:36,610
palaist 10 reizes ātrāk,
vai 1000 reizes ātrāk,

300
00:14:36,610 --> 00:14:41,570
jo mēs esam izplata viena gara
ķēde pāri 1000 mazākām ķēdēm.

301
00:14:41,570 --> 00:14:45,090
Un tā katru reizi, kad mums ir jāmeklē
izmantojot kādu no šīm ķēdēm mēs varam

302
00:14:45,090 --> 00:14:50,290
ignorēt 999 ķēdes mēs vienalga
par, un tikai meklēt, ka viens.

303
00:14:50,290 --> 00:14:53,220
>> Kas ir vidēji līdz
būt 1000 reizes īsāks.

304
00:14:53,220 --> 00:14:56,460
Un tā mēs joprojām esam sava veida
noslieci uz šo vidējo gadījumā

305
00:14:56,460 --> 00:15:01,610
būt pastāvīgu laiku, bet
tikai tāpēc, ka mums ir piesaistot

306
00:15:01,610 --> 00:15:03,730
dalot ar kādu milzīgu nemainīgu koeficientu.

307
00:15:03,730 --> 00:15:05,804
Let 's redzēt, kā tas varētu
tiešām izskatās gan.

308
00:15:05,804 --> 00:15:08,720
Tātad tas bija hash tabulu mums bija
pirms mēs pasludināja hash tabulu, kas

309
00:15:08,720 --> 00:15:10,270
bija spēj uzglabāt 10 stīgas.

310
00:15:10,270 --> 00:15:11,728
Mēs nebrauksim darīt vairs.

311
00:15:11,728 --> 00:15:13,880
Mēs jau zinām,
ierobežojumi šī metode.

312
00:15:13,880 --> 00:15:20,170
Tagad mūsu hash tabulu, būs
masīvs 10 mezgliem, norādes

313
00:15:20,170 --> 00:15:22,120
vadītājiem saistītas sarakstiem.

314
00:15:22,120 --> 00:15:23,830
>> Un tagad tas ir null.

315
00:15:23,830 --> 00:15:26,170
Katrs no tiem 10 norādes ir nulle.

316
00:15:26,170 --> 00:15:29,870
Tur nekas Mūsu
hash tabulu tieši tagad.

317
00:15:29,870 --> 00:15:32,690
>> Tagad sāksim likt dažus
lietas šajā hash tabulu.

318
00:15:32,690 --> 00:15:35,440
Un pieņemsim redzēt, kā šī metode ir
gatavojas labumu mums mazliet.

319
00:15:35,440 --> 00:15:36,760
Pieņemsim tagad hash Joey.

320
00:15:36,760 --> 00:15:40,210
Mēs darbosies virkne Joey caur
hash funkciju un mēs atgriežamies 6.

321
00:15:40,210 --> 00:15:41,200
Nu ko mēs darām tagad?

322
00:15:41,200 --> 00:15:44,090
>> Nu tagad strādā ar saistītiem sarakstiem,
mēs nedarbojas ar masīviem.

323
00:15:44,090 --> 00:15:45,881
Un, kad mēs strādājam
ar saistītiem sarakstiem mēs

324
00:15:45,881 --> 00:15:49,790
zinām, mums ir nepieciešams, lai sāktu dinamiski
piešķirot telpas un ēkas ķēdes.

325
00:15:49,790 --> 00:15:54,020
Tas ir sava veida how-- tie ir galvenais
elementus veidot saistīts sarakstu.

326
00:15:54,020 --> 00:15:57,670
Tātad pieņemsim dinamiski
piešķirt telpas Joey,

327
00:15:57,670 --> 00:16:00,390
un tad pieņemsim pievienot viņu uz ķēdi.

328
00:16:00,390 --> 00:16:03,170
>> Tāpēc tagad meklēt to, ko mēs esam darījuši.

329
00:16:03,170 --> 00:16:06,440
Kad mēs hash Joey mēs saņēmām hashcode 6.

330
00:16:06,440 --> 00:16:11,790
Tagad rādītājs pie masīva vietā 6
norāda uz galvas saistītā saraksta

331
00:16:11,790 --> 00:16:14,900
un šobrīd tas ir vienīgais
no saistītā saraksta elements.

332
00:16:14,900 --> 00:16:18,350
Un mezglu, kas
saistīts saraksts ir Joey.

333
00:16:18,350 --> 00:16:22,300
>> Tātad, ja mums ir nepieciešams, lai uzmeklētu Joey
vēlāk, mēs vienkārši hash Joey atkal,

334
00:16:22,300 --> 00:16:26,300
mēs iegūstam 6 vēlreiz, jo mūsu
hash funkcija ir determinēti.

335
00:16:26,300 --> 00:16:30,400
Un tad mēs sākam pie galvas
no saistītā saraksta norādīja

336
00:16:30,400 --> 00:16:33,360
līdz ar masīvu vietu
6, un mēs varam atkārtot

337
00:16:33,360 --> 00:16:35,650
pāri, kas cenšas atrast Joey.

338
00:16:35,650 --> 00:16:37,780
Un, ja mēs veidojam mūsu
efektīvi hash tabulu,

339
00:16:37,780 --> 00:16:41,790
un mūsu hash funkciju efektīvi
izplatīt datus labi,

340
00:16:41,790 --> 00:16:45,770
vidēji par katru no tiem, kas saistīti
saraksti uz katra masīva vietā

341
00:16:45,770 --> 00:16:50,110
būs 1/10 izmēru, ja mēs
tikko bija to kā vienu milzīgu

342
00:16:50,110 --> 00:16:51,650
saistīts saraksts ar visu tajā.

343
00:16:51,650 --> 00:16:55,670
>> Ja mēs izplatīt, ka milzīgs saistīta
saraksts pāri 10, kas saistīti saraksti

344
00:16:55,670 --> 00:16:57,760
katrs saraksts būs 1/10 izmērs.

345
00:16:57,760 --> 00:17:01,432
Un tādējādi 10 reizes ātrāk
lai meklētu, izmantojot.

346
00:17:01,432 --> 00:17:02,390
Tātad, pieņemsim darīt atkal.

347
00:17:02,390 --> 00:17:04,290
Pieņemsim tagad hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> Un teiksim Ross, kad mēs to darām
hash kodu mēs saņemam atpakaļ, ir 2.

349
00:17:07,540 --> 00:17:10,630
Nu tagad mēs dinamiski piešķir
jaunu mezglu, mēs ieliekam Ross šajā mezglā,

350
00:17:10,630 --> 00:17:14,900
un tagad mēs sakām masīvs vieta
2, tā vietā, norādot uz null,

351
00:17:14,900 --> 00:17:18,579
norāda uz galvas saistītais
sarakstu, kuru vienīgais mezgls ir Ross.

352
00:17:18,579 --> 00:17:22,660
Un mēs varam darīt vēl vienu reizi, mēs
var hash Rachel un saņemt hashcode 4.

353
00:17:22,660 --> 00:17:25,490
malloc jaunu mezglu, ielieciet Rachel in
mezglu, un teikt masīvs vietu

354
00:17:25,490 --> 00:17:27,839
4. tagad norāda uz galvas
par saistītu sarakstu, kuras

355
00:17:27,839 --> 00:17:31,420
Vienīgais elements, notiek, ir Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK, bet to, kas notiek, ja
mums ir sadursmes?

357
00:17:33,470 --> 00:17:38,560
Let 's redzēt, kā mēs risinām sadursmes
izmantojot atsevišķu Ķēžu metodi.

358
00:17:38,560 --> 00:17:39,800
Pieņemsim hash Phoebe.

359
00:17:39,800 --> 00:17:41,094
Mēs saņemam hashcode 6.

360
00:17:41,094 --> 00:17:44,010
Pēc mūsu iepriekšējo piemēru mēs bijām tikko
uzglabājot stīgas masīvā.

361
00:17:44,010 --> 00:17:45,980
Tas bija problēma.

362
00:17:45,980 --> 00:17:48,444
>> Mēs nevēlamies, lai clobber
Joey, un mēs esam jau

363
00:17:48,444 --> 00:17:51,110
redzams, ka mēs varam dabūt klasteru
problēmas, ja mēs mēģinātu solis

364
00:17:51,110 --> 00:17:52,202
caur un zonde.

365
00:17:52,202 --> 00:17:54,660
Bet ko tad, ja mēs tikai veida
ārstēt tas tāpat, vai ne?

366
00:17:54,660 --> 00:17:57,440
Tas ir tāpat kā pievienojot elementu
uz galvas saistītā saraksta.

367
00:17:57,440 --> 00:18:00,220
Pieņemsim tikai malloc telpu Fēbes.

368
00:18:00,220 --> 00:18:04,764
>> Mēs sakām Phoebe nākamais rādītājs punktus
uz veco galvas saistītā saraksta,

369
00:18:04,764 --> 00:18:07,180
un pēc tam 6 tikai norāda uz
jaunais vadītājs saistīts sarakstā.

370
00:18:07,180 --> 00:18:10,150
Un tagad izskatās, mēs esam mainījušies Phoebe in.

371
00:18:10,150 --> 00:18:14,210
Tagad mēs varam saglabāt divas
elementi ar hashcode 6,

372
00:18:14,210 --> 00:18:17,170
un mums nav nekādu problēmu.

373
00:18:17,170 --> 00:18:20,147
>> Tas ir diezgan daudz viss
tur ir Virknējuma.

374
00:18:20,147 --> 00:18:21,980
Un virknes intervāli ir noteikti
metode, kas ir

375
00:18:21,980 --> 00:18:27,390
būs visefektīvākais jums, ja
jums ir uzglabātu datus hash tabulā.

376
00:18:27,390 --> 00:18:30,890
Bet šī kombinācija
bloki un saistīti saraksti

377
00:18:30,890 --> 00:18:36,080
kopā, lai veidotu hash tabulu patiešām
ievērojami uzlabo savu spēju

378
00:18:36,080 --> 00:18:40,550
uzglabāt lielu datu apjomu, un
ļoti ātri un efektīvi meklēt

379
00:18:40,550 --> 00:18:41,630
caur šiem datiem.

380
00:18:41,630 --> 00:18:44,150
>> Tur ir vēl viens
datu struktūra, kas tur

381
00:18:44,150 --> 00:18:48,700
ka pat varētu būt nedaudz
labāk ziņā garantējot

382
00:18:48,700 --> 00:18:51,920
ka mūsu ievietošana, dzēšana, un
Uzmeklēt laiki ir vēl ātrāk.

383
00:18:51,920 --> 00:18:55,630
Un mēs redzam, ka ar video valstīs.

384
00:18:55,630 --> 00:18:58,930
Es esmu Doug Lloyd, tas ir CS50.

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