>> ROB BOWDEN: Salut.
Je suis Rob, et le hash de let cette solution rupture.
Donc, ici, nous allons mettre en œuvre une table de hachage général.
Nous voyons que le noeud de structure de notre hachage table va ressembler à ceci.
Donc ça va avoir un mot char tableau de longueur de taille plus 1.
Ne pas oublier le 1 depuis le maximum mot dans le dictionnaire est de 45
caractères, puis nous allons besoin d'un caractère supplémentaire pour la
barre oblique inverse 0.
>> Et puis notre table de hachage dans chaque seau va stocker une
liste chaînée de noeuds.
Nous ne faisons pas linéaire sondage ici.
Et afin de relier à l'autre élément dans le seau, nous avons besoin d'une
noeud de struct * prochaine.
C'est ce que un nœud ressemble.
Maintenant, voici la déclaration de notre table de hachage.
Il va avoir 16 384 seaux, mais ce nombre n'a pas vraiment d'importance.
Et enfin, nous allons avoir l' hashtable_size variable globale, qui
va commencer à 0, et c'est va garder une trace de combien de mots
étaient dans notre dictionnaire.
Très bien.
>> Donc, nous allons jeter un oeil à charge.
Donc remarquer que la charge, elle retourne un bool.
Vous revenez vrai si c'était avec succès chargé et faux sinon.
Et il faut un const char * étoiles dictionnaire, qui est le dictionnaire
que nous voulons ouvrir.
Donc, c'est la première chose nous allons faire.
Nous allons fopen le dictionnaire pour lecture, et nous allons devoir
pour s'assurer qu'il réussit si il est retourné NULL, alors nous n'avons pas
réussir à ouvrir le dictionnaire et nous devons retourner false.
>> Mais en supposant qu'il a fait avec succès ouvert, alors que nous voulons lire le
dictionnaire.
Donc tourne en boucle jusqu'à ce qu'on trouve une certaine raison de sortir de cette
boucle qui nous verrons.
Donc, gardons en boucle, et maintenant nous allons à malloc un seul nœud.
Et bien sûr, nous avons besoin de contrôle d'erreur encore si allouer de ne pas réussir
et nous voulons décharger un nœud que nous arrivé à malloc avant, fermer la
dictionnaire et retourner false.
>> Mais en ignorant que, en supposant que nous réussi, alors nous voulons utiliser fscanf
de lire un seul mot de notre par dictionnaire dans notre nœud.
Alors, n'oubliez pas que le mot d'entrée-> est le produit de carbonisation mot tampon de longueur de taille plus
celui que nous allons stocker le mot po
Donc fscanf va revenir 1 tant comme il a été en mesure de lire correctement une
mot à partir du fichier.
>> Si une erreur se produit soit ou nous rejoindre la fin du fichier, il ne sera pas
retourner 1, dans lequel cas, si ce n'est pas le retour 1, nous allons enfin briser
en dehors de cette boucle while.
Ainsi, nous voyons qu'une fois que nous avons réussi à lire un mot en
entrée-> mot, puis nous allons à hacher ce mot en utilisant notre fonction de hachage.
Jetons un coup d'œil à la fonction de hachage.
>> Donc, vous n'avez pas vraiment besoin pour comprendre cela.
Et en fait, nous avons juste tiré ce fonction de hachage à partir d'Internet.
La seule chose que vous devez reconnaître, c'est que cela prend un char * mot const,
il prend une chaîne en entrée et retour d'un unsigned int en sortie.
Donc, c'est tout une fonction de hachage est, est-il prend dans une entrée, il vous donne un
index dans la table de hachage.
Notez que nous n'avons modding par num_buckets si la valeur de hachage est retourné
est en fait un index dans la table de hachage et n'indexe pas au-delà de la
limites du tableau.
>> Donc, étant donné que la fonction de hachage, nous allons pour hacher le mot que nous lisons
dans le dictionnaire et puis nous allons à utiliser qui a pour insérer l'
entrée dans la table de hachage.
Maintenant, hash table de hachage est le courant liste liée dans la table de hachage, et
il est très possible que tout est NULL.
Nous voulons insérer notre entrée à l' à partir de cette liste chaînée, et ainsi de
nous allons avoir notre entrée actuelle signaler ce la table de hachage a
points et nous allons stocker dans la table de hachage au hachage
l'entrée de courant.
>> Donc, ces deux lignes insérer avec succès l'entrée au début de l'
liste liée à l'index dans la table de hachage.
Une fois que nous en avons terminé avec cela, nous savons que nous avons trouvé un autre mot dans la
dictionnaire et nous incrémenter à nouveau.
Donc, nous continuons à faire que jusqu'à fscanf retourne enfin quelque chose de non 1 à
quel point nous rappeler que nous devons entrée libre, donc ici, nous malloced une
entrée et nous avons essayé de lire quelque chose du dictionnaire.
Et nous n'avons pas lu avec succès quelque chose du dictionnaire dans lequel
cas, nous devons libérer l'entrée que nous jamais mettre dans la table de hachage
et enfin briser.
>> Une fois que nous échappons, nous avons besoin de voir, ainsi, n'avons nous rompons parce qu'il n'y
a été une erreur de lecture du fichier, ou n'avons nous rompons parce que nous avons atteint
la fin du fichier?
S'il y avait une erreur, nous voulons return false car la charge n'a pas
réussissons, et dans le processus, nous voulons décharger tous les mots que nous lisons
dans et fermez le fichier de dictionnaire.
En supposant que nous avons réussi, alors que nous venons de encore besoin de fermer le dictionnaire
déposer, et retourner vrai que finalement nous avons chargé le
dictionnaire.
Et c'est tout pour la charge.
>> Alors maintenant, vérifier, étant donné une table de hachage chargé, va ressembler à ceci.
Afin de vérifier, il retourne un bool, qui va indiquer si l'
passé en char * mot, si l' chaîne de caractères passée en est dans notre dictionnaire.
Donc, si elle est dans le dictionnaire, si elle est dans notre table de hachage, nous reviendrons
vrai, et si ce n'est pas, nous reviendrons faux.
Compte tenu de ce mot passé dans, nous sommes va hacher le mot.
>> Maintenant, une chose importante à reconnaître est que de la charge, nous savions que tous
les mots allaient être minuscules, mais ici, nous ne sommes pas si sûr.
Si nous prenons un coup d'oeil à notre fonction de hachage, notre fonction de hachage fait
est en minuscules chaque caractère du mot.
Donc, quelle que soit la capitalisation des mot, notre fonction de hachage va
retourner le même indice pour quelle que soit la capitalisation est comme il aurait
retourné pour un tout minuscule version du mot.
Très bien.
>> C'est donc notre indice.
C'est la table de hachage pour ce mot.
Or, cette boucle va à plus de la liste chaînée
que c'était à cet index.
Donc, nous remarquons l'initialisation entrée pour pointer vers cet index.
Nous allons continuer en entrée ne pas égale NULL, et n'oubliez pas que
mise à jour du pointeur dans notre liste chaînée entrée est égale à l'entrée-> prochaine, ont donc
notre point d'entrée actuel de la article suivant dans la liste liée.
Très bien.
>> Ainsi, pour chaque entrée dans la liste liée, nous allons utiliser strcasecmp.
Ce n'est pas parce STRCMP une fois de plus, nous vouloir faire les choses sensible à la casse.
Nous utilisons donc strcasecmp de comparer le mot qui a été adoptée à cette fonction
contre le mot que est dans cette entrée.
Si elle retourne 0, cela signifie qu'il a été un match, dans ce cas, nous voulons
return true.
Nous avons trouvé le succès mot dans notre table de hachage.
>> S'il n'y avait pas un match, alors nous sommes aller à boucle encore et regarder la
entrée suivante.
Et nous allons continuer boucle alors qu'il sont entrées dans cette liste chaînée.
Qu'advient-il si nous rompons sortir de cette boucle?
Cela signifie que nous n'avons pas trouvé une entrée qui identifié ce mot, dans ce cas,
nous retournons false pour indiquer que notre table de hachage des ne contient pas ce mot.
Et c'est tout pour l'enregistrement.
Très bien.
>> Donc, nous allons jeter un oeil à la taille.
Maintenant, la taille va être assez simple rappelez-vous depuis la charge, pour chaque mot
nous avons trouvé nous incrémentons un mondial hashtable_size variable.
Donc, la fonction de taille est juste va revenir que mondial
variables, et c'est tout.
>> Maintenant, enfin, nous avons besoin de décharger le dictionnaire une fois que tout est fait.
Alors, comment allons-nous faire?
Ici, nous sommes en boucle sur toutes les seaux de notre table de hachage.
Donc, il ya num_buckets seaux.
Et pour chaque liste liée dans notre hachage table, nous allons faire une boucle sur l'
intégralité de la liste chaînée libérer chaque élément.
Maintenant, nous devons être prudents, alors voici nous avoir une variable temporaire qui est
mémoriser le pointeur à l'autre élément dans la liste chaînée.
Et puis nous allons à la libre l'élément courant.
>> Nous devons être sûrs que nous faisons depuis que nous avons ne peut pas simplement libérer l'élément courant
puis essayer d'accéder au pointeur suivant car une fois que nous avons libéré il l'
la mémoire devient invalide.
Nous devons donc garder autour d'un pointeur vers l'élément suivant, alors nous pouvons libérer l'
élément courant, et alors nous pouvons mettre à jour notre élément courant jusqu'au point de
l'élément suivant.
>> Nous allons boucle alors qu'il ya des éléments dans cette liste chaînée.
Nous le ferons pour toutes les listes liées à la table de hachage, et une fois que nous aurons terminé
avec cela, nous avons complètement déchargé la table de hachage, et nous avons fini.
Il est donc impossible pour les déchargements à jamais return false, et quand nous aurons terminé, nous
il suffit de retourner vrai.