Iterating over HashMap values compared to Vec

Question

In the program I'm currently writing (a game engine), I would like an efficient way to map integer values (IDs) to an array of objects. The data structure I see as most fit for this is a HashMap, but I would also like to be able to loop over the array of objects.

How much slower is it to iterate through the values of a HashMap using:

for val in map.values()

Compared to having a Vec and iterating over it:

for val in vec.iter()

and then having another system in place for mapping IDs to different indices of the vector?

Are there any other drawbacks to the HashMap approach?

Answer 1

Iterating over a HashMap will be slower, simply because the values are not as tightly packed in the HashMap: there are empty slots.

How many empty slots there are will depend on your usage, if you have high peak usage however iterating over a now mostly empty HashMap will be quite slower than iterating over a Vec which is much more compact.

For this particular usecase I would recommend indexmap which marries the good characteristics of both HashMap and Vec:

• the values are accessible by key, with performance similar to HashMap,
• the values are kept in a Vec, with no interleaving empty slot, so iterating has the same performance as iterating a Vec.