is linear search faster than HashMap/HashSet for small sets?

published 2026-07-24 | tags: #gamedev #bevy #rust

I've heard from multiple sources that when you are operating on small sets, performance matters, like in the hot-path in a game that runs every frame, it is often better to use a Vec or some sort of array and to linearly search through the data through the data instead of using a HashSet or HashMap. The rationale is that while hash-based fetches and inserts are constant time, that may be a high enough constant time that just ripping through the array is faster. At some [small] size it must be faster to just iterate through the array instead of hashing a value...

So is it?

To test this out I made simple VecSet and VecMap that implement a limited subset of the HashSet and HashMap API, namely insert, remove, get, and iter. My implementation also went the route of storing Option<T> and Option<(K,V)> for Set and Map respectively, so I added a compact() method to remove None values from the storage; I could have done a swap_remove instead of Option, since order doesn't matter, but I don't think it will really matter; our tests don't do much get and set so we don't generate many empty holes.

Aside: Why are we using Maps and Sets in a game?

Both Hash and Vec Map/Sets tend to allocate memory on the heap which I also hear is bad for games. Especially if you are allocating new memory every frame, the time to allocate memory (it is said) can dominate your frame time, drastically lowering your FPS.

In Bevy it's much more idiomatic to just make everything a Query, and do a for (a, b, c) in query.iter() or for (mut a, b, c) in query.iter_mut().

So why do we need a Map or a Set? Basically: memoization.

I often want to ask questions like "What entities are near this entity?" which falls into the category of "You can derive this from existing components, but there isn't a component to make this a Query'able directly."

fn my_system(
  query: Query<Entity, With<???>>,
  // ...
) {
  // What would this look like??
  // ...
}

so instead we build a little cache every time the system executes:

fn my_system(
  foos: Query<(Entity, &Coordinates), With<Foo>>,
  bars: Query<(Entity, &Coordinates), With<Foo>>,
  mut near_map: Local<HashMap<Entity, usize>>,
) {
  // Build the HashMap of Entity -> Number of neighbors
  // (Yes I prefer `query.iter().chain().things(|foo| ...)` over `for thing in query`)
  near_map = foos.iter().map(|(e_foo, c_foo)| {
    // Filter to just bar coordinates near foo's coordinates
    // Sum the resulting set of 1s
    let near_foo = bars
      .iter()
      .filter_map(|(e_bar, c_bar)| do_check(c_foo, c_bar).then_some(0))
      .sum();
    // Return a tuple of (Entity, usize)
    ( e_foo, near_foo )
  }).collect();

  // ... use near_map ...
}

This both gives me a nice computed lookup table, and using Bevy's Local<T> ensures I don't re-allocate memory every frame, assuming I don't you know... overlook something.

Benchmarking

• I got Claude to write some benchmarks comparing VecSet vs HashSet and VecMap vs HashMap at different data volumes, 4, 8, etc up to 1024 elements
• Data was always u64s for keys and values
• Comparing against Bevy's collections library which uses the non-standard FixedHasher
• Optimizations turned on
• All value are in nanoseconds.

VecSet vs HashSet

Winner is the fast implementation.

VecMap vs HashMap

jUsT uSe RaYoN

After the initial results I thought "surely we can parallelize the linear search right? Rayon makes things fast right?!" and did a side-quest adding a par_* version of the VecSet/VecMap types using Rayon as the underlying engine. Here are those results:

As it turns out, Rayon has hella overhead so for small sets like this the startup cost way overshadows the compute time. Rayon took at least 11-12 µs which makes it much slower at these small sizes.

Takeway: Rayon is great for processing lots of data, like in batch jobs.

wHaT aBoUt MiCroPoOl

I heard about a cool library that's basically "Rayon for Games" called micropool. The main selling point is that it avoids some of the pitfalls of Rayon.

The results were interesting!

contains — miss (ns):

remove one (ns):

Micropool was better than Rayon but still not nearly good enough to beat an optimized build for either Hash nor Vec implementation.

Takeaways

• Use VecMap and VecSet when I want to memoize a set and iterate over every element sequentally.

• Use HashMap and HashSet if you intend to search for specific elements in the set.

Notes

A few admissions:

1. I didn't test this against Bevy's Query nor did I test it against Rust's stdlib DefaultHasher, which I expect to perform worse but that would just move the line not change the story.

2. We could probably improve search performance in the Vec* implementations to get better performance, like sorting elements or... something. That wasn't the point of this exploration though. The bit is to see if we are leaving an obvoius naive optimization on the table.

3. It's tempting to turn VecSet and VecMap into a library, if it isn't already, but I promise it was a very quick type to implement, and even after building it out I'm not using it in my game because the use-case for it is niche enough that I haven't actually needed it.

Conclusion

So in conclusion... wait -- now that I think about it... a set that you always want to iterate over is... a Vec. So this is basically nothing! This is just Vec with more steps!

Happy hacking~