C Program to Implement Hash Tables Chaining with Doubly Linked Lists

This is a C Program to Implement Hash Tables Chaining with Doubly Linked Lists.

Problem Description

A hash table is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots. Implementing hash table using Doubly Linked List is similar to implementing hash table using Singly Linked List. The difference is that every node of Linked List has address of both, the next and the previous node. This will help removing data from this Linked List faster than Singly Linked List.

Problem Solution

1. Create an array of Doubly Linked List (i.e a hash table).
2. Take a key and a value to be stored in hash table as input.
3. Corresponding to the key, an index will be generated i.e every key is stored in a Linked List of a particular array index.
4. Using the generated index, extract the Linked List located in that array index.
5. In case of absence of a list, create one and insert a data item (key and value) into it and increment the size of hash table.
6. In case the list already exists, search for the key (given as input) in the list, and add the data item (key and value) at the end of list if key does not belong to the list and increment the size, otherwise update the value of given (and already present) key in the Linked List.
7. To display all the elements of hash table, Linked List at each index is extracted and elements (key and value) are read until we reach at its end.
8. To remove a key from hash table, we will first calculate its index and extract its Linked List, find the key in list and remove it if it is present.
9. Exit

Program/Source Code

Here is the source code of the C Program to implement a Hash table chaining with Doubly Linked List. The program is successfully compiled and tested using Turbo C compiler in windows environment. The program output is also shown below.

```
 
```
```
#include<stdio.h>
```
```
#include<stdlib.h>
```
```
 
```

/* Node for storing an item in a Doubly Linked List */

```
struct node 
```
```
{
```
```
	int key;
```
```
	int value;
```
```
	struct node *next;
```
```
	struct node *prev;
```
```
};
```
```
 
```

/* For storing a Linked List at each index of Hash table */

```
struct arrayitem 
```
```
{
```
```
 
```
```
	struct node *head;
```

	/* head pointing the first element of Linked List at an index of Hash table */

```
 
```
```
	struct node *tail;
```

	/* tail pointing the last element of Linked List at an index of Hash table */

```
 
```
```
};
```
```
 
```
```
struct arrayitem *array;
```

int size = 0;         /* Determines the no. of elements present in Hash table */

int max = 10;	      /* Determines the maximum capacity of Hash table array */

```
 
```

/* This function creates an index corresponding to the every given key */

```
int hashcode(int key)
```
```
{
```
```
	return (key % max);
```
```
}
```
```
 
```

struct node* get_element(struct node *list, int find_index);

```
void remove_element(int key);
```
```
void rehash();
```
```
void init_array();
```
```
 
```
```
void insert(int key, int value)
```
```
{
```
```
	float n = 0.0;
```

	/*  n => Load Factor, keeps check on whether rehashing is required or not */

```
 
```
```
	int index = hashcode(key);
```
```
 
```

	/* Extracting Linked List at a given index */

	struct node *list = (struct node*) array[index].head;

```
 
```

	/* Creating an item to insert in the hash table */

	struct node *item = (struct node*) malloc(sizeof(struct node));

```
	item->key = key;
```
```
	item->value = value;
```
```
	item->next = NULL;
```
```
	item->prev = NULL;
```
```
 
```
```
	if (list == NULL) 
```
```
        {
```

		/* Absence of Linked List at a given index of Hash table */

```
 
```

		printf("\n  %d (key) and %d (value) has been inserted  \n", key, value);

```
		array[index].head = item;
```
```
		array[index].tail = item;
```
```
		size++;
```
```
 
```
```
	}
```
```
        else
```
```
        {
```

		/* A Linked List is present at given index of Hash table */

```
 
```
```
		int find_index = find(list, key);
```
```
		if (find_index == -1) 
```
```
                {
```
```
		 	/*
```

			 *Key not found in existing Linked List

			 *Adding the key at the end of the Linked List

```
			*/
```
```
			item->prev = array[index].tail;
```
```
			array[index].tail->next = item;
```
```
			array[index].tail = item;
```
```
			size++;
```

			printf("\n %d (key) and %d (value) has been inserted \n", key, value);

```
 
```
```
 
```
```
		}else {
```
```
			/*
```
```
			 *Key already present in Linked List
```

			 *Updating the value of already existing key

```
			*/
```
```
 
```

			struct node *element = get_element(list, find_index);

