Jusqu'à maintenant, nous avons couvert les types séquences, avec notamment les listes, les chaînes de caractères et les tuples. Dans cette vidéo, nous allons parler des tables de hash, une structure de données qui permet de répondre à certaines limitations des types séquences. Ouvrons un interpréteur Python pour commencer à découvrir ces limitations.

Les types séquences ont été optimisés pour l'accès, la modification et l'effacement en fonction d'un numéro de séquence. Cependant, ces types n'ont pas été optimisés pour le test d'appartenance. Regardons un exemple pour illustrer cela.

Je vais utiliser l'instruction *timeit*, qui me permet de calculer le temps d'exécution d'une expression, et je vais regarder si la chaîne de caractères 'x' est dans range de 100. En fait, range de 100 va produire des entiers allant de 0 à 99, x n'étant pas dedans, je vais être obligé de parcourir chaque élément pour vérifier que x n'est pas dans cet élément. Faisons le test, et on voit que le temps d'exécution est de l'ordre de 2,33 microsecondes. Évidemment, c'est rapide. Mais maintenant, prenons un range qui est plus grand et multiplions-le par 100. Donc au lieu de prendre 100, je vais prendre 10 000. J'utilise au passage la notation underscore dans les entiers qui me permet de découper mon entier pour faciliter sa lecture. Donc on voit que j'ai dix et mille, j'ai bien un entier qui vaut dix mille. Faisons le test d'appartenance et regardons combien de temps cela prend, cela prend 284 microsecondes. Donc c'est à peu près 100 fois plus lent. Multiplions encore par 100 cette séquence et prenons maintenant un million. Je réexécute mon timeit, et regardons le temps d'exécution: 28 millisecondes. C'est de nouveau 100 fois plus lent. On voit clairement que l'opération de test d'appartenance sur une séquence est linéaire en fonction du nombre d'éléments que j'ai dans ma séquence. Là, évidemment, j'ai pris le cas le plus défavorable mais c'est la complexité du test d'appartenance sur la liste qui est linéaire avec le nombre d'éléments. Ça, c'est un problème parce qu'en fait le test d'appartenance est quelque chose de tellement commode qu'on aimerait pouvoir faire un test d'appartenance qui est indépendant du nombre d'éléments.

Une deuxième limitation des séquences est la suivante: vous savez que si je prends une séquence *t*qui est une liste qui contient deux éléments, [1, 2], je peux accéder au premier élément en faisant *t[0]*. Mais maintenant, supposons que dans ma séquence, dans ma liste, j'ai des âges, et que par exemple j'écrive t égale 18 et 35. Je pourrais très bien vouloir au lieu de faire t de 0 égale 18 écrire t de Alice ; je reprends : écrire *t['Alice'] = 35*pour lier un nom à un âge, donc “indicer” mes séquences non plus avec des entiers mais avec par exemple des chaînes de caractères. Et bien ça, je ne peux pas le faire ; j'ai donc une erreur qui me dit que les indices des listes doivent être des entiers ou des slices mais pas des chaînes de caractères. La structure de données table de hash permet de répondre à ces deux limitations.

