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

2
00:00:00,500 --> 00:00:01,900
[Música tocando]

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: Até agora você
sabe muito sobre arrays,

5
00:00:09,150 --> 00:00:11,610
e você sabe muito sobre listas ligadas.

6
00:00:11,610 --> 00:00:13,650
E nós discutir a
prós e contras, temos

7
00:00:13,650 --> 00:00:16,620
discutido que ligava listas
pode ficar maior e menor,

8
00:00:16,620 --> 00:00:18,630
mas elas ocupam mais tamanho.

9
00:00:18,630 --> 00:00:22,359
Arrays são muito mais simples de
usar, mas eles são restritivos, na medida em

10
00:00:22,359 --> 00:00:24,900
como temos de definir o tamanho da
o array no início

11
00:00:24,900 --> 00:00:26,910
e então nós está preso com ele.

12
00:00:26,910 --> 00:00:30,470
>> Mas isso é, nós temos praticamente
esgotado todos os nossos temas

13
00:00:30,470 --> 00:00:33,040
sobre listas ligadas e matrizes.

14
00:00:33,040 --> 00:00:34,950
Ou não é?

15
00:00:34,950 --> 00:00:37,720
Talvez possamos fazer algo
ainda mais criativo.

16
00:00:37,720 --> 00:00:40,950
E esse tipo de empresta
a idéia de uma tabela hash.

17
00:00:40,950 --> 00:00:46,680
>> Assim, em uma tabela hash vamos tentar
combinar uma matriz com uma lista ligada.

18
00:00:46,680 --> 00:00:49,520
Nós vamos ter as vantagens
da matriz, como a de acesso aleatório,

19
00:00:49,520 --> 00:00:53,510
ser capaz de simplesmente ir a matriz
elemento 4 ou matriz elemento 8

20
00:00:53,510 --> 00:00:55,560
sem ter que interagir transversalmente.

21
00:00:55,560 --> 00:00:57,260
Isso é muito rápido, certo?

22
00:00:57,260 --> 00:01:00,714
>> Mas também queremos ter nossos dados
estrutura capaz de aumentar e diminuir.

23
00:01:00,714 --> 00:01:02,630
Nós não precisamos, nós não
pretende ser restrita.

24
00:01:02,630 --> 00:01:04,588
E nós queremos ser capazes
para adicionar e remover as coisas

25
00:01:04,588 --> 00:01:08,430
muito facilmente, o que se você se lembra,
é muito complexo, com uma matriz.

26
00:01:08,430 --> 00:01:11,650
E nós podemos chamar isso de
coisa nova uma tabela hash.

27
00:01:11,650 --> 00:01:15,190
>> E, se implementada corretamente,
estamos espécie de tomar

28
00:01:15,190 --> 00:01:18,150
as vantagens de ambos os dados
estruturas que você já viu,

29
00:01:18,150 --> 00:01:19,880
matrizes e listas ligadas.

30
00:01:19,880 --> 00:01:23,070
A inserção pode começar a
tendem a teta de uma.

31
00:01:23,070 --> 00:01:26,207
Theta não temos realmente discutido,
mas é apenas o caso teta média,

32
00:01:26,207 --> 00:01:27,540
o que realmente vai acontecer.

33
00:01:27,540 --> 00:01:29,680
Você nem sempre vai
tem o pior cenário,

34
00:01:29,680 --> 00:01:32,555
e você não está indo sempre ter
o melhor cenário, então o que é

35
00:01:32,555 --> 00:01:33,900
o cenário de média?

36
00:01:33,900 --> 00:01:36,500
>> Bem uma inserção média
em uma tabela hash

37
00:01:36,500 --> 00:01:39,370
pode começar a chegar perto de tempo constante.

38
00:01:39,370 --> 00:01:41,570
E eliminação pode obter
fechar com o tempo constante.

39
00:01:41,570 --> 00:01:44,440
E pesquisa pode obter
fechar com o tempo constante.

40
00:01:44,440 --> 00:01:48,600
That's-- não temos um conjunto de dados
estrutura ainda que pode fazer isso,

41
00:01:48,600 --> 00:01:51,180
e por isso este já soa
como uma coisa muito grande.

42
00:01:51,180 --> 00:01:57,010
Nós realmente mitigados o
desvantagens de cada um por conta própria.

43
00:01:57,010 --> 00:01:59,160
>> Para obter este desempenho
atualizar, porém, temos

44
00:01:59,160 --> 00:02:03,580
Precisamos repensar como podemos adicionar
de dados na estrutura.

45
00:02:03,580 --> 00:02:07,380
Especificamente queremos que o
dados em si para nos dizer

46
00:02:07,380 --> 00:02:09,725
onde ele deve ir na estrutura.

47
00:02:09,725 --> 00:02:12,850
E se nós então precisamos ver se ele está em
a estrutura, se precisamos encontrá-lo,

48
00:02:12,850 --> 00:02:16,610
nós queremos olhar para os dados
de novo e ser capaz de eficazmente,

49
00:02:16,610 --> 00:02:18,910
usando os dados, acessá-lo de forma aleatória.

50
00:02:18,910 --> 00:02:20,700
Basta olhar para o
dados que devem ter

51
00:02:20,700 --> 00:02:25,890
uma idéia de onde exatamente estamos
vai encontrá-lo na tabela de hash.

