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

2
00:00:00,500 --> 00:00:01,900
[RIPRODUZIONE DI BRANI MUSICALI]

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: Ormai
sapere molto su array,

5
00:00:09,150 --> 00:00:11,610
e si sa molto su liste concatenate.

6
00:00:11,610 --> 00:00:13,650
E abbiamo discutere la
pro e contro, abbiamo

7
00:00:13,650 --> 00:00:16,620
discusso che collegava gli elenchi
può ottenere più grande e più piccolo,

8
00:00:16,620 --> 00:00:18,630
ma si occupano più dimensioni.

9
00:00:18,630 --> 00:00:22,359
Gli array sono molto più semplici da
uso, ma sono restrittive in quanto

10
00:00:22,359 --> 00:00:24,900
come abbiamo per impostare la dimensione di
la matrice proprio all'inizio

11
00:00:24,900 --> 00:00:26,910
e poi siamo bloccati con esso.

12
00:00:26,910 --> 00:00:30,470
>> Ma questo è, abbiamo praticamente
esaurito tutti i nostri argomenti

13
00:00:30,470 --> 00:00:33,040
su liste e matrici collegate.

14
00:00:33,040 --> 00:00:34,950
O abbiamo?

15
00:00:34,950 --> 00:00:37,720
Forse possiamo fare qualcosa
ancora più creativi.

16
00:00:37,720 --> 00:00:40,950
E questo genere di presta
l'idea di una tabella di hash.

17
00:00:40,950 --> 00:00:46,680
>> Quindi, in una tabella hash che andremo a provare
combinare una matrice con una lista collegata.

18
00:00:46,680 --> 00:00:49,520
Stiamo andando a prendere i vantaggi
della matrice, come ad accesso casuale,

19
00:00:49,520 --> 00:00:53,510
essere in grado di andare solo a matrice
Elemento 4 o array elemento 8

20
00:00:53,510 --> 00:00:55,560
senza dover scorrere tutta.

21
00:00:55,560 --> 00:00:57,260
Questo è abbastanza veloce, giusto?

22
00:00:57,260 --> 00:01:00,714
>> Ma dobbiamo anche avere i nostri dati
struttura in grado di crescere e restringersi.

23
00:01:00,714 --> 00:01:02,630
Non abbiamo bisogno, non lo facciamo
vogliono essere limitato.

24
00:01:02,630 --> 00:01:04,588
E noi vogliamo essere in grado
per aggiungere e rimuovere le cose

25
00:01:04,588 --> 00:01:08,430
molto facilmente, che se vi ricordate,
è molto complesso con una matrice.

26
00:01:08,430 --> 00:01:11,650
E possiamo chiamare questo
cosa nuova una tabella hash.

27
00:01:11,650 --> 00:01:15,190
>> E se implementato correttamente,
stiamo sorta di presa

28
00:01:15,190 --> 00:01:18,150
i vantaggi di entrambi i dati
strutture che hai già visto,

29
00:01:18,150 --> 00:01:19,880
array e liste concatenate.

30
00:01:19,880 --> 00:01:23,070
L'inserimento può iniziare a
tendere theta di 1.

31
00:01:23,070 --> 00:01:26,207
Theta non abbiamo davvero discusso,
ma theta è solo il caso medio,

32
00:01:26,207 --> 00:01:27,540
quello che in realtà sta per accadere.

33
00:01:27,540 --> 00:01:29,680
Non stai andando sempre
avere la peggiore delle ipotesi,

34
00:01:29,680 --> 00:01:32,555
e non sei sempre andando ad avere
la migliore delle ipotesi, quindi qual è

35
00:01:32,555 --> 00:01:33,900
lo scenario medio?

36
00:01:33,900 --> 00:01:36,500
>> Beh un inserimento medio
in una tabella hash

37
00:01:36,500 --> 00:01:39,370
può iniziare ad avvicinarsi a tempo costante.

38
00:01:39,370 --> 00:01:41,570
E l'eliminazione può ottenere
vicino al tempo costante.

39
00:01:41,570 --> 00:01:44,440
E ricerca può ottenere
vicino al tempo costante.

40
00:01:44,440 --> 00:01:48,600
That's-- non abbiamo un dato
struttura ma che può farlo,

41
00:01:48,600 --> 00:01:51,180
e quindi questo suona già
come una bella grande cosa.

42
00:01:51,180 --> 00:01:57,010
Abbiamo davvero attenuato la
svantaggi di ciascuno per conto suo.

43
00:01:57,010 --> 00:01:59,160
>> Per ottenere queste prestazioni
l'aggiornamento, però, abbiamo

44
00:01:59,160 --> 00:02:03,580
bisogno di ripensare il modo in cui aggiungiamo
i dati nella struttura.

45
00:02:03,580 --> 00:02:07,380
In particolare vogliamo che il
dati stessi a dirci

46
00:02:07,380 --> 00:02:09,725
dove dovrebbe andare nella struttura.

47
00:02:09,725 --> 00:02:12,850
E se poi bisogna vedere se è in
la struttura, se abbiamo bisogno di trovarlo,

48
00:02:12,850 --> 00:02:16,610
vogliamo guardare ai dati
nuovo e poter efficacemente,

49
00:02:16,610 --> 00:02:18,910
utilizzando i dati, in modo casuale accedervi.

50
00:02:18,910 --> 00:02:20,700
Solo guardando il
dati dovremmo avere

51
00:02:20,700 --> 00:02:25,890
un'idea di dove esattamente siamo
andando a trovare nella tabella hash.

