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

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

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG Lloyd: mennessä sinun
tietää paljon paneelit,

5
00:00:09,150 --> 00:00:11,610
ja tiedät paljon linkitettyjen listojen.

6
00:00:11,610 --> 00:00:13,650
Ja olemme keskustella
hyvät ja huonot puolensa, olemme

7
00:00:13,650 --> 00:00:16,620
keskustelivat että liittyvät luettelot
voi saada isompi ja pienempi,

8
00:00:16,620 --> 00:00:18,630
mutta ne vievät enemmän koko.

9
00:00:18,630 --> 00:00:22,359
Taulukot ovat paljon yksinkertaisempaa
käyttää, mutta ne rajoittavat niin paljon

10
00:00:22,359 --> 00:00:24,900
koska meidän on asettaa koko
array aivan alussa

11
00:00:24,900 --> 00:00:26,910
ja sitten me pääse siitä eroon.

12
00:00:26,910 --> 00:00:30,470
>> Mutta se, olemme melko paljon
käyttänyt kaikki meidän aiheista

13
00:00:30,470 --> 00:00:33,040
noin liittyvät luettelot ja taulukot.

14
00:00:33,040 --> 00:00:34,950
Tai me?

15
00:00:34,950 --> 00:00:37,720
Ehkä voimme tehdä jotain
Luovempaan.

16
00:00:37,720 --> 00:00:40,950
Ja tällaista se lainaa
ajatus hajautustaulun.

17
00:00:40,950 --> 00:00:46,680
>> Joten hajautustaulun aiomme kokeilla
yhdistää array linkitetty lista.

18
00:00:46,680 --> 00:00:49,520
Aiomme ottaa edut
array, kuten random access,

19
00:00:49,520 --> 00:00:53,510
että voimme vain mennä array
elementti 4 tai ryhmän elementin 8

20
00:00:53,510 --> 00:00:55,560
ilman kerrata poikki.

21
00:00:55,560 --> 00:00:57,260
Se on melko nopeasti, eikö?

22
00:00:57,260 --> 00:01:00,714
>> Mutta haluamme myös olla tietomme
rakenne voi kasvaa ja kutistua.

23
00:01:00,714 --> 00:01:02,630
Emme tarvitse, emme
haluavat rajoittaa.

24
00:01:02,630 --> 00:01:04,588
Ja haluamme pystyä
lisätä ja poistaa asioita

25
00:01:04,588 --> 00:01:08,430
hyvin helposti, joka Jos muistatte,
on erittäin monimutkainen jono.

26
00:01:08,430 --> 00:01:11,650
Voimme kutsua tätä
uusi asia hajautustaulua.

27
00:01:11,650 --> 00:01:15,190
>> Ja jos ne toteutetaan oikein,
olemme tavallaan ottaen

28
00:01:15,190 --> 00:01:18,150
edut sekä data-
rakenteet olet jo nähnyt,

29
00:01:18,150 --> 00:01:19,880
taulukot ja linkitettyjen listojen.

30
00:01:19,880 --> 00:01:23,070
Asennus voi alkaa
pyrkivän kohti thetalla 1.

31
00:01:23,070 --> 00:01:26,207
Theta emme ole oikeastaan ​​keskusteltu,
mutta theta on vain keskimääräisestä tapauksesta,

32
00:01:26,207 --> 00:01:27,540
mitä todella tapahtuu.

33
00:01:27,540 --> 00:01:29,680
Et aina aio
on pahimmassa tapauksessa,

34
00:01:29,680 --> 00:01:32,555
ja et aina olemaan
Parhaassa tapauksessa niin mitä

35
00:01:32,555 --> 00:01:33,900
keskimääräinen skenaario?

36
00:01:33,900 --> 00:01:36,500
>> No keskimääräinen lisäys
osaksi hash table

37
00:01:36,500 --> 00:01:39,370
voi alkaa päästä lähelle vakio aikaa.

38
00:01:39,370 --> 00:01:41,570
Ja poisto voi saada
lähes vakio aikaa.

39
00:01:41,570 --> 00:01:44,440
Ja lookup voi saada
lähes vakio aikaa.

40
00:01:44,440 --> 00:01:48,600
That's-- meillä ei ole tietoa
rakenne vielä, että voi tehdä sitä,

41
00:01:48,600 --> 00:01:51,180
ja niin tämä jo kuulostaa
kuten melko suuri asia.

42
00:01:51,180 --> 00:01:57,010
Olemme todella lieventää
haittoja kunkin omasta.

43
00:01:57,010 --> 00:01:59,160
>> Jotta saat tämän suorituskyvyn
päivittää vaikka me

44
00:01:59,160 --> 00:02:03,580
on harkittava uudelleen, kuinka lisäämme
tietojen rakenteeseen.

45
00:02:03,580 --> 00:02:07,380
Erityisesti haluamme
tiedot itse kertoa meille

46
00:02:07,380 --> 00:02:09,725
jos se pitäisi mennä rakenteessa.

47
00:02:09,725 --> 00:02:12,850
Ja jos me sitten täytyy nähdä, jos se on
rakenne, jos meidän on löydettävä se,

48
00:02:12,850 --> 00:02:16,610
haluamme tarkastella tietoja
uudelleen ja pystyä tehokkaasti,

49
00:02:16,610 --> 00:02:18,910
käyttäen tietoja, satunnaisesti käyttää sitä.

50
00:02:18,910 --> 00:02:20,700
Vain tarkastelemalla
tietojen pitäisi olla

51
00:02:20,700 --> 00:02:25,890
siitä, missä tarkalleen olemme
menossa löytää sen tiiviste.

52
00:02:25,890 --> 00:02:28,770
>> Nyt haittapuoli hash
pöytä on, että he todella

