[Jouer de la musique] DOUG LLOYD: A présent, vous en savoir beaucoup sur les tableaux, et vous savez beaucoup de choses sur les listes chaînées. Et nous avons de discuter de la avantages et les inconvénients, nous avons discuté liée listes peut devenir plus grand et plus petit, mais ils prennent plus de taille. Les tableaux sont beaucoup plus faciles à utilisent, mais ils sont restrictive dans la mesure que nous avons pour définir la taille de le tableau au début puis nous sommes coincés avec elle. 

Mais voilà, nous avons à peu près épuisé tous nos sujets à propos des listes chaînées et les tableaux. Ou avons-nous? Peut-être que nous pouvons faire quelque chose encore plus créatif. Et ce genre de Prête l'idée d'une table de hachage. 

Ainsi, dans une table de hachage, nous allons essayer combiner un tableau avec une liste chaînée. Nous allons prendre les avantages du tableau, comme l'accès aléatoire, être en mesure de simplement aller à tableau élément 4 ou un tableau élément 8 sans avoir à parcourir à travers. Voilà assez rapide, non? 

Mais nous voulons aussi avoir nos données la structure soit en mesure de croître et de se rétrécir. Nous ne devons pas, nous ne faisons pas vouloir être limité. Et nous voulons être en mesure pour ajouter et supprimer des choses très facilement, ce qui si vous vous souvenez, est très complexe avec un tableau. Et nous pouvons appeler cela chose de nouveau une table de hachage. 

Et si elles sont appliquées correctement, nous sorte de prendre les avantages des deux données structures que vous avez déjà vu, les tableaux et les listes chaînées. L'insertion peut commencer à tendre vers thêta de 1. Theta nous avons pas vraiment discuté, mais thêta est seulement le cas en moyenne, ce qui va réellement se passer. Vous n'êtes pas toujours aller à avoir le pire des cas, et vous n'êtes pas toujours avoir le meilleur des cas, alors quel est le scénario moyen? 

Eh bien une insertion moyenne dans une table de hachage peut commencer à se rapprocher de la constante de temps. Et la suppression peut obtenir fermer à temps constant. Et recherche peut obtenir fermer à temps constant. That's-- nous ne disposons pas de données d'un la structure encore que ne peut le faire, et si cela sonne déjà comme une jolie grande chose. Nous avons vraiment atténué les les inconvénients de chacun sur son propre. 

Pour obtenir cette performance mise à niveau si, nous nécessité de repenser la façon dont nous ajoutons des données dans la structure. Plus précisément, nous voulons que le données lui-même pour nous dire où il doit aller dans la structure. Et si nous devons ensuite pour voir si elle est dans la structure, si nous avons besoin de le trouver, nous voulons examiner les données nouveau et pouvoir efficacement, en utilisant les données, accéder hasard il. Juste en regardant la nous devrions avoir des données une idée d'où nous sommes exactement va trouver dans la table de hachage. 

Maintenant, l'inconvénient d'un hachage table est qu'ils sont vraiment assez mauvais à ordonner ou trier les données. Et en fait, si vous commencez de les utiliser pour commander ou trier des données vous perdez la totalité de la avantages vous avez déjà eu en termes d'insertion et de suppression. Il se rapproche de thêta de n, et nous avons essentiellement régressé dans une liste chaînée. Et si nous voulons seulement utiliser hachage tableaux si nous ne nous soucions pas si les données sont triées. Pour le contexte dans lequel vous les utilisez dans CS50 vous avez probablement ne vous souciez pas que les données sont triées. 

Donc, une table de hachage est une combinaison de deux pièces distinctes avec lesquels nous sommes familiers. La première est une fonction, qui nous appelons habituellement une fonction de hachage. Et cette fonction de hachage va retourner un entier non-négatif, ce qui nous appelons habituellement un hashcode, OK? La deuxième pièce est un tableau, qui est Capable de stocker des données du type nous vouloir placer dans la structure de données. Nous allons tenir au loin sur la liée élément de la liste pour l'instant et il suffit de commencer avec les bases d'un la table de hachage pour obtenir votre tête autour de lui, et puis nous allons peut-être sauter votre esprit un peu quand nous combiner les tableaux et les listes de liens ensemble. 

