In this lab, you will be implementing a Hash Table that hashes the HashedObj type, which is another class that has a string key (no templates on this one). You will implement linear and quadratic probing, and double hashing.

----------------------------------------------------------------------------

HashTable.cpp

#include

#include "HashTable.h"

HashTable::HashTable(int _size, ResolutionType _resolutionFunction):

resolutionFunction {_resolutionFunction},

size {0}

{

v = std::vector{size_t(nextPrime(_size-1))};

}

// accessors -------------------

// will return the current capacity of the vector storing the HashEntrys

size_t HashTable::tableCapacity() const {

return v.capacity();

}

// normal hash for strings (we saw in class)

// Takes a HashedObj and will return a hash value.

// NOTE: this does not ensure it is within range of the

// tablesize, and therefore your code should ensure it is

// after calling this function.

int HashTable::hash (const HashedObj& x) const {

unsigned int hashVal= 0;

for (int i = 0; i < std::min(3,int(x.key.size())); ++i){

hashVal = 37*hashVal + x.key[i];

}

return hashVal;

}

// a handy resolution-function selector method.

// Since we store the resolution type as part of the hash table,

// we can just call this function in place of

// linearResolution, quadraticResolution, or doubleHashResolution.

// Takes:

// i: resolution number (i.e. # of collisions occurred)

// x: HashedObj to hash on. Note this is only needed by

// doubleHashResolution().

// Returns:

// int that is a hash value offset for resolution.

int HashTable::resolution (int i, const HashedObj& x) const {

if (resolutionFunction == LINEAR){

return linearResolution(i);

} else if (resolutionFunction == QUADRATIC) {

return quadraticResolution(i);

} else {

return doubleHashResolution(i, x);

}

}

// computes the ith linear resolution offset

int HashTable::linearResolution (int i) const {

// CODE HERE

return -1; // PLACEHOLDER

}

// computes the ith quadratic resolution offset

int HashTable::quadraticResolution (int i) const {

// CODE HERE

return -1; // PLACEHOLDER

}

// computes the ith double hash resolution of x

int HashTable::doubleHashResolution (int i, const HashedObj& x) const {

// CODE HERE

return -1; // PLACEHOLDER

}

// second hash function for double hashing. The prime number used can be

// any prime number that satisfies the criteria (what is the criteria for

// for second hash function?)

int HashTable::hash2 (const HashedObj& x) const {

// CODE HERE

return -1; // PLACEHOLDER

}

// takes a HashedObj x and will return a bool; true if x is

// in the table and false if it is not in the table.

bool HashTable::contains (const HashedObj& x) const {

// CODE HERE

return false; // PLACEHOLDER

}

// prints the private table v.

// Used primarily for testing.

void HashTable::printAll() const {

std::cout << "[ ";

for (HashEntry a : v){

std::string blah;

if (!a.element.key.compare("") || a.info == DELETED){

blah = "_";

} else {

blah = a.element.key;

}

std::cout << blah << " ";

}

std::cout << "]" << std::endl;

}

// computes the sieve of eratosthenes and returns the next prime

// higher than the input x. There are several more efficient ways to

// find the next prime, see the second answer here:

// http://stackoverflow.com/questions/4475996/given-prime-number-n-compute-the-next-prime

int HashTable::nextPrime (int x) const {

// CODE HERE

return -1; // PLACEHOLDER

}

// mutators -----------------------------------------------------

// empties the table, and must use /lazy deletion/

void HashTable::makeEmpty(){

// CODE HERE

}

// inserts HashedObj x into the table, if it is not already in table.

// Should call the resolution selector function above.

bool HashTable::insert(const HashedObj& x){

// CODE HERE

return false; // PLACEHOLDER

}

bool HashTable::insert(HashedObj&& x){

HashedObj y {x};

return insert(y);

}

// removes the specified object if it is active in the table and returns true.

// If it is not found (i.e. finds an EMPTY position), then it returns false.

bool HashTable::remove(const HashedObj& x){

// CODE HERE

return false; // PLACEHOLDER

}

// first computes the load factor for the table. If it is not too large,

// return from function. Else:

// finds the next prime after doubling the tablesize, and resizes the table

// v to that size. then it iterates over the old values and rehashes the

// ACTIVE ones into the new table.

void HashTable::rehash(){

// CODE HERE

}

----------------------------------------------------------------------------

HashTable.h

#ifndef HASHTABLE_H

#define HASHTABLE_H

#include "HashedObj.h"

#include

#include

#include

class HashTable {

public:

enum EntryType {ACTIVE, EMPTY, DELETED};

enum ResolutionType {LINEAR, QUADRATIC, DOUBLE};

explicit HashTable(int size = 101,

ResolutionType resolution = LINEAR); // init to prime

// accessors

size_t tableCapacity() const;

int hash (const HashedObj& x) const;

int resolution (int i, const HashedObj& x) const;

int linearResolution (int i) const;

int quadraticResolution (int i) const;

int doubleHashResolution (int i, const HashedObj& x) const;

int hash2 (const HashedObj& x) const;

bool contains (const HashedObj& x) const;

void printAll() const;

int nextPrime (int x) const;

// mutators

void makeEmpty();

bool insert(const HashedObj& x);

bool insert(HashedObj&& x);

bool remove(const HashedObj& x);

void rehash();

private:

struct HashEntry

{

HashedObj element;

EntryType info;

HashEntry(const HashedObj& e = HashedObj{}, EntryType i = EMPTY) :

element {e},

info {i} {}

HashEntry(HashedObj&& e, EntryType i = EMPTY) :

element {std::move (e)},

info {i} {}

};

int size;

std::vector v;

const ResolutionType resolutionFunction;

};

#endif