52
00:02:25,890 --> 00:02:28,770
>> Ora, il lato negativo di un hash
tavolo è che sono davvero

53
00:02:28,770 --> 00:02:31,770
piuttosto male a ordinare o l'ordinamento dei dati.

54
00:02:31,770 --> 00:02:34,970
E infatti, se si avvia
usarli per ordinare o specie

55
00:02:34,970 --> 00:02:37,990
dati si perde tutto il
vantaggi che in precedenza

56
00:02:37,990 --> 00:02:40,710
avuto in termini di inserimento e cancellazione.

57
00:02:40,710 --> 00:02:44,060
Il tempo diventa più vicino
theta di n, e abbiamo praticamente

58
00:02:44,060 --> 00:02:45,530
regredito in una lista collegata.

59
00:02:45,530 --> 00:02:48,850
E così abbiamo solo vogliamo usare hash
tavoli se non ci stanno a cuore

60
00:02:48,850 --> 00:02:51,490
se i dati vengono ordinati.

61
00:02:51,490 --> 00:02:54,290
Per il contesto in cui
ti usarli in CS50

62
00:02:54,290 --> 00:02:58,900
probabilmente non si cura
che i dati vengono ordinati.

63
00:02:58,900 --> 00:03:03,170
>> Quindi una tabella di hash è una combinazione
di due pezzi distinti

64
00:03:03,170 --> 00:03:04,980
con cui siamo a conoscenza.

65
00:03:04,980 --> 00:03:07,930
Il primo è una funzione che
che di solito chiamiamo una funzione di hash.

66
00:03:07,930 --> 00:03:11,760
E che la funzione di hash sta per
tornare un intero non negativo, che

67
00:03:11,760 --> 00:03:14,870
che di solito chiamiamo un codice hash, OK?

68
00:03:14,870 --> 00:03:20,230
Il secondo pezzo è un array, che è
in grado di memorizzare i dati del tipo che abbiamo

69
00:03:20,230 --> 00:03:22,190
desidera inserire nella struttura di dati.

70
00:03:22,190 --> 00:03:24,310
Terremo via sul
linked elemento di lista, per ora

71
00:03:24,310 --> 00:03:27,810
e iniziare con le basi di una
hash tavolo per ottenere la testa intorno ad esso,

72
00:03:27,810 --> 00:03:30,210
e poi ci magari saltare
la mente un po 'quando abbiamo

73
00:03:30,210 --> 00:03:32,920
combinano matrici ed elenchi di link insieme.

74
00:03:32,920 --> 00:03:35,590
>> L'idea di base se
è prendiamo alcuni dati.

75
00:03:35,590 --> 00:03:37,860
Corriamo che i dati attraverso
la funzione di hash.

76
00:03:37,860 --> 00:03:41,980
E così i dati sono trattati
e sputa fuori un numero, OK?

77
00:03:41,980 --> 00:03:44,890
E poi con quel numero
abbiamo appena memorizzare i dati

78
00:03:44,890 --> 00:03:48,930
vogliamo memorizzare nella
matrice in quella posizione.

79
00:03:48,930 --> 00:03:53,990
Così, per esempio abbiamo forse
questa tabella hash di stringhe.

80
00:03:53,990 --> 00:03:57,350
E 'ottenuto 10 elementi in esso, in modo
possiamo inserire 10 corde in esso.

81
00:03:57,350 --> 00:03:59,320
>> Diciamo che vogliamo hash John.

82
00:03:59,320 --> 00:04:02,979
Così Giovanni come i dati che vogliamo inserire
in questa tabella hash da qualche parte.

83
00:04:02,979 --> 00:04:03,770
Dove la mettiamo?

84
00:04:03,770 --> 00:04:05,728
Bene in genere con un
matrice finora abbiamo probabilmente

85
00:04:05,728 --> 00:04:07,610
avrebbe messo in ordine posizione 0.

86
00:04:07,610 --> 00:04:09,960
Ma ora abbiamo questa nuova funzione di hash.

87
00:04:09,960 --> 00:04:13,180
>> E diciamo che corriamo John
attraverso questa funzione hash

88
00:04:13,180 --> 00:04:15,417
ed è sputa fuori 4.

89
00:04:15,417 --> 00:04:17,500
Beh, questo è dove siamo
intenzione di voler mettere John.

90
00:04:17,500 --> 00:04:22,050
Vogliamo mettere Giovanni in posizione dell'array
4, perché se hash John again--

91
00:04:22,050 --> 00:04:23,810
diciamo dopo siamo
desidera cercare e vedere

92
00:04:23,810 --> 00:04:26,960
se John esiste in questo hash
table-- tutto quello che dobbiamo fare

93
00:04:26,960 --> 00:04:30,310
è gestito attraverso lo stesso hash
la funzione, ottenere il numero 4 fuori,

94
00:04:30,310 --> 00:04:33,929
ed essere in grado di trovare John
immediatamente nella nostra struttura dati.

95
00:04:33,929 --> 00:04:34,720
Questo è abbastanza buono.

96
00:04:34,720 --> 00:04:36,928
>> Diciamo che ora facciamo
ancora una volta, vogliamo hash Paolo.

97
00:04:36,928 --> 00:04:39,446
Vogliamo aggiungere Paul
in questa tabella di hash.

98
00:04:39,446 --> 00:04:42,070
Diciamo che questa volta si corre
Paolo attraverso la funzione di hash,

99
00:04:42,070 --> 00:04:44,600
il codice hash che viene generato è di 6.

