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

2
00:00:00,500 --> 00:00:01,900
[Jouer de la musique]

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: A présent, vous
en savoir beaucoup sur les tableaux,

5
00:00:09,150 --> 00:00:11,610
et vous savez beaucoup de choses sur les listes chaînées.

6
00:00:11,610 --> 00:00:13,650
Et nous avons de discuter de la
avantages et les inconvénients, nous avons

7
00:00:13,650 --> 00:00:16,620
discuté liée listes
peut devenir plus grand et plus petit,

8
00:00:16,620 --> 00:00:18,630
mais ils prennent plus de taille.

9
00:00:18,630 --> 00:00:22,359
Les tableaux sont beaucoup plus faciles à
utilisent, mais ils sont restrictive dans la mesure

10
00:00:22,359 --> 00:00:24,900
que nous avons pour définir la taille de
le tableau au début

11
00:00:24,900 --> 00:00:26,910
puis nous sommes coincés avec elle.

12
00:00:26,910 --> 00:00:30,470
>> Mais voilà, nous avons à peu près
épuisé tous nos sujets

13
00:00:30,470 --> 00:00:33,040
à propos des listes chaînées et les tableaux.

14
00:00:33,040 --> 00:00:34,950
Ou avons-nous?

15
00:00:34,950 --> 00:00:37,720
Peut-être que nous pouvons faire quelque chose
encore plus créatif.

16
00:00:37,720 --> 00:00:40,950
Et ce genre de Prête
l'idée d'une table de hachage.

17
00:00:40,950 --> 00:00:46,680
>> Ainsi, dans une table de hachage, nous allons essayer
combiner un tableau avec une liste chaînée.

18
00:00:46,680 --> 00:00:49,520
Nous allons prendre les avantages
du tableau, comme l'accès aléatoire,

19
00:00:49,520 --> 00:00:53,510
être en mesure de simplement aller à tableau
élément 4 ou un tableau élément 8

20
00:00:53,510 --> 00:00:55,560
sans avoir à parcourir à travers.

21
00:00:55,560 --> 00:00:57,260
Voilà assez rapide, non?

22
00:00:57,260 --> 00:01:00,714
>> Mais nous voulons aussi avoir nos données
la structure soit en mesure de croître et de se rétrécir.

23
00:01:00,714 --> 00:01:02,630
Nous ne devons pas, nous ne faisons pas
vouloir être limité.

24
00:01:02,630 --> 00:01:04,588
Et nous voulons être en mesure
pour ajouter et supprimer des choses

25
00:01:04,588 --> 00:01:08,430
très facilement, ce qui si vous vous souvenez,
est très complexe avec un tableau.

26
00:01:08,430 --> 00:01:11,650
Et nous pouvons appeler cela
chose de nouveau une table de hachage.

27
00:01:11,650 --> 00:01:15,190
>> Et si elles sont appliquées correctement,
nous sorte de prendre

28
00:01:15,190 --> 00:01:18,150
les avantages des deux données
structures que vous avez déjà vu,

29
00:01:18,150 --> 00:01:19,880
les tableaux et les listes chaînées.

30
00:01:19,880 --> 00:01:23,070
L'insertion peut commencer à
tendre vers thêta de 1.

31
00:01:23,070 --> 00:01:26,207
Theta nous avons pas vraiment discuté,
mais thêta est seulement le cas en moyenne,

32
00:01:26,207 --> 00:01:27,540
ce qui va réellement se passer.

33
00:01:27,540 --> 00:01:29,680
Vous n'êtes pas toujours aller à
avoir le pire des cas,

34
00:01:29,680 --> 00:01:32,555
et vous n'êtes pas toujours avoir
le meilleur des cas, alors quel est

35
00:01:32,555 --> 00:01:33,900
le scénario moyen?

36
00:01:33,900 --> 00:01:36,500
>> Eh bien une insertion moyenne
dans une table de hachage

37
00:01:36,500 --> 00:01:39,370
peut commencer à se rapprocher de la constante de temps.

38
00:01:39,370 --> 00:01:41,570
Et la suppression peut obtenir
fermer à temps constant.

39
00:01:41,570 --> 00:01:44,440
Et recherche peut obtenir
fermer à temps constant.

40
00:01:44,440 --> 00:01:48,600
That's-- nous ne disposons pas de données d'un
la structure encore que ne peut le faire,

41
00:01:48,600 --> 00:01:51,180
et si cela sonne déjà
comme une jolie grande chose.

42
00:01:51,180 --> 00:01:57,010
Nous avons vraiment atténué les
les inconvénients de chacun sur son propre.

43
00:01:57,010 --> 00:01:59,160
>> Pour obtenir cette performance
mise à niveau si, nous

44
00:01:59,160 --> 00:02:03,580
nécessité de repenser la façon dont nous ajoutons
des données dans la structure.

45
00:02:03,580 --> 00:02:07,380
Plus précisément, nous voulons que le
données lui-même pour nous dire

46
00:02:07,380 --> 00:02:09,725
où il doit aller dans la structure.

47
00:02:09,725 --> 00:02:12,850
Et si nous devons ensuite pour voir si elle est dans
la structure, si nous avons besoin de le trouver,

48
00:02:12,850 --> 00:02:16,610
nous voulons examiner les données
nouveau et pouvoir efficacement,

49
00:02:16,610 --> 00:02:18,910
en utilisant les données, accéder hasard il.

50
00:02:18,910 --> 00:02:20,700
Juste en regardant la
nous devrions avoir des données

51
00:02:20,700 --> 00:02:25,890
une idée d'où nous sommes exactement
va trouver dans la table de hachage.

