NEED HELP WITH HASH TABLES (URGENT)

[beginner123]

I need to write a menu controlled program using classes and arrays and integer data to
1) create a hash table (i.e. mark all the elements in the table as "EMPTY")
2) clear a hash table of its contents
3) add data to the hash table (this code is below)
4) remove data from the hash table (also print each value as it is removed),
5) print the contents of the hash table,
6) search the hash table for some target key value (this code is below)

I have been searching the internet and books for a week looking for simple code for the functions above and everything I find is to complicated or its just explaining the maths behind the hash table.
I was given some code to start with but I'm getting errors:

//exType.cpp - implementation of exType.h, where functionality of ExType obj's are defined
#include"exType.h"
ExType::ExType()
{
	idNum=0;
}
ExType::ExType(int id)
{
	idNum=id;
}

istream& operator>>(istream &is, ExType &item)
{
	is>>item.idNum;
	return is;
}
ostream& operator<<(ostream &os, ExType item)
{
	os<<item.idNum;
	return os;
}

bool ExType::operator==(const ExType& item) const
{
	if(idNum == item.idNum)
		return true;
	else
		return false;
}
bool ExType::operator!=(const ExType& item) const
{
	if(idNum != item.idNum)
		return true;
	else
		return false;
}

ExType::~ExType()
{

}

int ExType::Hash() const
//Post: Function value is an integer between 0 //      and MAX_ITEMS-1
{
	return (idNum % MAX_ITEMS);
}

template<class ItemType>			      
void ListType<ItemType>::InsertItem(ItemType item)
// Post: item is stored in the array at position
//item.Hash() or the next free spot.
{
    int location;
    location = item.Hash();
    while (info[location] != emptyItem && info[location] != deletedItem)
    location = (location + 1) % MAX_ITEMS;
    info[location] = item;
    length++;
}

template<class ItemType>			    
void ListType<ItemType>::RetrieveItem(ItemType& item, bool& found)
{
    int location;
    int startLoc;
    bool moreToSearch = true;

    startLoc = item.Hash();
    location = startLoc;
	do
    {
	if (info[location] == item || 					
		info[location] == emptyItem)
	    moreToSearch = false;
	else
	    location = (location + 1) % MAX_ITEMS;
    } while(location != startLoc && moreToSearch);
    
    found = (info[location] == item);
    if ( found)
	item = info[location];
}

//exType.h defines the item saved sorted and searched in the Hash table.
#ifndef EXTYPE
#define EXTYPE
#include<iostream.h>
const int MAX_ITEMS = 11;
class ExType{
private:
	int idNum;
public:
	ExType();
	ExType(int);
	int Hash()const;	
	friend istream& operator>>(istream &is,ExType &item);
	friend ostream& operator<<(ostream &os,ExType item);
	bool operator==(const ExType& item)const;
	bool operator!=(const ExType& item)const;
	~ExType();
	void ListType<ItemType>::InsertItem(ItemType item);
	void ListType<ItemType>::RetrieveItem(ItemType& item, bool& found);
};
#endif

and main.cpp just contains the menu(no problems with this part).
I have just two functions so far and I really don't know what to do for the others.

I don't have to use the code I was given (so if someone has an easier way to do this please let me know bacause I don't really understand the above code and other codes I have looked at seem nothing like this). I understand how hash tables work but I really don't know anything about the code for it. Could someone please help me with this as I am completely lost at what to do.

Thanks

[beginner123]

I know I am asking a lot but I need someone to help me understand the code of hash tables. The lecturer i have pretty much left us on your own on this and I don't want to get a bad mark because he didn't tell us anything about the code necessary for all this. #

I would really appreciate it if someone could show me an easy way to write the functions I need.

[Peter87]

ExType is just an example type to be stored in your hash table. It has the Hash() member function that your hash table can use to get the hash value of an object. It also have comparison operators that is useful to check if two objects are the same (Two objects with the same hash value is not necessary equal).

ListType is the hash table class. info is an array of size MAX_ITEMS. The hash value decides at what position in the array an element should be stored. If that position is already taken it just looks for the next empty location and stores it there. It also uses the hash value to find elements. It will here have to search the next location until it finds the element. If it finds an empty spot it means the element is not in the list so it can stop search.

I'm not sure how to best implement "remove data from the hash table" with the current implementation. If you remove an element by just marking it as empty it will create a hole in the array that will disturb search for other elements. I guess you will have to scan all the locations and move them to the correct location. The scan can stop when an empty location is found.

Another approach to implement hash tables is to store a linked list at each array location. That way you can store all the elements with the same hash value in the same list. To find an element in the hash table you just use the hash value to lookup the linked list and then you scan the linked list to see if it contains the element you search for. Note that this approach would require you to rewrite the two functions InsertItem and RetrieveItem.

[beginner123]

thanks for replying but that doesn't really help. I just started learning programming so everything you told me doesn't help me write the code I need or that the code I posted is giving me errors. The removed data from hash table is just deleting a value from the table. I need to create another constant value deletedItem, to use in slots that were occupied by deleted records so when a value is deleted it won't say empty it will say deletedItem and my insert function already handles this

 while (info[location] != emptyItem && info[location] != deletedItem)

so it won't disturb anything.

As I said a understand how a hash table works its the code I have no idea about and finding a simple example is very difficult to find. I just need the basic functions - insert, delete one value, delete the whole table, print the table and search for a value and of course actually creating the table

[Peter87]

The definition of ListType is left for you to write. Without it you will have errors with RetrieveItem and InsertItem.

[beginner123]

yes and thats my problem, I don't know what to put into ListType or how to write any of the other functions..
I pretty much know nothing about coding a hash table which is why I have been searching for some basic source code

[Peter87]

Line 18-19 in exType.h is wrong. Those function declarations should be put inside the ListType class defintion which you have not yet created. Start write the class ListType, look inside the member functions and see what variables they use and add them to the class. Make sure the functions are working before you start worrying about the other functions.