100
00:04:44,600 --> 00:04:47,340
Bene, ora siamo in grado di mettere Paul
nella posizione di matrice 6.

101
00:04:47,340 --> 00:04:50,040
E se abbiamo bisogno di cercare se
Paolo è in questa tabella di hash,

102
00:04:50,040 --> 00:04:53,900
tutto quello che dobbiamo fare è eseguire Paul
attraverso la funzione hash di nuovo

103
00:04:53,900 --> 00:04:55,830
e stiamo andando a ottenere 6 di nuovo fuori.

104
00:04:55,830 --> 00:04:57,590
>> E poi ci limitiamo a guardare
in posizione di matrice 6.

105
00:04:57,590 --> 00:04:58,910
È Paul lì?

106
00:04:58,910 --> 00:05:00,160
Se è così, lui è nella tabella hash.

107
00:05:00,160 --> 00:05:01,875
È Paolo non ci sono?

108
00:05:01,875 --> 00:05:03,000
Non è nella tabella hash.

109
00:05:03,000 --> 00:05:05,720
E 'piuttosto semplice.

110
00:05:05,720 --> 00:05:07,770
>> Ora, come si fa a definire una funzione di hash?

111
00:05:07,770 --> 00:05:11,460
Beh, non c'è davvero alcun limite al
numero di possibili funzioni hash.

112
00:05:11,460 --> 00:05:14,350
In realtà c'è un certo numero di realtà,
quelli veramente buoni su internet.

113
00:05:14,350 --> 00:05:17,560
C'è un certo numero di realtà,
quelli veramente negative su internet.

114
00:05:17,560 --> 00:05:21,080
E 'anche abbastanza facile
di scrivere uno cattivo.

115
00:05:21,080 --> 00:05:23,760
>> Quindi, ciò che rende una buona
funzione di hash, giusto?

116
00:05:23,760 --> 00:05:27,280
Beh, una buona funzione di hash dovrebbe
utilizzare solo i dati che vengono hash,

117
00:05:27,280 --> 00:05:29,420
e tutti i dati che vengono hashing.

118
00:05:29,420 --> 00:05:32,500
Quindi noi non vogliamo usare anything--
noi non incorporiamo nulla

119
00:05:32,500 --> 00:05:35,560
altro che i dati.

120
00:05:35,560 --> 00:05:37,080
E vogliamo utilizzare tutti i dati.

121
00:05:37,080 --> 00:05:39,830
Non vogliamo usare solo un pezzo
di essa, vogliamo usare tutto.

122
00:05:39,830 --> 00:05:41,710
Una funzione hash dovrebbe
anche essere deterministico.

123
00:05:41,710 --> 00:05:42,550
Che cosa significa?

124
00:05:42,550 --> 00:05:46,200
Beh, vuol dire che ogni volta che
passare la stessa porzione di dati

125
00:05:46,200 --> 00:05:50,040
nella funzione di hash che abbiamo sempre
ottenere lo stesso codice hash fuori.

126
00:05:50,040 --> 00:05:52,870
Se io passo John nella
funzione hash esco 4.

127
00:05:52,870 --> 00:05:56,110
Dovrei essere in grado di farlo 10.000
tempi e sarò sempre ottengono 4.

128
00:05:56,110 --> 00:06:00,810
Quindi niente numeri casuali in modo efficace
possono essere coinvolti nel nostro hash tables--

129
00:06:00,810 --> 00:06:02,750
nelle nostre funzioni di hash.

130
00:06:02,750 --> 00:06:05,750
>> Una funzione hash dovrebbe anche
distribuire uniformemente i dati.

131
00:06:05,750 --> 00:06:09,700
Se ogni volta che si esegue dati attraverso il
funzione hash si ottiene il codice hash 0,

132
00:06:09,700 --> 00:06:11,200
che probabilmente non è così grande, giusto?

133
00:06:11,200 --> 00:06:14,600
Probabilmente si desidera grande
una serie di codici hash.

134
00:06:14,600 --> 00:06:17,190
Anche le cose possono essere diffuse
durante tutta la tabella.

135
00:06:17,190 --> 00:06:23,210
Ed inoltre sarebbe bello se davvero
dati simili, come John e Jonathan,

136
00:06:23,210 --> 00:06:26,320
forse sono stati sparsi per pesare
diverse posizioni nella tabella hash.

137
00:06:26,320 --> 00:06:28,750
Questo sarebbe un bel vantaggio.

138
00:06:28,750 --> 00:06:31,250
>> Ecco un esempio di una funzione di hash.

139
00:06:31,250 --> 00:06:33,150
Ho scritto questo in precedenza.

140
00:06:33,150 --> 00:06:35,047
Non è un particolarmente
buona funzione di hash

141
00:06:35,047 --> 00:06:37,380
per ragioni che non lo fanno davvero
orso andando in questo momento.

142
00:06:37,380 --> 00:06:41,040
Ma si vede che cosa sta succedendo qui?

143
00:06:41,040 --> 00:06:44,420
Sembra che stiamo dichiarazione di una variabile
chiamato somma e porla uguale a 0.

144
00:06:44,420 --> 00:06:50,010
E poi pare che sto facendo qualcosa
purché strstr [j] non è uguale

145
00:06:50,010 --> 00:06:52,490
di backslash 0.

146
00:06:52,490 --> 00:06:54,870
Che cosa sto facendo lì?

147
00:06:54,870 --> 00:06:57,440
>> Questo è fondamentalmente solo un altro
modo di attuare [? strl?]

148
00:06:57,440 --> 00:06:59,773
e rilevare quando hai
raggiunta la fine della stringa.