52
00:02:25,890 --> 00:02:28,770
>> Agora, a desvantagem de um hash
mesa é que eles são realmente

53
00:02:28,770 --> 00:02:31,770
muito ruim em encomendar ou ordenar dados.

54
00:02:31,770 --> 00:02:34,970
E, de fato, se você começar
para usá-los para ordenar ou classificar

55
00:02:34,970 --> 00:02:37,990
dados você perde toda a
vantagens anteriormente

56
00:02:37,990 --> 00:02:40,710
teve em termos de inserção e exclusão.

57
00:02:40,710 --> 00:02:44,060
O tempo torna-se mais perto
theta de n, e nós temos, basicamente,

58
00:02:44,060 --> 00:02:45,530
regrediu em uma lista ligada.

59
00:02:45,530 --> 00:02:48,850
E assim nós só quer usar de hash
tabelas se não se preocupam

60
00:02:48,850 --> 00:02:51,490
se os dados são ordenados.

61
00:02:51,490 --> 00:02:54,290
Para o contexto em que
você vai usá-los em CS50

62
00:02:54,290 --> 00:02:58,900
você provavelmente não me importo
que os dados são classificados.

63
00:02:58,900 --> 00:03:03,170
>> Assim, uma tabela hash é uma combinação
de duas peças distintas

64
00:03:03,170 --> 00:03:04,980
com a qual estamos familiarizados.

65
00:03:04,980 --> 00:03:07,930
A primeira é uma função, que
que costumamos chamar uma função hash.

66
00:03:07,930 --> 00:03:11,760
E essa função hash vai
retornar algum número inteiro não negativo, que

67
00:03:11,760 --> 00:03:14,870
que costumamos chamar de um hashcode, OK?

68
00:03:14,870 --> 00:03:20,230
A segunda peça é uma matriz, que é
capaz de armazenar dados do tipo que

69
00:03:20,230 --> 00:03:22,190
pretende colocar na estrutura de dados.

70
00:03:22,190 --> 00:03:24,310
Nós vamos adiar o
ligada elemento da lista para agora

71
00:03:24,310 --> 00:03:27,810
e só começar com o básico de um
hash de tabela para obter a sua cabeça em torno dele,

72
00:03:27,810 --> 00:03:30,210
e depois vamos talvez explodir
sua mente um pouco quando nós

73
00:03:30,210 --> 00:03:32,920
combinar matrizes e listas de links juntos.

74
00:03:32,920 --> 00:03:35,590
>> A idéia básica embora
é tomarmos alguns dados.

75
00:03:35,590 --> 00:03:37,860
Corremos que os dados através de
a função hash.

76
00:03:37,860 --> 00:03:41,980
E assim os dados são processados
e ele cospe um número, OK?

77
00:03:41,980 --> 00:03:44,890
E, em seguida, com o número
nós apenas armazenar os dados

78
00:03:44,890 --> 00:03:48,930
queremos armazenar na
matriz nesse local.

79
00:03:48,930 --> 00:03:53,990
Assim, por exemplo, temos talvez
esta tabela hash de cordas.

80
00:03:53,990 --> 00:03:57,350
Ele tem 10 elementos em que, de modo
podemos encaixar 10 cordas nele.

81
00:03:57,350 --> 00:03:59,320
>> Vamos dizer que queremos botar John.

82
00:03:59,320 --> 00:04:02,979
Então John como os dados que deseja inserir
para esta tabela de hash em algum lugar.

83
00:04:02,979 --> 00:04:03,770
Onde é que vamos colocá-lo?

84
00:04:03,770 --> 00:04:05,728
Bem tipicamente com um
matriz, até agora, provavelmente

85
00:04:05,728 --> 00:04:07,610
iria colocá-lo em ordem de localização 0.

86
00:04:07,610 --> 00:04:09,960
Mas agora temos essa nova função hash.

87
00:04:09,960 --> 00:04:13,180
>> E vamos dizer que corremos John
através desta função hash

88
00:04:13,180 --> 00:04:15,417
e é cospe 4.

89
00:04:15,417 --> 00:04:17,500
Bem, isso é onde estamos
vai querer colocar John.

90
00:04:17,500 --> 00:04:22,050
Queremos colocar João no local da matriz
4, porque se nós botar John novamente--

91
00:04:22,050 --> 00:04:23,810
digamos que depois nós
deseja pesquisar e ver

92
00:04:23,810 --> 00:04:26,960
John se existe neste haxixe
mesa-- tudo o que precisamos fazer

93
00:04:26,960 --> 00:04:30,310
é executá-lo através do mesmo hash
função, obter o número 4,

94
00:04:30,310 --> 00:04:33,929
e ser capaz de encontrar John
imediatamente na nossa estrutura de dados.

95
00:04:33,929 --> 00:04:34,720
Isso é muito bom.

96
00:04:34,720 --> 00:04:36,928
>> Vamos dizer que nós agora fazer isso
novamente, queremos botar Paul.

97
00:04:36,928 --> 00:04:39,446
Queremos adicionar Paul
para esta tabela hash.

98
00:04:39,446 --> 00:04:42,070
Vamos dizer que, desta vez, corremos
Paul através da função hash,

99
00:04:42,070 --> 00:04:44,600
o hashcode que é gerado é 6.

100
00:04:44,600 --> 00:04:47,340
Bem, agora podemos colocar Paul
no local da matriz 6.