53
00:02:28,770 --> 00:02:31,770
melko huono tilaus tai lajittelu tietoja.

54
00:02:31,770 --> 00:02:34,970
Ja itse asiassa, jos käynnistät
käyttää niitä tilata tai lajitella

55
00:02:34,970 --> 00:02:37,990
tiedot menetät kaikki
etuja aiemmin

56
00:02:37,990 --> 00:02:40,710
oli kannalta paikoilleen ja poisto.

57
00:02:40,710 --> 00:02:44,060
Aika lähenee
theta n, ja olemme periaatteessa

58
00:02:44,060 --> 00:02:45,530
taantunut osaksi linkitetty lista.

59
00:02:45,530 --> 00:02:48,850
Ja niin me vain haluamme käyttää hash
taulukot jos emme välitä

60
00:02:48,850 --> 00:02:51,490
onko tiedot lajitellaan.

61
00:02:51,490 --> 00:02:54,290
Sillä asiayhteys, jossa
voit käyttää niitä CS50

62
00:02:54,290 --> 00:02:58,900
luultavasti eivät välitä
että tiedot on järjestetty.

63
00:02:58,900 --> 00:03:03,170
>> Niin hash table on yhdistelmä
kaksi erillistä kappaletta

64
00:03:03,170 --> 00:03:04,980
jonka kanssa olemme tuttuja.

65
00:03:04,980 --> 00:03:07,930
Ensimmäinen on toiminto, joka
me yleensä kutsumme hajautusfunktio.

66
00:03:07,930 --> 00:03:11,760
Ja että tiivistefunktiota aikoo
palata joitakin ei-negatiivinen kokonaisluku, joka

67
00:03:11,760 --> 00:03:14,870
me yleensä kutsumme hashcode, OK?

68
00:03:14,870 --> 00:03:20,230
Toinen kappale on matriisi, joka on
joka pystyy tallentamaan dataa tyypin me

69
00:03:20,230 --> 00:03:22,190
haluavat sijoittaa osaksi tietorakennetta.

70
00:03:22,190 --> 00:03:24,310
Me pitää pois
linkitetty lista osa nyt

71
00:03:24,310 --> 00:03:27,810
ja juuri aloittaa perusasiat
tiiviste saada pään ympärille,

72
00:03:27,810 --> 00:03:30,210
ja sitten me ehkä puhalla
mielesi hieman kun me

73
00:03:30,210 --> 00:03:32,920
yhdistää taulukot ja linkit yhteen.

74
00:03:32,920 --> 00:03:35,590
>> Perusajatuksena vaikka
on otamme joitakin tietoja.

75
00:03:35,590 --> 00:03:37,860
Otamme että dataa
tiivistefunktio.

76
00:03:37,860 --> 00:03:41,980
Ja niin tietoja käsitellään
ja se sylkee numero, OK?

77
00:03:41,980 --> 00:03:44,890
Ja sitten, että määrä
me vain tallentaa tiedot

78
00:03:44,890 --> 00:03:48,930
Haluamme tallentaa
array kyseisessä paikassa.

79
00:03:48,930 --> 00:03:53,990
Niinpä esimerkiksi meillä on ehkä
tämä tiiviste merkkijonojen.

80
00:03:53,990 --> 00:03:57,350
Se sai 10 elementtejä se, niin
me mahtuu 10 jousille se.

81
00:03:57,350 --> 00:03:59,320
>> Sanotaan haluamme hash John.

82
00:03:59,320 --> 00:04:02,979
Niin Johanneksen tiedot haluamme lisätä
tähän tiiviste jonnekin.

83
00:04:02,979 --> 00:04:03,770
Mistä me laittaa sen?

84
00:04:03,770 --> 00:04:05,728
Hyvin tyypillisesti
array toistaiseksi emme luultavasti

85
00:04:05,728 --> 00:04:07,610
asettaisi se array sijainti 0.

86
00:04:07,610 --> 00:04:09,960
Mutta nyt meillä on tämä uusi hajautusfunktio.

87
00:04:09,960 --> 00:04:13,180
>> Ja sanotaan, että otamme John
kautta tiivistefunktio

88
00:04:13,180 --> 00:04:15,417
ja se sylkee 4.

89
00:04:15,417 --> 00:04:17,500
No siitähän olemme
menossa halua laittaa John.

90
00:04:17,500 --> 00:04:22,050
Haluamme laittaa John array sijainti
4, koska jos me hash John again--

91
00:04:22,050 --> 00:04:23,810
Sanotaan myöhemmin me
haluat etsiä ja nähdä

92
00:04:23,810 --> 00:04:26,960
jos John olemassa tässä hash
table-- kaikki meidän täytyy tehdä

93
00:04:26,960 --> 00:04:30,310
on ajaa se läpi sama tiiviste
toiminto, saat numero 4 ulos,

94
00:04:30,310 --> 00:04:33,929
ja löytää John
välittömästi meidän tietorakenne.

95
00:04:33,929 --> 00:04:34,720
Se on aika hyvä.

96
00:04:34,720 --> 00:04:36,928
>> Sanotaan nyt tehdä tämän
jälleen, haluamme hash Paul.

97
00:04:36,928 --> 00:04:39,446
Haluamme lisätä Paul
tähän tiiviste.

98
00:04:39,446 --> 00:04:42,070
Oletetaan, että tällä kertaa otamme
Paul kautta hajautusfunktio,

99
00:04:42,070 --> 00:04:44,600
hashcode, joka syntyy on 6.

100
00:04:44,600 --> 00:04:47,340
No nyt voimme laittaa Paul
jono sijainti 6.

