Une brève discussion sur les dictionnaires et les tables de hachage en Python et la résolution des conflits de hachage

Le contenu de cet article concerne une brève discussion sur les dictionnaires et les tables de hachage en Python et sur la résolution des conflits de hachage. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Python utilise des tables de hachage pour implémenter dict.

Une table de hachage est en fait un tableau clairsemé (un tableau qui contient toujours des éléments vides est appelé un tableau clairsemé). Dans les livres généraux, les unités d'une table de hachage sont généralement appelées compartiments. exister dicter Dans la table de hachage, chaque paire clé-valeur occupe un élément de table et chaque élément de table comporte deux parties, l'une est une référence à la clé et l'autre est une référence à la valeur. Étant donné que chaque cellule du tableau a la même taille, vous pouvez lire une cellule du tableau par décalage.

Python essaiera de s'assurer qu'environ un tiers des éléments de la table sont vides. Lorsque ce seuil est presque atteint, il développera et copiera la table de hachage d'origine dans une table de hachage plus grande.

Si vous souhaitez mettre un objet dans une table de hachage, vous devez d'abord calculer la valeur de hachage de la clé de l'élément. Cela nécessite que la clé soit hachable.

Un objet hachable doit remplir les conditions suivantes :

Prend en charge la fonction hash() et la valeur de hachage obtenue par la méthode __hash__() est inchangée.

Prend en charge la détection d'égalité via la méthode __eq__().

Si a == b est vrai, alors hash(a) == hash(b) est également vrai.

Ce qui suit explique principalement l'algorithme de la table de hachage.

Pour obtenir la clé La valeur search_value correspondant à search_key, Python appellera d'abord hash(search_key) pour calculer clé_de recherche La valeur de hachage de la valeur, les chiffres les plus bas de cette valeur sont utilisés comme décalages et l'élément de table est recherché dans la table de hachage (le nombre spécifique dépend de la taille de la table de hachage actuelle). Si l'élément de table trouvé est vide, une KeyError est levée Exception ; s'il n'est pas vide, il y aura une paire de found_key:found_value dans l'élément table, vérifiez search_key et found_key S'ils sont égaux, si tel est le cas, renvoyez found_value. S’ils ne sont pas égaux, cette situation est appelée collision de hachage.

Afin de résoudre le conflit de hachage, l'algorithme prendra quelques bits supplémentaires dans la valeur de hachage, puis la traitera avec une méthode spéciale et utilisera la nouvelle valeur obtenue comme décalage pour rechercher dans l'élément de table de table de hachage, si l'élément de table trouvé est vide, une exception KeyError sera également levée s'il n'est pas vide, comparez les clés pour voir si elles sont cohérentes et renvoyez la valeur correspondante si elles sont cohérentes ; Un conflit de hachage est détecté, répétez les étapes ci-dessus.

Le processus d'ajout d'un nouvel élément est presque le même que ci-dessus, sauf que lorsqu'un élément de table vide est trouvé, le nouvel élément sera inséré. S'il n'est pas vide, le hachage sera répété et la recherche continuera.

Allez-y Lorsqu'un nouvel élément est ajouté au dict et qu'un conflit de hachage se produit, le nouvel élément peut être organisé pour être stocké dans un autre emplacement. La situation suivante se produira donc : dict([key1, valeur1], [clé2, valeur2]) et dict([clé2, valeur2], [clé1, valeur1]) Deux dictionnaires sont égaux lorsqu'on les compare, mais si les hachages de key1 et key2 sont en conflit, l'ordre des deux clés dans le dictionnaire est différent.

À chaque fois, partez Ajouter de nouvelles clés à dict, python L'analyseur peut décider d'étendre le dictionnaire. Le résultat de l'expansion est de créer une table de hachage plus grande et d'ajouter des éléments existants dans le dictionnaire à la nouvelle table de hachage. De nouveaux conflits de hachage peuvent survenir au cours de ce processus, entraînant une modification de l'ordre des clés dans la nouvelle table de hachage. Que se passe-t-il si vous parcourez un dictionnaire tout en y ajoutant de nouvelles clés ? Malheureusement, la capacité a été agrandie. Malheureusement, l'ordre des clés a changé, puis. orz.

Étant donné que la table de hachage doit être clairsemée, sa consommation d'espace doit être beaucoup plus importante. Il s'agit d'un compromis espace-temps typique.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!