149
00:06:59,773 --> 00:07:02,480
Quindi io non devo realmente
calcolare la lunghezza della stringa,

150
00:07:02,480 --> 00:07:05,640
Sto usando solo quando ho colpito la
backslash 0 personaggio che conosco

151
00:07:05,640 --> 00:07:07,185
Ho raggiunto la fine della stringa.

152
00:07:07,185 --> 00:07:09,560
E poi ho intenzione di continuare a
scorrendo la stringa,

153
00:07:09,560 --> 00:07:15,310
aggiungendo strstr [j] per riassumere, e poi al
fine della giornata andando a tornare somma mod

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

155
00:07:16,200 --> 00:07:18,700
>> Fondamentalmente tutto questo hash
Funzione sta facendo è sommando

156
00:07:18,700 --> 00:07:23,450
tutti i valori ASCII
mia stringa, e quindi è

157
00:07:23,450 --> 00:07:26,390
tornare un codice hash
modded by HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
E 'probabilmente la dimensione
della mia matrice, giusto?

159
00:07:29,790 --> 00:07:33,160
Non voglio essere sempre hash
codici se la mia matrice è di dimensioni 10,

160
00:07:33,160 --> 00:07:35,712
Io non voglio essere sempre
codici hash fuori 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, non riesco a mettere le cose in
quelle posizioni della matrice,

162
00:07:38,690 --> 00:07:39,790
che sarebbe illegale.

163
00:07:39,790 --> 00:07:42,130
Mi piacerebbe soffro un segmentation fault.

164
00:07:42,130 --> 00:07:45,230
>> Ora qui è un altro rapido da parte.

165
00:07:45,230 --> 00:07:48,470
In generale si sta probabilmente non andare a
vogliono scrivere le proprie funzioni di hash.

166
00:07:48,470 --> 00:07:50,997
In realtà è un po 'di
un'arte, non una scienza.

167
00:07:50,997 --> 00:07:52,580
E ci sono un sacco che va in loro.

168
00:07:52,580 --> 00:07:55,288
Internet, come ho detto, è piena
di veramente buono funzioni hash,

169
00:07:55,288 --> 00:07:58,470
e si dovrebbe utilizzare internet per
trovare funzioni hash perché è davvero

170
00:07:58,470 --> 00:08:03,230
solo una specie di inutile
perdita di tempo per creare il proprio.

171
00:08:03,230 --> 00:08:05,490
>> È possibile scrivere quelle semplici
a scopo di test.

172
00:08:05,490 --> 00:08:08,323
Ma quando effettivamente intenzione di
iniziare hashing dei dati e la memorizzazione

173
00:08:08,323 --> 00:08:10,780
in una tabella hash sei
probabilmente andando a voler

174
00:08:10,780 --> 00:08:14,580
usare qualche funzione che è stato generato
per te, che esiste su Internet.

175
00:08:14,580 --> 00:08:17,240
Se non tanto per essere sicuro
per citare le tue fonti.

176
00:08:17,240 --> 00:08:21,740
Non c'è motivo per
plagiare nulla qui.

177
00:08:21,740 --> 00:08:25,370
>> La comunità informatica è
decisamente in crescita, e davvero i valori

178
00:08:25,370 --> 00:08:28,796
open source, ed è molto importante
per citare le fonti in modo che la gente

179
00:08:28,796 --> 00:08:30,670
può ottenere attribuzione per
il lavoro che sono

180
00:08:30,670 --> 00:08:32,312
facendo per il beneficio della comunità.

181
00:08:32,312 --> 00:08:34,020
Quindi, essere sempre sure--
e non solo per hash

182
00:08:34,020 --> 00:08:37,270
funzioni, ma in genere quando si
utilizzare il codice da una fonte esterna,

183
00:08:37,270 --> 00:08:38,299
citare sempre la vostra fonte.

184
00:08:38,299 --> 00:08:43,500
Devi riconoscere il soggetto che ha fatto
alcuni dei lavori in modo da non devi.

185
00:08:43,500 --> 00:08:46,720
>> OK quindi cerchiamo di rivisitare questo
tabella di hash per un secondo.

186
00:08:46,720 --> 00:08:48,780
Questo è dove abbiamo lasciato
dopo abbiamo inserito

187
00:08:48,780 --> 00:08:53,300
Giovanni e Paolo in questa tabella di hash.

188
00:08:53,300 --> 00:08:55,180
Vedete un problema qui?

189
00:08:55,180 --> 00:08:58,410
Si potrebbe vedere due.

190
00:08:58,410 --> 00:09:02,240
Ma in particolare, si fa
vedere questo possibile problema?

191
00:09:02,240 --> 00:09:06,770
>> Cosa succede se Hash Ringo, e
risulta che dopo la trasformazione

192
00:09:06,770 --> 00:09:14,000
che i dati tramite la funzione hash
Ringo anche generato il codice hash 6.

193
00:09:14,000 --> 00:09:16,810
Ho già dati a
hashcode-- posizione di matrice 6.

194
00:09:16,810 --> 00:09:22,000
Quindi è destinata probabilmente ad essere un po '
di un problema per me, ora, giusto?

195
00:09:22,000 --> 00:09:23,060
>> Noi chiamiamo questo una collisione.

196
00:09:23,060 --> 00:09:26,460
E la collisione si verifica quando due
pezzi di dati attraversano lo stesso hash

197
00:09:26,460 --> 00:09:29,200
funzione di cedere lo stesso codice hash.