L'idée de base si est que nous prenons certaines données. Nous courons que les données par le biais la fonction de hachage. Et si les données sont traitées et il crache un certain nombre, OK? Et puis avec ce numéro nous stockons seulement les données on veut stocker dans la réseau à cet endroit. Ainsi, par exemple, nous avons peut-être cette table de hachage de chaînes. Il a obtenu 10 éléments en elle, donc nous pouvons tenir 10 chaînes en elle. 

Disons que nous voulons pour hacher John. Alors John que les données que nous voulons insérer dans cette table de hachage quelque part. Où allons-nous dire? Bien typiquement avec un tableau jusqu'ici nous avons probablement le mettrait en position de tableau 0. Mais maintenant nous avons cette nouvelle fonction de hachage. 

Et disons que nous courons John grâce à cette fonction de hachage et ça crache 4. Eh bien voilà où nous en sommes allez vouloir mettre John. Nous voulons mettre John dans un endroit du tableau 4, parce que si nous hachage John again-- disons que plus tard nous vouloir rechercher et de voir si John existe dans ce hachage table-- tout ce que nous devons faire est le lancer à travers le même hachage fonction, obtenir le numéro à 4, et être en mesure de trouver John immédiatement dans notre structure de données. Cela est assez bon. 

Disons que nous faisons maintenant ce encore une fois, nous voulons hachage Paul. Nous voulons ajouter Paul dans cette table de hachage. Disons que cette fois nous courons Paul à travers la fonction de hachage, le code de hachage qui est généré est 6. Eh bien maintenant, nous pouvons mettre Paul à l'emplacement de tableau 6. Et si nous avons besoin de regarder si Paul est dans cette table de hachage, tout ce que nous devons faire est de lancer Paul grâce à la fonction de hachage à nouveau et nous allons obtenir 6 à nouveau. 

Et ensuite nous regardons à l'emplacement du tableau 6. Paul est là? Si oui, il est dans la table de hachage. Paul est pas là? Il est pas dans la table de hachage. Il est assez simple. 

Maintenant, comment définissez-vous une fonction de hachage? Eh bien il n'y a vraiment aucune limite à la nombre de fonctions possibles de hachage. En fait, il ya un certain nombre de vraiment, vraiment bons sur Internet. Il ya un certain nombre de vraiment, vraiment mauvais sur Internet. Il est également assez facile pour écrire une mauvaise. 

Donc, ce qui fait un bon fonction de hachage, non? Eh bien une bonne fonction de hachage devrait utilisent uniquement les données hachés, et l'ensemble des données étant hachée. Donc, nous ne voulons pas utiliser anything-- nous ne incorporons rien d'autre part les données. Et nous voulons utiliser toutes les données. Nous ne voulons pas simplement utiliser un morceau de celui-ci, nous voulons utiliser tout cela. Une fonction de hachage devrait être aussi déterministe. Qu'est-ce que cela veut dire? Eh bien, cela signifie que chaque fois que nous passer le même morceau exacte des données dans la fonction de hachage nous avons toujours obtenir le même code de hachage sur. Si je passe dans le John fonction de hachage je sors 4. Je devrais être capable de le faire 10.000 fois et je aurez toujours 4. Donc pas de nombres aléatoires efficacement peuvent être impliqués dans notre hachage tables-- dans nos fonctions de hachage. 

Une fonction de hachage devrait également distribuer uniformément données. Si chaque fois que vous exécutez données à travers le fonction de hachage vous obtenez le hashcode 0, qui est sans doute pas si grand, non? Vous voulez sans doute à la grande une gamme de codes de hachage. Les choses peuvent aussi être réparties tout au long de la table. Et aussi que ce serait formidable si vraiment des données similaires, comme John et Jonathan, peut-être ont été répartis à peser différents endroits dans la table de hachage. Ce serait un grand avantage. 

