Back to Code List
c++

Hash - Separate Chaining

An implementation of a hash map using the separate chaining method with a linked list.

   main.cpp

#include<iostream>
#include<fstream>
#include<string>
using namespace std;

ofstream outputFile;//defined as a global variable

struct Element
{
	int key;
	Element * next;
	Element(int key_input, Element * next_input = NULL)
	{
		key = key_input;
		next = next_input;
	}
};

class HashTable // separate chaining 
{
	private:
		int m; // the size of the table
		Element ** T; //the hash table
		int hash(int); // the hash function

	public:
		HashTable(int size);
		void insert(int x);// insert a new element with key x
		void remove(int x);// remove an element whose key is x
		bool search(int x); // search an element whose key is x and return true if it is found 
		void printTableEntry(int i);//print the list in T[i]
};

bool HashTable::search (int x)
{
	int idx = hash(x);
	Element *list = T[idx];
	while (list != NULL) {
		if (list->key == x) return true;
		list = list->next;
	}
	return false;
}

void HashTable::remove (int x)
{
	if (!search(x)) return;
	int idx = hash(x);
	Element *list = T[idx];
	auto temp = list;
	while (list != NULL) {
		if (list->key == x) {
			if (list == T[idx]) //head
				T[idx] = list->next;
			else
				temp->next = list->next;
			delete list;
			break;
		}
		temp = list;
		list = list->next;
	}
}

void HashTable::insert(int x)
{
	if (search(x)) return;
	int idx = hash(x);
	Element *list = T[idx];
	Element *new_list = new Element(x);
	if (list == NULL) T[idx] = new_list;
	else {
		new_list->next = list;
		T[idx] = new_list;
	}
}

void HashTable::printTableEntry(int i)
{
	cout << "Entry " << i << ":"; 
	outputFile << "Entry " << i << ":"; 

	Element * p = T[i];
	while (p != NULL)
	{
		cout << p->key;
		outputFile << p->key;

		if(p->next != NULL)
		{
			cout << "->";
			outputFile << "->";
		}
		p = p->next;
	}
	cout << endl;
	outputFile << endl;
}

int HashTable::hash(int x)
{
	return x % m;
}

HashTable::HashTable(int tableSize)
{
	m = tableSize;
	T = new Element * [m];
	for(int i = 0; i < m; i++)
		T[i] = NULL;
}

int main()
{

	//open files
	ifstream inputFile;
	inputFile.open("input.txt");
	if (!inputFile)
		cout << "Error opening the input file " << endl;
	
	//outputFile has been defined as a global variable
	outputFile.open("output.txt");
	if (!outputFile)
		cout << "Error opening the output file " << endl;

	string op;
	int tableSize;
	//read the hash table size
	inputFile >> tableSize;

	HashTable hashtable(tableSize);

	//read operations from the input file
	int x;
	while(inputFile >> op)
	{
		if (op == "insert")
		{
			inputFile >> x; // read the value x for insert
			hashtable.insert(x);
		}
		if (op == "remove")
		{
			inputFile >> x; // read the value x for remove 
			hashtable.remove(x);
		}
		if (op == "search")
		{
			inputFile >> x;
			if (hashtable.search(x) == true)
			{
				cout << "The key " << x << " is in the current hash table." << endl;
				outputFile << "The key " << x << " is in the current hash table." << endl;
			}
			else// x is not in the hash table
			{
				cout << "The key " << x << " is not in the current hash table." << endl;
				outputFile << "The key " << x << " is not in the current hash table." << endl;
			}
		}
	}
	cout << endl;
	outputFile << endl;

	cout << "The following is the current hash table:" << endl;
	outputFile << "The following is the current hash table:" << endl;

	//print out the current hash table
	for (int i = 0; i < tableSize; i++)
		hashtable.printTableEntry(i);


	inputFile.close();
	outputFile.close();

	return 1;
}
    

   input.txt

13
insert 514
insert 100
insert 185
insert 117
insert 268
insert 651
insert 168
insert 88
insert 19
insert 186
insert 173
remove 185
insert 40
insert 586
search 185
insert 66
insert 781
insert 111
insert 123
insert 333
remove 173
insert 207
insert 335
insert 155
insert 26
search 100
insert 23
insert 13
remove 88
remove 186
insert 42
insert 180
insert 200
remove 117
search 19
insert 90
insert 70
remove 13
insert 152
insert 58
insert 383
remove 383
insert 15
search 117
insert 184
insert 169
search 13
insert 167
insert 93
insert 20
insert 5
insert 161
insert 300
insert 304
insert 739
insert 869
    

   output.txt

The key 185 is not in the current hash table.
The key 100 is in the current hash table.
The key 19 is in the current hash table.
The key 117 is not in the current hash table.
The key 13 is not in the current hash table.

The following is the current hash table:
Entry 0:169->26
Entry 1:300->781->66->586->40->651
Entry 2:93->184->15
Entry 3:42
Entry 4:
Entry 5:304->161->5->70->200
Entry 6:58->123->19
Entry 7:20->111->514
Entry 8:333->268
Entry 9:152->100
Entry 10:23->335
Entry 11:869->739->167->180
Entry 12:90->155->207->168