1
00:00:00,000 --> 00:00:11,856

2
00:00:11,856 --> 00:00:13,050
>> ROB BOWDEN: Salut.

3
00:00:13,050 --> 00:00:16,210
Je suis Rob, et le hash de let
cette solution rupture.

4
00:00:16,210 --> 00:00:20,070
Donc, ici, nous allons mettre en œuvre
une table de hachage général.

5
00:00:20,070 --> 00:00:24,090
Nous voyons que le noeud de structure de notre hachage
table va ressembler à ceci.

6
00:00:24,090 --> 00:00:28,710
Donc ça va avoir un mot char
tableau de longueur de taille plus 1.

7
00:00:28,710 --> 00:00:32,259
Ne pas oublier le 1 depuis le maximum
mot dans le dictionnaire est de 45

8
00:00:32,259 --> 00:00:35,110
caractères, puis nous allons
besoin d'un caractère supplémentaire pour la

9
00:00:35,110 --> 00:00:37,070
barre oblique inverse 0.

10
00:00:37,070 --> 00:00:40,870
>> Et puis notre table de hachage dans chaque
seau va stocker une

11
00:00:40,870 --> 00:00:42,320
liste chaînée de noeuds.

12
00:00:42,320 --> 00:00:44,420
Nous ne faisons pas linéaire sondage ici.

13
00:00:44,420 --> 00:00:48,430
Et afin de relier à l'autre
élément dans le seau, nous avons besoin d'une

14
00:00:48,430 --> 00:00:51,110
noeud de struct * prochaine.

15
00:00:51,110 --> 00:00:53,090
C'est ce que un nœud ressemble.

16
00:00:53,090 --> 00:00:56,180
Maintenant, voici la déclaration
de notre table de hachage.

17
00:00:56,180 --> 00:01:01,910
Il va avoir 16 384 seaux, mais
ce nombre n'a pas vraiment d'importance.

18
00:01:01,910 --> 00:01:05,450
Et enfin, nous allons avoir l'
hashtable_size variable globale, qui

19
00:01:05,450 --> 00:01:08,640
va commencer à 0, et c'est
va garder une trace de combien de mots

20
00:01:08,640 --> 00:01:10,080
étaient dans notre dictionnaire.

21
00:01:10,080 --> 00:01:10,760
Très bien.

22
00:01:10,760 --> 00:01:13,190
>> Donc, nous allons jeter un oeil à charge.

23
00:01:13,190 --> 00:01:16,390
Donc remarquer que la charge,
elle retourne un bool.

24
00:01:16,390 --> 00:01:20,530
Vous revenez vrai si c'était avec succès
chargé et faux sinon.

25
00:01:20,530 --> 00:01:23,990
Et il faut un const char * étoiles
dictionnaire, qui est le dictionnaire

26
00:01:23,990 --> 00:01:25,280
que nous voulons ouvrir.

27
00:01:25,280 --> 00:01:27,170
Donc, c'est la première chose
nous allons faire.

28
00:01:27,170 --> 00:01:30,420
Nous allons fopen le dictionnaire pour
lecture, et nous allons devoir

29
00:01:30,420 --> 00:01:34,700
pour s'assurer qu'il réussit si
il est retourné NULL, alors nous n'avons pas

30
00:01:34,700 --> 00:01:37,440
réussir à ouvrir le dictionnaire
et nous devons retourner false.

31
00:01:37,440 --> 00:01:41,580
>> Mais en supposant qu'il a fait avec succès
ouvert, alors que nous voulons lire le

32
00:01:41,580 --> 00:01:42,400
dictionnaire.

33
00:01:42,400 --> 00:01:46,210
Donc tourne en boucle jusqu'à ce qu'on trouve une certaine
raison de sortir de cette

34
00:01:46,210 --> 00:01:47,570
boucle qui nous verrons.

35
00:01:47,570 --> 00:01:51,780
Donc, gardons en boucle, et maintenant nous allons
à malloc un seul nœud.

36
00:01:51,780 --> 00:01:56,800
Et bien sûr, nous avons besoin de contrôle d'erreur
encore si allouer de ne pas réussir

37
00:01:56,800 --> 00:02:00,660
et nous voulons décharger un nœud que nous
arrivé à malloc avant, fermer la

38
00:02:00,660 --> 00:02:02,590
dictionnaire et retourner false.

39
00:02:02,590 --> 00:02:07,440
>> Mais en ignorant que, en supposant que nous
réussi, alors nous voulons utiliser fscanf

40
00:02:07,440 --> 00:02:12,400
de lire un seul mot de notre
par dictionnaire dans notre nœud.

41
00:02:12,400 --> 00:02:17,310
Alors, n'oubliez pas que le mot d'entrée-> est le produit de carbonisation
mot tampon de longueur de taille plus

42
00:02:17,310 --> 00:02:20,300
celui que nous allons
stocker le mot po

43
00:02:20,300 --> 00:02:25,280
Donc fscanf va revenir 1 tant
comme il a été en mesure de lire correctement une

44
00:02:25,280 --> 00:02:26,750
mot à partir du fichier.

45
00:02:26,750 --> 00:02:31,030
>> Si une erreur se produit soit ou nous rejoindre
la fin du fichier, il ne sera pas

46
00:02:31,030 --> 00:02:34,950
retourner 1, dans lequel cas, si ce n'est pas le
retour 1, nous allons enfin briser

47
00:02:34,950 --> 00:02:37,280
en dehors de cette boucle while.

48
00:02:37,280 --> 00:02:42,770
Ainsi, nous voyons qu'une fois que nous avons réussi à
lire un mot en

49
00:02:42,770 --> 00:02:48,270
entrée-> mot, puis nous allons à hacher
ce mot en utilisant notre fonction de hachage.

50
00:02:48,270 --> 00:02:49,580
Jetons un coup d'œil à
la fonction de hachage.

51
00:02:49,580 --> 00:02:52,430

52
00:02:52,430 --> 00:02:55,610
>> Donc, vous n'avez pas vraiment besoin
pour comprendre cela.

53
00:02:55,610 --> 00:02:59,460
Et en fait, nous avons juste tiré ce
fonction de hachage à partir d'Internet.

54
00:02:59,460 --> 00:03:04,010
La seule chose que vous devez reconnaître, c'est
que cela prend un char * mot const,

55
00:03:04,010 --> 00:03:08,960
il prend une chaîne en entrée et
retour d'un unsigned int en sortie.

56
00:03:08,960 --> 00:03:12,360
Donc, c'est tout une fonction de hachage est, est-il
prend dans une entrée, il vous donne un

57
00:03:12,360 --> 00:03:14,490
index dans la table de hachage.

58
00:03:14,490 --> 00:03:18,530
Notez que nous n'avons modding par num_buckets
si la valeur de hachage est retourné

59
00:03:18,530 --> 00:03:21,730
est en fait un index dans la table de hachage
et n'indexe pas au-delà de la

60
00:03:21,730 --> 00:03:24,320
limites du tableau.

61
00:03:24,320 --> 00:03:27,855
>> Donc, étant donné que la fonction de hachage, nous allons
pour hacher le mot que nous lisons

62
00:03:27,855 --> 00:03:31,700
dans le dictionnaire et puis nous allons
à utiliser qui a pour insérer l'

63
00:03:31,700 --> 00:03:33,750
entrée dans la table de hachage.

64
00:03:33,750 --> 00:03:38,830
Maintenant, hash table de hachage est le courant
liste liée dans la table de hachage, et

65
00:03:38,830 --> 00:03:41,410
il est très possible que tout est NULL.

66
00:03:41,410 --> 00:03:45,640
Nous voulons insérer notre entrée à l'
à partir de cette liste chaînée, et ainsi de

67
00:03:45,640 --> 00:03:48,910
nous allons avoir notre entrée actuelle
signaler ce la table de hachage a

68
00:03:48,910 --> 00:03:54,030
points et nous allons stocker
dans la table de hachage au hachage

69
00:03:54,030 --> 00:03:55,350
l'entrée de courant.

70
00:03:55,350 --> 00:03:59,320
>> Donc, ces deux lignes insérer avec succès
l'entrée au début de l'

71
00:03:59,320 --> 00:04:02,270
liste liée à l'index
dans la table de hachage.

72
00:04:02,270 --> 00:04:04,900
Une fois que nous en avons terminé avec cela, nous savons
que nous avons trouvé un autre mot dans la

73
00:04:04,900 --> 00:04:07,800
dictionnaire et nous incrémenter à nouveau.

74
00:04:07,800 --> 00:04:13,960
Donc, nous continuons à faire que jusqu'à fscanf
retourne enfin quelque chose de non 1 à

75
00:04:13,960 --> 00:04:18,560
quel point nous rappeler que nous devons
entrée libre, donc ici, nous malloced une

76
00:04:18,560 --> 00:04:21,329
entrée et nous avons essayé de lire quelque chose
du dictionnaire.

77
00:04:21,329 --> 00:04:24,110
Et nous n'avons pas lu avec succès
quelque chose du dictionnaire dans lequel