Voici un exemple d'une fonction de hachage. Je l'ai écrit plus tôt celui-ci. Il est pas particulièrement bonne fonction de hachage pour des raisons qui ne sont pas vraiment supporter entrer dans ce moment. Mais voyez-vous ce qui se passe ici? Il semble que nous allons déclarer une variable appelé somme et sa mise en égal à 0. Et puis, apparemment, je fais quelque chose tant strstr [j] est pas égal backslasher 0. Qu'est-ce que je fais là? 

Ceci est fondamentalement juste un autre façon de mettre en œuvre [? strl?] et détecter le moment où vous avez atteint la fin de la chaîne. Donc, je ne dois pas fait calculer la longueur de la chaîne, Je suis juste en utilisant quand je frappe la 0 caractère barre oblique inverse je sais Je suis arrivé à la fin de la chaîne. Et puis je vais continuer à itérer cette chaîne, ajoutant strstr [j] pour résumer, puis à la fin de la journée va revenir somme mod HASH_MAX. 

Fondamentalement tout ce hachage fonction est en train de faire est d'ajouter jusqu'à toutes les valeurs ASCII des ma chaîne, puis il est retourner un hashcode modded par HASH_MAX. Il est probablement la taille de mon tableau, non? Je ne veux pas être obtenir hachage codes si mon tableau est de taille 10, Je ne veux pas être obtenir codes de hachage sur 11, 12, 13, je ne peux pas mettre les choses en les emplacements de la matrice, ce serait illégal. Je souffre d'une erreur de segmentation. 

Maintenant, voici une autre petite parenthèse. En général, vous allez probablement pas à envie d'écrire vos propres fonctions de hachage. Il est en fait un peu de un art, pas une science. Et il ya beaucoup qui va en eux. L'Internet, comme je l'ai dit, est pleine des fonctions de hachage très bons, et vous devriez utiliser l'Internet pour trouver des fonctions de hachage, car il est vraiment juste une sorte d'inutiles perte de temps pour créer votre propre. 

Vous pouvez écrire les plus simples à des fins de test. Mais quand vous avez réellement allez commencer hachage des données et le stockage dans une table de hachage vous êtes probablement vouloir à utiliser une fonction qui a été généré pour vous, ce qui existe sur l'internet. Si vous ne juste être sûr de citer vos sources. Il n'y a pas de raison de plagier quelque chose ici. 

La communauté de la science informatique est certainement de plus en plus, et vraiment valeurs open source, et il est vraiment important de citer vos sources afin que les gens peut obtenir l'attribution de le travail qu'ils sont faire au bénéfice de la communauté. Il faut donc toujours être sure-- et pas seulement pour hachage fonctions, mais généralement lorsque vous utiliser le code d'une source extérieure, Toujours citer votre source. Vous citez le nom de la personne qui a fait une partie du travail de sorte que vous ne devez. 

OK donc, revenons sur ce Table hachage pour une seconde. Ceci est où nous avons laissé éteint après nous avons inséré John et Paul dans cette table de hachage. Voyez-vous un problème? Vous pouvez voir deux. Mais en particulier, avez-vous voir ce problème possible? 

Que faire si je hachage Ringo, et il qui se révèle après traitement que les données grâce à la fonction de hachage Ringo a également généré la hashcode 6. Je ai déjà données au Lieu de tableau hashcode-- 6. Donc, il va probablement être un peu d'un problème pour moi maintenant, à droite? 

Nous appelons cela une collision. Et la collision se produit lorsque deux morceaux de données passent par le même hachage Fonction donné le même code de hachage. On peut supposer que nous voulons toujours obtenir à la fois morceaux de données dans la table de hachage, sinon nous ne serions pas en cours d'exécution Ringo arbitrairement par la fonction de hachage. Nous voulons sans doute pour obtenir Ringo dans ce tableau. 