101
00:04:47,340 --> 00:04:50,040
E se nós precisamos de olhar para cima se
Paul está nesta tabela hash,

102
00:04:50,040 --> 00:04:53,900
tudo o que precisamos fazer é executar Paul
através da função hash novamente

103
00:04:53,900 --> 00:04:55,830
e nós estamos indo para chegar em 6º novamente.

104
00:04:55,830 --> 00:04:57,590
>> E então nós apenas olhar
no local da matriz 6.

105
00:04:57,590 --> 00:04:58,910
Paul é lá?

106
00:04:58,910 --> 00:05:00,160
Se assim for, ele está na tabela hash.

107
00:05:00,160 --> 00:05:01,875
Paul não é lá?

108
00:05:01,875 --> 00:05:03,000
Ele não está na tabela hash.

109
00:05:03,000 --> 00:05:05,720
É bastante simples.

110
00:05:05,720 --> 00:05:07,770
>> Agora, como você define uma função hash?

111
00:05:07,770 --> 00:05:11,460
Bem, não há realmente nenhum limite para o
número de possíveis funções hash.

112
00:05:11,460 --> 00:05:14,350
Na verdade há um número de realmente,
realmente bons na internet.

113
00:05:14,350 --> 00:05:17,560
Há um número de realmente,
realmente ruins na internet.

114
00:05:17,560 --> 00:05:21,080
É também muito fácil
para escrever um mau.

115
00:05:21,080 --> 00:05:23,760
>> Então, o que faz um bom
função hash, certo?

116
00:05:23,760 --> 00:05:27,280
Bem uma boa função hash deve
usar somente os dados que estão sendo hash,

117
00:05:27,280 --> 00:05:29,420
e todos os dados a ser hash.

118
00:05:29,420 --> 00:05:32,500
Então, nós não deseja usar anything--
nós não incorporar qualquer coisa

119
00:05:32,500 --> 00:05:35,560
outra coisa que não seja os dados.

120
00:05:35,560 --> 00:05:37,080
E nós queremos usar todos os dados.

121
00:05:37,080 --> 00:05:39,830
Nós não queremos usar apenas um pedaço
disso, nós queremos usar tudo isso.

122
00:05:39,830 --> 00:05:41,710
A função hash deve
também ser determinista.

123
00:05:41,710 --> 00:05:42,550
O que isso significa?

124
00:05:42,550 --> 00:05:46,200
Bem, isso significa que cada vez que
passar a mesma peça exata de dados

125
00:05:46,200 --> 00:05:50,040
para a função hash sempre
obter o mesmo hashcode para fora.

126
00:05:50,040 --> 00:05:52,870
Se eu passar para o John
função hash eu saio 4.

127
00:05:52,870 --> 00:05:56,110
Eu deveria ser capaz de fazer isso 10.000
vezes e eu sempre terá 4.

128
00:05:56,110 --> 00:06:00,810
Assim, não números aleatórios de forma eficaz
pode ser envolvido em nosso hash de tables--

129
00:06:00,810 --> 00:06:02,750
em nossas funções hash.

130
00:06:02,750 --> 00:06:05,750
>> A função hash deve também
uniformemente distribuir dados.

131
00:06:05,750 --> 00:06:09,700
Se cada vez que você executar dados através do
função hash que você obtenha o hashcode 0,

132
00:06:09,700 --> 00:06:11,200
que provavelmente não é tão grande, certo?

133
00:06:11,200 --> 00:06:14,600
Você provavelmente vai querer grande
uma gama de códigos de hash.

134
00:06:14,600 --> 00:06:17,190
Também coisas podem se espalhar
ao longo do quadro.

135
00:06:17,190 --> 00:06:23,210
E também seria ótimo se realmente
dados semelhantes, como John e Jonathan,

136
00:06:23,210 --> 00:06:26,320
talvez foram espalhados para pesar
locais diferentes na tabela de hash.

137
00:06:26,320 --> 00:06:28,750
Isso seria uma boa vantagem.

138
00:06:28,750 --> 00:06:31,250
>> Aqui está um exemplo de uma função hash.

139
00:06:31,250 --> 00:06:33,150
Eu escrevi este mais cedo.

140
00:06:33,150 --> 00:06:35,047
Não é um particularmente
boa função hash

141
00:06:35,047 --> 00:06:37,380
por motivos que não o fazem realmente
Urso que vai para agora.

142
00:06:37,380 --> 00:06:41,040
Mas você vê o que está acontecendo aqui?

143
00:06:41,040 --> 00:06:44,420
Parece que estamos declarando uma variável
chamado de soma e defini-la igual a 0.

144
00:06:44,420 --> 00:06:50,010
E então, aparentemente, eu estou fazendo algo
contanto que strstr [j] não é igual

145
00:06:50,010 --> 00:06:52,490
a barra invertida 0.

146
00:06:52,490 --> 00:06:54,870
O que estou fazendo lá?

147
00:06:54,870 --> 00:06:57,440
>> Este é basicamente apenas um outro
forma de implementar [? strl?]

148
00:06:57,440 --> 00:06:59,773
e detectar quando você tem
chegou ao fim da cadeia.

149
00:06:59,773 --> 00:07:02,480
Então, eu não tenho que, na verdade,
calcular o comprimento da corda,

150
00:07:02,480 --> 00:07:05,640
Eu só estou usando quando eu bati o
barra invertida 0 personagem que eu sei