198
00:09:29,200 --> 00:09:32,850
Presumibilmente abbiamo ancora voglia di ottenere sia
pezzi di dati nella tabella di hash,

199
00:09:32,850 --> 00:09:36,330
altrimenti non saremmo in esecuzione Ringo
arbitrariamente attraverso la funzione hash.

200
00:09:36,330 --> 00:09:40,870
Noi presumibilmente vogliamo ottenere
RINGO in tale matrice.

201
00:09:40,870 --> 00:09:46,070
>> Come lo facciamo, però, se lui
e Paolo sia resa codice hash 6?

202
00:09:46,070 --> 00:09:49,520
Non vogliamo sovrascrivere Paul,
vogliamo che Paul sia lì.

203
00:09:49,520 --> 00:09:52,790
Quindi abbiamo bisogno di trovare un modo per ottenere
elementi nella tabella hash

204
00:09:52,790 --> 00:09:56,550
conserva ancora il nostro rapido
inserimento e rapido sguardo in su.

205
00:09:56,550 --> 00:10:01,350
E un modo per affrontare il problema è quello di
fare qualcosa chiamato scansione lineare.

206
00:10:01,350 --> 00:10:04,170
>> Utilizzando questo metodo, se abbiamo un
collisione, beh, che cosa facciamo?

207
00:10:04,170 --> 00:10:08,580
Beh, non possiamo mettere in posizione dell'array
6, o qualunque codice hash è stato generato,

208
00:10:08,580 --> 00:10:10,820
Mettiamolo in codice hash più 1.

209
00:10:10,820 --> 00:10:13,670
E se questo è pieno di let
metterlo in codice hash più 2.

210
00:10:13,670 --> 00:10:17,420
Il vantaggio di questo essere se e '
Non esattamente dove pensiamo che è,

211
00:10:17,420 --> 00:10:20,850
e dobbiamo cominciare a cercare,
forse non dobbiamo andare troppo lontano.

212
00:10:20,850 --> 00:10:23,900
Forse noi non dobbiamo cercare
tutti gli n elementi della tabella hash.

213
00:10:23,900 --> 00:10:25,790
Forse dobbiamo cercare
un paio di loro.

214
00:10:25,790 --> 00:10:30,680
>> E così siamo ancora tendente
quel caso media prossima a 1 vs

215
00:10:30,680 --> 00:10:34,280
vicino ai n, quindi forse sarà il lavoro.

216
00:10:34,280 --> 00:10:38,010
Quindi cerchiamo di vedere come questo
potrebbe funzionare nella realtà.

217
00:10:38,010 --> 00:10:41,460
E vediamo se forse possiamo scoprire
il problema che potrebbe verificarsi qui.

218
00:10:41,460 --> 00:10:42,540
>> Diciamo che Hash Bart.

219
00:10:42,540 --> 00:10:45,581
Così ora stiamo andando a correre una nuova serie
di stringhe tramite la funzione di hash,

220
00:10:45,581 --> 00:10:48,460
e corriamo Bart attraverso l'hash
Funzione, otteniamo codice hash 6.

221
00:10:48,460 --> 00:10:52,100
Diamo uno sguardo, vediamo 6 è
vuoto, in modo che possiamo mettere Bart lì.

222
00:10:52,100 --> 00:10:55,410
>> Ora ci hash Lisa e che
genera anche codice hash 6.

223
00:10:55,410 --> 00:10:58,330
Bene, ora che stiamo usando questo
lineare metodo partiamo alle 6 sondare,

224
00:10:58,330 --> 00:10:59,330
vediamo che 6 è piena.

225
00:10:59,330 --> 00:11:00,990
Non possiamo mettere Lisa in 6.

226
00:11:00,990 --> 00:11:02,090
Allora dove andiamo?

227
00:11:02,090 --> 00:11:03,280
Andiamo a 7.

228
00:11:03,280 --> 00:11:04,610
7 di vuoto, in modo che funziona.

229
00:11:04,610 --> 00:11:06,510
Quindi cerchiamo di mettere Lisa lì.

230
00:11:06,510 --> 00:11:10,200
>> Ora ci hash Omero e otteniamo 7.

231
00:11:10,200 --> 00:11:13,380
OK bene sappiamo che 7 di piena
ora, in modo da non possiamo mettere Omero lì.

232
00:11:13,380 --> 00:11:14,850
Così andiamo a 8.

233
00:11:14,850 --> 00:11:15,664
È disponibile 8?

234
00:11:15,664 --> 00:11:18,330
Sì, e 8 di quasi il 7, quindi se
dobbiamo iniziare a cercare siamo

235
00:11:18,330 --> 00:11:20,020
non andando ad avere per andare troppo lontano.

236
00:11:20,020 --> 00:11:22,860
E così mettiamo Omero a 8.

237
00:11:22,860 --> 00:11:25,151
>> Ora ci hash Maggie e
restituisce 3, grazie al cielo

238
00:11:25,151 --> 00:11:26,650
siamo in grado di mettere solo Maggie lì.

239
00:11:26,650 --> 00:11:29,070
Non abbiamo a che fare ogni
sorta di sondare per questo.

240
00:11:29,070 --> 00:11:32,000
Ora noi Hash Marge, e
Marge restituisce anche 6.

241
00:11:32,000 --> 00:11:39,560
>> Ebbene 6 è pieno, 7 è pieno, 8 è piena,
9, va bene grazie a Dio, 9 è vuoto.

242
00:11:39,560 --> 00:11:41,600
Posso mettere Marge a 9.