101
00:04:47,340 --> 00:04:50,040
Ja jos meidän etsiä onko
Paul on tässä tiiviste,

102
00:04:50,040 --> 00:04:53,900
kaikki meidän täytyy tehdä on ajaa Paul
kautta tiivistefunktio uudelleen

103
00:04:53,900 --> 00:04:55,830
ja me aiomme saada 6 ulos.

104
00:04:55,830 --> 00:04:57,590
>> Ja sitten me vain katsoa
at array Sijainti 6.

105
00:04:57,590 --> 00:04:58,910
Onko Paul siellä?

106
00:04:58,910 --> 00:05:00,160
Jos näin on, hän on tiiviste.

107
00:05:00,160 --> 00:05:01,875
Paavali ei siellä?

108
00:05:01,875 --> 00:05:03,000
Hän ei ole tiiviste.

109
00:05:03,000 --> 00:05:05,720
Se on melko yksinkertainen.

110
00:05:05,720 --> 00:05:07,770
>> Nyt Miten määrittelet hajautusfunktio?

111
00:05:07,770 --> 00:05:11,460
No siellä oikeastaan ​​mitään rajaa
useita mahdollisia hash toimintoja.

112
00:05:11,460 --> 00:05:14,350
Itse asiassa on olemassa useita todella,
todella hyviä Internetissä.

113
00:05:14,350 --> 00:05:17,560
On useita todella,
todella huonoja internetissä.

114
00:05:17,560 --> 00:05:21,080
Se on myös melko helppo
kirjoittaa huono.

115
00:05:21,080 --> 00:05:23,760
>> Joten mitä tekee jopa hyvää
tiivistefunktiota, eikö?

116
00:05:23,760 --> 00:05:27,280
No hyvä hajautusfunktio pitäisi
Käytä vain datan hashed,

117
00:05:27,280 --> 00:05:29,420
ja kaikki tiedot on hajauttamat.

118
00:05:29,420 --> 00:05:32,500
Joten emme halua käyttää anything--
emme sisällyttää mitään

119
00:05:32,500 --> 00:05:35,560
muualla kuin tiedot.

120
00:05:35,560 --> 00:05:37,080
Ja haluamme käyttää kaikki tiedot.

121
00:05:37,080 --> 00:05:39,830
Emme halua vain käyttää pala
sitä, haluamme käyttää kaikki.

122
00:05:39,830 --> 00:05:41,710
Hajautusfunktio pitäisi
myös deterministinen.

123
00:05:41,710 --> 00:05:42,550
Mitä se tarkoittaa?

124
00:05:42,550 --> 00:05:46,200
No se tarkoittaa, että joka kerta kun
siirtää täsmälleen samoja tietoja

125
00:05:46,200 --> 00:05:50,040
osaksi tiivistefunktio aina
saada sama hashcode ulos.

126
00:05:50,040 --> 00:05:52,870
Jos kuljen John osaksi
tiivistefunktio pääsen pois 4.

127
00:05:52,870 --> 00:05:56,110
Minun pitäisi pystyä tekemään, että 10000
ajat ja tulen aina saada 4.

128
00:05:56,110 --> 00:06:00,810
Joten ei satunnaisia ​​numeroita tehokkaasti
voi olla mukana meidän hash tables--

129
00:06:00,810 --> 00:06:02,750
meidän hash toimintoja.

130
00:06:02,750 --> 00:06:05,750
>> Hajautusfunktio olisi myös
tasaisesti jakaa tietoja.

131
00:06:05,750 --> 00:06:09,700
Jos aina käyttää dataa
hajautusfunktio saat hashcode 0,

132
00:06:09,700 --> 00:06:11,200
se luultavasti ei ole niin suuri, oikea?

133
00:06:11,200 --> 00:06:14,600
Et luultavasti halua iso
erilaisia ​​hash koodeja.

134
00:06:14,600 --> 00:06:17,190
Myös asiat voidaan levittää
ulos koko pöydän.

135
00:06:17,190 --> 00:06:23,210
Ja myös se olisi hienoa, jos todella
samoja tietoja, kuten John ja Jonathan,

136
00:06:23,210 --> 00:06:26,320
ehkä oli levittää punnita
eri paikoissa tiiviste.

137
00:06:26,320 --> 00:06:28,750
Se olisi kiva etu.

138
00:06:28,750 --> 00:06:31,250
>> Tässä on esimerkki hajautusfunktiota.

139
00:06:31,250 --> 00:06:33,150
Kirjoitin tämän yhden jopa aikaisemmin.

140
00:06:33,150 --> 00:06:35,047
Se ei ole erityisen
hyvä tiivistefunktio

141
00:06:35,047 --> 00:06:37,380
syistä, jotka eivät oikeastaan
karhu menee juuri nyt.

142
00:06:37,380 --> 00:06:41,040
Mutta näetkö mitä täällä tapahtuu?

143
00:06:41,040 --> 00:06:44,420
Tuntuu siltä, ​​olemme julistamisesta muuttuja
nimeltään summa ja asettamalla se yhtä suuri kuin 0.

144
00:06:44,420 --> 00:06:50,010
Ja sitten ilmeisesti olen tekemässä jotain
niin kauan kuin strstr [j] ei ole yhtä suuri kuin

145
00:06:50,010 --> 00:06:52,490
on Kenoviiva 0.

146
00:06:52,490 --> 00:06:54,870
Mitä teen siellä?

147
00:06:54,870 --> 00:06:57,440
>> Tämä on pohjimmiltaan vain toinen
tapa toteuttaa [? strl?]

148
00:06:57,440 --> 00:06:59,773
ja havaitsemaan milloin olet
lopussa merkkijonon.