151
00:07:05,640 --> 00:07:07,185
Cheguei ao fim da cadeia.

152
00:07:07,185 --> 00:07:09,560
E então eu vou continuar
iteração através dessa cadeia,

153
00:07:09,560 --> 00:07:15,310
adicionando strstr [j] a soma, e, em seguida, no
final do dia vai voltar soma mod

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

155
00:07:16,200 --> 00:07:18,700
>> Basicamente tudo isso de hash
função está fazendo é somando

156
00:07:18,700 --> 00:07:23,450
todos os valores de ASCII
minha corda, e então é

157
00:07:23,450 --> 00:07:26,390
voltar algum hashcode
modded por HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
É provavelmente o tamanho
da minha matriz, certo?

159
00:07:29,790 --> 00:07:33,160
Eu não quero estar ficando de hash
códigos se minha matriz é de tamanho 10,

160
00:07:33,160 --> 00:07:35,712
Eu não quero ser como chegar
códigos de hash para fora 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, eu não posso colocar as coisas em
esses locais da matriz,

162
00:07:38,690 --> 00:07:39,790
que seria ilegal.

163
00:07:39,790 --> 00:07:42,130
Eu sofrer uma falha de segmentação.

164
00:07:42,130 --> 00:07:45,230
>> Agora, aqui é outra rápida de lado.

165
00:07:45,230 --> 00:07:48,470
Geralmente você provavelmente não vai
quer escrever suas próprias funções hash.

166
00:07:48,470 --> 00:07:50,997
É realmente um pouco de
uma arte, não uma ciência.

167
00:07:50,997 --> 00:07:52,580
E há muito que vai para eles.

168
00:07:52,580 --> 00:07:55,288
A internet, como eu disse, está cheio
de realmente bons funções hash,

169
00:07:55,288 --> 00:07:58,470
e você deve usar a internet para
encontrar funções hash porque é realmente

170
00:07:58,470 --> 00:08:03,230
apenas uma espécie de um desnecessário
desperdício de tempo para criar o seu próprio.

171
00:08:03,230 --> 00:08:05,490
>> Você pode escrever mais simples
para fins de teste.

172
00:08:05,490 --> 00:08:08,323
Mas quando você realmente está indo para
iniciar hash dados e armazená-lo

173
00:08:08,323 --> 00:08:10,780
em uma tabela hash que você é
provavelmente vai querer

174
00:08:10,780 --> 00:08:14,580
utilizar algumas das funções que foi gerado
para você, que existe na internet.

175
00:08:14,580 --> 00:08:17,240
Se você só não se esqueça
para citar suas fontes.

176
00:08:17,240 --> 00:08:21,740
Não há nenhuma razão para
plagiar qualquer coisa aqui.

177
00:08:21,740 --> 00:08:25,370
>> A comunidade de ciência da computação é
definitivamente crescendo, e realmente valores

178
00:08:25,370 --> 00:08:28,796
open source, e é realmente importante
para citar suas fontes para que as pessoas

179
00:08:28,796 --> 00:08:30,670
pode obter para atribuição
o trabalho que eles estão

180
00:08:30,670 --> 00:08:32,312
fazendo para o benefício da comunidade.

181
00:08:32,312 --> 00:08:34,020
Portanto, seja sempre sure--
e não apenas para haxixe

182
00:08:34,020 --> 00:08:37,270
funções, mas geralmente quando você
usar o código de uma fonte externa,

183
00:08:37,270 --> 00:08:38,299
sempre citar sua fonte.

184
00:08:38,299 --> 00:08:43,500
Dê crédito para a pessoa que fez
algum do trabalho para que você não precisa.

185
00:08:43,500 --> 00:08:46,720
>> OK, então vamos voltar a esta
tabela hash para um segundo.

186
00:08:46,720 --> 00:08:48,780
Este é onde paramos
off depois inserimos

187
00:08:48,780 --> 00:08:53,300
John e Paul para esta tabela hash.

188
00:08:53,300 --> 00:08:55,180
Você vê um problema aqui?

189
00:08:55,180 --> 00:08:58,410
Você pode ver dois.

190
00:08:58,410 --> 00:09:02,240
Mas, em particular, fazer você
veja este possível problema?

191
00:09:02,240 --> 00:09:06,770
>> E se eu botar Ringo, e
Acontece que após o processamento

192
00:09:06,770 --> 00:09:14,000
que os dados através da função hash
Ringo também gerou o hashcode 6.

193
00:09:14,000 --> 00:09:16,810
Eu já tenho os dados no
hashcode-- localização matriz 6.

194
00:09:16,810 --> 00:09:22,000
Por isso, provavelmente vai ser um pouco
de um problema para mim agora, certo?

195
00:09:22,000 --> 00:09:23,060
>> Chamamos isso de uma colisão.

196
00:09:23,060 --> 00:09:26,460
E a colisão ocorre quando dois
pedaços de dados percorrem o mesmo hash

197
00:09:26,460 --> 00:09:29,200
função de produzir o mesmo código hash.

198
00:09:29,200 --> 00:09:32,850
Presumivelmente, ainda queremos obter tanto
pedaços de dados para a tabela hash,

199
00:09:32,850 --> 00:09:36,330
caso contrário, não estaria correndo Ringo
arbitrariamente através da função hash.

