iterators in Unordered (or Hash) Maps

As far as I understand, Hashmaps are preferable to standard maps because you can find elements in close to O(1) time. This is done by using a hash or the key as an array lookup. We then resolve any collisions and pull out the value.

This works great for lookup, but if our array-space into which we do the hash lookup is sparsely populated, how does the hashmap/unorderedmap efficiently iterate all the elements in our hashmap without exhaustively going 开发者_开发知识库through our array-space?

Edit: yet Boost, SGI and C++11 hashmaps/unordered maps have iterators, so how do they work?

Unless there's a parallel structure (for example a linked list as in a LinkedHashMap) it can't: iteration will need to check each bucket for content.

So if your buckets are very sparsely populated, this can become a factor. That's one of the reasons why you don't want to choose a bucket count that is too high (the bigger one obviously being wasted memory).

The iteration is O(n), where n is the capacity (i.e. the number of buckets) of the map. But normally, you shouldn't have a capacity of 100000 to store 6 keys. This means that O(size) should be O(capacity), which means that iteration is also normally O(size).