Je pense qu'il y a plusieurs raisons pour que le type « tableau associatif » du C++ soit un arbre binaire plutôt qu'une table de hachage. Entre autre choses il faut voir que cela date du début des années 90, quand il n'y avait même pas de standardisation du langage. Ensuite il faut voir qu'un arbre binaire c'est intellectuellement plaisant, et les gens qui ont produit la base du C++ à cette époque étaient plutôt intellos, du genre à considérer que tous les algos en O(n) se valent. À côté de ça une table de hachage c'est un peu bête : c'est juste un gros tableau. Et encore ça ne résout que la moitié du problème puisqu'il faut en plus lui donner une fonction de hachage rapide et avec peu de collisions. Pas simple. Dans le pire des cas on a une recherche en O(n) (toutes valeurs ont le même hash), là où l'arbre binaire est en O(log(n)) (qu'on va déguiser en O(1) en le qualifiant d'« amorti »).
[^] # Re: Héritage de std::map
Posté par Julien Jorge (site web personnel) . En réponse au lien Effortless Performance Improvements in C++: std::unordered_map. Évalué à 5.
Je pense qu'il y a plusieurs raisons pour que le type « tableau associatif » du C++ soit un arbre binaire plutôt qu'une table de hachage. Entre autre choses il faut voir que cela date du début des années 90, quand il n'y avait même pas de standardisation du langage. Ensuite il faut voir qu'un arbre binaire c'est intellectuellement plaisant, et les gens qui ont produit la base du C++ à cette époque étaient plutôt intellos, du genre à considérer que tous les algos en O(n) se valent. À côté de ça une table de hachage c'est un peu bête : c'est juste un gros tableau. Et encore ça ne résout que la moitié du problème puisqu'il faut en plus lui donner une fonction de hachage rapide et avec peu de collisions. Pas simple. Dans le pire des cas on a une recherche en O(n) (toutes valeurs ont le même hash), là où l'arbre binaire est en O(log(n)) (qu'on va déguiser en O(1) en le qualifiant d'« amorti »).