200
00:09:36,330 --> 00:09:40,870
Nós presumivelmente deseja obter
Ringo para essa matriz.

201
00:09:40,870 --> 00:09:46,070
>> Como podemos fazê-lo, porém, se ele
e Paul ambos rendimento hashcode 6?

202
00:09:46,070 --> 00:09:49,520
Nós não queremos substituir Paul,
queremos Paul estar lá também.

203
00:09:49,520 --> 00:09:52,790
Por isso, precisamos encontrar uma maneira de obter
elementos para a tabela hash que

204
00:09:52,790 --> 00:09:56,550
ainda preserva a nossa rápida
inserção e rápido olhar para cima.

205
00:09:56,550 --> 00:10:01,350
E uma maneira de lidar com isso é para
fazer algo chamado linear sondagem.

206
00:10:01,350 --> 00:10:04,170
>> Usando este método, se temos um
colisão, bem, o que vamos fazer?

207
00:10:04,170 --> 00:10:08,580
Bem, não podemos colocá-lo no local da matriz
6, ou o que quer hashcode foi gerado,

208
00:10:08,580 --> 00:10:10,820
vamos colocá-lo em hashcode mais 1.

209
00:10:10,820 --> 00:10:13,670
E se isso é deixar de cheia
colocá-lo em hashcode mais 2.

210
00:10:13,670 --> 00:10:17,420
O benefício de este ser se ele é
não exatamente onde nós pensamos que ele é,

211
00:10:17,420 --> 00:10:20,850
e nós temos que começar a procurar,
talvez a gente não tem que ir longe demais.

212
00:10:20,850 --> 00:10:23,900
Talvez a gente não tem que procurar
todos os elementos n da tabela hash.

213
00:10:23,900 --> 00:10:25,790
Talvez a gente tem que procurar
um par deles.

214
00:10:25,790 --> 00:10:30,680
>> E assim nós ainda estamos tendendo para
Nesse caso, média de perto de 1 vs

215
00:10:30,680 --> 00:10:34,280
perto de n, talvez por isso que vou trabalhar.

216
00:10:34,280 --> 00:10:38,010
Então, vamos ver como isso
pode exercitar-se realidade.

217
00:10:38,010 --> 00:10:41,460
E vamos ver se talvez possamos detectar
o problema que possa ocorrer aqui.

218
00:10:41,460 --> 00:10:42,540
>> Vamos dizer que o hash Bart.

219
00:10:42,540 --> 00:10:45,581
Então, agora nós estamos indo para executar um novo conjunto
de cordas através da função hash,

220
00:10:45,581 --> 00:10:48,460
e corremos Bart através do hash
função, temos hashcode 6.

221
00:10:48,460 --> 00:10:52,100
Vamos dar uma olhada, vemos 6 é
vazio, para que possamos colocar Bart lá.

222
00:10:52,100 --> 00:10:55,410
>> Agora vamos botar Lisa e que
também gera hashcode 6.

223
00:10:55,410 --> 00:10:58,330
Bem, agora que estamos usando esta
método que começam em 6 linear sondagem,

224
00:10:58,330 --> 00:10:59,330
vemos que 6 está cheio.

225
00:10:59,330 --> 00:11:00,990
Não podemos colocar em 6 Lisa.

226
00:11:00,990 --> 00:11:02,090
Então, para onde vamos?

227
00:11:02,090 --> 00:11:03,280
Vamos para 7.

228
00:11:03,280 --> 00:11:04,610
7 de vazio, de modo que funciona.

229
00:11:04,610 --> 00:11:06,510
Então, vamos colocar Lisa lá.

230
00:11:06,510 --> 00:11:10,200
>> Agora vamos botar para Homer e temos 7.

231
00:11:10,200 --> 00:11:13,380
OK bem sabemos que 7 do total
agora, por isso não podemos colocar Homer lá.

232
00:11:13,380 --> 00:11:14,850
Então vamos a 8.

233
00:11:14,850 --> 00:11:15,664
É 8 está disponível?

234
00:11:15,664 --> 00:11:18,330
Sim, e 8 de perto de 7, por isso, se
temos de começar a procurar estamos

235
00:11:18,330 --> 00:11:20,020
não vai ter que ir longe demais.

236
00:11:20,020 --> 00:11:22,860
E assim vamos colocar Homer às 8.

237
00:11:22,860 --> 00:11:25,151
>> Agora vamos botar para Maggie e
retorna 3, graças a Deus

238
00:11:25,151 --> 00:11:26,650
somos capazes de simplesmente colocar Maggie lá.

239
00:11:26,650 --> 00:11:29,070
Nós não temos que fazer qualquer
tipo de sondagem para isso.

240
00:11:29,070 --> 00:11:32,000
Agora vamos botar Marge, e
Marge também retorna 6.

241
00:11:32,000 --> 00:11:39,560
>> Bem 6 está cheio, 7 é completa, 8 é cheio,
9, tudo bem graças a Deus, 9 está vazio.

242
00:11:39,560 --> 00:11:41,600
Eu posso colocar Marge, às 9.

243
00:11:41,600 --> 00:11:45,280
Já podemos ver que estamos começando
para ter este problema em que agora estamos

244
00:11:45,280 --> 00:11:48,780
começando a esticar coisas tipo
de longe de seus códigos de hash.