149
00:06:59,773 --> 00:07:02,480
Joten minun ei tarvitse itse
laskea merkkijonon pituus,

150
00:07:02,480 --> 00:07:05,640
Olen vain käyttää kun osuin
kenoviiva 0 merkki Tiedän

151
00:07:05,640 --> 00:07:07,185
Olen lopussa merkkijonon.

152
00:07:07,185 --> 00:07:09,560
Ja sitten aion pitää
iteroimalla läpi merkkijono,

153
00:07:09,560 --> 00:07:15,310
lisäämällä strstr [j] Yhteenvetona, ja sitten
Päivän päätteeksi palaavansa summa mod

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

155
00:07:16,200 --> 00:07:18,700
>> Periaatteessa kaikki tämä hash
toiminto tekee on lisätä ylös

156
00:07:18,700 --> 00:07:23,450
kaikki ASCII-arvojen
minun merkkijono, ja sitten se on

157
00:07:23,450 --> 00:07:26,390
palaavat jotkut hashcode
modded mukaan HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Se on luultavasti koko
minun array, eikö?

159
00:07:29,790 --> 00:07:33,160
En halua saada hash
koodit jos joukko on koko 10,

160
00:07:33,160 --> 00:07:35,712
En halua olla saada
out hash koodit 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, en voi laittaa asiat oikeisiin
niihin paikkoihin array,

162
00:07:38,690 --> 00:07:39,790
että olisi laitonta.

163
00:07:39,790 --> 00:07:42,130
Olin kärsivät segmentointi vika.

164
00:07:42,130 --> 00:07:45,230
>> Nyt täällä on toinen nopea syrjään.

165
00:07:45,230 --> 00:07:48,470
Yleensä olet todennäköisesti aio
haluavat kirjoittaa oman hash toimintoja.

166
00:07:48,470 --> 00:07:50,997
Se on oikeastaan ​​hieman
taidetta, ei tiedettä.

167
00:07:50,997 --> 00:07:52,580
Ja siellä on paljon että menee niitä.

168
00:07:52,580 --> 00:07:55,288
Internet, kuten sanoin, on täynnä
todella hyvä hash toimintoja,

169
00:07:55,288 --> 00:07:58,470
ja sinun pitäisi käyttää Internetiä
löytää hash toimintoja, koska se on todella

170
00:07:58,470 --> 00:08:03,230
juuri sellainen tarpeeton
ajanhukkaa luoda oman.

171
00:08:03,230 --> 00:08:05,490
>> Voit kirjoittaa yksinkertaisia,
testausta varten.

172
00:08:05,490 --> 00:08:08,323
Mutta kun itse on menossa
aloittaa hajautusta tiedot ja varastointia

173
00:08:08,323 --> 00:08:10,780
osaksi hash table olet
luultavasti menossa haluavat

174
00:08:10,780 --> 00:08:14,580
käyttää joitakin toiminto luotiin
sinulle, että on olemassa Internetissä.

175
00:08:14,580 --> 00:08:17,240
Jos et vain olla varma
mainita käyttämäsi lähteet.

176
00:08:17,240 --> 00:08:21,740
Ei ole mitään syytä
plagioida mitään täällä.

177
00:08:21,740 --> 00:08:25,370
>> Tietojenkäsittelytiede yhteisö on
varmasti kasvaa, ja todella arvot

178
00:08:25,370 --> 00:08:28,796
avoimen lähdekoodin, ja se on todella tärkeää
mainita lähteet niin, että ihmiset

179
00:08:28,796 --> 00:08:30,670
voi saada Nimeä varten
työstä, jota he

180
00:08:30,670 --> 00:08:32,312
tekee koko yhteisön hyväksi.

181
00:08:32,312 --> 00:08:34,020
Joten aina sure--
ja ei vain hash

182
00:08:34,020 --> 00:08:37,270
toiminnot, mutta yleensä kun
käytä koodia ulkopuolisista lähteistä,

183
00:08:37,270 --> 00:08:38,299
aina mainita lähde.

184
00:08:38,299 --> 00:08:43,500
Antaa tunnustusta henkilölle, joka teki
osan työstä, joten sinun ei tarvitse.

185
00:08:43,500 --> 00:08:46,720
>> OK joten katsotaanpa uudelleen tämän
tiiviste toista.

186
00:08:46,720 --> 00:08:48,780
Täällä jätimme
pois, kun lisäsimme

187
00:08:48,780 --> 00:08:53,300
John ja Paul tähän tiiviste.

188
00:08:53,300 --> 00:08:55,180
Näetkö ongelma täällä?

189
00:08:55,180 --> 00:08:58,410
Saatat nähdä kaksi.

190
00:08:58,410 --> 00:09:02,240
Mutta erityisesti, oletteko
katso tämä mahdollinen ongelma?

191
00:09:02,240 --> 00:09:06,770
>> Mitä jos hash Ringo, ja se
Osoittautuu, että käsittelyn jälkeen

192
00:09:06,770 --> 00:09:14,000
että dataa hajautusfunktio
Ringo myös tuotti hashcode 6.

193
00:09:14,000 --> 00:09:16,810
Olen jo saanut tietoja
hashcode-- array Sijainti 6.

194
00:09:16,810 --> 00:09:22,000
Joten se luultavasti olemaan hieman
ongelma minulle nyt, eikö?

195
00:09:22,000 --> 00:09:23,060
>> Kutsumme tätä törmäys.

196
00:09:23,060 --> 00:09:26,460
Ja törmäys tapahtuu, kun kaksi
datajoukkoja läpi sama tiiviste

197
00:09:26,460 --> 00:09:29,200
toiminto saadaan sama hashcode.

198
00:09:29,200 --> 00:09:32,850
Oletettavasti haluamme kuitenkin saada molemmat
kappaletta datan hash table,