52
00:02:25,890 --> 00:02:28,770
>> Maintenant, l'inconvénient d'un hachage
table est qu'ils sont vraiment

53
00:02:28,770 --> 00:02:31,770
assez mauvais à ordonner ou trier les données.

54
00:02:31,770 --> 00:02:34,970
Et en fait, si vous commencez
de les utiliser pour commander ou trier

55
00:02:34,970 --> 00:02:37,990
des données vous perdez la totalité de la
avantages vous avez déjà

56
00:02:37,990 --> 00:02:40,710
eu en termes d'insertion et de suppression.

57
00:02:40,710 --> 00:02:44,060
Il se rapproche de
thêta de n, et nous avons essentiellement

58
00:02:44,060 --> 00:02:45,530
régressé dans une liste chaînée.

59
00:02:45,530 --> 00:02:48,850
Et si nous voulons seulement utiliser hachage
tableaux si nous ne nous soucions pas

60
00:02:48,850 --> 00:02:51,490
si les données sont triées.

61
00:02:51,490 --> 00:02:54,290
Pour le contexte dans lequel
vous les utilisez dans CS50

62
00:02:54,290 --> 00:02:58,900
vous avez probablement ne vous souciez pas
que les données sont triées.

63
00:02:58,900 --> 00:03:03,170
>> Donc, une table de hachage est une combinaison
de deux pièces distinctes

64
00:03:03,170 --> 00:03:04,980
avec lesquels nous sommes familiers.

65
00:03:04,980 --> 00:03:07,930
La première est une fonction, qui
nous appelons habituellement une fonction de hachage.

66
00:03:07,930 --> 00:03:11,760
Et cette fonction de hachage va
retourner un entier non-négatif, ce qui

67
00:03:11,760 --> 00:03:14,870
nous appelons habituellement un hashcode, OK?

68
00:03:14,870 --> 00:03:20,230
La deuxième pièce est un tableau, qui est
Capable de stocker des données du type nous

69
00:03:20,230 --> 00:03:22,190
vouloir placer dans la structure de données.

70
00:03:22,190 --> 00:03:24,310
Nous allons tenir au loin sur la
liée élément de la liste pour l'instant

71
00:03:24,310 --> 00:03:27,810
et il suffit de commencer avec les bases d'un
la table de hachage pour obtenir votre tête autour de lui,

72
00:03:27,810 --> 00:03:30,210
et puis nous allons peut-être sauter
votre esprit un peu quand nous

73
00:03:30,210 --> 00:03:32,920
combiner les tableaux et les listes de liens ensemble.

74
00:03:32,920 --> 00:03:35,590
>> L'idée de base si
est que nous prenons certaines données.

75
00:03:35,590 --> 00:03:37,860
Nous courons que les données par le biais
la fonction de hachage.

76
00:03:37,860 --> 00:03:41,980
Et si les données sont traitées
et il crache un certain nombre, OK?

77
00:03:41,980 --> 00:03:44,890
Et puis avec ce numéro
nous stockons seulement les données

78
00:03:44,890 --> 00:03:48,930
on veut stocker dans la
réseau à cet endroit.

79
00:03:48,930 --> 00:03:53,990
Ainsi, par exemple, nous avons peut-être
cette table de hachage de chaînes.

80
00:03:53,990 --> 00:03:57,350
Il a obtenu 10 éléments en elle, donc
nous pouvons tenir 10 chaînes en elle.

81
00:03:57,350 --> 00:03:59,320
>> Disons que nous voulons pour hacher John.

82
00:03:59,320 --> 00:04:02,979
Alors John que les données que nous voulons insérer
dans cette table de hachage quelque part.

83
00:04:02,979 --> 00:04:03,770
Où allons-nous dire?

84
00:04:03,770 --> 00:04:05,728
Bien typiquement avec un
tableau jusqu'ici nous avons probablement

85
00:04:05,728 --> 00:04:07,610
le mettrait en position de tableau 0.

86
00:04:07,610 --> 00:04:09,960
Mais maintenant nous avons cette nouvelle fonction de hachage.

87
00:04:09,960 --> 00:04:13,180
>> Et disons que nous courons John
grâce à cette fonction de hachage

88
00:04:13,180 --> 00:04:15,417
et ça crache 4.

89
00:04:15,417 --> 00:04:17,500
Eh bien voilà où nous en sommes
allez vouloir mettre John.

90
00:04:17,500 --> 00:04:22,050
Nous voulons mettre John dans un endroit du tableau
4, parce que si nous hachage John again--

91
00:04:22,050 --> 00:04:23,810
disons que plus tard nous
vouloir rechercher et de voir

92
00:04:23,810 --> 00:04:26,960
si John existe dans ce hachage
table-- tout ce que nous devons faire

93
00:04:26,960 --> 00:04:30,310
est le lancer à travers le même hachage
fonction, obtenir le numéro à 4,

94
00:04:30,310 --> 00:04:33,929
et être en mesure de trouver John
immédiatement dans notre structure de données.

95
00:04:33,929 --> 00:04:34,720
Cela est assez bon.

96
00:04:34,720 --> 00:04:36,928
>> Disons que nous faisons maintenant ce
encore une fois, nous voulons hachage Paul.

97
00:04:36,928 --> 00:04:39,446
Nous voulons ajouter Paul
dans cette table de hachage.

98
00:04:39,446 --> 00:04:42,070
Disons que cette fois nous courons
Paul à travers la fonction de hachage,

99
00:04:42,070 --> 00:04:44,600
le code de hachage qui est généré est 6.