245
00:11:48,780 --> 00:11:52,960
E essa teta de 1, essa média
caso de ser de tempo constante,

246
00:11:52,960 --> 00:11:56,560
está começando a ficar um pouco more--
começando a tendência um pouco mais

247
00:11:56,560 --> 00:11:58,050
no sentido de n teta.

248
00:11:58,050 --> 00:12:01,270
Estamos começando a perder essa
vantagem de tabelas de hash.

249
00:12:01,270 --> 00:12:03,902
>> Este problema que acabamos de ver
é algo chamado de agrupamento.

250
00:12:03,902 --> 00:12:06,360
E o que é realmente ruim sobre
agrupamento é que uma vez que você agora

251
00:12:06,360 --> 00:12:09,606
tem dois elementos que estão lado a
o outro torna-se ainda mais provável,

252
00:12:09,606 --> 00:12:11,480
você tem o dobro da
oportunidade, que você está indo

253
00:12:11,480 --> 00:12:13,516
para ter uma outra colisão
com esse cluster,

254
00:12:13,516 --> 00:12:14,890
eo cluster irá crescer a um.

255
00:12:14,890 --> 00:12:19,640
E você vai continuar crescendo e crescendo
a sua probabilidade de ter uma colisão.

256
00:12:19,640 --> 00:12:24,470
E, eventualmente, ele é tão ruim
como não a classificação dos dados de todo.

257
00:12:24,470 --> 00:12:27,590
>> O outro problema, porém, é que
Ainda assim, até agora e, até este ponto,

258
00:12:27,590 --> 00:12:30,336
temos sido apenas uma espécie de
compreender o que é uma tabela hash,

259
00:12:30,336 --> 00:12:31,960
nós ainda só tem espaço para 10 cordas.

260
00:12:31,960 --> 00:12:37,030
Se queremos continuar para hash
os cidadãos de Springfield,

261
00:12:37,030 --> 00:12:38,790
só podemos obter 10 deles lá.

262
00:12:38,790 --> 00:12:42,619
E se nós tentamos e adicione um 11º ou 12º,
não temos um lugar para colocá-los.

263
00:12:42,619 --> 00:12:45,660
Nós só poderia ser girando em torno de
círculos tentando encontrar um lugar vazio,

264
00:12:45,660 --> 00:12:49,000
e nós talvez ficar preso
em um loop infinito.

265
00:12:49,000 --> 00:12:51,810
>> Portanto, este tipo de empresta ao idéia
de algo chamado de encadeamento.

266
00:12:51,810 --> 00:12:55,790
E este é o lugar onde nós estamos indo para trazer
listas ligadas volta para a imagem.

267
00:12:55,790 --> 00:13:01,300
E se em vez de armazenar apenas
os dados em si na matriz,

268
00:13:01,300 --> 00:13:04,471
cada elemento da matriz poderia
realizar múltiplas peças de dados?

269
00:13:04,471 --> 00:13:05,970
Bem, isso não faz sentido, certo?

270
00:13:05,970 --> 00:13:09,280
Sabemos que uma matriz só pode
hold-- cada elemento de uma matriz

271
00:13:09,280 --> 00:13:12,930
só pode conter uma peça
de dados desse tipo de dados.

272
00:13:12,930 --> 00:13:16,750
>> Mas e se esse tipo de dados
é uma lista ligada, certo?

273
00:13:16,750 --> 00:13:19,830
Então, o que se cada
elemento da matriz foi

274
00:13:19,830 --> 00:13:22,790
um ponteiro para a cabeça de uma lista vinculada?

275
00:13:22,790 --> 00:13:24,680
E então nós poderíamos construir
essas listas ligadas

276
00:13:24,680 --> 00:13:27,120
e cultivá-las arbitrariamente,
porque listas ligadas permitir

277
00:13:27,120 --> 00:13:32,090
nos a crescer e encolher muito mais
flexibilidade do que uma matriz faz.

278
00:13:32,090 --> 00:13:34,210
Então, o que se usam agora,
aproveitamos isso, certo?

279
00:13:34,210 --> 00:13:37,760
Começamos a crescer estas cadeias
fora desses locais matriz.

280
00:13:37,760 --> 00:13:40,740
>> Agora podemos encaixar um infinito
quantidade de dados, ou não é infinito,

281
00:13:40,740 --> 00:13:44,170
uma quantidade arbitrária de
dados, em nossa tabela hash

282
00:13:44,170 --> 00:13:47,760
sem nunca correr em
o problema da colisão.

283
00:13:47,760 --> 00:13:50,740
Nós também eliminamos
agrupamento, fazendo isso.

284
00:13:50,740 --> 00:13:54,380
E bem sabemos que quando nós inserimos
em uma lista ligada, se você se lembra

285
00:13:54,380 --> 00:13:57,779
do nosso vídeo sobre listas ligadas, isoladamente
listas ligadas e listas duplamente vinculadas,

286
00:13:57,779 --> 00:13:59,070
é uma operação de tempo constante.

287
00:13:59,070 --> 00:14:00,710
Nós estamos apenas adicionando para a frente.

288
00:14:00,710 --> 00:14:04,400
>> E para olhar para cima, bem sabemos
que olhar para cima em uma lista encadeada

289
00:14:04,400 --> 00:14:05,785
pode ser um problema, certo?

290
00:14:05,785 --> 00:14:07,910
Temos que pesquisar
-lo do começo ao fim.