243
00:11:41,600 --> 00:11:45,280
Già possiamo vedere che stiamo iniziando
di avere questo problema in cui ora siamo

244
00:11:45,280 --> 00:11:48,780
iniziando ad allungare le cose tipo
di lontano dalle loro codici hash.

245
00:11:48,780 --> 00:11:52,960
E che theta di 1, questa media
caso di essere costante di tempo,

246
00:11:52,960 --> 00:11:56,560
sta iniziando a diventare un po 'more--
iniziando a tendere un po 'più

247
00:11:56,560 --> 00:11:58,050
verso theta di n.

248
00:11:58,050 --> 00:12:01,270
Stiamo iniziando a perdere quel
vantaggio di tabelle hash.

249
00:12:01,270 --> 00:12:03,902
>> Questo problema che abbiamo appena visto
è qualcosa chiamato clustering.

250
00:12:03,902 --> 00:12:06,360
E ciò che è veramente male su
il clustering è che una volta ora

251
00:12:06,360 --> 00:12:09,606
avere due elementi che sono fianco a
lato si rende ancora più probabile,

252
00:12:09,606 --> 00:12:11,480
si ha il doppio
possibilità, che si sta andando

253
00:12:11,480 --> 00:12:13,516
di avere un altro scontro
con quel gruppo,

254
00:12:13,516 --> 00:12:14,890
e il cluster crescerà di uno.

255
00:12:14,890 --> 00:12:19,640
E ti tenere a crescere e crescere
la probabilità di avere una collisione.

256
00:12:19,640 --> 00:12:24,470
E alla fine è proprio così male
da non classificare i dati a tutti.

257
00:12:24,470 --> 00:12:27,590
>> L'altro problema è se siamo
ancora, e finora fino a questo punto,

258
00:12:27,590 --> 00:12:30,336
che abbiamo appena sorta di
capire che cosa una tabella hash è,

259
00:12:30,336 --> 00:12:31,960
abbiamo ancora spazio solo per 10 corde.

260
00:12:31,960 --> 00:12:37,030
Se vogliamo continuare a hash
i cittadini di Springfield,

261
00:12:37,030 --> 00:12:38,790
siamo in grado di ottenere solo 10 di loro in là.

262
00:12:38,790 --> 00:12:42,619
E se cerchiamo di aggiungere un 11 ° o 12,
non abbiamo un posto dove metterli.

263
00:12:42,619 --> 00:12:45,660
Potremmo essere in Spinning Around
cerchi cercando di trovare un punto vuoto,

264
00:12:45,660 --> 00:12:49,000
e noi forse si blocca
in un ciclo infinito.

265
00:12:49,000 --> 00:12:51,810
>> Quindi questo tipo di presta all'idea
di una cosa chiamata concatenamento.

266
00:12:51,810 --> 00:12:55,790
E questo è dove stiamo andando a portare
liste collegate torna in scena.

267
00:12:55,790 --> 00:13:01,300
Che cosa succede se invece di memorizzare solo
i dati stessi nella matrice,

268
00:13:01,300 --> 00:13:04,471
ogni elemento della matrice potrebbe
tenere più pezzi di dati?

269
00:13:04,471 --> 00:13:05,970
Beh, questo non ha senso, giusto?

270
00:13:05,970 --> 00:13:09,280
Sappiamo che una matrice solo è possibile
hold-- ogni elemento di un array

271
00:13:09,280 --> 00:13:12,930
può contenere solo un pezzo
di dati di tale tipo di dati.

272
00:13:12,930 --> 00:13:16,750
>> Ma cosa succede se quel tipo di dati
è una lista collegata, giusto?

273
00:13:16,750 --> 00:13:19,830
Così che cosa se ogni
elemento della matrice era

274
00:13:19,830 --> 00:13:22,790
un puntatore alla testa di una lista collegata?

275
00:13:22,790 --> 00:13:24,680
E allora potremmo costruire
quelle liste concatenate

276
00:13:24,680 --> 00:13:27,120
e farle crescere arbitrariamente,
perché liste concatenate consentono

277
00:13:27,120 --> 00:13:32,090
di crescere e ridurre molto di più
flessibilità di un array fa.

278
00:13:32,090 --> 00:13:34,210
Che importa se ora usiamo,
facciamo leva questo, giusto?

279
00:13:34,210 --> 00:13:37,760
Si comincia a coltivare queste catene
da queste posizioni di matrice.

280
00:13:37,760 --> 00:13:40,740
>> Ora possiamo andare bene un infinito
quantità di dati, o non infinito,

281
00:13:40,740 --> 00:13:44,170
una quantità arbitraria di
i dati, nella nostra tabella hash

282
00:13:44,170 --> 00:13:47,760
senza mai incorrere in
il problema di collisione.

283
00:13:47,760 --> 00:13:50,740
Abbiamo anche eliminato
il clustering in questo modo.

284
00:13:50,740 --> 00:13:54,380
E ben sappiamo che quando inseriamo
in una lista collegata, se vi ricordate

285
00:13:54,380 --> 00:13:57,779
dal nostro video su liste concatenate, singolarmente
liste concatenate e liste doppiamente collegate,

286
00:13:57,779 --> 00:13:59,070
si tratta di una operazione di tempo costante.

287
00:13:59,070 --> 00:14:00,710
Stiamo solo aggiungendo alla parte anteriore.

288
00:14:00,710 --> 00:14:04,400
>> E per guardare in alto, ben sappiamo
quello sguardo in una lista collegata

289
00:14:04,400 --> 00:14:05,785
può essere un problema, giusto?