Comment le faisons-nous si, si, il et Paul à la fois le rendement hashcode 6? Nous ne voulons pas remplacer Paul, Paul nous voulons être là aussi. Donc, nous devons trouver un moyen d'obtenir éléments dans la table de hachage conserve encore notre rapide insertion et de recherche rapide. Et une façon de traiter avec elle est de faire quelque chose appelé sondage linéaire. 

En utilisant cette méthode, si nous avons un collision, ainsi, que faisons-nous? 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, nous allons le mettre à hashcode plus 1. Et si cela let complet de le mettre dans hashcode plus 2. L'avantage de cet être si il est pas exactement où nous pensons qu'il est, et nous devons commencer à chercher, peut-être nous ne devons pas aller trop loin. Peut-être que nous ne devons pas chercher tous les éléments de n de la table de hachage. Peut-être que nous devons rechercher deux d'entre eux. 

Et donc nous sommes toujours tendre vers ce cas moyenne étant de près de 1 vs près de n, alors peut-être que va marcher. Voyons donc comment cette pourrait fonctionner dans la réalité. Et nous allons voir si nous pouvons peut détecter le problème qui pourrait se produire ici. 

Disons que nous hachage Bart. Alors maintenant, nous allons lancer un nouveau jeu de chaînes à travers la fonction de hachage, et nous courons Bart travers le hachage fonction, nous obtenons hashcode 6. Nous prenons un coup d'oeil, nous voyons 6 est vide, afin que nous puissions mettre Bart là. 

Maintenant, nous hachage Lisa et que génère également hashcode 6. Eh bien maintenant que nous utilisons cette linéaire méthode que nous commençons à 6 sondage, nous voyons que 6 est pleine. Nous ne pouvons pas mettre en 6 Lisa. Alors, où allons-nous? Allons à 7. 7 de vide, donc cela fonctionne. Mettons donc Lisa il. 

Maintenant, nous hachage Homer et nous obtenons 7. OK et nous savons que 7 est pleine maintenant, de sorte que nous ne pouvons pas mettre Homer il. Allons donc à 8. 8 est disponible? Ouais, et de 8 à proximité de 7, donc si nous devons commencer à chercher nous sommes ne va pas avoir à aller trop loin. Et donc nous allons mettre Homer à 8. 

Maintenant, nous hachage Maggie et renvoie 3, Dieu merci nous sommes en mesure de mettre juste Maggie il. Nous ne devons pas faire de sorte de sondage pour cela. Maintenant, nous hachage Marge, et Marge renvoie également six. 

Eh bien 6 est plein, 7 est plein, 8 est plein, 9, remercier tous droit divin, 9 est vide. Je peux mettre Marge à 9. Déjà, nous pouvons voir que nous commençons d'avoir ce problème là où nous sommes maintenant commencer à étirer les choses genre de loin de leurs codes de hachage. Et ce thêta de 1, cette moyenne cas d'être constante de temps, commence à devenir un peu plus-- à partir de tendre un peu plus vers thêta de n. Nous commençons à perdre ce avantage de tables de hachage. 

Ce problème que nous venons de voir est ce qu'on appelle le clustering. Et ce qui est vraiment mal regroupement est qu'une fois que vous maintenant avoir deux éléments qui sont côte à côté, il rend encore plus probable, vous avez le double de la hasard, que vous allez d'avoir une autre collision avec cette grappe, et le cluster va croître par un. Et vous allez continuer à grandir et grandir votre probabilité d'avoir une collision. Et finalement, il est tout aussi mauvais de ne pas trier les données du tout. 

