Fastest (lookup time) map for short keys


What is currently best performing (lookup time) map collection if my key is something like two i32 in a struct? From what I’ve seen it’s a HashMap, but it seems I should use custom Hash algorithm. Is it true, and if so which one?


rustc is using HashMap with a simple and fast hash function (FNV source). You can do the same, it’s just that using custom hashers is unstable at the moment, so you need the nightly channel compiler.


For keys <= 8 bytes it’s really hard to beat FNV as it’s super simple and small (thus inlined).


There’s a lot of fast (and relatively new) hashing contenders though, for example this benchmark, which includes farmhash, apparently google’s latest and fastest.


These benchmarks revolve around hashing longer streams of data. It’s entirely different story when hashing just single integers etc.


As dpc already said, it’s highly dependent on the size.

See for an example.


Those benchmarks had a plot of data size vs hash rate though, so it illustrates that nicely. Since farmhash for example has been designed to be fast even for small datums, I bet you’ll find it is faster than fnv.