199
00:09:32,850 --> 00:09:36,330
muuten emme olisi käynnissä Ringo
mielivaltaisesti kautta hajautusfunktio.

200
00:09:36,330 --> 00:09:40,870
Me oletettavasti haluavat saada
Ringo tuohon array.

201
00:09:40,870 --> 00:09:46,070
>> Miten teemme sen kuitenkin, jos hän
ja Paul sekä tuotto- hashcode 6?

202
00:09:46,070 --> 00:09:49,520
Emme halua korvata Paul,
haluamme Paul olla sielläkin.

203
00:09:49,520 --> 00:09:52,790
Joten meidän on löydettävä tapa saada
elementtejä tiiviste että

204
00:09:52,790 --> 00:09:56,550
on säilyttänyt meidän nopeasti
paikoilleen ja nopea etsiä.

205
00:09:56,550 --> 00:10:01,350
Ja yksi tapa käsitellä sitä on
tehdä jotain kutsutaan lineaarinen luotaa.

206
00:10:01,350 --> 00:10:04,170
>> Käyttämällä tätä menetelmää, jos meillä
törmäys, hyvin, mitä me teemme?

207
00:10:04,170 --> 00:10:08,580
No emme voi häntä array sijainti
6, tai mitä tahansa hashcode syntyi,

208
00:10:08,580 --> 00:10:10,820
Laitetaan hänet hashcode plus 1.

209
00:10:10,820 --> 00:10:13,670
Ja jos se täydellinen Katsotaan
pani hänet hashcode plus 2.

210
00:10:13,670 --> 00:10:17,420
Hyöty olennon jos hän on
ei tarkalleen missä meidän mielestämme hän on,

211
00:10:17,420 --> 00:10:20,850
ja meidän on alkaa etsiä,
Ehkä meidän ei tarvitse mennä liian pitkälle.

212
00:10:20,850 --> 00:10:23,900
Ehkä meidän ei tarvitse etsiä
kaikki n elementit hajautustaulun.

213
00:10:23,900 --> 00:10:25,790
Ehkä meidän täytyy etsiä
pari niistä.

214
00:10:25,790 --> 00:10:30,680
>> Ja niin olemme yhä omiaan kohti
että keskimääräinen tapaus ovat lähellä 1 vs

215
00:10:30,680 --> 00:10:34,280
lähellä n, niin ehkä se täytyy harjoitella.

216
00:10:34,280 --> 00:10:38,010
Joten miten tämä
voi treenata todellisuudessa.

217
00:10:38,010 --> 00:10:41,460
Ja katsotaanpa jos ehkä voimme havaita
ongelma, joka voi esiintyä tässä.

218
00:10:41,460 --> 00:10:42,540
>> Sanotaan hash Bart.

219
00:10:42,540 --> 00:10:45,581
Joten nyt aiomme ajaa uusia
merkkijonojen kautta hajautusfunktio,

220
00:10:45,581 --> 00:10:48,460
ja otamme Bart läpi hash
toiminto, saamme hashcode 6.

221
00:10:48,460 --> 00:10:52,100
Me katsomaan, näemme 6
tyhjä, joten voimme laittaa Bart sinne.

222
00:10:52,100 --> 00:10:55,410
>> Nyt hash Lisa ja että
tuottaa myös hashcode 6.

223
00:10:55,410 --> 00:10:58,330
No nyt, että käytämme tätä
lineaarinen hyvää menetelmä aloitamme 6,

224
00:10:58,330 --> 00:10:59,330
näemme, että 6 on täynnä.

225
00:10:59,330 --> 00:11:00,990
Emme voi laittaa Lisa 6.

226
00:11:00,990 --> 00:11:02,090
Joten jos me menisimme?

227
00:11:02,090 --> 00:11:03,280
Mennään 7.

228
00:11:03,280 --> 00:11:04,610
7: n tyhjä, niin että toimii.

229
00:11:04,610 --> 00:11:06,510
Joten laittaa Lisa siellä.

230
00:11:06,510 --> 00:11:10,200
>> Nyt hash Homer ja saamme 7.

231
00:11:10,200 --> 00:11:13,380
OK hyvin tiedämme, että 7 täyden
nyt, joten emme voi laittaa Homer siellä.

232
00:11:13,380 --> 00:11:14,850
Joten mennään 8.

233
00:11:14,850 --> 00:11:15,664
On 8 käytettävissä?

234
00:11:15,664 --> 00:11:18,330
Joo, ja 8: n lähes 7, joten jos
meidän täytyy alkaa etsiä olemme

235
00:11:18,330 --> 00:11:20,020
aio tarvitse mennä liian pitkälle.

236
00:11:20,020 --> 00:11:22,860
Ja niin katsotaanpa laittaa Homer 8.

237
00:11:22,860 --> 00:11:25,151
>> Nyt hash Maggie ja
palauttaa 3, luojan kiitos

238
00:11:25,151 --> 00:11:26,650
pystymme vain laittaa Maggie siellä.

239
00:11:26,650 --> 00:11:29,070
Meidän ei tarvitse tehdä mitään
tavallaan hyvää siitä.

240
00:11:29,070 --> 00:11:32,000
Nyt hash Marge, ja
Marge myös palauttaa 6.

241
00:11:32,000 --> 00:11:39,560
>> No 6 on täynnä, 7 on täynnä, 8 on täynnä,
9, okei luojan kiitos, 9 on tyhjä.

242
00:11:39,560 --> 00:11:41,600
Voin laittaa Marge 9.

243
00:11:41,600 --> 00:11:45,280
Jo voimme nähdä, että olemme alkaneet
on tämä ongelma, jossa nyt olemme

244
00:11:45,280 --> 00:11:48,780
alkaa venyttää asioita laji
on kaukana niiden hash koodeja.

245
00:11:48,780 --> 00:11:52,960
Ja että theta 1, että keskimääräinen
kyseessä on vakio aikaa,

246
00:11:52,960 --> 00:11:56,560
alkaa saada hieman more--
alkaa yleensä hieman enemmän

247
00:11:56,560 --> 00:11:58,050
kohti thetalla n.

248
00:11:58,050 --> 00:12:01,270
Olemme alkaneet menettää että
etuna hash taulukoita.

249
00:12:01,270 --> 00:12:03,902
>> Tämä ongelma, että me juuri näin
on jotain kutsutaan klustereiden.

250
00:12:03,902 --> 00:12:06,360
Ja mitä todella pahaa
klusterointi on, että kun nyt

251
00:12:06,360 --> 00:12:09,606
on kaksi tekijää, jotka ovat rinta
puolella se tekee siitä entistä todennäköisemmin,

252
00:12:09,606 --> 00:12:11,480
sinulla on kaksinkertainen
mahdollisuus, että olet menossa

253
00:12:11,480 --> 00:12:13,516
on toinen törmäys
kanssa, että klusteri,

254
00:12:13,516 --> 00:12:14,890
ja klusterin kasvaa yhdellä.

255
00:12:14,890 --> 00:12:19,640
Ja sinun pitää kasvaa ja kasvaa
todennäköisyyttä, jolla törmäys.

256
00:12:19,640 --> 00:12:24,470
Ja lopulta se on aivan yhtä huono
koska ei lajittelu tietoja lainkaan.

257
00:12:24,470 --> 00:12:27,590
>> Toinen ongelma kuitenkin on meidän
edelleen, ja toistaiseksi tähän asti,

258
00:12:27,590 --> 00:12:30,336
Olemme juuri eräänlainen
ymmärtää, mitä hajautustaulun on,

259
00:12:30,336 --> 00:12:31,960
meillä on edelleen vain on tilaa 10 jousille.

260
00:12:31,960 --> 00:12:37,030
Jos haluamme jatkaa hash
kansalaiset Springfield,

261
00:12:37,030 --> 00:12:38,790
voimme vain saada 10 niistä siellä.

262
00:12:38,790 --> 00:12:42,619
Ja jos yritämme lisätä 11. tai 12.,
meillä ei ole paikka laittaa ne.

263
00:12:42,619 --> 00:12:45,660
Voisimme vain pyöriä ympäri
piireissä yrittää löytää tyhjässä,

264
00:12:45,660 --> 00:12:49,000
ja me ehkä juuttua
päättymättömään silmukkaan.

265
00:12:49,000 --> 00:12:51,810
>> Joten tällainen se lainaa ajatus
jotain kutsutaan ketjuttamalla.

266
00:12:51,810 --> 00:12:55,790
Ja tämä on, jos aiomme tuoda
liittyvät luettelot takaisin kuvaan.

267
00:12:55,790 --> 00:13:01,300
Mitä jos sen sijaan tallentaa vain
tiedot itse array,

268
00:13:01,300 --> 00:13:04,471
jokainen alkio voisi
olla useita paloja tiedot?

269
00:13:04,471 --> 00:13:05,970
No se ei ole järkeä, eikö?

270
00:13:05,970 --> 00:13:09,280
Tiedämme, että jono voi vain
hold-- kukin elementti array

271
00:13:09,280 --> 00:13:12,930
voi olla vain yksi pala
datan tietojen tyyppi.

272
00:13:12,930 --> 00:13:16,750
>> Mutta entä jos se tietotyyppi
on linkitetty lista, eikö?

273
00:13:16,750 --> 00:13:19,830
Joten mitä jos jokainen
alkio oli

274
00:13:19,830 --> 00:13:22,790
osoitin johtaja linkitetty lista?

275
00:13:22,790 --> 00:13:24,680
Ja sitten voisimme rakentaa
ne liittyvät luettelot

276
00:13:24,680 --> 00:13:27,120
ja kasvattaa ne mielivaltaisesti,
koska linkitettyjen listojen avulla

277
00:13:27,120 --> 00:13:32,090
meille mahdollisuuden kasvaa ja kutistua paljon enemmän
joustavasti kuin array tekee.

278
00:13:32,090 --> 00:13:34,210
Joten mitä jos me nyt käyttää,
Hyödynnämme tätä, eikö?

279
00:13:34,210 --> 00:13:37,760
Meidän alkaa kasvaa nämä ketjut
Näistä array paikoista.

280
00:13:37,760 --> 00:13:40,740
>> Nyt mahtuu ääretön
datan määrä, tai ääretön,

281
00:13:40,740 --> 00:13:44,170
mielivaltainen määrä
tiedot, meidän tiiviste

282
00:13:44,170 --> 00:13:47,760
ilman koskaan ajautumassa
ongelma törmäyksen.

283
00:13:47,760 --> 00:13:50,740
Olemme myös poistettava
klustereiden tekemällä näin.

284
00:13:50,740 --> 00:13:54,380
Ja hyvin me tiedämme, että kun lisäämme
osaksi linkitetty lista, jos muistatte

285
00:13:54,380 --> 00:13:57,779
meidän video linkitettyjen listojen, yksittäin
liittyvät luettelot ja kaksinkertaisesti liittyvät luettelot,

286
00:13:57,779 --> 00:13:59,070
se jatkuva aika operaatio.

287
00:13:59,070 --> 00:14:00,710
Olemme vain lisäämällä eteen.

288
00:14:00,710 --> 00:14:04,400
>> Ja katsoa ylös, hyvin tiedämme
jotka näyttävät ylöspäin linkitetty lista

