Skip to content
Snippets Groups Projects
Select Git revision
  • benchmark-plot
  • main default protected
2 results

hashtable-open-addressing

  • Open with
  • Download source code
  • Your workspaces

      A workspace is a virtual sandbox environment for your code in GitLab.

      No agents available to create workspaces. Please consult Workspaces documentation for troubleshooting.

    • Name Last commit Last update
    plot
    src
    tests
    .gitignore
    CMakeLists.txt
    readme.md
    readme.md

    A hashtable implementation using open addressing.

    Dependencies

    • Google Tests (tests/CMakeList.txt assumes /usr/src/gtest)

    Building

    Create a build folder and run cmake/make.

    mkdir build && cd build
cmake ..
make # makes everything
make hashtable # builds only lib/libhashtable.a

    Tests

    Run make test after make or execute the test_* binaries in bin/.

    Benchmark

    Run bin/benchmark, e.g.:

    $ bin/benchmark 10000000
Inserting integers from 1 to 10000000 into different hashtables.
All measurements are averages over 10 runs.

Table: hashing by division, linear probing, alpha: 0.5, s: 2
Time: 0.259487s, size: 10000000, capacity: 33554432, alpha: 0.298023

Table: hashing by division, linear probing, alpha: 0.5, s: 4
Time: 0.264414s, size: 10000000, capacity: 67108864, alpha: 0.149012

Table: hashing by division, linear probing, alpha: 0.75, s: 2
Time: 0.182584s, size: 10000000, capacity: 16777216, alpha: 0.596046

Table: hashing by division, quadratic probing, alpha: 0.5, s: 2
Time: 0.261645s, size: 10000000, capacity: 33554432, alpha: 0.298023

Table: hashing by division, quadratic probing, alpha: 0.5, s: 4
Time: 0.266709s, size: 10000000, capacity: 67108864, alpha: 0.149012

Table: hashing by division, quadratic probing, alpha: 0.75, s: 2
Time: 0.18543s, size: 10000000, capacity: 16777216, alpha: 0.596046

Table: hashing by division, double hashing, alpha: 0.5, s: 2
Time: 0.258031s, size: 10000000, capacity: 33554432, alpha: 0.298023

Table: hashing by division, double hashing, alpha: 0.5, s: 4
Time: 0.263584s, size: 10000000, capacity: 67108864, alpha: 0.149012

Table: hashing by division, double hashing, alpha: 0.75, s: 2
Time: 0.182143s, size: 10000000, capacity: 16777216, alpha: 0.596046

Table: hashing by multiplication, linear probing, alpha: 0.5, s: 2
Time: 2.34331s, size: 10000000, capacity: 33554432, alpha: 0.298023

Table: hashing by multiplication, linear probing, alpha: 0.5, s: 4
Time: 2.26132s, size: 10000000, capacity: 67108864, alpha: 0.149012

Table: hashing by multiplication, linear probing, alpha: 0.75, s: 2
Time: 1.89938s, size: 10000000, capacity: 16777216, alpha: 0.596046

Table: hashing by multiplication, quadratic probing, alpha: 0.5, s: 2
Time: 5.27264s, size: 10000000, capacity: 33554432, alpha: 0.298023

Table: hashing by multiplication, quadratic probing, alpha: 0.5, s: 4
Time: 4.91861s, size: 10000000, capacity: 67108864, alpha: 0.149012

Table: hashing by multiplication, quadratic probing, alpha: 0.75, s: 2
Time: 4.98173s, size: 10000000, capacity: 16777216, alpha: 0.596046

Table: hashing by multiplication, double hashing, alpha: 0.5, s: 2
Time: 19.5598s, size: 10000000, capacity: 33554432, alpha: 0.298023

Table: hashing by multiplication, double hashing, alpha: 0.5, s: 4
Time: 18.4405s, size: 10000000, capacity: 67108864, alpha: 0.149012

Table: hashing by multiplication, double hashing, alpha: 0.75, s: 2
Time: 15.5715s, size: 10000000, capacity: 16777216, alpha: 0.596046

    Results

    Barplot of the benchmark results