Sans Pareil Technologies, Inc.

Key To Your Business

Lab 6 - Hash Table Implementations


We will look at three different implementations of hash tables using techniques discussed in the course.

For each of the implementations we will run a series of tests to compare the following characteristics of a hash table:
  • Number of occupied buckets
  • Number of items that overflowed.
  • Time to perform insertions into table
  • Time to iterate over table
  • Performance characteristics as number of items stored exceeds configured capacity of the table.
Common functions header for all the tests 
// functions.h
#pragma once

#include <algorithm>
#include <fstream>
#include <random>

namespace csc280::test
{
  static std::string const defaultChars =
    "abcdefghijklmnaoqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";

  static std::ofstream ofs( "test.txt", std::ofstream::out );

  inline std::string generateRandomString( std::size_t len = 15, const std::string& allowedChars = defaultChars )
  {
    std::mt19937_64 gen{ std::random_device()() };
    std::uniform_int_distribution<size_t> dist{ 0, allowedChars.length() - 1 };

    std::string ret;
    std::generate_n( std::back_inserter( ret ), len, [&] { return allowedChars[dist( gen )]; } );
    return ret;
  }
}