78
00:04:24,110 --> 00:04:27,440
cas, nous devons libérer l'entrée que nous
jamais mettre dans la table de hachage

79
00:04:27,440 --> 00:04:29,110
et enfin briser.

80
00:04:29,110 --> 00:04:32,750
>> Une fois que nous échappons, nous avons besoin de voir, ainsi,
n'avons nous rompons parce qu'il n'y

81
00:04:32,750 --> 00:04:35,840
a été une erreur de lecture du fichier, ou
n'avons nous rompons parce que nous avons atteint

82
00:04:35,840 --> 00:04:37,120
la fin du fichier?

83
00:04:37,120 --> 00:04:40,150
S'il y avait une erreur, nous voulons
return false car la charge n'a pas

84
00:04:40,150 --> 00:04:43,260
réussissons, et dans le processus, nous voulons
décharger tous les mots que nous lisons

85
00:04:43,260 --> 00:04:45,670
dans et fermez le fichier de dictionnaire.

86
00:04:45,670 --> 00:04:48,740
En supposant que nous avons réussi, alors que nous venons de
encore besoin de fermer le dictionnaire

87
00:04:48,740 --> 00:04:51,970
déposer, et retourner vrai que finalement
nous avons chargé le

88
00:04:51,970 --> 00:04:53,040
dictionnaire.

89
00:04:53,040 --> 00:04:54,420
Et c'est tout pour la charge.

90
00:04:54,420 --> 00:04:59,020
>> Alors maintenant, vérifier, étant donné une table de hachage chargé,
va ressembler à ceci.

91
00:04:59,020 --> 00:05:02,690
Afin de vérifier, il retourne un bool, qui
va indiquer si l'

92
00:05:02,690 --> 00:05:07,530
passé en char * mot, si l'
chaîne de caractères passée en est dans notre dictionnaire.

93
00:05:07,530 --> 00:05:10,530
Donc, si elle est dans le dictionnaire, si elle est
dans notre table de hachage, nous reviendrons

94
00:05:10,530 --> 00:05:13,380
vrai, et si ce n'est pas,
nous reviendrons faux.

95
00:05:13,380 --> 00:05:17,770
Compte tenu de ce mot passé dans, nous sommes
va hacher le mot.

96
00:05:17,770 --> 00:05:22,020
>> Maintenant, une chose importante à reconnaître est
que de la charge, nous savions que tous

97
00:05:22,020 --> 00:05:25,820
les mots allaient être minuscules,
mais ici, nous ne sommes pas si sûr.

98
00:05:25,820 --> 00:05:29,510
Si nous prenons un coup d'oeil à notre fonction de hachage,
notre fonction de hachage fait

99
00:05:29,510 --> 00:05:32,700
est en minuscules chaque caractère
du mot.

100
00:05:32,700 --> 00:05:37,580
Donc, quelle que soit la capitalisation des
mot, notre fonction de hachage va

101
00:05:37,580 --> 00:05:42,270
retourner le même indice pour quelle que soit la
capitalisation est comme il aurait

102
00:05:42,270 --> 00:05:45,280
retourné pour un tout minuscule
version du mot.

103
00:05:45,280 --> 00:05:45,950
Très bien.

104
00:05:45,950 --> 00:05:47,410
>> C'est donc notre indice.

105
00:05:47,410 --> 00:05:49,790
C'est la table de hachage pour ce mot.

106
00:05:49,790 --> 00:05:52,940
Or, cette boucle va
à plus de la liste chaînée

107
00:05:52,940 --> 00:05:55,000
que c'était à cet index.

108
00:05:55,000 --> 00:05:59,630
Donc, nous remarquons l'initialisation entrée
pour pointer vers cet index.

109
00:05:59,630 --> 00:06:03,480
Nous allons continuer en entrée ne
pas égale NULL, et n'oubliez pas que

110
00:06:03,480 --> 00:06:08,350
mise à jour du pointeur dans notre liste chaînée
entrée est égale à l'entrée-> prochaine, ont donc

111
00:06:08,350 --> 00:06:13,840
notre point d'entrée actuel de la
article suivant dans la liste liée.

112
00:06:13,840 --> 00:06:14,400
Très bien.

113
00:06:14,400 --> 00:06:19,150
>> Ainsi, pour chaque entrée dans la liste liée,
nous allons utiliser strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Ce n'est pas parce STRCMP une fois de plus, nous
vouloir faire les choses sensible à la casse.

115
00:06:23,780 --> 00:06:28,830
Nous utilisons donc strcasecmp de comparer le mot
qui a été adoptée à cette fonction