Commençons par regarder comment fonctionne une table de hash et dans de prochaines vidéos, nous regarderons comment est-ce qu'elles sont implémentées en Python. Regardons maintenant le fonctionnement de ces tables de hash. Je vais vous présenter ici évidemment une version simplifiée du fonctionnement des tables de hash mais dont le but est de vous faire comprendre le fonctionnement de cette structure de données. Essentiellement, une table de hash est constituée d'un tableau ; nous avons ici un tableau avec 6 éléments, et d'une fonction dont le but est le suivant: lorsque je passe à ma fonction un objet elle va me calculer une valeur qui va être comprise entre 1 et 6. Essentiellement le but de cette fonction est de créer une correspondance entre un objet quelconque et une case dans mon tableau. Regardons maintenant ce fonctionnement, cet ensemble fonction de hash et tableau constitue ce qu'on appelle une table de hash. Maintenant supposons que je veuille ajouter la chaîne de caractères 'eve', que je veuille créer une correspondance entre 'eve' et l'âge 34. Comment ça va fonctionner ? Je vais passer ce qu'on appelle une clé, la clé étant ce que je spécifie entre crochets, et je vais associer cette clé à ce qu'on appelle une valeur. Ce que j'ai entre crochets s'appelle la clé ce que j'ai après le signe = s'appelle la valeur. Je vais passer 'eve' à ma fonction de hash, ma fonction de hash va faire un calcul sur cet objet, et va me retourner une case dans le tableau, ici la case 2. Et je vais écrire ici le couple 'eve', 34. Ensuite, je fais t de 'bob' ; t de 'bob', ça veut dire que la clé est 'bob' et la valeur est 27 ; je passe 'bob' à ma fonction de hash, ça va me retourner une nouvelle case la case 4, et je vais stocker le couple 'bob', 27 dans mon tableau. Ensuite, si je veux accéder à 'eve', je vais simplement faire t de 'eve', par exemple, un print t de 'eve' ; je vais repasser 'eve' à ma fonction de hash ; ma fonction de hash va faire le même calcul, elle va donc arriver à la même case, je vais obtenir la case 2 du tableau, et je vais pouvoir afficher 'eve', 34, je vais donc afficher la valeur correspondant à 'eve' qui est la valeur 34. On voit donc que dans une table de hash l'insertion, l'effacement, la recherche d'élément sont indépendants du nombre d'éléments, c'est conditionné par la vitesse de la fonction de hash. Je fais un calcul et j'obtiens directement la case où est stockée la valeur correspondant à la clé.

Maintenant, regardons le cas suivant: je fais t de 'jo' égale 46. En fait, vous comprenez bien que dans mon tableau, je n'ai que 6 cases disponibles ; dans une vraie table de hash, j'aurai évidemment plus d'éléments, mais le nombre d'éléments est limité. Au bout d'un moment, je vais avoir ma fonction de hash qui va retourner une case qui est déjà occupée. Regardons ce qu'il se passe. t de 'jo' égale 46, ma fonction de hash me retourne la case 2. Je vais donc stocker 'jo', 46 dans cette table de hash à la suite de l'autre clé 'eve' associée à sa valeur 34. Si maintenant je fais un t de 'jo', qu'est-ce qu'il va se passer ? Je vais aller chercher 'jo' avec ma fonction de hash qui va toujours me retourner la case n°2, et je vais regarder est-ce que 'jo' est la clé correspondant au premier couple non je vais donc passer au deuxième couple ; est-ce que 'jo' est la clé correspondant au deuxième couple ? oui Je retourne donc la valeur 46.

Vous voyez donc que l'efficacité d'une table de hash est conditionnée non seulement par la taille du tableau, si j'ai un tableau trop petit je vais avoir beaucoup de ce qu'on appelle des collisions, une collision , c'est lorsque deux clés correspondent à la même entrée dans le tableau, et l'efficacité de ma table de hash est également conditionnée à la capacité de ma fonction de hash à bien répartir les clés dans les différentes cases du tableau. Évidemment, cette efficacité de fonction de hash, cette capacité de la fonction de hash à bien répartir les clés, est une caractéristique majeure d'une table de hash efficace. En Python, il faut savoir que les tables de hash ont été implémentées de manière très efficace ; vous n'avez pas à vous préoccuper de cette fonction de hash, vous n'avez pas à vous préoccuper de la taille du tableau ; Python va automatiquement gérer ça pour vous de manière à ce que vous ayez une efficacité qui soit excellente. Donc, essentiellement, vous pouvez faire l'hypothèse qu'en Python, les tables de hash vous permettent d'avoir un temps d'accès, un temps d'insertion, un temps d'effacement et un temps de recherche qui soient indépendants du nombre d'éléments.

Les tables de hash vous permettent d'accéder, d'effacer, de modifier, mais également de faire des tests d'appartenance avec une complexité qu'on appelle O(1) qui veut essentiellement dire que c'est indépendant du nombre d'éléments dans notre table de hash. C'est donc une structure de données très intéressante et qui permet également d'indexer des valeurs non pas avec des entiers comme dans une séquence, mais avec par exemple des chaînes de caractères. En Python, nous avons deux implémentations de tables de hash que sont les sets et les dictionnaires que nous allons voir dans une prochaine vidéo.