Fastest (lookup time) map for short keys


#1

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?


#2

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.


#3

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


#4

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.


#5

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


#6

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

See https://github.com/shepmaster/twox-hash/blob/master/README.md for an example.


#7

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.


#8

http://cglab.ca/~abeinges/blah/hash-rs/