Back to Code List
c++

Hash - Open Addressing

A hash map implementation using open addressing. This includes three main types: linear probing, quadratic probing, and double hash.

   main.cpp

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

ofstream outputFile;//defined as a global variable

//define an enumerated date type
enum EntryType {EMPTY, ACTIVE, DELETED};

struct Element
{
	int key;
	EntryType flag;
};

class HashTable
	private:
		int m; // the size of the table
		Element * T; //the hash table
		int hash(int); // the hash function
		int hash2(int);
		int probe(int x, int i);
		int outerProbe(int x, int i);

	public:
		HashTable(int size);// set the size of the table
		void insert(int x);// insert a new element with key x 
		void remove(int x);// remove an element whose key is x
		int search(int x); // search an element whose key is x and return the index, and if there is no such key, return -1 
		void printTableEntry();//print the list in T[i]
};

// search an element whose key is x and return the index of the element in T, and if there is no such key, return -1 
int HashTable::search (int x)
{
	int i = 0;
	int p = probe(x, i);

	while (T[p].flag == ACTIVE) {
		if (T[p].key == x)
			return p;
		p = probe(x, ++i);
	}
	return -1;
}

void HashTable::remove (int x)
{
	int pos = search(x);
	if (pos > -1) {
		T[pos].flag = DELETED;
	}
}

void HashTable::insert(int x)
{
	int i = 0;
	int p = probe(x, i);
	while (T[p].flag == ACTIVE) {
		p = probe(x, ++i);
	}
	T[p].key = x;
	T[p].flag = ACTIVE;
}

void HashTable::printTableEntry()
{
	for (int i = 0; i < m; i++)
	{
		switch (T[i].flag)
		{
			case EMPTY:
				cout << "The entry "<< i << " is empty." << endl;
				outputFile << "The entry "<< i << " is empty." << endl;
				break;
			case ACTIVE:
				cout << "The entry "<< i << " is " << T[i].key << endl; 
				outputFile << "The entry "<< i << " is " << T[i].key << endl; 
				break;
			case DELETED:
				cout << "The entry "<< i << " is " << T[i].key << ", but is deleted."<< endl; 
				outputFile << "The entry "<< i << " is " << T[i].key << ", but is deleted."<< endl; 
				break;
			default:
				cout << "No such entry flag.\n";
				outputFile << "No such entry flag.\n";
		}
	}
	cout << endl;
}


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

int HashTable::hash2(int x)
{
	return x % 9 + 1;
}

int HashTable::probe(int x, int i)
{
	return outerProbe(x, i);
}

int HashTable::outerProbe(int x, int i)
{
	//Uncomment for linear probing
    //return (hash(x) + i) % m;
    
    //Uncomment for a quadratic probe
    //return (hash(x) + i*i) % m;
    
    //Uncomment for Double hashing
	return (hash(x) + i*hash2(x)) % m;
}


HashTable::HashTable(int size)
{
	m = size;
	T = new Element[m];
	for(int i = 0; i < m; i++)
		T[i].flag = EMPTY;
}

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;
			int k = hashtable.search(x); 
			if (k != -1)
			{
				cout << "The key " << x << " is in T[" << k <<"]." << endl;
				outputFile << "The key " << x << " is in T[" << k <<"]." << 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
	hashtable.printTableEntry();

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

	return 1;
}
    

   input.txt

61
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
search 200
search 13
    

   output.txt


The following is the current hash table:
The entry 0 is 44
The entry 1 is 40
The entry 2 is 12
The entry 3 is 36
The entry 4 is 26
The entry 5 is 5
The entry 6 is empty.
The entry 7 is 92
The entry 8 is empty.
The entry 9 is 42
The entry 10 is 59