100
00:04:44,600 --> 00:04:47,340
Eh bien maintenant, nous pouvons mettre Paul
à l'emplacement de tableau 6.

101
00:04:47,340 --> 00:04:50,040
Et si nous avons besoin de regarder si
Paul est dans cette table de hachage,

102
00:04:50,040 --> 00:04:53,900
tout ce que nous devons faire est de lancer Paul
grâce à la fonction de hachage à nouveau

103
00:04:53,900 --> 00:04:55,830
et nous allons obtenir 6 à nouveau.

104
00:04:55,830 --> 00:04:57,590
>> Et ensuite nous regardons
à l'emplacement du tableau 6.

105
00:04:57,590 --> 00:04:58,910
Paul est là?

106
00:04:58,910 --> 00:05:00,160
Si oui, il est dans la table de hachage.

107
00:05:00,160 --> 00:05:01,875
Paul est pas là?

108
00:05:01,875 --> 00:05:03,000
Il est pas dans la table de hachage.

109
00:05:03,000 --> 00:05:05,720
Il est assez simple.

110
00:05:05,720 --> 00:05:07,770
>> Maintenant, comment définissez-vous une fonction de hachage?

111
00:05:07,770 --> 00:05:11,460
Eh bien il n'y a vraiment aucune limite à la
nombre de fonctions possibles de hachage.

112
00:05:11,460 --> 00:05:14,350
En fait, il ya un certain nombre de vraiment,
vraiment bons sur Internet.

113
00:05:14,350 --> 00:05:17,560
Il ya un certain nombre de vraiment,
vraiment mauvais sur Internet.

114
00:05:17,560 --> 00:05:21,080
Il est également assez facile
pour écrire une mauvaise.

115
00:05:21,080 --> 00:05:23,760
>> Donc, ce qui fait un bon
fonction de hachage, non?

116
00:05:23,760 --> 00:05:27,280
Eh bien une bonne fonction de hachage devrait
utilisent uniquement les données hachés,

117
00:05:27,280 --> 00:05:29,420
et l'ensemble des données étant hachée.

118
00:05:29,420 --> 00:05:32,500
Donc, nous ne voulons pas utiliser anything--
nous ne incorporons rien

119
00:05:32,500 --> 00:05:35,560
d'autre part les données.

120
00:05:35,560 --> 00:05:37,080
Et nous voulons utiliser toutes les données.

121
00:05:37,080 --> 00:05:39,830
Nous ne voulons pas simplement utiliser un morceau
de celui-ci, nous voulons utiliser tout cela.

122
00:05:39,830 --> 00:05:41,710
Une fonction de hachage devrait
être aussi déterministe.

123
00:05:41,710 --> 00:05:42,550
Qu'est-ce que cela veut dire?

124
00:05:42,550 --> 00:05:46,200
Eh bien, cela signifie que chaque fois que nous
passer le même morceau exacte des données

125
00:05:46,200 --> 00:05:50,040
dans la fonction de hachage nous avons toujours
obtenir le même code de hachage sur.

126
00:05:50,040 --> 00:05:52,870
Si je passe dans le John
fonction de hachage je sors 4.

127
00:05:52,870 --> 00:05:56,110
Je devrais être capable de le faire 10.000
fois et je aurez toujours 4.

128
00:05:56,110 --> 00:06:00,810
Donc pas de nombres aléatoires efficacement
peuvent être impliqués dans notre hachage tables--

129
00:06:00,810 --> 00:06:02,750
dans nos fonctions de hachage.

130
00:06:02,750 --> 00:06:05,750
>> Une fonction de hachage devrait également
distribuer uniformément données.

131
00:06:05,750 --> 00:06:09,700
Si chaque fois que vous exécutez données à travers le
fonction de hachage vous obtenez le hashcode 0,

132
00:06:09,700 --> 00:06:11,200
qui est sans doute pas si grand, non?

133
00:06:11,200 --> 00:06:14,600
Vous voulez sans doute à la grande
une gamme de codes de hachage.

134
00:06:14,600 --> 00:06:17,190
Les choses peuvent aussi être réparties
tout au long de la table.

135
00:06:17,190 --> 00:06:23,210
Et aussi que ce serait formidable si vraiment
des données similaires, comme John et Jonathan,

136
00:06:23,210 --> 00:06:26,320
peut-être ont été répartis à peser
différents endroits dans la table de hachage.

137
00:06:26,320 --> 00:06:28,750
Ce serait un grand avantage.

138
00:06:28,750 --> 00:06:31,250
>> Voici un exemple d'une fonction de hachage.

139
00:06:31,250 --> 00:06:33,150
Je l'ai écrit plus tôt celui-ci.

140
00:06:33,150 --> 00:06:35,047
Il est pas particulièrement
bonne fonction de hachage

141
00:06:35,047 --> 00:06:37,380
pour des raisons qui ne sont pas vraiment
supporter entrer dans ce moment.

142
00:06:37,380 --> 00:06:41,040
Mais voyez-vous ce qui se passe ici?

143
00:06:41,040 --> 00:06:44,420
Il semble que nous allons déclarer une variable
appelé somme et sa mise en égal à 0.

144
00:06:44,420 --> 00:06:50,010
Et puis, apparemment, je fais quelque chose
tant strstr [j] est pas égal

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

146
00:06:52,490 --> 00:06:54,870
Qu'est-ce que je fais là?

147
00:06:54,870 --> 00:06:57,440
>> Ceci est fondamentalement juste un autre
façon de mettre en œuvre [? strl?]

148
00:06:57,440 --> 00:06:59,773
et détecter le moment où vous avez
atteint la fin de la chaîne.