L'autre problème est que nous encore, et jusqu'à présent, jusqu'à ce point, On vient de nous sorte de comprendre ce qu'est une table de hachage est, nous avons encore la place que pour 10 cordes. Si nous voulons continuer à hacher les citoyens de Springfield, nous ne pouvons obtenir 10 d'entre eux là-bas. Et si nous essayons et nous ajoutons un 11ème ou 12ème, nous ne disposons pas d'un endroit pour les mettre. Nous pourrions être juste Spinning Around dans cercles essayant de trouver un endroit vide, et nous sommes peut-être coincés dans une boucle infinie. 

Donc, ce genre de prête à l'idée de quelque chose appelé chaînage. Et voilà où nous allons apporter listes chaînées retour dans l'image. Et si au lieu de stocker tout les données elles-mêmes dans le réseau, chaque élément de la matrice pouvait contenir plusieurs morceaux de données? Eh bien cela n'a pas de sens, non? Nous savons qu'un tableau ne peut hold-- chaque élément d'un tableau ne peut contenir une seule pièce de données de ce type de données. 

Mais que faire si ce type de données est une liste liée, non? Alors que faire si tous les élément du tableau a un pointeur à la tête d'une liste chaînée? Et puis nous pourrions construire ces listes chaînées et de grandir arbitrairement, parce que les listes chaînées permettent nous de grandir et rétrécir beaucoup plus flexible qu'un tableau fait. Alors que faire si nous utilisons maintenant, nous misons sur cela, non? Nous commençons à cultiver ces chaînes en dehors de ces emplacements de tableau. 

Maintenant, nous pouvons adapter un infini quantité de données, ou pas infinie, une quantité arbitraire de données, dans notre table de hachage sans jamais courir dans le problème de la collision. Nous avons également éliminé regroupement en faisant cela. Et bien nous savons que lorsque nous insérons dans une liste chaînée, si vous vous souvenez de notre vidéo sur les listes chaînées, seuls listes chaînées et les listes doublement chaînées, il est une opération de constante de temps. Nous ne faisons qu'ajouter à l'avant. 

Et pour regarder en haut, bien que nous ne savons ce regard dans une liste chaînée peut être un problème, non? Nous avons à parcourir du début à la fin. Il n'y a pas aléatoire l'accès à une liste chaînée. Mais si au lieu d'avoir une liée liste où une recherche serait O n, nous avons maintenant 10 listes chaînées, ou 1.000 listes chaînées, maintenant il est de O n divisé par 10, O ou de n divisé par 1000. 

Et pendant que nous parlions théoriquement de la complexité on fait abstraction des constantes, dans le réel monde ces choses comptent vraiment, droit? Nous allons effectivement remarquer que tel est le cas de courir 10 fois plus rapide, ou 1000 fois plus rapide, parce que nous sommes distribuer une longue la chaîne à travers 1000 petites chaînes. Et chaque fois que nous avons à la recherche par une de ces chaînes que nous pouvons ignorer les 999 chaînes nous ne nous soucions pas à propos, et il suffit de chercher celui-là. 

Qui est, en moyenne, 1000 fois plus courte. Et si nous sommes encore sorte de tendant vers ce cas moyenne d'être constante de temps, mais seulement parce que nous misons divisant par un facteur constant énorme. Voyons comment cela pourrait effectivement regarder bien. Donc, ce fut la table de hachage nous avions avant, nous avons déclaré une table de hachage était capable de stocker 10 cordes. On ne va pas faire ça. Nous connaissons déjà la les limites de cette méthode. Maintenant, notre table de hachage va être un tableau de 10 nœuds, les pointeurs aux chefs de listes chaînées. 

Et maintenant il est nul. Chacun de ces 10 pointeurs est nulle. Il n'y a rien dans notre hash table en ce moment. 

Maintenant, nous allons commencer à mettre un peu choses dans cette table de hachage. Et nous allons voir comment cette méthode est va nous profiter un peu. Disons hacher maintenant Joey. Nous allons courir à travers la chaîne Joey une fonction de hachage et nous reviennent 6. Bien que faisons-nous maintenant? 

