Une vidéo de la PyCon 2010 qui explique comment Python trouve rapidement une clé, ou si elle n’existe pas, sans recourir à un arbre binaire :
Si on regarde du coté de C++, ce qui se rapproche donc plus de l’implémentation de Python est donc le conteneur « unordered_map » standardisé dans C++11 qui se base aussi sur des tables de hachage pour ranger les clés. A ne pas confondre avec le traditionnel conteneur « map » qui maintient les clés classées par ordre croissant et utilise ensuite un arbre binaire pour la recherche de clé.
A noter que Python 3.6 utilise une méthode encore plus évoluée qui réduit la consommation mémoire des dictionnaires (détail)