149
00:06:59,773 --> 00:07:02,480
Donc, je ne dois pas fait
calculer la longueur de la chaîne,

150
00:07:02,480 --> 00:07:05,640
Je suis juste en utilisant quand je frappe la
0 caractère barre oblique inverse je sais

151
00:07:05,640 --> 00:07:07,185
Je suis arrivé à la fin de la chaîne.

152
00:07:07,185 --> 00:07:09,560
Et puis je vais continuer à
itérer cette chaîne,

153
00:07:09,560 --> 00:07:15,310
ajoutant strstr [j] pour résumer, puis à la
fin de la journée va revenir somme mod

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

155
00:07:16,200 --> 00:07:18,700
>> Fondamentalement tout ce hachage
fonction est en train de faire est d'ajouter jusqu'à

156
00:07:18,700 --> 00:07:23,450
toutes les valeurs ASCII des
ma chaîne, puis il est

157
00:07:23,450 --> 00:07:26,390
retourner un hashcode
modded par HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Il est probablement la taille
de mon tableau, non?

159
00:07:29,790 --> 00:07:33,160
Je ne veux pas être obtenir hachage
codes si mon tableau est de taille 10,

160
00:07:33,160 --> 00:07:35,712
Je ne veux pas être obtenir
codes de hachage sur 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, je ne peux pas mettre les choses en
les emplacements de la matrice,

162
00:07:38,690 --> 00:07:39,790
ce serait illégal.

163
00:07:39,790 --> 00:07:42,130
Je souffre d'une erreur de segmentation.

164
00:07:42,130 --> 00:07:45,230
>> Maintenant, voici une autre petite parenthèse.

165
00:07:45,230 --> 00:07:48,470
En général, vous allez probablement pas à
envie d'écrire vos propres fonctions de hachage.

166
00:07:48,470 --> 00:07:50,997
Il est en fait un peu de
un art, pas une science.

167
00:07:50,997 --> 00:07:52,580
Et il ya beaucoup qui va en eux.

168
00:07:52,580 --> 00:07:55,288
L'Internet, comme je l'ai dit, est pleine
des fonctions de hachage très bons,

169
00:07:55,288 --> 00:07:58,470
et vous devriez utiliser l'Internet pour
trouver des fonctions de hachage, car il est vraiment

170
00:07:58,470 --> 00:08:03,230
juste une sorte d'inutiles
perte de temps pour créer votre propre.

171
00:08:03,230 --> 00:08:05,490
>> Vous pouvez écrire les plus simples
à des fins de test.

172
00:08:05,490 --> 00:08:08,323
Mais quand vous avez réellement allez
commencer hachage des données et le stockage

173
00:08:08,323 --> 00:08:10,780
dans une table de hachage vous êtes
probablement vouloir

174
00:08:10,780 --> 00:08:14,580
à utiliser une fonction qui a été généré
pour vous, ce qui existe sur l'internet.

175
00:08:14,580 --> 00:08:17,240
Si vous ne juste être sûr
de citer vos sources.

176
00:08:17,240 --> 00:08:21,740
Il n'y a pas de raison de
plagier quelque chose ici.

177
00:08:21,740 --> 00:08:25,370
>> La communauté de la science informatique est
certainement de plus en plus, et vraiment valeurs

178
00:08:25,370 --> 00:08:28,796
open source, et il est vraiment important
de citer vos sources afin que les gens

179
00:08:28,796 --> 00:08:30,670
peut obtenir l'attribution de
le travail qu'ils sont

180
00:08:30,670 --> 00:08:32,312
faire au bénéfice de la communauté.

181
00:08:32,312 --> 00:08:34,020
Il faut donc toujours être sure--
et pas seulement pour hachage

182
00:08:34,020 --> 00:08:37,270
fonctions, mais généralement lorsque vous
utiliser le code d'une source extérieure,

183
00:08:37,270 --> 00:08:38,299
Toujours citer votre source.

184
00:08:38,299 --> 00:08:43,500
Vous citez le nom de la personne qui a fait
une partie du travail de sorte que vous ne devez.

185
00:08:43,500 --> 00:08:46,720
>> OK donc, revenons sur ce
Table hachage pour une seconde.

186
00:08:46,720 --> 00:08:48,780
Ceci est où nous avons laissé
éteint après nous avons inséré

187
00:08:48,780 --> 00:08:53,300
John et Paul dans cette table de hachage.

188
00:08:53,300 --> 00:08:55,180
Voyez-vous un problème?

189
00:08:55,180 --> 00:08:58,410
Vous pouvez voir deux.

190
00:08:58,410 --> 00:09:02,240
Mais en particulier, avez-vous
voir ce problème possible?

191
00:09:02,240 --> 00:09:06,770
>> Que faire si je hachage Ringo, et il
qui se révèle après traitement

192
00:09:06,770 --> 00:09:14,000
que les données grâce à la fonction de hachage
Ringo a également généré la hashcode 6.

193
00:09:14,000 --> 00:09:16,810
Je ai déjà données au
Lieu de tableau hashcode-- 6.

194
00:09:16,810 --> 00:09:22,000
Donc, il va probablement être un peu
d'un problème pour moi maintenant, à droite?

195
00:09:22,000 --> 00:09:23,060
>> Nous appelons cela une collision.

196
00:09:23,060 --> 00:09:26,460
Et la collision se produit lorsque deux
morceaux de données passent par le même hachage

197
00:09:26,460 --> 00:09:29,200
Fonction donné le même code de hachage.

198
00:09:29,200 --> 00:09:32,850
On peut supposer que nous voulons toujours obtenir à la fois
morceaux de données dans la table de hachage,