```
			element->value = value;
```
```
 
```
```
		       }
```
```
 
```
```
	}
```
```
 
```
```
	/* Calculating Load factor */
```
```
	n = (1.0 * size) / max;
```
```
	if (n >= 0.75) 
```
```
        {
```
```
		/* rehashing */
```
```
 
```
```
		printf("going to rehash\n");
```
```
		rehash();
```
```
 
```
```
	}
```
```
 
```
```
}
```
```
 
```
```
void rehash()
```
```
{
```
```
	struct arrayitem *temp = array;
```

	/* temp pointing to the current Hash table array */

```
 
```
```
	int i = 0, n=max;
```
```
	size = 0;
```
```
	max = 2 * max;
```
```
 
```
```
	/*
```

	 *array variable is assigned with newly created Hash table

```
	 *with double of previous array size
```
```
	*/
```

	array = (struct arrayitem*) malloc(size * sizeof(struct node));

```
	init_array();
```
```
 
```
```
	for (i = 0; i < n; i++) 
```
```
        {
```
```
 
```

		/* Extracting the Linked List at position i of Hash table array

		struct node* list = (struct node*) temp[i].head;

```
 
```
```
		if (list == NULL)
```
```
                {
```
```
 
```

			/* if there is no Linked List, then continue */

```
			continue;
```
```
 
```
```
		}
```
```
		else 
```
```
                {
```
```
			/*
```
```
			 *Presence of Linked List at i
```

			 *Keep moving and accessing the Linked List item until the end.

			 *Get one key and value at a time and add it to new Hash table array.

```
			*/
```
```
 
```
```
			while (list != NULL)
```
```
                        {
```
```
				insert(list->key, list->value);
```
```
				list = list->next;
```
```
			}
```
```
 
```
```
		}
```
```
 
```
```
	}
```
```
	temp = NULL;
```
```
}
```
```
 
```
```
/*
```

 *This function finds the given key in the Linked List

```
 *Returns it's index
```

 *Returns -1 in case key is not present

```
*/
```
```
int find(struct node *list, int key)
```
```
{
```
```
	int retval = 0;
```
```
	struct node *temp = list;
```
```
	while (temp != NULL)
```
```
        {
```
```
		if (temp->key == key)
```
```
                {
```
```
			return retval;
```
```
		}
```
```
		temp = temp->next;
```
```
		retval++;
```
```
	}
```
```
	return -1;
```
```
 
```
```
}
```
```
 
```

/* Returns the node (Linked list item) located at given find_index */

struct node* get_element(struct node *list, int find_index)

```
{
```
```
	int i = 0;
```
```
	struct node *temp = list;
```
```
	while (i != find_index)
```
```
        {
```
```
		temp = temp->next;
```
```
		i++;
```
```
	}
```
```
	return temp;
```
```
}
```
```
 
```

/* To remove an element from Hash table */

```
void remove_element(int key)
```
```
{
```
```
	int index = hashcode(key);
```

	struct node *list = (struct node*) array[index].head;

```
 
```
```
	if (list == NULL)
```
```
        {
```

		printf("\n This key does not exists \n");

```
 
```
```
	}
```
```
	else
```
```
        {
```
```
		int find_index = find(list, key);
```
```
 
```
```
		if (find_index == -1)
```
```
                {
```

			printf("\n This key does not exists \n");

```
 
```
```
		}
```
```
		else 
```
```
                {
```
```
			struct node *temp = list;
```
```
			if (temp->key == key)
```
```
                        {
```
```
 
```
```
				array[index].head = temp->next;
```
```
				array[index].head->prev = NULL;
```
```
				size--;
```

				printf("\n This key has been removed \n");

```
				return;
```
```
			}
```
```
 
```
```
			while (temp->key != key)
```
```
                        {
```
```
				  temp = temp->next;
```
```
			}
```
```
 
```
```
			if (array[index].tail == temp)
```
```
                        {
```
```
				temp->prev->next = NULL;
```
```
				array[index].tail = temp->prev;
```
```
				size--;
```
```
 
```
```
			}
```
```
                        else 
```
```
                        {
```
```
				temp->prev->next = temp->next;
```
```
				temp->next->prev = temp->prev;
```
```
				size--;
```
```
 
```
```
			}
```
```
 
```

			printf("This key has been removed\n");

```
 
```
```
		}
```
```
 
```
```
	}
```
```
 
```
```
}
```
```
 
```

