itérateurs dans les cartes non ordonnées (ou cartes de hachage)

Question

D'après ce que j'ai compris, les cartes de hachage sont préférables aux cartes standard car elles permettent de trouver des éléments en un temps proche de O(1). Cela se fait en utilisant un hachage ou la clé comme un tableau de recherche. Nous résolvons ensuite les collisions et extrayons la valeur.

Cela fonctionne très bien pour la recherche, mais si notre espace tableau dans lequel nous effectuons la recherche de hachage est peu peuplé, comment le hashmap/unorderedmap peut-il itérer efficacement tous les éléments de notre hashmap sans parcourir exhaustivement notre espace tableau ?

Edit : pourtant les hashmaps/cartes non ordonnées de Boost, SGI et C++11 ont des itérateurs, alors comment fonctionnent-ils ?

Answer 1

À moins qu'il n'y ait une structure parallèle (par exemple une liste chaînée comme dans un LinkedHashMap ), ce n'est pas possible : l'itération devra vérifier le contenu de chaque bac.

Ainsi, si vos godets sont très peu peuplée, cette peut deviennent un facteur. C'est l'une des raisons pour lesquelles il ne faut pas choisir un nombre de godets qui soit aussi élevée (la plus grande étant évidemment une perte de mémoire).

Answer 2

L'itération est O(n), où n est la capacité (c'est-à-dire le nombre de godets) de la carte. Mais normalement, vous ne devriez pas avoir une capacité de 100000 pour stocker 6 clés. Cela signifie que O(taille) devrait être O(capacité), ce qui signifie que l'itération est aussi normalement O(taille).