291
00:14:07,910 --> 00:14:10,460
Não há nenhuma aleatório
acesso em uma lista vinculada.

292
00:14:10,460 --> 00:14:15,610
Mas se, em vez de ter um ligado
lista onde uma pesquisa seria O de n,

293
00:14:15,610 --> 00:14:19,590
agora temos 10 listas ligadas,
ou 1.000 listas ligadas,

294
00:14:19,590 --> 00:14:24,120
agora é O de n dividido por 10,
ou O de n dividido por 1,000.

295
00:14:24,120 --> 00:14:26,940
>> E enquanto nós estávamos falando
teoricamente sobre a complexidade

296
00:14:26,940 --> 00:14:30,061
desconsiderarmos constantes, no real
mundo estas coisas realmente importa,

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

298
00:14:30,560 --> 00:14:33,080
Nós, na verdade, vai notar
que isto acontece

299
00:14:33,080 --> 00:14:36,610
para executar 10 vezes mais rápido,
ou 1.000 vezes mais rápida,

300
00:14:36,610 --> 00:14:41,570
porque nós estamos distribuindo uma longa
cadeia em toda 1.000 cadeias menores.

301
00:14:41,570 --> 00:14:45,090
E assim cada vez que tem que procurar
através de uma daquelas correntes que nós podemos

302
00:14:45,090 --> 00:14:50,290
ignorar as 999 cadeias de nós não nos importamos
aproximadamente, e basta procurar aquele.

303
00:14:50,290 --> 00:14:53,220
>> Que é, em média,
ser 1000 vezes mais curto.

304
00:14:53,220 --> 00:14:56,460
E assim nós ainda são uma espécie de
tendendo para este caso médio

305
00:14:56,460 --> 00:15:01,610
de ser de tempo constante, mas
só porque estamos alavancando

306
00:15:01,610 --> 00:15:03,730
dividindo-se por um enorme fator constante.

307
00:15:03,730 --> 00:15:05,804
Vamos ver como isso pode
realmente olhar embora.

308
00:15:05,804 --> 00:15:08,720
Portanto, esta foi a tabela hash tivemos
antes que declarou uma tabela hash que

309
00:15:08,720 --> 00:15:10,270
era capaz de armazenar 10 cordas.

310
00:15:10,270 --> 00:15:11,728
Nós não vamos mais fazer isso.

311
00:15:11,728 --> 00:15:13,880
Nós já sabemos o
limitações desse método.

312
00:15:13,880 --> 00:15:20,170
Agora a nossa tabela de hash vai ser
uma matriz de 10 nós, ponteiros

313
00:15:20,170 --> 00:15:22,120
aos chefes de listas ligadas.

314
00:15:22,120 --> 00:15:23,830
>> E agora é nulo.

315
00:15:23,830 --> 00:15:26,170
Cada um desses 10 ponteiros é nulo.

316
00:15:26,170 --> 00:15:29,870
Não há nada em nossa
hash de tabela agora.

317
00:15:29,870 --> 00:15:32,690
>> Agora vamos começar a colocar alguns
coisas para esta tabela hash.

318
00:15:32,690 --> 00:15:35,440
E vamos ver como esse método é
vai nos beneficiar um pouco.

319
00:15:35,440 --> 00:15:36,760
Vamos agora botar Joey.

320
00:15:36,760 --> 00:15:40,210
Vamos irá executar a seqüência de Joey através
uma função hash e voltamos 6.

321
00:15:40,210 --> 00:15:41,200
Bem, o que fazemos agora?

322
00:15:41,200 --> 00:15:44,090
>> Bem, agora trabalhando com listas ligadas,
nós não estamos trabalhando com arrays.

323
00:15:44,090 --> 00:15:45,881
E quando estamos trabalhando
com listas ligadas nós

324
00:15:45,881 --> 00:15:49,790
sabemos que precisamos para começar dinamicamente
alocação de espaço e construção de cadeias.

325
00:15:49,790 --> 00:15:54,020
Isso é uma espécie de how-- aqueles são o núcleo
elementos de construção de uma lista ligada.

326
00:15:54,020 --> 00:15:57,670
Então, vamos dinamicamente
alocar espaço para Joey,

327
00:15:57,670 --> 00:16:00,390
e, em seguida, vamos adicioná-lo à cadeia.

328
00:16:00,390 --> 00:16:03,170
>> Então agora veja o que temos feito.

329
00:16:03,170 --> 00:16:06,440
Quando o hash Joey temos o hashcode 6.

330
00:16:06,440 --> 00:16:11,790
Agora o ponteiro no local da matriz 6
aponta para a cabeça de uma lista ligada,

331
00:16:11,790 --> 00:16:14,900
e agora é a única
elemento de uma lista ligada.

332
00:16:14,900 --> 00:16:18,350
E em que o nó
lista ligada é Joey.

333
00:16:18,350 --> 00:16:22,300
>> Então, se nós precisamos de olhar para cima Joey
depois, nós apenas o hash Joey de novo,

334
00:16:22,300 --> 00:16:26,300
temos 6 novamente porque a nossa
função hash é determinista.

335
00:16:26,300 --> 00:16:30,400
E então começamos na cabeça
da lista ligada apontou

336
00:16:30,400 --> 00:16:33,360
a matriz por localização
6, e nós podemos fazer uma iteração

337
00:16:33,360 --> 00:16:35,650
do outro lado que tentar encontrar Joey.

338
00:16:35,650 --> 00:16:37,780
E se nós construirmos nosso
Tabela de Hash de forma eficaz,

339
00:16:37,780 --> 00:16:41,790
e nossa função hash de forma eficaz
para distribuir dados bem,

340
00:16:41,790 --> 00:16:45,770
em média, cada um dos aqueles ligados
listas em cada local da matriz

341
00:16:45,770 --> 00:16:50,110
será de 1/10 do tamanho de se
só tinha ele como um único grande

342
00:16:50,110 --> 00:16:51,650
lista ligada com tudo na mesma.

343
00:16:51,650 --> 00:16:55,670
>> Se distribuir esse enorme ligado
lista em 10 listas ligadas

344
00:16:55,670 --> 00:16:57,760
cada lista será de 1/10 do tamanho.

345
00:16:57,760 --> 00:17:01,432
E, portanto, 10 vezes mais rápido
pesquisar.

346
00:17:01,432 --> 00:17:02,390
Então vamos fazer isso de novo.

347
00:17:02,390 --> 00:17:04,290
Vamos agora botar Ross.

348
00:17:04,290 --> 00:17:07,540
>> E digamos que Ross, quando fazemos isso
o código de hash voltarmos é 2.

349
00:17:07,540 --> 00:17:10,630
Bem, agora vamos alocar dinamicamente um
novo nó, colocamos Ross nesse nó,

350
00:17:10,630 --> 00:17:14,900
e dizemos agora local da matriz
2, em vez de apontar para null,

351
00:17:14,900 --> 00:17:18,579
aponta para a cabeça de um ligado
lista cujo único nó é Ross.

352
00:17:18,579 --> 00:17:22,660
E nós podemos fazer isso mais uma vez, nós
pode botar para Rachel e obter hashcode 4.

353
00:17:22,660 --> 00:17:25,490
malloc um novo nó, coloque em Rachel
o nó, e dizer um local matriz

354
00:17:25,490 --> 00:17:27,839
4 agora aponta para a cabeça
de uma lista ligada cujo

355
00:17:27,839 --> 00:17:31,420
único elemento passa a ser Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK, mas o que acontece se
temos uma colisão?

357
00:17:33,470 --> 00:17:38,560
Vamos ver como lidamos com colisões
utilizando o método de encadeamento separado.

358
00:17:38,560 --> 00:17:39,800
Vamos botar Phoebe.

359
00:17:39,800 --> 00:17:41,094
Ficamos com a hashcode 6.

360
00:17:41,094 --> 00:17:44,010
Em nosso exemplo anterior estávamos apenas
armazenar as cordas na matriz.

361
00:17:44,010 --> 00:17:45,980
Este foi um problema.

362
00:17:45,980 --> 00:17:48,444
>> Nós não deve sobrescreve
Joey, e nós já

363
00:17:48,444 --> 00:17:51,110
visto que podemos obter algum agrupamento
problemas se nós tentamos e passo

364
00:17:51,110 --> 00:17:52,202
e através de sonda.

365
00:17:52,202 --> 00:17:54,660
Mas e se nós apenas uma espécie de
tratar isso da mesma maneira, certo?

366
00:17:54,660 --> 00:17:57,440
É como adicionar um elemento
para a cabeça de uma lista ligada.

367
00:17:57,440 --> 00:18:00,220
Vamos espaço apenas malloc para Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Vamos dizer próximos ponteiro pontos de Phoebe
para o antigo chefe da lista ligada,

369
00:18:04,764 --> 00:18:07,180
e, em seguida, apenas 6 aponta para a
novo chefe da lista ligada.

370
00:18:07,180 --> 00:18:10,150
E agora olha, nós mudamos Phoebe in.

371
00:18:10,150 --> 00:18:14,210
Agora podemos armazenar dois
elementos com hashcode 6,

372
00:18:14,210 --> 00:18:17,170
e não temos quaisquer problemas.

373
00:18:17,170 --> 00:18:20,147
>> Isso é muito bonito tudo
existe ao encadeamento.

374
00:18:20,147 --> 00:18:21,980
E encadeamento é definitivamente
o método que é

375
00:18:21,980 --> 00:18:27,390
vai ser mais eficaz para você se
você está armazenando dados em uma tabela hash.

376
00:18:27,390 --> 00:18:30,890
Mas esta combinação de
matrizes e listas ligadas

377
00:18:30,890 --> 00:18:36,080
em conjunto para formar uma tabela hash realmente
melhora drasticamente a sua capacidade

378
00:18:36,080 --> 00:18:40,550
para armazenar grandes quantidades de dados, e
muito rapidamente e eficientemente procurar

379
00:18:40,550 --> 00:18:41,630
por meio de que os dados.

380
00:18:41,630 --> 00:18:44,150
>> Ainda há mais uma
estrutura de dados lá fora

381
00:18:44,150 --> 00:18:48,700
que pode até ser um pouco
melhor em termos de garantia

382
00:18:48,700 --> 00:18:51,920
que a nossa inserção, exclusão e
olhar para cima os tempos são ainda mais rápido.

383
00:18:51,920 --> 00:18:55,630
E nós vamos ver que em um vídeo no tentativas.

384
00:18:55,630 --> 00:18:58,930
Eu sou Doug Lloyd, este é CS50.

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