Pourquoi Python utilise-t-il une table de hachage pour implémenter dict, mais pas Red-Black Tree? [fermé]

Pourquoi Python utilise-t-il une table de hachage pour implémenter dict, mais pas Red-Black Tree?

Quelle est la clé? Performance?

Il s'agit d'une réponse générale, non spécifique à Python.

Comparaison de complexité algorithmique

       | Hash Table  |   Red-Black Tree    |
-------+-------------+---------------------+
Space  | O(n) : O(n) | O(n)     : O(n)     |
Insert | O(1) : O(n) | O(log n) : O(log n) |
Fetch  | O(1) : O(n) | O(log n) : O(log n) |
Delete | O(1) : O(n) | O(log n) : O(log n) |
       | avg  :worst | average  : worst    |

Le problème avec les tables de hachage est que les hachages peuvent entrer en collision. Il existe différents mécanismes pour résoudre les collisions, par exemple l'adressage ouvert ou le chaînage séparé. Le pire des cas est que toutes les clés ont le même code de hachage, auquel cas une table de hachage se dégradera en une liste liée.

Dans tous les autres cas, une table de hachage est une excellente structure de données facile à implémenter et qui offre de bonnes performances. Un inconvénient est que les implémentations qui peuvent rapidement augmenter la table et redistribuer leurs entrées gaspilleront probablement autant de mémoire que ce qui est réellement utilisé.

Les RB-Trees sont auto-équilibrés et ne changent pas leur complexité algorithmique dans le pire des cas. Cependant, ils sont plus difficiles à mettre en œuvre. Leur complexité moyenne est également pire que celle d'une table de hachage.

Restrictions sur les clés

Toutes les clés d'une table de hachage doivent être lavables et comparables pour une égalité entre elles. Ceci est particulièrement facile pour les chaînes ou les entiers, mais est également assez simple à étendre aux types définis par l'utilisateur. Dans certains langages comme Java, ces propriétés sont garanties par définition.

Les clés d'un RB-Tree doivent avoir un ordre total: chaque clé doit être comparable à toute autre clé, et les deux clés doivent soit comparer plus petites, plus grandes ou égales. Cette égalité d'ordre doit être équivalente à l'égalité sémantique. C'est simple pour les entiers et autres nombres, également assez facile pour les chaînes (l'ordre n'a besoin que d'être cohérent et non observable en externe, donc l'ordre n'a pas besoin de prendre en compte les paramètres régionaux ^[1] ), mais difficile pour les autres types qui n'ont pas d'ordre inhérent . Il est absolument impossible d'avoir des clés de types différents à moins qu'une comparaison entre elles ne soit possible.

^{[1]: En fait, je me trompe ici. Deux chaînes peuvent ne pas être égales à l'octet mais être toujours équivalentes selon les règles de certains langages. Voir par exemple les normalisations Unicode pour un exemple où deux chaînes égales sont codées différemment. L'importance de la composition des caractères Unicode pour votre clé de hachage est quelque chose qu'une implémentation de table de hachage ne peut pas savoir.}

On pourrait penser qu'une solution bon marché pour les clés RB-Tree serait de tester d'abord l'égalité, puis de comparer l'identité (c.-à-d. Comparer les pointeurs). Cependant, cet ordre ne serait pas transitif: si a == bet id(a) > id(c), alors il doit suivre cela id(b) > id(c)aussi, ce qui n'est pas garanti ici. Donc, à la place, nous pourrions utiliser le code de hachage des clés comme clés de recherche. Ici, l'ordre fonctionne correctement, mais nous pourrions nous retrouver avec plusieurs clés distinctes avec le même code de hachage, qui seront attribuées au même nœud dans l'arborescence RB. Pour résoudre ces collisions de hachage, nous pouvons utiliser un chaînage séparé comme avec les tables de hachage, mais cela hérite également du comportement le plus défavorable pour les tables de hachage - le pire des deux mondes.

Autres aspects

• Je m'attends à ce qu'une table de hachage ait une meilleure localité de mémoire qu'un arbre, car une table de hachage n'est essentiellement qu'un tableau.

• Les entrées dans les deux structures de données ont une surcharge assez élevée:

  • table de hachage: clé, valeur et pointeur d'entrée suivante dans le cas d'un chaînage séparé. Le stockage du code de hachage peut également accélérer le redimensionnement.
  • RB-tree: clé, valeur, couleur, pointeur enfant gauche, pointeur enfant droit. Notez que bien que la couleur soit un seul bit, des problèmes d'alignement pourraient signifier que vous perdriez toujours assez d'espace pour presque tout un pointeur, ou même près de quatre pointeurs lorsque seuls des blocs de mémoire de taille deux peuvent être alloués. Dans tous les cas, une entrée d'arborescence RB consomme plus de mémoire qu'une entrée de table de hachage.

• Les insertions et les suppressions dans un arbre RB impliquent des rotations d'arbre. Ce ne sont pas vraiment coûteux, mais impliquent des frais généraux. Dans un hachage, l'insertion et la suppression ne sont pas plus coûteuses qu'un simple accès (bien que le redimensionnement d'une table de hachage lors de l'insertion soit un O(n)effort).

• Les tables de hachage sont intrinsèquement mutables, tandis qu'un arbre RB pourrait également être implémenté de manière immuable. Cependant, cela est rarement utile.

Il existe toute une série de raisons qui peuvent être vraies, mais les principales sont probablement:

• Les tables de hachage sont plus faciles à implémenter que les arbres. Ni l'un ni l'autre n'est tout à fait trivial, mais les tables de hachage sont un peu plus faciles, et l'impact sur le domaine des clés légales est moins strict car vous avez juste besoin d'une fonction de hachage et d'une fonction d'égalité; les arbres nécessitent une fonction d'ordre total, ce qui est beaucoup plus difficile à écrire.
• Les tables de hachage (peuvent) avoir de meilleures performances à de petites tailles. Cela est très important car une fraction importante du travail ne traite théoriquement que de grands ensembles de données; dans la pratique, une grande partie ne fonctionne qu'avec des dizaines ou des centaines de clés, pas des millions. Les performances à petite échelle sont très importantes et vous ne pouvez pas utiliser l'analyse asymptotique pour déterminer ce qui est le mieux là-bas; vous devez réellement mettre en œuvre et mesurer.

Plus facile à écrire / à maintenir et à gagner des performances dans des cas d'utilisation typiques? Inscrivez-moi, s'il vous plaît!