199
00:09:32,850 --> 00:09:36,330
sinon nous ne serions pas en cours d'exécution Ringo
arbitrairement par la fonction de hachage.

200
00:09:36,330 --> 00:09:40,870
Nous voulons sans doute pour obtenir
Ringo dans ce tableau.

201
00:09:40,870 --> 00:09:46,070
>> Comment le faisons-nous si, si, il
et Paul à la fois le rendement hashcode 6?

202
00:09:46,070 --> 00:09:49,520
Nous ne voulons pas remplacer Paul,
Paul nous voulons être là aussi.

203
00:09:49,520 --> 00:09:52,790
Donc, nous devons trouver un moyen d'obtenir
éléments dans la table de hachage

204
00:09:52,790 --> 00:09:56,550
conserve encore notre rapide
insertion et de recherche rapide.

205
00:09:56,550 --> 00:10:01,350
Et une façon de traiter avec elle est de
faire quelque chose appelé sondage linéaire.

206
00:10:01,350 --> 00:10:04,170
>> En utilisant cette méthode, si nous avons un
collision, ainsi, que faisons-nous?

207
00:10:04,170 --> 00:10:08,580
Eh bien, nous ne pouvons pas le mettre dans un endroit du tableau
6, ou quel que soit hashcode a été générée,

208
00:10:08,580 --> 00:10:10,820
nous allons le mettre à hashcode plus 1.

209
00:10:10,820 --> 00:10:13,670
Et si cela let complet de
le mettre dans hashcode plus 2.

210
00:10:13,670 --> 00:10:17,420
L'avantage de cet être si il est
pas exactement où nous pensons qu'il est,

211
00:10:17,420 --> 00:10:20,850
et nous devons commencer à chercher,
peut-être nous ne devons pas aller trop loin.

212
00:10:20,850 --> 00:10:23,900
Peut-être que nous ne devons pas chercher
tous les éléments de n de la table de hachage.

213
00:10:23,900 --> 00:10:25,790
Peut-être que nous devons rechercher
deux d'entre eux.

214
00:10:25,790 --> 00:10:30,680
>> Et donc nous sommes toujours tendre vers
ce cas moyenne étant de près de 1 vs

215
00:10:30,680 --> 00:10:34,280
près de n, alors peut-être que va marcher.

216
00:10:34,280 --> 00:10:38,010
Voyons donc comment cette
pourrait fonctionner dans la réalité.

217
00:10:38,010 --> 00:10:41,460
Et nous allons voir si nous pouvons peut détecter
le problème qui pourrait se produire ici.

218
00:10:41,460 --> 00:10:42,540
>> Disons que nous hachage Bart.

219
00:10:42,540 --> 00:10:45,581
Alors maintenant, nous allons lancer un nouveau jeu
de chaînes à travers la fonction de hachage,

220
00:10:45,581 --> 00:10:48,460
et nous courons Bart travers le hachage
fonction, nous obtenons hashcode 6.

221
00:10:48,460 --> 00:10:52,100
Nous prenons un coup d'oeil, nous voyons 6 est
vide, afin que nous puissions mettre Bart là.

222
00:10:52,100 --> 00:10:55,410
>> Maintenant, nous hachage Lisa et que
génère également hashcode 6.

223
00:10:55,410 --> 00:10:58,330
Eh bien maintenant que nous utilisons cette
linéaire méthode que nous commençons à 6 sondage,

224
00:10:58,330 --> 00:10:59,330
nous voyons que 6 est pleine.

225
00:10:59,330 --> 00:11:00,990
Nous ne pouvons pas mettre en 6 Lisa.

226
00:11:00,990 --> 00:11:02,090
Alors, où allons-nous?

227
00:11:02,090 --> 00:11:03,280
Allons à 7.

228
00:11:03,280 --> 00:11:04,610
7 de vide, donc cela fonctionne.

229
00:11:04,610 --> 00:11:06,510
Mettons donc Lisa il.

230
00:11:06,510 --> 00:11:10,200
>> Maintenant, nous hachage Homer et nous obtenons 7.

231
00:11:10,200 --> 00:11:13,380
OK et nous savons que 7 est pleine
maintenant, de sorte que nous ne pouvons pas mettre Homer il.

232
00:11:13,380 --> 00:11:14,850
Allons donc à 8.

233
00:11:14,850 --> 00:11:15,664
8 est disponible?

234
00:11:15,664 --> 00:11:18,330
Ouais, et de 8 à proximité de 7, donc si
nous devons commencer à chercher nous sommes

235
00:11:18,330 --> 00:11:20,020
ne va pas avoir à aller trop loin.

236
00:11:20,020 --> 00:11:22,860
Et donc nous allons mettre Homer à 8.

237
00:11:22,860 --> 00:11:25,151
>> Maintenant, nous hachage Maggie et
renvoie 3, Dieu merci

238
00:11:25,151 --> 00:11:26,650
nous sommes en mesure de mettre juste Maggie il.

239
00:11:26,650 --> 00:11:29,070
Nous ne devons pas faire de
sorte de sondage pour cela.

240
00:11:29,070 --> 00:11:32,000
Maintenant, nous hachage Marge, et
Marge renvoie également six.

241
00:11:32,000 --> 00:11:39,560
>> Eh bien 6 est plein, 7 est plein, 8 est plein,
9, remercier tous droit divin, 9 est vide.

242
00:11:39,560 --> 00:11:41,600
Je peux mettre Marge à 9.