289
00:14:04,400 --> 00:14:05,785
voi olla ongelma, eikö?

290
00:14:05,785 --> 00:14:07,910
Meidän on etsiä
se alusta loppuun.

291
00:14:07,910 --> 00:14:10,460
Ei ole satunnainen
pääsy linkitetty lista.

292
00:14:10,460 --> 00:14:15,610
Mutta jos sen sijaan, että yksi yhdistetty
lista jossa lookup olisi O n,

293
00:14:15,610 --> 00:14:19,590
meillä on nyt 10 linkitettyjen listojen,
tai 1000 linkitettyjen listojen,

294
00:14:19,590 --> 00:14:24,120
nyt se on O n jaettuna 10,
tai O n jaettuna 1000.

295
00:14:24,120 --> 00:14:26,940
>> Ja kun me puhuimme
teoreettisesti noin monimutkaisuus

296
00:14:26,940 --> 00:14:30,061
emme ota huomioon vakiot, todellisessa
maailma nämä asiat todella väliä,

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

298
00:14:30,560 --> 00:14:33,080
Me itse asiassa huomaavat
että näin tapahtuu

299
00:14:33,080 --> 00:14:36,610
ajaa 10 kertaa nopeammin,
tai 1000 kertaa nopeammin,

300
00:14:36,610 --> 00:14:41,570
koska me jakaa yksi pitkä
ketju yli 1000 pienempiä ketjuja.

301
00:14:41,570 --> 00:14:45,090
Ja niin joka kerta meillä on etsiä
kautta yksi näistä ketjuista voimme

302
00:14:45,090 --> 00:14:50,290
sivuuttaa 999 ketjut emme välitä
noin, ja vain etsiä, että yksi.

303
00:14:50,290 --> 00:14:53,220
>> Joka on keskimäärin
olla 1000 kertaa lyhyempi.

304
00:14:53,220 --> 00:14:56,460
Ja niin me vielä olemme tavallaan
omiaan johtamaan tätä keskimääräistä tapauksessa

305
00:14:56,460 --> 00:15:01,610
olemisen jatkuva aikaa, mutta
vain koska olemme vipuvaikutusta

306
00:15:01,610 --> 00:15:03,730
jakamalla valtavia vakiokertoimella.

307
00:15:03,730 --> 00:15:05,804
Katsotaanpa, miten tämä voisi
todella näyttävät kuitenkin.

308
00:15:05,804 --> 00:15:08,720
Joten tämä oli tiiviste meillä oli
ennen kuin julisti hajautustaulun joka

309
00:15:08,720 --> 00:15:10,270
oli pystyy varastoimaan 10 jouset.

310
00:15:10,270 --> 00:15:11,728
Emme aio tehdä sitä enää.

311
00:15:11,728 --> 00:15:13,880
Tiedämme jo
rajoitukset kyseistä menetelmää.

312
00:15:13,880 --> 00:15:20,170
Nyt meidän tiiviste tulee olemaan
joukko 10 solmuja, osoittimet

313
00:15:20,170 --> 00:15:22,120
päälliköille linkitettyjen listojen.

314
00:15:22,120 --> 00:15:23,830
>> Ja nyt se on null.

315
00:15:23,830 --> 00:15:26,170
Jokainen näistä 10 viitteitä on null.

316
00:15:26,170 --> 00:15:29,870
Ei ole mitään meidän
hash taulukko juuri nyt.

317
00:15:29,870 --> 00:15:32,690
>> Nyt alkaa laittaa
asiat tähän tiiviste.

318
00:15:32,690 --> 00:15:35,440
Ja katsotaan, miten tämä menetelmä on
aikoo hyötyä meille hieman.

319
00:15:35,440 --> 00:15:36,760
Katsotaanpa nyt hash Joey.

320
00:15:36,760 --> 00:15:40,210
Me ajaa merkkijono Joey kautta
hajautusfunktiota ja palaamme 6.

321
00:15:40,210 --> 00:15:41,200
No mitä teemme nyt?

322
00:15:41,200 --> 00:15:44,090
>> No nyt työskentelee linkitettyjen listojen,
emme kanssa paneelit.

323
00:15:44,090 --> 00:15:45,881
Ja kun pyrimme
linkitettyjä luetteloita meillä

324
00:15:45,881 --> 00:15:49,790
tietävät meidän on aloitettava dynaamisesti
jakamisesta tilaa ja rakennuksen ketjut.

325
00:15:49,790 --> 00:15:54,020
Se on eräänlainen how-- ne ovat keskeisiä
elementit rakentaa linkitetyn listan.

326
00:15:54,020 --> 00:15:57,670
Joten dynaamisesti
jakaa tilaa Joey,

327
00:15:57,670 --> 00:16:00,390
ja sitten katsotaanpa lisätä hänet ketjuun.

328
00:16:00,390 --> 00:16:03,170
>> Joten nyt näyttää mitä olemme tehneet.

329
00:16:03,170 --> 00:16:06,440
Kun me hash Joey saimme hashcode 6.

330
00:16:06,440 --> 00:16:11,790
Nyt kohdistin array sijainti 6
viittaa pään linkitetty lista,

331
00:16:11,790 --> 00:16:14,900
ja nyt se on ainoa
osa linkitetyn listan.

332
00:16:14,900 --> 00:16:18,350
Ja solmu että
linkitetty lista on Joey.

333
00:16:18,350 --> 00:16:22,300
>> Joten jos meidän etsiä Joey
myöhemmin, me vain hash Joey uudelleen,

334
00:16:22,300 --> 00:16:26,300
saamme 6 uudelleen, koska meidän
tiivistefunktio on deterministinen.

