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()