243
00:11:41,600 --> 00:11:45,280
Déjà, nous pouvons voir que nous commençons
d'avoir ce problème là où nous sommes maintenant

244
00:11:45,280 --> 00:11:48,780
commencer à étirer les choses genre
de loin de leurs codes de hachage.

245
00:11:48,780 --> 00:11:52,960
Et ce thêta de 1, cette moyenne
cas d'être constante de temps,

246
00:11:52,960 --> 00:11:56,560
commence à devenir un peu plus--
à partir de tendre un peu plus

247
00:11:56,560 --> 00:11:58,050
vers thêta de n.

248
00:11:58,050 --> 00:12:01,270
Nous commençons à perdre ce
avantage de tables de hachage.

249
00:12:01,270 --> 00:12:03,902
>> Ce problème que nous venons de voir
est ce qu'on appelle le clustering.

250
00:12:03,902 --> 00:12:06,360
Et ce qui est vraiment mal
regroupement est qu'une fois que vous maintenant

251
00:12:06,360 --> 00:12:09,606
avoir deux éléments qui sont côte à
côté, il rend encore plus probable,

252
00:12:09,606 --> 00:12:11,480
vous avez le double de la
hasard, que vous allez

253
00:12:11,480 --> 00:12:13,516
d'avoir une autre collision
avec cette grappe,

254
00:12:13,516 --> 00:12:14,890
et le cluster va croître par un.

255
00:12:14,890 --> 00:12:19,640
Et vous allez continuer à grandir et grandir
votre probabilité d'avoir une collision.

256
00:12:19,640 --> 00:12:24,470
Et finalement, il est tout aussi mauvais
de ne pas trier les données du tout.

257
00:12:24,470 --> 00:12:27,590
>> L'autre problème est que nous
encore, et jusqu'à présent, jusqu'à ce point,

258
00:12:27,590 --> 00:12:30,336
On vient de nous sorte de
comprendre ce qu'est une table de hachage est,

259
00:12:30,336 --> 00:12:31,960
nous avons encore la place que pour 10 cordes.

260
00:12:31,960 --> 00:12:37,030
Si nous voulons continuer à hacher
les citoyens de Springfield,

261
00:12:37,030 --> 00:12:38,790
nous ne pouvons obtenir 10 d'entre eux là-bas.

262
00:12:38,790 --> 00:12:42,619
Et si nous essayons et nous ajoutons un 11ème ou 12ème,
nous ne disposons pas d'un endroit pour les mettre.

263
00:12:42,619 --> 00:12:45,660
Nous pourrions être juste Spinning Around dans
cercles essayant de trouver un endroit vide,

264
00:12:45,660 --> 00:12:49,000
et nous sommes peut-être coincés
dans une boucle infinie.

265
00:12:49,000 --> 00:12:51,810
>> Donc, ce genre de prête à l'idée
de quelque chose appelé chaînage.

266
00:12:51,810 --> 00:12:55,790
Et voilà où nous allons apporter
listes chaînées retour dans l'image.

267
00:12:55,790 --> 00:13:01,300
Et si au lieu de stocker tout
les données elles-mêmes dans le réseau,

268
00:13:01,300 --> 00:13:04,471
chaque élément de la matrice pouvait
contenir plusieurs morceaux de données?

269
00:13:04,471 --> 00:13:05,970
Eh bien cela n'a pas de sens, non?

270
00:13:05,970 --> 00:13:09,280
Nous savons qu'un tableau ne peut
hold-- chaque élément d'un tableau

271
00:13:09,280 --> 00:13:12,930
ne peut contenir une seule pièce
de données de ce type de données.

272
00:13:12,930 --> 00:13:16,750
>> Mais que faire si ce type de données
est une liste liée, non?

273
00:13:16,750 --> 00:13:19,830
Alors que faire si tous les
élément du tableau a

274
00:13:19,830 --> 00:13:22,790
un pointeur à la tête d'une liste chaînée?

275
00:13:22,790 --> 00:13:24,680
Et puis nous pourrions construire
ces listes chaînées

276
00:13:24,680 --> 00:13:27,120
et de grandir arbitrairement,
parce que les listes chaînées permettent

277
00:13:27,120 --> 00:13:32,090
nous de grandir et rétrécir beaucoup plus
flexible qu'un tableau fait.

278
00:13:32,090 --> 00:13:34,210
Alors que faire si nous utilisons maintenant,
nous misons sur cela, non?

279
00:13:34,210 --> 00:13:37,760
Nous commençons à cultiver ces chaînes
en dehors de ces emplacements de tableau.

280
00:13:37,760 --> 00:13:40,740
>> Maintenant, nous pouvons adapter un infini
quantité de données, ou pas infinie,

281
00:13:40,740 --> 00:13:44,170
une quantité arbitraire de
données, dans notre table de hachage

282
00:13:44,170 --> 00:13:47,760
sans jamais courir dans
le problème de la collision.

283
00:13:47,760 --> 00:13:50,740
Nous avons également éliminé
regroupement en faisant cela.

284
00:13:50,740 --> 00:13:54,380
Et bien nous savons que lorsque nous insérons
dans une liste chaînée, si vous vous souvenez

285
00:13:54,380 --> 00:13:57,779
de notre vidéo sur les listes chaînées, seuls
listes chaînées et les listes doublement chaînées,

286
00:13:57,779 --> 00:13:59,070
il est une opération de constante de temps.

287
00:13:59,070 --> 00:14:00,710
Nous ne faisons qu'ajouter à l'avant.

288
00:14:00,710 --> 00:14:04,400
>> Et pour regarder en haut, bien que nous ne savons
ce regard dans une liste chaînée