Eh bien travailler maintenant avec les listes chaînées, nous ne travaillons pas avec des tableaux. Et lorsque nous travaillons par des listes chaînées nous savons que nous devons commencer à dynamiquement l'allocation d'espace et de renforcement des chaînes. Voilà sorte de how-- ceux qui sont le noyau éléments de la construction d'une liste chaînée. Nous allons donc dynamiquement allouer de l'espace pour Joey, et puis nous allons l'ajouter à la chaîne. 

Alors maintenant, regardez ce que nous avons fait. Quand nous hachage Joey nous avons obtenu le hashcode 6. Maintenant le pointeur à l'emplacement du tableau 6 des points à la tête d'une liste chaînée, et maintenant il est le seul élément d'une liste chaînée. Et en ce que le noeud liste chaînée est Joey. 

Donc, si nous avons besoin de regarder Joey plus tard, nous venons de hachage nouveau Joey, nous obtenons 6 nouveau parce que notre fonction de hachage est déterministe. Et puis nous commençons à la tête de la liste liée souligné par emplacement de tableau 6, et nous pouvons itérer pour que d'essayer de trouver Joey. Et si nous construisons notre la table de hachage de manière efficace, et de notre fonction de hachage efficace pour distribuer des données de puits, en moyenne, chacun de ceux qui sont liés listes au niveau de chaque tableau sera 1/10 de la taille de si nous juste eu comme un seul grand liste chaînée avec tout ce qu'il. 

Si nous distribuons cette énorme liés liste dans 10 listes chaînées chaque liste sera 1/10 de la taille. Et donc 10 fois plus rapide à parcourir. Donc, nous allons le faire à nouveau. Voyons maintenant hacher Ross. 

Et disons Ross, quand nous faisons cela le code de hachage nous serons de retour est de 2. Eh bien maintenant, nous alloue dynamiquement un nouveau nœud, nous mettons Ross dans ce nœud, et nous disons maintenant l'emplacement de tableau 2, au lieu de pointer à null, des points à la tête d'un lien liste dont seul noeud est Ross. Et nous pouvons le faire une fois de plus, nous peut hacher Rachel et obtenir hashcode 4. malloc un nouveau nœud, mettre Rachel dans le noeud, et dire un emplacement de tableau 4 points maintenant à la tête d'une liste chaînée dont seul élément se trouve être Rachel. 

OK, mais ce qui arrive si nous avons une collision? Voyons comment nous traitons les collisions en utilisant la méthode de chaînage séparé. Disons hacher Phoebe. Nous obtenons le hashcode 6. Dans notre exemple précédent, nous étions juste mémoriser les chaînes du tableau. Ce fut un problème. 

Nous ne voulons pas tabasser Joey, et nous avons déjà vu que nous pouvons obtenir un certain regroupement problèmes si nous essayons de l'étape à travers et sonde. Mais que faire si nous avons juste un peu traiter ce de la même manière, non? Il est juste comme l'ajout d'un élément à la tête d'une liste chaînée. Voyons espace juste malloc pour Phoebe. 

Nous dirons prochaines pointeur de Phoebe à l'ancien chef de la liste chaînée, puis 6 points seulement à la nouveau chef de la liste chaînée. Et maintenant, regardez, nous avons changé de Phoebe. Nous pouvons maintenant stocker deux éléments avec hashcode 6, et nous ne disposons pas des problèmes. 

Voilà à peu près tout il est de chaînage. Et chaînage est certainement la méthode qui est va être le plus efficace pour vous si vous stockez des données dans une table de hachage. Mais cette combinaison de les tableaux et les listes chaînées ensemble pour former une table de hachage vraiment améliore considérablement votre capacité pour stocker de grandes quantités de données, et très rapidement et efficacement la recherche par ces données. 

Il ya encore une structure de données là-bas qui pourrait même être un peu mieux en termes de garantie que notre insertion, deletion, et Look Up fois sont encore plus rapides. Et nous verrons que, dans une vidéo sur essais. Je suis Doug Lloyd, cela est CS50.