/* To display the contents of Hash table */

```
void display()
```
```
{
```
```
	int i = 0;
```
```
	for (i = 0; i < max; i++)
```
```
        {
```
```
		struct node *temp = array[i].head;
```
```
		if (temp == NULL)
```
```
                {
```

			printf("array[%d] has no elements \n", i);

```
 
```
```
		}
```
```
		else 
```
```
                {
```

			printf("array[%d] has elements-: ", i);

```
			while (temp != NULL) 
```
```
                        {
```

				printf("key= %d  value= %d\t", temp->key, temp->value);

```
				temp = temp->next;
```
```
			}
```
```
			printf("\n");
```
```
 
```
```
		}
```
```
	}
```
```
}
```
```
 
```
```
/* For initializing the Hash table */
```
```
void init_array()
```
```
{
```
```
	int i;
```
```
	for (i = 0; i < max; i++)
```
```
        {
```
```
		array[i].head = NULL;
```
```
		array[i].tail = NULL;
```
```
	}
```
```
 
```
```
}
```
```
 
```
```
/* Returns size of Hash table */
```
```
int size_of_array()
```
```
{
```
```
	return size;
```
```
}
```
```
 
```
```
void main()
```
```
{
```
```
	int choice, key, value, n, c;
```
```
	clrscr();
```
```
 
```

	array = (struct arrayitem*) malloc(max * sizeof(struct arrayitem*));

```
	init_array();
```
```
 
```
```
	do {
```

		printf("Implementation of Hash Table in C chaining with Doubly Linked List \n\n");

		printf("MENU-: \n1.Inserting item in the Hash Table"

                              "\n2.Removing item from the Hash Table"

                              "\n3.Check the size of Hash Table"

                              "\n4.Display a Hash Table"

		       "\n\n Please enter your choice-:");

```
 
```
```
		scanf("%d", &choice);
```
```
 
```
```
		switch(choice) 
```
```
                {
```
```
 
```
```
		case 1:
```
```
 
```

		      printf("Inserting element in Hash Table\n");

		      printf("Enter key and value-:\t");

```
		      scanf("%d %d", &key, &value);
```
```
		      insert(key, value);
```
```
 
```
```
		      break;
```
```
 
```
```
		case 2:
```
```
 
```

		      printf("Deleting in Hash Table \n Enter the key to delete-:");

```
		      scanf("%d", &key);
```
```
		      remove_element(key);
```
```
 
```
```
		      break;
```
```
 
```
```
		case 3:
```
```
 
```
```
		      n = size_of_array();
```

		      printf("Size of Hash Table is-: %d\n", n);

```
 
```
```
		      break;
```
```
 
```
```
		case 4:
```
```
 
```
```
		      display();
```
```
 
```
```
		      break;
```
```
 
```
```
		default:
```
```
 
```
```
		       printf("Wrong Input\n");
```
```
 
```
```
		}
```
```
 
```

		printf("\n Do you want to continue-:(press 1 for yes)\t");

```
		scanf("%d", &c);
```
```
 
```
```
	}while(c == 1);
```
```
 
```
```
	getch();
```
```
 
```
```
}
```

Program Explanation

1. Create a structure node (Doubly Linked List item) with key and value as data and next as a pointer variable which points the structure element of node type.
2. Create another structure (for Doubly Linked List) with head having the address of first element of Linked List and tail having the address of last element of Linked List.
3. Now create an array of Doubly Linked List of some certain size (10, in this case).
4. A menu is displayed on the screen.
5. User must choose one option from four choices given in the menu.
6. 1st choice: Inserting item into hash table
(a) Take a key and a value as input.
(b) Calculate index as per the given key.
(c) Locate the linked list at the calculated array index.
(d) If Linked List is present, check whether the key already present in it by finding the location of key using find() method which returns -1 if key is not present. In that case, we will create a data item and add it to the end of Linked List. If key is already present in the list, we will get its location index and extract the element using get_element() function and update its value.
(e) If there is no Linked List at that particular array index, which means the key is not present in hash table, then create a data item and a Linked List and add the data item to it.
7. 2nd choice: Removing a key from hash table
(a) Take a key as input which needs to be removed.
(b) Calculate index as per the given key.
(c) Locate the Linked List at the calculated array index.
(d) If Linked List is present, find the location index of the key in Linked List using find() method which returns -1 if key not present. The key is removed using remove() method if it is present otherwise ‘Key not present’ message will get displayed.
(e) If there is no Linked List at that particular array index, which means the key is not present in hash table, therefore no deletion is required.
8. 3rd choice: Size of hash table
(a) Each time we add a new data item into the hash table, we increment its size by 1.
(b) The size of the hash table can be determined either by size variable or size_of_hashtable() method.