335
00:16:26,300 --> 00:16:30,400
Ja sitten aloitamme kärjessä
on linkitetyn listan huomautti

336
00:16:30,400 --> 00:16:33,360
TO array sijainti
6, ja voimme kerrata

337
00:16:33,360 --> 00:16:35,650
poikki yrittää löytää Joey.

338
00:16:35,650 --> 00:16:37,780
Ja jos me rakennamme
tiiviste tehokkaasti,

339
00:16:37,780 --> 00:16:41,790
ja meidän hajautusfunktio tehokkaasti
jakaa tietoja hyvin,

340
00:16:41,790 --> 00:16:45,770
keskimäärin jokainen näistä liittyvät
luettelot kaikissa array sijainti

341
00:16:45,770 --> 00:16:50,110
on kymmenesosa koko, jos me
vain oli se yhtenä valtava

342
00:16:50,110 --> 00:16:51,650
linkitetty lista kaiken siinä.

343
00:16:51,650 --> 00:16:55,670
>> Jos jaamme että valtava liittyvät
luettelo yli 10 linkitettyjen listojen

344
00:16:55,670 --> 00:16:57,760
kukin luettelo on kymmenesosa koko.

345
00:16:57,760 --> 00:17:01,432
Ja näin 10 kertaa nopeammin
etsiä.

346
00:17:01,432 --> 00:17:02,390
Joten tehdä tätä uudelleen.

347
00:17:02,390 --> 00:17:04,290
Katsotaanpa nyt hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> Ja sanotaanko Ross, kun me teemme, että
hash palaamme on 2.

349
00:17:07,540 --> 00:17:10,630
No nyt meillä dynaamisesti jakaa
uusi solmu, laitamme Ross että solmu,

350
00:17:10,630 --> 00:17:14,900
ja sanomme nyt array sijainti
2, sen sijaan osoittaa null,

351
00:17:14,900 --> 00:17:18,579
viittaa pää liittyy
lista jonka ainoa solmu on Ross.

352
00:17:18,579 --> 00:17:22,660
Ja voimme tehdä tämän vielä kerran, me
voi hash Rachel ja saada hashcode 4.

353
00:17:22,660 --> 00:17:25,490
malloc uusi solmu, laita Rachel vuonna
solmu, ja sanoa array sijainti

354
00:17:25,490 --> 00:17:27,839
4 nyt viittaa pään
linkitetyn listan, jonka

355
00:17:27,839 --> 00:17:31,420
vain osa sattuu olemaan Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK, mutta mitä tapahtuu, jos
meillä törmäyksen?

357
00:17:33,470 --> 00:17:38,560
Katsotaanpa, miten voimme käsitellä törmäykset
käyttämällä erillistä ketjutuksen menetelmällä.

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

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

360
00:17:41,094 --> 00:17:44,010
Edellisessä esimerkissä olimme
tallennetaan merkkijonoja jono.

361
00:17:44,010 --> 00:17:45,980
Tämä oli ongelma.

362
00:17:45,980 --> 00:17:48,444
>> Emme halua hakata
Joey, ja olemme jo

363
00:17:48,444 --> 00:17:51,110
nähdä, että saamme joitakin klustereiden
ongelmia, jos yritämme askel

364
00:17:51,110 --> 00:17:52,202
kautta ja koetin.

365
00:17:52,202 --> 00:17:54,660
Mutta entä jos olemme juuri sellainen
käsitellä tätä samalla tavalla, eikö?

366
00:17:54,660 --> 00:17:57,440
Se on aivan kuten lisäämällä elementti
johtaja linkitetyn listan.

367
00:17:57,440 --> 00:18:00,220
Haluan vain malloc tilaa Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Me sanoa Phoeben seuraava osoitin
vanha johtaja linkitetyn listan,

369
00:18:04,764 --> 00:18:07,180
ja sitten 6 vain osoittaa
uusi johtaja linkitetyn listan.

370
00:18:07,180 --> 00:18:10,150
Ja nyt näyttää, olemme muuttaneet Phoebe.

371
00:18:10,150 --> 00:18:14,210
Voimme nyt tallentaa kaksi
elementtien hashcode 6,

372
00:18:14,210 --> 00:18:17,170
ja meillä ei ole mitään ongelmia.

373
00:18:17,170 --> 00:18:20,147
>> Se on aika paljon kaikki
siellä on ketjutus.

374
00:18:20,147 --> 00:18:21,980
Ja ketjutus on ehdottomasti
menetelmä, joka on

375
00:18:21,980 --> 00:18:27,390
olemaan tehokkain sinulle, jos
tallennat tietoja hash table.

376
00:18:27,390 --> 00:18:30,890
Mutta tämä yhdistelmä
taulukot ja linkitettyjen listojen

377
00:18:30,890 --> 00:18:36,080
yhteen muodostaen hajautustaulun todella
dramaattisesti parantaa kykyäsi

378
00:18:36,080 --> 00:18:40,550
tallentaa suuria määriä dataa, ja
hyvin nopeasti ja tehokkaasti etsiä

379
00:18:40,550 --> 00:18:41,630
kautta, että tiedot.

380
00:18:41,630 --> 00:18:44,150
>> Vielä yksi
tietorakenne siellä

381
00:18:44,150 --> 00:18:48,700
jotka saattavat jopa olla hieman
paremmin ehdoin taata

382
00:18:48,700 --> 00:18:51,920
että lisäys, poisto, ja
etsiä ajat ovat vieläkin nopeammin.

383
00:18:51,920 --> 00:18:55,630
Ja näemme, että video yrittää.

384
00:18:55,630 --> 00:18:58,930
Olen Doug Lloyd, tämä on CS50.

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