I Wrote The Fastest Hashtable—Malte Skarupke

Save to:
Instapaper Pocket Readability

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

You must sign in or register to add a comment.

Comments (0)

There are currently no comments on this entry.