Source code used in the hashing experiments of the thesis On the Analysis of Two Randomized Algorithms: Multi-Pivot Quicksort and Efficient Hash Functions. The code measures running time and cache behavior of the constructions, more cpu measures can be easily added.
The following hash functions are compared:
- Polynomial hashing (using the Carter-Wegman-Trick)
- Multiply-Shift
- Tabulation-Hashing
- Tabulation + Universal hashing (ADW)
- Murmur3
| Number of keys inserted | Tabulation (1 Byte Characters) | Tabulation (2 Bytes Characters) | Murmur3 | 3-independent Hashing | Tabulation + Universal |
|---|---|---|---|---|---|
| 4194304 | 286.32 ms | 293.20 ms | 312.13 ms | 375.00 ms | 510.35 ms |
The numbers show the average time it took to insert around 4 million keys into the cuckoo hash table using the specific hashing scheme see. (Threshold set very close to the theoretical limit at 49.995% load.) See the thesis for more results and details.
Needs g++, cmake in version >= 2.8, libboost-random and libpapi for performance measurements. (Enabled by default, can be changed in CMakeLists.txt.)
Use the following commands on the top-level directory of the project.
mkdir build; cd build cmake .. make
For a release build with optimization flags, use
cmake -DCMAKE_BUILD_TYPE=Release
After successful compilation, the executable is located at build/src/hashingtest.
Example calls can be found in the directory examples.
The output generated by the program can be directly read and processed using the beautiful SqlPlotTools.