289
00:14:04,400 --> 00:14:05,785
peut être un problème, non?

290
00:14:05,785 --> 00:14:07,910
Nous avons à parcourir
du début à la fin.

291
00:14:07,910 --> 00:14:10,460
Il n'y a pas aléatoire
l'accès à une liste chaînée.

292
00:14:10,460 --> 00:14:15,610
Mais si au lieu d'avoir une liée
liste où une recherche serait O n,

293
00:14:15,610 --> 00:14:19,590
nous avons maintenant 10 listes chaînées,
ou 1.000 listes chaînées,

294
00:14:19,590 --> 00:14:24,120
maintenant il est de O n divisé par 10,
O ou de n divisé par 1000.

295
00:14:24,120 --> 00:14:26,940
>> Et pendant que nous parlions
théoriquement de la complexité

296
00:14:26,940 --> 00:14:30,061
on fait abstraction des constantes, dans le réel
monde ces choses comptent vraiment,

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

298
00:14:30,560 --> 00:14:33,080
Nous allons effectivement remarquer
que tel est le cas

299
00:14:33,080 --> 00:14:36,610
de courir 10 fois plus rapide,
ou 1000 fois plus rapide,

300
00:14:36,610 --> 00:14:41,570
parce que nous sommes distribuer une longue
la chaîne à travers 1000 petites chaînes.

301
00:14:41,570 --> 00:14:45,090
Et chaque fois que nous avons à la recherche
par une de ces chaînes que nous pouvons

302
00:14:45,090 --> 00:14:50,290
ignorer les 999 chaînes nous ne nous soucions pas
à propos, et il suffit de chercher celui-là.

303
00:14:50,290 --> 00:14:53,220
>> Qui est, en moyenne,
1000 fois plus courte.

304
00:14:53,220 --> 00:14:56,460
Et si nous sommes encore sorte de
tendant vers ce cas moyenne

305
00:14:56,460 --> 00:15:01,610
d'être constante de temps, mais
seulement parce que nous misons

306
00:15:01,610 --> 00:15:03,730
divisant par un facteur constant énorme.

307
00:15:03,730 --> 00:15:05,804
Voyons comment cela pourrait
effectivement regarder bien.

308
00:15:05,804 --> 00:15:08,720
Donc, ce fut la table de hachage nous avions
avant, nous avons déclaré une table de hachage

309
00:15:08,720 --> 00:15:10,270
était capable de stocker 10 cordes.

310
00:15:10,270 --> 00:15:11,728
On ne va pas faire ça.

311
00:15:11,728 --> 00:15:13,880
Nous connaissons déjà la
les limites de cette méthode.

312
00:15:13,880 --> 00:15:20,170
Maintenant, notre table de hachage va être
un tableau de 10 nœuds, les pointeurs

313
00:15:20,170 --> 00:15:22,120
aux chefs de listes chaînées.

314
00:15:22,120 --> 00:15:23,830
>> Et maintenant il est nul.

315
00:15:23,830 --> 00:15:26,170
Chacun de ces 10 pointeurs est nulle.

316
00:15:26,170 --> 00:15:29,870
Il n'y a rien dans notre
hash table en ce moment.

317
00:15:29,870 --> 00:15:32,690
>> Maintenant, nous allons commencer à mettre un peu
choses dans cette table de hachage.

318
00:15:32,690 --> 00:15:35,440
Et nous allons voir comment cette méthode est
va nous profiter un peu.

319
00:15:35,440 --> 00:15:36,760
Disons hacher maintenant Joey.

320
00:15:36,760 --> 00:15:40,210
Nous allons courir à travers la chaîne Joey
une fonction de hachage et nous reviennent 6.

321
00:15:40,210 --> 00:15:41,200
Bien que faisons-nous maintenant?

322
00:15:41,200 --> 00:15:44,090
>> Eh bien travailler maintenant avec les listes chaînées,
nous ne travaillons pas avec des tableaux.

323
00:15:44,090 --> 00:15:45,881
Et lorsque nous travaillons
par des listes chaînées nous

324
00:15:45,881 --> 00:15:49,790
savons que nous devons commencer à dynamiquement
l'allocation d'espace et de renforcement des chaînes.

325
00:15:49,790 --> 00:15:54,020
Voilà sorte de how-- ceux qui sont le noyau
éléments de la construction d'une liste chaînée.

326
00:15:54,020 --> 00:15:57,670
Nous allons donc dynamiquement
allouer de l'espace pour Joey,

327
00:15:57,670 --> 00:16:00,390
et puis nous allons l'ajouter à la chaîne.

328
00:16:00,390 --> 00:16:03,170
>> Alors maintenant, regardez ce que nous avons fait.

329
00:16:03,170 --> 00:16:06,440
Quand nous hachage Joey nous avons obtenu le hashcode 6.

330
00:16:06,440 --> 00:16:11,790
Maintenant le pointeur à l'emplacement du tableau 6
des points à la tête d'une liste chaînée,

331
00:16:11,790 --> 00:16:14,900
et maintenant il est le seul
élément d'une liste chaînée.

332
00:16:14,900 --> 00:16:18,350
Et en ce que le noeud
liste chaînée est Joey.

333
00:16:18,350 --> 00:16:22,300
>> Donc, si nous avons besoin de regarder Joey
plus tard, nous venons de hachage nouveau Joey,

334
00:16:22,300 --> 00:16:26,300
nous obtenons 6 nouveau parce que notre
fonction de hachage est déterministe.

335
00:16:26,300 --> 00:16:30,400
Et puis nous commençons à la tête
de la liste liée souligné

336
00:16:30,400 --> 00:16:33,360
par emplacement de tableau
6, et nous pouvons itérer

337
00:16:33,360 --> 00:16:35,650
pour que d'essayer de trouver Joey.

338
00:16:35,650 --> 00:16:37,780
Et si nous construisons notre
la table de hachage de manière efficace,

339
00:16:37,780 --> 00:16:41,790
et de notre fonction de hachage efficace
pour distribuer des données de puits,

340
00:16:41,790 --> 00:16:45,770
en moyenne, chacun de ceux qui sont liés
listes au niveau de chaque tableau

341
00:16:45,770 --> 00:16:50,110
sera 1/10 de la taille de si nous
juste eu comme un seul grand

342
00:16:50,110 --> 00:16:51,650
liste chaînée avec tout ce qu'il.

343
00:16:51,650 --> 00:16:55,670
>> Si nous distribuons cette énorme liés
liste dans 10 listes chaînées

344
00:16:55,670 --> 00:16:57,760
chaque liste sera 1/10 de la taille.

345
00:16:57,760 --> 00:17:01,432
Et donc 10 fois plus rapide
à parcourir.

346
00:17:01,432 --> 00:17:02,390
Donc, nous allons le faire à nouveau.

347
00:17:02,390 --> 00:17:04,290
Voyons maintenant hacher Ross.

348
00:17:04,290 --> 00:17:07,540
>> Et disons Ross, quand nous faisons cela
le code de hachage nous serons de retour est de 2.

349
00:17:07,540 --> 00:17:10,630
Eh bien maintenant, nous alloue dynamiquement un
nouveau nœud, nous mettons Ross dans ce nœud,

350
00:17:10,630 --> 00:17:14,900
et nous disons maintenant l'emplacement de tableau
2, au lieu de pointer à null,

351
00:17:14,900 --> 00:17:18,579
des points à la tête d'un lien
liste dont seul noeud est Ross.

352
00:17:18,579 --> 00:17:22,660
Et nous pouvons le faire une fois de plus, nous
peut hacher Rachel et obtenir hashcode 4.

353
00:17:22,660 --> 00:17:25,490
malloc un nouveau nœud, mettre Rachel dans
le noeud, et dire un emplacement de tableau

354
00:17:25,490 --> 00:17:27,839
4 points maintenant à la tête
d'une liste chaînée dont

355
00:17:27,839 --> 00:17:31,420
seul élément se trouve être Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK, mais ce qui arrive si
nous avons une collision?

357
00:17:33,470 --> 00:17:38,560
Voyons comment nous traitons les collisions
en utilisant la méthode de chaînage séparé.

358
00:17:38,560 --> 00:17:39,800
Disons hacher Phoebe.

359
00:17:39,800 --> 00:17:41,094
Nous obtenons le hashcode 6.

360
00:17:41,094 --> 00:17:44,010
Dans notre exemple précédent, nous étions juste
mémoriser les chaînes du tableau.

361
00:17:44,010 --> 00:17:45,980
Ce fut un problème.

362
00:17:45,980 --> 00:17:48,444
>> Nous ne voulons pas tabasser
Joey, et nous avons déjà

363
00:17:48,444 --> 00:17:51,110
vu que nous pouvons obtenir un certain regroupement
problèmes si nous essayons de l'étape

364
00:17:51,110 --> 00:17:52,202
à travers et sonde.

365
00:17:52,202 --> 00:17:54,660
Mais que faire si nous avons juste un peu
traiter ce de la même manière, non?

366
00:17:54,660 --> 00:17:57,440
Il est juste comme l'ajout d'un élément
à la tête d'une liste chaînée.

367
00:17:57,440 --> 00:18:00,220
Voyons espace juste malloc pour Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Nous dirons prochaines pointeur de Phoebe
à l'ancien chef de la liste chaînée,

369
00:18:04,764 --> 00:18:07,180
puis 6 points seulement à la
nouveau chef de la liste chaînée.

370
00:18:07,180 --> 00:18:10,150
Et maintenant, regardez, nous avons changé de Phoebe.

371
00:18:10,150 --> 00:18:14,210
Nous pouvons maintenant stocker deux
éléments avec hashcode 6,

372
00:18:14,210 --> 00:18:17,170
et nous ne disposons pas des problèmes.

373
00:18:17,170 --> 00:18:20,147
>> Voilà à peu près tout
il est de chaînage.

374
00:18:20,147 --> 00:18:21,980
Et chaînage est certainement
la méthode qui est

375
00:18:21,980 --> 00:18:27,390
va être le plus efficace pour vous si
vous stockez des données dans une table de hachage.

376
00:18:27,390 --> 00:18:30,890
Mais cette combinaison de
les tableaux et les listes chaînées

377
00:18:30,890 --> 00:18:36,080
ensemble pour former une table de hachage vraiment
améliore considérablement votre capacité

378
00:18:36,080 --> 00:18:40,550
pour stocker de grandes quantités de données, et
très rapidement et efficacement la recherche

379
00:18:40,550 --> 00:18:41,630
par ces données.

380
00:18:41,630 --> 00:18:44,150
>> Il ya encore une
structure de données là-bas

381
00:18:44,150 --> 00:18:48,700
qui pourrait même être un peu
mieux en termes de garantie

382
00:18:48,700 --> 00:18:51,920
que notre insertion, deletion, et
Look Up fois sont encore plus rapides.

383
00:18:51,920 --> 00:18:55,630
Et nous verrons que, dans une vidéo sur essais.

384
00:18:55,630 --> 00:18:58,930
Je suis Doug Lloyd, cela est CS50.

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