A comparison of the performance of different hash functions for Cuckoo Hashing
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
examples Initial code commit Mar 2, 2018
src
CMakeLists.txt Initial code commit Mar 2, 2018
LICENSE Initial commit Mar 2, 2018
README.md Update README.md Mar 2, 2018

README.md

Performance of different hash functions in Cuckoo Hashing

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.

Hashing Functions

The following hash functions are compared:

  • Polynomial hashing (using the Carter-Wegman-Trick)
  • Multiply-Shift
  • Tabulation-Hashing
  • Tabulation + Universal hashing (ADW)
  • Murmur3

Results

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.

Dependencies

Needs g++, cmake in version >= 2.8, libboost-random and libpapi for performance measurements. (Enabled by default, can be changed in CMakeLists.txt.)

How to build

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.

Examples

Example calls can be found in the directory examples.

Evaluation

The output generated by the program can be directly read and processed using the beautiful SqlPlotTools.