290
00:14:05,785 --> 00:14:07,910
Dobbiamo per la ricerca in
che dall'inizio alla fine.

291
00:14:07,910 --> 00:14:10,460
Non c'è nessun caso
accesso in una lista collegata.

292
00:14:10,460 --> 00:14:15,610
Ma se invece di avere uno collegato
lista in cui una ricerca sarebbe O di n,

293
00:14:15,610 --> 00:14:19,590
ora abbiamo 10 liste collegate,
o 1.000 liste collegate,

294
00:14:19,590 --> 00:14:24,120
ora è O di n diviso 10,
o O di n diviso per 1.000.

295
00:14:24,120 --> 00:14:26,940
>> E mentre stavamo parlando
teoricamente sulla complessità

296
00:14:26,940 --> 00:14:30,061
ignoriamo costanti, nel vero
mondo queste cose realmente importa,

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

298
00:14:30,560 --> 00:14:33,080
Noi in realtà noteremo
che ciò avvenga

299
00:14:33,080 --> 00:14:36,610
per eseguire 10 volte più veloce,
o 1.000 volte più veloce,

300
00:14:36,610 --> 00:14:41,570
perché stiamo distribuendo una lunga
catena in tutto 1.000 catene più piccole.

301
00:14:41,570 --> 00:14:45,090
E così ogni volta che dobbiamo cercare
attraverso una di quelle catene che possiamo

302
00:14:45,090 --> 00:14:50,290
ignorare le 999 catene non ci preoccupiamo
su, e basta cercare quello.

303
00:14:50,290 --> 00:14:53,220
>> Che è, in media, a
essere 1000 volte più breve.

304
00:14:53,220 --> 00:14:56,460
E così siamo ancora sorta di
tendente questo caso medio

305
00:14:56,460 --> 00:15:01,610
di essere costante di tempo, ma
solo perché facciamo leva

306
00:15:01,610 --> 00:15:03,730
dividendo per qualche enorme fattore costante.

307
00:15:03,730 --> 00:15:05,804
Vediamo come questo potrebbe
effettivamente guardare però.

308
00:15:05,804 --> 00:15:08,720
Quindi questa è stata la tabella di hash che abbiamo avuto
prima abbiamo dichiarato una tabella hash che

309
00:15:08,720 --> 00:15:10,270
era in grado di memorizzare 10 stringhe.

310
00:15:10,270 --> 00:15:11,728
Non abbiamo intenzione di farlo più.

311
00:15:11,728 --> 00:15:13,880
Sappiamo già la
limitazioni di quel metodo.

312
00:15:13,880 --> 00:15:20,170
Ora la nostra tabella di hash sarà
un array di 10 nodi, puntatori

313
00:15:20,170 --> 00:15:22,120
ai capi di liste collegate.

314
00:15:22,120 --> 00:15:23,830
>> E in questo momento è nullo.

315
00:15:23,830 --> 00:15:26,170
Ognuno di questi 10 puntatori è nullo.

316
00:15:26,170 --> 00:15:29,870
Non c'è nulla nel nostro
hash tavolo in questo momento.

317
00:15:29,870 --> 00:15:32,690
>> Ora cominciamo a mettere un po '
cose in questa tabella di hash.

318
00:15:32,690 --> 00:15:35,440
E vediamo come questo metodo
andare a beneficio di noi un po '.

319
00:15:35,440 --> 00:15:36,760
Vediamo ora l'hashing Joey.

320
00:15:36,760 --> 00:15:40,210
Ti verrà eseguito la stringa Joey attraverso
una funzione hash e torniamo 6.

321
00:15:40,210 --> 00:15:41,200
Beh, cosa facciamo adesso?

322
00:15:41,200 --> 00:15:44,090
>> Bene, ora si lavora con liste collegate,
non stiamo lavorando con gli array.

323
00:15:44,090 --> 00:15:45,881
E quando stiamo lavorando
con liste concatenate noi

324
00:15:45,881 --> 00:15:49,790
sappiamo che dobbiamo iniziare in modo dinamico
assegnazione catene di spazio e di costruzione.

325
00:15:49,790 --> 00:15:54,020
Questo è una sorta di how-- questi sono il nucleo
elementi di costruzione di una lista collegata.

326
00:15:54,020 --> 00:15:57,670
Quindi cerchiamo di dinamicamente
allocare spazio per Joey,

327
00:15:57,670 --> 00:16:00,390
e poi facciamo lo aggiungiamo alla catena.

328
00:16:00,390 --> 00:16:03,170
>> Ora guardiamo quello che abbiamo fatto.

329
00:16:03,170 --> 00:16:06,440
Quando abbiamo hash Joey abbiamo ottenuto il codice hash 6.

330
00:16:06,440 --> 00:16:11,790
Ora il puntatore in posizione di matrice 6
punta alla testa di una lista collegata,

331
00:16:11,790 --> 00:16:14,900
e in questo momento è l'unica
elemento di una lista collegata.

332
00:16:14,900 --> 00:16:18,350
E il nodo che
lista collegata è Joey.

333
00:16:18,350 --> 00:16:22,300
>> Quindi, se abbiamo bisogno di guardare in alto Joey
più tardi, abbiamo appena hash di nuovo Joey,

334
00:16:22,300 --> 00:16:26,300
otteniamo 6 di nuovo perché il nostro
funzione hash è deterministica.

335
00:16:26,300 --> 00:16:30,400
E poi si parte in testa
della lista collegata puntato

336
00:16:30,400 --> 00:16:33,360
a da posizione dell'array
6, e siamo in grado di iterare