116
00:06:28,830 --> 00:06:31,860
contre le mot que
est dans cette entrée.

117
00:06:31,860 --> 00:06:35,570
Si elle retourne 0, cela signifie qu'il a été
un match, dans ce cas, nous voulons

118
00:06:35,570 --> 00:06:36,630
return true.

119
00:06:36,630 --> 00:06:39,590
Nous avons trouvé le succès
mot dans notre table de hachage.

120
00:06:39,590 --> 00:06:43,040
>> S'il n'y avait pas un match, alors nous sommes
aller à boucle encore et regarder la

121
00:06:43,040 --> 00:06:43,990
entrée suivante.

122
00:06:43,990 --> 00:06:47,640
Et nous allons continuer boucle alors qu'il
sont entrées dans cette liste chaînée.

123
00:06:47,640 --> 00:06:50,160
Qu'advient-il si nous rompons
sortir de cette boucle?

124
00:06:50,160 --> 00:06:55,110
Cela signifie que nous n'avons pas trouvé une entrée qui
identifié ce mot, dans ce cas,

125
00:06:55,110 --> 00:07:00,220
nous retournons false pour indiquer que notre
table de hachage des ne contient pas ce mot.

126
00:07:00,220 --> 00:07:01,910
Et c'est tout pour l'enregistrement.

127
00:07:01,910 --> 00:07:02,540
Très bien.

128
00:07:02,540 --> 00:07:04,790
>> Donc, nous allons jeter un oeil à la taille.

129
00:07:04,790 --> 00:07:09,280
Maintenant, la taille va être assez simple
rappelez-vous depuis la charge, pour chaque mot

130
00:07:09,280 --> 00:07:12,880
nous avons trouvé nous incrémentons un mondial
hashtable_size variable.

131
00:07:12,880 --> 00:07:15,830
Donc, la fonction de taille est juste
va revenir que mondial

132
00:07:15,830 --> 00:07:18,150
variables, et c'est tout.

133
00:07:18,150 --> 00:07:22,300
>> Maintenant, enfin, nous avons besoin de décharger le
dictionnaire une fois que tout est fait.

134
00:07:22,300 --> 00:07:25,340
Alors, comment allons-nous faire?

135
00:07:25,340 --> 00:07:30,440
Ici, nous sommes en boucle sur toutes les
seaux de notre table de hachage.

136
00:07:30,440 --> 00:07:33,240
Donc, il ya num_buckets seaux.

137
00:07:33,240 --> 00:07:37,490
Et pour chaque liste liée dans notre hachage
table, nous allons faire une boucle sur l'

138
00:07:37,490 --> 00:07:41,070
intégralité de la liste chaînée
libérer chaque élément.

139
00:07:41,070 --> 00:07:46,070
Maintenant, nous devons être prudents, alors voici nous
avoir une variable temporaire qui est

140
00:07:46,070 --> 00:07:49,740
mémoriser le pointeur à l'autre
élément dans la liste chaînée.

141
00:07:49,740 --> 00:07:52,140
Et puis nous allons à la libre
l'élément courant.

142
00:07:52,140 --> 00:07:55,990
>> Nous devons être sûrs que nous faisons depuis que nous avons
ne peut pas simplement libérer l'élément courant

143
00:07:55,990 --> 00:07:59,260
puis essayer d'accéder au pointeur suivant
car une fois que nous avons libéré il l'

144
00:07:59,260 --> 00:08:00,870
la mémoire devient invalide.

145
00:08:00,870 --> 00:08:04,990
Nous devons donc garder autour d'un pointeur vers
l'élément suivant, alors nous pouvons libérer l'

146
00:08:04,990 --> 00:08:08,360
élément courant, et alors nous pouvons mettre à jour
notre élément courant jusqu'au point de

147
00:08:08,360 --> 00:08:09,590
l'élément suivant.

148
00:08:09,590 --> 00:08:12,770
>> Nous allons boucle alors qu'il ya des éléments
dans cette liste chaînée.

149
00:08:12,770 --> 00:08:16,450
Nous le ferons pour toutes les listes liées à
la table de hachage, et une fois que nous aurons terminé

150
00:08:16,450 --> 00:08:20,180
avec cela, nous avons complètement déchargé
la table de hachage, et nous avons fini.

151
00:08:20,180 --> 00:08:24,050
Il est donc impossible pour les déchargements à jamais
return false, et quand nous aurons terminé, nous

152
00:08:24,050 --> 00:08:25,320
il suffit de retourner vrai.

153
00:08:25,320 --> 00:08:27,563