stl hash map

ce que je sais c que la difference entre une map est une multimap, c au niveau des doublons
mais quelle difference y a t il entre les deux conteneurs precedants et la hash_map ???

Une hash_map n'est pas triée, et son acces est généralement plus rapide (généralement simplifié en O(1) au lieu de O(Log N)).

Par contre, j'ignore si elle peut ou non contenir des doublons, mais j'en doute.

Salut,

L'un des premiers liens fournis par google est http://www.sgi.com/tech/stl/hash_map.html

Assez bizarement, la description qui en est donnée sur cette page ressemble énormément à la map :P

Une autre recherche essayant de mettre les deux en parallelle semble indiquer que le but de la hash_map est d'améliorer le temps de recherche par rapport à la map:P

Mais la litérature que j'ai trouvée ne semble pas indiquer précisement comment ils comptent s'y prendre :P

std::map est un arbre binaire ordonné (enfin, c'est juste une conséquence de ses spécifications dans la norme), la recherche est donc en temps logarithmique puisqu'il faut au pire des cas parcourir toute la hauteur de l'arbre.

hash_map est une table de hachage, càd que la clé donne directement l'indice de l'élément correspondant par hachage (les algorithmes de hachages pour les types courants sont bien connus), ce qui implique le temps de recherche en temps constant. Selon le type de table de hachage, les collisions (plusieurs clés ayant la même valeur de hachage) peuvent être gérées, dans ce cas une clé renverra non pas à un élément, mais à une liste d'éléments.

Voir un cours d'algo / structures de données pour plus de détails.