HashMap vs Vec for integer lookups

This is maybe a generic programming question as opposed to Rust-specific, but since Rust also allows customizing the hasher function…

Use-case is wanting to use u32 as lookup ids, in three different scenarios:

  1. Unpredictable: Hashmap makes sense since allocating a Vec or Array would need to be too huge

  2. Predictable and within low ranges: say storing an attribute location lookup in a shader. Not sure of the exact limit, but let’s say pre-allocating an array of 1024 ints would cover it.

  3. Unpredictable but managable: say using like an Entity Component System where each item has a u32 for an id. These get assigned at runtime - but most likely it can be easily managed with relatively few allocations by growing a Vec by a certain capacity each time, and re-using dead ids (i.e. pooling).

I’m thinking that Hashmap is the right choice for the first scenario, an Array (set to a hard but padded limit like 1024, even if I just need 256) for the second, and Vec with some housekeeping for the third.

However - it might be that there’s a super simple hasher for numbers that makes Hashmap actually the better choice for scenario #3

Thoughts?

In my usecase (which might of course differ from yours in several aspects) I’ve found that I could keep my Vec ordered easily, so I could apply a binary search for lookup. That made it vastly faster than a HashMap or any other datastructure I’ve tried, and a Vec is just easy to work with. So check if you can do that, and benchmark it, I’d say :slight_smile:

1 Like

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.