9. 4th choice: Display hash table
(a) Function display() runs for displaying hash table contents.
(b) Here a for loop runs from 0 to array_size-1 with i as iterator.
(c) The code inside loop consists of taking i as index and locating each linked list at that index of array.
(d) As the content of each node of Linked List is displayed the next variable (pointer) is used to proceed further until the end of list is reached.

Runtime Test Cases

 
Implementation of Hash Table in C chaining with Binary Tree.
MENU-:
1. Inserting item in the Hash Table
2. Removing item from the Hash Table
3. Check the size of Hash Table
4. Display Hash Table
 
Please enter your choice-: 3
Size of Hash Table is-: 0
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C chaining with Binary Tree.
MENU-:
1. Inserting item in the Hash Table
2. Removing item from the Hash Table
3. Check the size of Hash Table
4. Display Hash Table
 
Please enter your choice-: 1
Inserting element in Hash Table
Enter key and value-:   1 	10
 
 1(key) and 10(value) has been inserted
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C chaining with Binary Tree.
MENU-:
1. Inserting item in the Hash Table
2. Removing item from the Hash Table
3. Check the size of Hash Table
4. Display Hash Table
 
Please enter your choice-: 1
Inserting element in Hash Table
Enter key and value-:   101 	1
 
 101(key) and 1(value) has been inserted
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C chaining with Binary Tree.
MENU-:
1. Inserting item in the Hash Table
2. Removing item from the Hash Table
3. Check the size of Hash Table
4. Display Hash Table
 
Please enter your choice-: 1
Inserting element in Hash Table
Enter key and value-:   51 	2
 
 51(key) and 2(value) has been inserted
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C chaining with Binary Tree.
MENU-:
1. Inserting item in the Hash Table
2. Removing item from the Hash Table
3. Check the size of Hash Table
4. Display Hash Table
 
Please enter your choice-: 4
array[0] has no elements		
array[1] has no elements	key=1  value=10		key=101  value=1	key=51  value=2
array[2] has no elements
array[3] has no elements
array[4] has no elements
array[5] has no elements
array[6] has no elements
array[7] has no elements
array[8] has no elements
array[9] has no elements
*****************************
 
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C chaining with Binary Tree.
MENU-:
1. Inserting item in the Hash Table
2. Removing item from the Hash Table
3. Check the size of Hash Table
4. Display Hash Table
 
Please enter your choice-: 2
Deleting key from Hash Table
Enter the key to delete-: 3
 
 This key does not exists.
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C chaining with Binary Tree.
MENU-:
1. Inserting item in the Hash Table
2. Removing item from the Hash Table
3. Check the size of Hash Table
4. Display Hash Table
 
Please enter your choice-: 2
Deleting key from Hash Table
Enter the key to delete-: 101
 
 This Key has been deleted.
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C chaining with Binary Tree.
MENU-:
1. Inserting item in the Hash Table
2. Removing item from the Hash Table
3. Check the size of Hash Table
4. Display Hash Table
 
Please enter your choice-: 4
array[0] has no elements		
array[1] has no elements	key=1  value=10		key=51  value=2
array[2] has no elements
array[3] has no elements
array[4] has no elements
array[5] has no elements
array[6] has no elements
array[7] has no elements
array[8] has no elements
array[9] has no elements
 
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C chaining with Binary Tree.
MENU-:
1. Inserting item in the Hash Table
2. Removing item from the Hash Table
3. Check the size of Hash Table
4. Display Hash Table
 
Please enter your choice-: 3
Size of Hash Table is-: 2
 
Do you want to continue-:(press 1 for yes) 2

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Subscribe Now: Data Structures in C Newsletter | Important Subjects Newsletters

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

« Prev - C Program to Implement Hash Tables Chaining with Binary Trees

» Next - Level Order Traversal of a Tree using Recursion

Related Posts:

Practice Programming MCQs
Apply for Computer Science Internship
Check Data Structure Books
Practice Design & Analysis of Algorithms MCQ
Practice Computer Science MCQs

Recommended Articles: