Please code the CODE HERE parts. Initial Problem: In this lab, you will be imple
ID: 3916941 • Letter: P
Question
Please code the CODE HERE parts.
Initial Problem: 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. The book will be especially helpful for this part. The only file you will need to edit is HashTable.cpp (aside from any extra testing). The functions are in an order you can follow if you wish.
//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
PROGRAM CODE:
HashTable.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"
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;
}
}
HasheObj.h
#ifndef HASHEDOBJ_H
#define HASHEDOBJ_H
#include <string>
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