C++ program to Implement Hash tables Chaining with Doubly Linked Lists

Article Creation Date : 24-Jun-2021 12:28:02 PM

             C++ program to Implement Hash tables Chaining with Doubly Linked lists
 
                                                              DESCRIPTION
A hash table is a data structure which is used to store key-value pairs. Hash function is used by hash table to compute an index into an array in which an element will be inserted or searched.

Implementing hash table using Chaining through Doubly Linked List . This will speed up the process of adding and removing elements from the list, hence the time complexity will be reduced drastically.         
                                              
                              
                                             
   /SOURCE CODE/

#include<iostream>
#include <stdbool.h> 
using namespace std; 

int const tablesize = 10;

 struct hash_node
 {
    int val,key;
    hash_node *next;
    hash_node *prev;
 };

class Hashchain
{ 
public: 
         hash_node **hashtable, **top; 
    Hashchain()
	{
	    hashtable= new hash_node*[tablesize];
	    top= new hash_node*[tablesize];
	    for(int i=0;i<tablesize;i++)
	    {
	        hashtable[i]=NULL;
	        top[i]=NULL;
	    }
	}
	int HashF(int key) 
	{ 
		 key % tablesize;
		 return key;
	} 
	void find(int key) 
	{ 
		int hash_val = HashF(key); 
		bool B = false; 
		hash_node* entry = hashtable[hash_val]; 

		if (entry != NULL) 
		{ 
			while (entry != NULL) 
			{ 
				if (entry->key == key) 
				{ 
					B = true; 
				} 
				if (B) 
				{ 
					cout << "Element found at key "<< key << " is "; 
					cout << entry->val << endl; 
				} 
				entry = entry->next; 
			} 
		} 
		if (!B) 
			cout << "No Element found at key "
				<< key << endl; 
	} 
	void remove(int key) 
	{ 
		int hash_val = HashF(key); 
		hash_node* entry = hashtable[hash_val]; 
		if (entry->key != key || entry == NULL)
		{ 
			cout << "Couldnot find any element at this key "<< key << endl; 
			return; 
		} 
		while (entry != NULL) 
		{ 
			if (entry->next == NULL) 
			{ 
				if (entry->prev == NULL) 
				{ 
					hashtable[hash_val] = NULL; 
					top[hash_val] = NULL; 
					delete entry; break; 
					
				} 
				else
				{ 
					top[hash_val] = entry->prev; 
					top[hash_val]->next = NULL; 
					delete entry; 
					entry = top[hash_val]; 
				} 
			} 
			entry = entry->next; 
		} 
		cout << "Element was removed at the key "<< key << endl; 
	} 
	void insert(int key, int value) 
	{ 
		int hash_val = HashF(key); 
		hash_node* entry = hashtable[hash_val]; 

		if (entry == NULL) 
		{ 
			entry = new hash_node; 
			entry->val = value; 
			entry->key = key; 
			entry->next = NULL; 
			entry->prev = NULL; 
			hashtable[hash_val] = entry; 
			top[hash_val] = entry; 
		} 
		else 
		{ 
			while (entry != NULL) 
				entry = entry->next; 
			entry = new hash_node;
			entry->val = value; 
			entry->key = key; 
			entry->next = NULL; 
			entry->prev = top[hash_val]; 
			top[hash_val]->next = entry; 
			top[hash_val] = entry; 
		} 
		cout << "Value " << value << " was added at key " << key << endl; 
	} 
}; 
int main() 
{ 
	Hashchain H; 
	H.insert(1,2); 
	H.find(1); 
	H.remove(1); 
	return 0; 
} 

 CONCLUSION
Thus the  Implementation of  Hash Tables chaining with doubly linked lists is CODED.