I recently stumbled across the wild world of hashmaps when I was writing a chapter about how dictionaries are implemented in Python and fell down a pretty deep rabbit hole. Intruiged, I set out to determine whether I myself could write a hashmap faster that would rival or potentially even surpass the performance of std::unordered_map.
The Makefile in the main directory holds all of the commands to compile, run, and clean up the code. There are three main commands:
- make all: This will compile all of the correctness tests and the benchmarking script.
.ofiles will be compiled to theout/folder and executables will be compiled to thebin/folder. - make test: This will run all four test files. The last script to run will be the benchmarking code. You can also run the executables yourself, but I like running correctness code whenever I make changes so it's a handy command
- make clean: This will clear out the object files, the executable files, and the
.csvbenchmarking outputs.
The first map that I made was a linear probe hashmap with tombstones for removal. This lives in linear_map2.hpp.
The second map I made was a Robinhood hashmap that uses backwards shifting for removal. This lives in robinhood_map.hpp
The third map I made was a modification of the tombstone LinearMap above. I modified the backwards shifting algorithm for Robinhood hashmaps to work for linear maps. The goal was to create a linearly probed hashmap with the same removal average-case time as Robinhood Hashing without the overhead of swapping for a boost in speed. This lives in linear_map.hpp.
A more in-depth analysis of my hashmaps and descriptions of my tests can be found in the file benchmark.ipnyb. Here are the final graphs of my performance:
