In this lab, you will be implementing a Hash Table that hashes the HashedObj typ
ID: 3917496 • Letter: I
Question
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 <cassert>
#include "HashTable.h"
HashTable::HashTable(int _size, ResolutionType _resolutionFunction):
resolutionFunction {_resolutionFunction},
size {0}
{
v = std::vector<HashEntry>{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 <iostream>
#include <vector>
#include <cmath>
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<HashEntry> v;
const ResolutionType resolutionFunction;
};
#endif
Explanation / Answer
HashTale.cpp
#include "HashTable.h"
HashTable::HashTable(int _size,ResolutionType _resolutionFuction):
resolutionFunction {_resolutionFuction},
size{_size},
numItems{0}{
v= std::vector<HashEntry>{size_t(_size)};
}
// accessors
int HashTable::hash (const HashedObj& x) const {
int hashVal{0};
std::string key = x.key.substr(0,3);
for(char ch : key){
hashVal = hashVal*37 + ch;
}
return hashVal % size;
}
int HashTable::linearResolution (int i) const {
return i;
}
int HashTable::quadraticResolution (int i) const {
return i * i;
}
// needs an extra parameter to call the second hash function, hash2
int HashTable::doubleHashResolution (int i, const HashedObj& x) const {
return i * hash2(x);
}
int HashTable::hash2 (const HashedObj& x) const {
int secondLowestPrime = size;
//std::cout<<size<<std::endl;
int numDivis = -1;
while ( numDivis!=0){
numDivis = 0;
secondLowestPrime--;
int thisNum = secondLowestPrime-1;
while(thisNum>1 && numDivis==0){
if((secondLowestPrime % thisNum) == 0)
numDivis++;
thisNum--;
}
}
//std::cout<<secondLowestPrime<<std::endl;
return secondLowestPrime - (hash(x) % secondLowestPrime);
}
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);
}
bool HashTable::contains (const HashedObj& x) const{
// CODE HERE
int hashVal = hash(x);
int i = 0;
while((v[(hashVal + resolution(i,x))%size].info != EMPTY && !(v[(hashVal + resolution(i,x))%size].element == x))
&& (i<=size)){//(limit in case all are marked as DELETED )
i++;
}
hashVal = (hashVal + resolution(i,x))%size;
if(v[hashVal].info == ACTIVE && v[hashVal].element == x){
return true;
}else
return false;
}
// mutators
void HashTable::makeEmpty(){
// CODE HERE
for(int i =0; i < size;i++){
v[i].info=EMPTY; //not actually deleting, just marking as deleted
v[i].element.key = "";
}
numItems = 0;
}
bool HashTable::insert(const HashedObj& x){
// CODE HERE //NOT COMPLETE!!!!
int hashVal = hash(x);
int i =0;
while(v[(hashVal + resolution(i,x))%size].info==ACTIVE){
i++;
}
hashVal = (hashVal + resolution(i,x))%size;
v[hashVal].element = x;
v[hashVal].info = ACTIVE;
numItems++;
double lf = (double)numItems / (double)size;
if (lf > 0.5){//if load facter >0.5, need to resize and rehash
//std::cout<<"rehash"<<std::endl;
rehash();
}
return true; // b/c will always be able to insert??
}
bool HashTable::insert(HashedObj&& x){
// CODE HERE
HashedObj& x2 = x;
return insert(x2);
}
bool HashTable::remove(const HashedObj& x){
// CODE HERE
int hashVal = hash(x);
int i =0;
while(!(v[(hashVal + resolution(i,x))%size].element== x) && v[(hashVal + resolution(i,x))%size].info!=EMPTY && i<=size){
i++;
}
hashVal = (hashVal + resolution(i,x))%size;
if(v[hashVal].info == EMPTY || i>size)
return false;
else{
v[hashVal].info = DELETED;
v[hashVal].element.key ="";
numItems--;
return true;
}
}
// performs a rehashing by finding the next prime after doubling the tableSize
void HashTable::rehash(){
// CODE HERE
int nextPrime = size*2;
//std::cout<<size<<std::endl;
int numDivis = -1;
while ( numDivis!=0){
numDivis = 0;
nextPrime++;
int thisNum = nextPrime-1;
while(thisNum>1 && numDivis==0){
if((nextPrime % thisNum) == 0)
numDivis++;
thisNum--;
}
}
size = nextPrime;
numItems = 0;
std::vector<HashEntry> oldTable =v;
v = std::vector<HashEntry>{size_t(nextPrime)};
for(HashEntry he : oldTable){
if(he.info == ACTIVE){
insert(he.element);
he.info=ACTIVE;
numItems++;
}
}
}
void HashTable::printHashTable(){
std::cout<<"|";
for (int i =0;i<size;i++){
std::cout<<v[i].element.key<<"|";
}
std::cout<<""<<std::endl;
}
HashTable.h
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include "HashedObj.h"
#include <iostream>
#include <vector>
class HashTable {
public:
enum ResolutionType {LINEAR,QUADRATIC,DOUBLE};//the resolution type
explicit HashTable(int size = 101,ResolutionType resolution = LINEAR);// init to prime
enum EntryType {ACTIVE, EMPTY, DELETED};//for bookeeping
// accessors
int hash (const HashedObj& x) const;
int linearResolution (int i) const;//helper method for linearResolution
int quadraticResolution (int i) const;//helper method for quadraticResolution
int doubleHashResolution (int i, const HashedObj& x) const;//helper method for doubleHashResolution
int hash2 (const HashedObj& x) const;//used for double hashing
bool contains (const HashedObj& x) const;//returns true if the hash table contains the item
int resolution (int i,const HashedObj& x)const;//gets the index of the resolution after a collision
// mutators
void makeEmpty();//removes all elements from the has table
bool insert(const HashedObj& x);//inserts into hash table
bool insert(HashedObj&& x);//inserts an r-value
bool remove(const HashedObj& x);//remove from hash table
void rehash();//used to resize the hash table when needed
//for testing
void printHashTable();
private:
//struct used to store table entires
struct HashEntry
{
HashedObj element;//the HasheObj element
EntryType info;//for bookeeping
HashEntry(const HashedObj& e = HashedObj{}, EntryType i = EMPTY) :
element {e},
info {i} {}
HashEntry(HashedObj&& e, EntryType i = EMPTY) :
element {std::move (e)},
info {i} {}
};
const ResolutionType resolutionFunction;//the collision resolution type
std::vector<HashEntry> v;//all the items
int size;//current max size of the table
int numItems;//num items in the hash table
};
#endif
HashedObj.cpp
#include "HashedObj.h"
/*
This class is the implementation of HashedObj.h. See HashedObj.h for
more information.
*/
HashedObj::HashedObj():
key {""} {}
HashedObj::HashedObj(std::string _key):
key {_key} {}
HashedObj::HashedObj (const HashedObj& other){
key = other.key;
}
HashedObj::HashedObj (HashedObj&& other){
key = std::move(other.key);
}
bool HashedObj::operator==(const HashedObj& other)const{
if (!key.compare(other.key)){
return true;
} else {
return false;
}
}
HashedObj.h
#ifndef HASHEDOBJ_H
#define HASHEDOBJ_H
#include <string>
/*
This class is used for data bookeeping in the hash table. It simply stores
a string key, and provides = and == overloads
*/
class HashedObj {
public:
std::string key; // the key for a hash object
HashedObj ();
//constructors
explicit HashedObj (const std::string _key);
explicit HashedObj (const HashedObj& other);
explicit HashedObj (HashedObj&& other);
//overloaded operators
HashedObj& operator=(const HashedObj& other) = default;
bool operator==(const HashedObj& other)const; // overloading equality check
};
#endif
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.