Answer to Question #335203 in C++ for Downer

Question

// Use c++ language and must use Standard Library List ( STL ) in your program

Please write class for hash table using chaining and it must contain the following  functions:

• Please insert an element in table
• Please search an element in table
• Please delete an element in table
• Please return no of the chains currently present
• Please display the hash table of the class
• Please write the main function to test the class created.

// Must use Standard Library List ( STL ) in your program

Answer 1

#include<iostream>
#include<list>

using namespace std;

class Hash
{
	int BUCKET; // No. of buckets
				// Pointer to an array containing buckets
	list<int> *table;
public:
	Hash(int V)
	{
		this->BUCKET = V;
		table = new list<int>[BUCKET];
	}
	// inserts a key into hash table
	void insertItem(int x)
	{
		int index = hashFunction(x);
		table[index].push_back(x);
	}
	// deletes a key from hash table
	void deleteItem(int key)
	{
		int index = hashFunction(key);
		// find the key in (index)th list
		list <int> ::iterator i;
		for (i = table[index].begin();i != table[index].end(); i++) 
		{
			if (*i == key)
				break;
		}
		// if key is found in hash table, remove it
		if (i != table[index].end())
			table[index].erase(i);
	}
	// search a key in hash table
	bool searchItem(int key)
	{
		int index = hashFunction(key);
		// find the key in (index)th list
		list <int> ::iterator i;
		for (i = table[index].begin(); i != table[index].end(); i++)
		{
			if (*i == key)
				break;
		}
		// if key is found in hash table, return true
		if (i != table[index].end())
			return true;
		return false;
	}
	int no_of_the_chains()
	{
		int res = 0;
		for (int i = 0; i < BUCKET; i++)
		{
			if (!table[i].empty())
				res++;
		}
		return res;
	}


	// hash function to map values to key
	int hashFunction(int x)
	{
		return (x % BUCKET);
	}
	// function to display hash table
	void displayHash()
	{
		for (int i = 0; i < BUCKET; i++)
		{
			cout << i;
			for (auto x : table[i])
				cout << " --> " << x;
			cout << endl;
		}
	}
};


// Driver program
int main()
{
	// array that contains keys to be mapped
	int a[] = { 15, 11, 27, 8, 12 };
	int n = sizeof(a) / sizeof(a[0]);
	// insert the keys into the hash table
	Hash h(7); // 7 is count of buckets in
			   // hash table
	for (int i = 0; i < n; i++)
		h.insertItem(a[i]);
	// delete 12 from hash table
	h.deleteItem(12);
	// display the Hash table
	h.displayHash();
	cout<<"h.searchItem(11)= "<<h.searchItem(11)<<endl;
	cout << "h.searchItem(12)= " << h.searchItem(12) << endl;
	cout << "h.no_of_the_chains()= " << h.no_of_the_chains() << endl;
	return 0;
}