Hashtables
Video This lab is part of the Hash homework the complete function list is defined in Hash.h for this lab to work I am supplying Hash.o it has compiled versions of the constructor,empty,full,search,insert and remove functions defined in Hash.h For this lab you will complete the functions in the Hash_stu.cpp file (hash1,hash2 and ToString), the prototypes and some comments are provided the Makefile will link in the functions i wrote with the ones you write complete the menu driven main to call all of the corresponding functions defined in Hash.h and behaves like the example for the homework you will add in the remainder of the functions. compare your output the the runable example, they should be identical for all the provided testfiles there are 5 testfiles to try also you could try something like pasting in i33i33i33i33i45i45i45d45d33d33i33d128p MAKE SURE YOUR PROGRAM WORKS LIKE THE EXAMPLE You will be able to use these with your hash homework All the functions for the homework are defined in Hash.h File: Hash.h#include <iostream> #include <limits> #include "cmpslib19.h" #include "easylogging++.h" using namespace std; #define MAX_CAPACITY 1013 // MAX_CAPACITY is a prime number #define EMPTY_VALUE -1 // invalid value, represents empty slot #define DELETED_VALUE -2 // invalid value, represents deleted slot class HashTable { private: int count; // count of values currently stored int hashtable[MAX_CAPACITY]; public: /* initialize all slots in the array to EMPTY_VALUE set count to 0 */ HashTable( ); // return true if hash table is empty, compare count with 0 bool empty(); // return true if hash table is full, compare count and MAX_CAPACITY bool full(); /* primary hash function: a modulo function it will return (value mod MAX_CAPACITY) */ int hash1(int value); /* secondary hash function. it will return MAX_CAPACITY - hash1(value) */ int hash2(int value); /* Searches for the value in the table, returning true if found, false if not search in the order 1st position hash1 % MAX_CAPACITY 2nd position hash2 % MAX_CAPACITY 3rd position (hash2 +5) % MAX_CAPACITY 4th position (hash2 +10) % MAX_CAPACITY 5th position (hash2 +15) % MAX_CAPACITY and so on If the position contains the value you are looking for return true If the position contains EMPTY_VALUE return false otherwise keep searching the next position do NOT stop when a DELETED_VALUE is reached */ bool search(int value); /* if the hash is full return false insert the value into the table 1st position hash1 % MAX_CAPACITY 2nd position hash2 % MAX_CAPACITY 3rd position (hash2 +5) % MAX_CAPACITY 4th position (hash2 +10) % MAX_CAPACITY 5th position (hash2 +15) % MAX_CAPACITY and so on insert at the first postition you find EMPTY_VALUE or DELETED_VALUE return true; */ bool insert(int value); /* search in the order 1st position hash1 % MAX_CAPACITY 2nd position hash2 % MAX_CAPACITY 3rd position (hash2 +5) % MAX_CAPACITY 4th position (hash2 +10) % MAX_CAPACITY 5th position (hash2 +15) % MAX_CAPACITY and so on if you find it replace it with DELETED_VALUE and return true if you find EMPTY_VALUE stope and return false */ bool remove(int value); /* returns a string representation of the hashtable */ string ToString(); };
for this lab however you only need to write bodies for the onces currently in Hash_stu.cpp ( add in the remainder when you do the homework ) File: Hash_stu.cpp#include "Hash.h" // Calculates the primary key using modulo arithmetic // Primary key will be in the range 0 to MAX_CAPACITY - 1 // value mod MAX_CAPACITY int HashTable::hash1(int value) // for the 2nd hash we want to have an alternate method of calculating a hash // MAX_CAPACITY - ( value % MAX_CAPACITY) int HashTable::hash2(int value) // create a string representation of the HashTable class // make sure your output from the ToString function matches the example // before AND AFTER you delete some items string HashTable::ToString()