337
00:16:33,360 --> 00:16:35,650
attraverso che cercando di trovare Joey.

338
00:16:35,650 --> 00:16:37,780
E se noi costruiamo il nostro
hash efficacemente tavolo,

339
00:16:37,780 --> 00:16:41,790
e la nostra funzione di hash in modo efficace
per distribuire bene i dati,

340
00:16:41,790 --> 00:16:45,770
in media ciascuno di quelli legati
liste in ogni posizione dell'array

341
00:16:45,770 --> 00:16:50,110
sarà 1/10 delle dimensioni di se
appena avuto come un unico enorme

342
00:16:50,110 --> 00:16:51,650
lista collegata con tutto ciò che contiene.

343
00:16:51,650 --> 00:16:55,670
>> Se distribuiamo quell'enorme collegati
Lista in 10 liste collegate

344
00:16:55,670 --> 00:16:57,760
ogni lista sarà 1/10 delle dimensioni.

345
00:16:57,760 --> 00:17:01,432
E così 10 volte più veloce
per la ricerca in.

346
00:17:01,432 --> 00:17:02,390
Quindi cerchiamo di farlo di nuovo.

347
00:17:02,390 --> 00:17:04,290
Vediamo ora l'hashing Ross.

348
00:17:04,290 --> 00:17:07,540
>> E diciamo Ross, quando lo facciamo
il codice hash torniamo è 2.

349
00:17:07,540 --> 00:17:10,630
Bene, ora abbiamo allocare dinamicamente un
nuovo nodo, abbiamo messo Ross in quel nodo,

350
00:17:10,630 --> 00:17:14,900
e noi diciamo ora posizione dell'array
2, invece di puntare su null,

351
00:17:14,900 --> 00:17:18,579
punta alla testa di un legato
lista il cui unico nodo è Ross.

352
00:17:18,579 --> 00:17:22,660
E possiamo farlo ancora una volta, abbiamo
può hash Rachel e ottenere codice hash 4.

353
00:17:22,660 --> 00:17:25,490
malloc un nuovo nodo, mettere Rachel
il nodo, e dire una posizione di matrice

354
00:17:25,490 --> 00:17:27,839
4 ora punta alla testa
di una lista collegata la cui

355
00:17:27,839 --> 00:17:31,420
unico elemento sembra essere Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK ma cosa succede se
abbiamo una collisione?

357
00:17:33,470 --> 00:17:38,560
Vediamo come gestiamo le collisioni
utilizzando il metodo concatenazioni separate.

358
00:17:38,560 --> 00:17:39,800
Cerchiamo di eseguire l'hashing Phoebe.

359
00:17:39,800 --> 00:17:41,094
Otteniamo il codice hash 6.

360
00:17:41,094 --> 00:17:44,010
Nel nostro esempio precedente eravamo solo
memorizzare le stringhe nella matrice.

361
00:17:44,010 --> 00:17:45,980
Questo è stato un problema.

362
00:17:45,980 --> 00:17:48,444
>> Noi non vogliamo clobber
Joey, e abbiamo già

363
00:17:48,444 --> 00:17:51,110
visto che siamo in grado di ottenere un po 'di clustering
problemi se cerchiamo di passo

364
00:17:51,110 --> 00:17:52,202
attraverso e sonda.

365
00:17:52,202 --> 00:17:54,660
Ma cosa succederebbe se solo tipo di
trattare questo allo stesso modo, giusto?

366
00:17:54,660 --> 00:17:57,440
E 'proprio come aggiunta di un elemento
alla testa di una lista collegata.

367
00:17:57,440 --> 00:18:00,220
Diamo spazio solo malloc per Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Diremo puntatore punti successivi di Phoebe
al vecchio capo della lista collegata,

369
00:18:04,764 --> 00:18:07,180
e poi 6 punti solo per la
nuovo capo della lista collegata.

370
00:18:07,180 --> 00:18:10,150
E ora guardiamo, abbiamo cambiato Phoebe in.

371
00:18:10,150 --> 00:18:14,210
Ora possiamo memorizzare due
elementi con codice hash 6,

372
00:18:14,210 --> 00:18:17,170
e non abbiamo alcun problema.

373
00:18:17,170 --> 00:18:20,147
>> Questo è praticamente tutto
c'è da concatenamento.

374
00:18:20,147 --> 00:18:21,980
E concatenamento è sicuramente
il metodo che è

375
00:18:21,980 --> 00:18:27,390
sta per essere più efficace per voi se
si memorizzano i dati in una tabella hash.

376
00:18:27,390 --> 00:18:30,890
Ma questa combinazione di
array e liste concatenate

377
00:18:30,890 --> 00:18:36,080
insieme per formare una tabella hash veramente
migliora notevolmente la vostra capacità

378
00:18:36,080 --> 00:18:40,550
per memorizzare grandi quantità di dati, e
molto rapido ed efficiente ricerca

379
00:18:40,550 --> 00:18:41,630
attraverso tali dati.

380
00:18:41,630 --> 00:18:44,150
>> C'è ancora un altro
struttura di dati là fuori

381
00:18:44,150 --> 00:18:48,700
che potrebbe anche essere un po '
migliore in termini di garantire

382
00:18:48,700 --> 00:18:51,920
che il nostro inserimento, cancellazione, e
consultare le tabelle sono ancora più veloci.

383
00:18:51,920 --> 00:18:55,630
E vedremo che in un video su tentativi.

384
00:18:55,630 --> 00:18:58,930
Sono Doug Lloyd, questo è CS50.

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