This is Malte's third article on hash table design. His solution shows favorable performance against std::unordered_map
, boost::multi_index
, google::dense_hash_map
, and more. Malte includes intuitive descriptions of why each design decision was made and what tradeoffs might exist. The article also describes some interesting artifacts in the implementations of other hash table implementations.
I Wrote The Fastest Hashtable
by Malte Skarupke
From the article:
There are many types of hashtables. For this one I chose
- Open addressing
- Linear probing
- Robing hood hashing
- Prime number amount of slots (but I provide an option for using powers of two)
- With an upper limit on the probe count
I believe that the last of these points is a new contribution to the world of hashtables. This is the main source of my speed up, [...]
Add a Comment
Comments are closed.