Double Hashing in C - Sanfoundry

This is a C Program to implement Hash Tables with Double Hashing.

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. To prevent the collision of two keys ,the idea of Double Hashing is used. In case any collision occurs when we just use traditional hash code evaluating function, another hash code is generated by some other function and both the hash codes are used to find a free space by probing through array elements.

Problem Solution

1. Create an array of structure (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 particular array index.
4. Using the generated index, access the data located in that array index.
5. In case of absence of data, create one and insert the data item (key and value) into it and increment the size of hash table.
6. In case the data exists, probe through the subsequent elements (looping back if necessary) for free space to insert new data item.
Note: Here, unlike quadratic and linear probing, we will first calculate another hash code of same key using formula-: hashcode2 = primeNum – (key % primeNum) , where primeNum is largest prime number less that array size
Probing formula after calculating hashcode2 -:
(hashcode1 + (h * hashcode2)) % arraySize , h = 1, 2, 3, 4 and so on
7. To display all the elements of hash table, element at each index is accessed (via for loop).
8. To remove a key from hash table, we will first calculate its index and delete it if key matches, else probe through elements (using above formula) until we find key or an empty space where not a single data has been entered (means data does not exist in the hash table).
9. Exit

Program/Source Code

Here is the source code of C Program to implement a Hash Table with Double Hashing. 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<conio.h>
```
```
#include<math.h>
```
```
 
```
```
struct data 
```
```
{
```
```
	int key;
```
```
	int value;
```
```
};
```
```
 
```
```
struct hashtable_item 
```
```
{
```
```
 
```
```
	int flag;
```
```
	/*
```
```
	 * flag = 0 : data not present
```

	 * flag = 1 : some data already present

	 * flag = 2 : data was present,but deleted

```
	*/
```
```
	struct data *item;
```
```
 
```
```
};
```
```
 
```
```
struct hashtable_item *array;
```
```
int max = 7;
```
```
int size = 0;
```
```
int prime = 3;
```
```
 
```
```
int hashcode1(int key)
```
```
{
```
```
	return (key % max);
```
```
}
```
```
 
```
```
int hashcode2(int key)
```
```
{
```
```
	return (prime - (key % prime));
```
```
}
```
```
 
```
```
void insert(int key, int value)
```
```
{
```
```
	int hash1 = hashcode1(key);
```
```
	int hash2 = hashcode2(key);
```
```
 
```
```
	int index = hash1;
```
```
 
```
```
	/* create new data to insert */
```

	struct data *new_item = (struct data*) malloc(sizeof(struct data));

```
	new_item->key = key;
```
```
	new_item->value = value;
```
```
 
```
```
	if (size == max) 
```
```
        {
```

		printf("\n Hash Table is full, cannot insert more items \n");

```
		return;
```
```
	}
```
```
 
```

	/* probing through other array elements */

```
	while (array[index].flag == 1) {
```
```
		if (array[index].item->key == key)
```
```
                {
```

			printf("\n Key already present, hence updating its value \n");

```
			array[index].item->value = value;
```
```
			return;
```
```
		}
```
```
		index = (index + hash2) % max; 
```
```
		if (index == hash1)
```
```
                {
```
```
			printf("\n Add is failed \n");
```
```
			return;
```
```
		}
```
```
		printf("\n probing \n");
```
```
 
```
```
	}
```
```
 
```
```
	array[index].item = new_item;
```
```
	array[index].flag = 1;
```
```
	size++;
```

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

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

/* to remove an element from the array */

```
void remove_element(int key)
```
```
{
```
```
	int hash1 = hashcode1(key);
```
```
	int hash2 = hashcode2(key);
```
```
	int index = hash1;
```
```
 
```
```
	if (size == 0)
```
```
        {
```
```
		printf("\n Hash Table is empty \n");
```
```
		return;
```
```
	}
```
```
 
```
```
	/* probing through other elements */
```
```
	while (array[index].flag != 0)
```
```
        {
```

		if (array[index].flag == 1  &&  array[index].item->key == key)

```
                {
```
```
			array[index].item = NULL;
```
```
			array[index].flag = 2;
```
```
			size--;
```

			printf("\n Key (%d) has been removed \n", key);

```
			return;
```
```
		}
```
```
		index = (index + hash2) % max;
```
```
		if (index == hash1)
```
```
                {
```
```
			break;
```
```
		}
```
```
	}
```
```
 
```

	printf("\n Key (%d) does not exist \n", key);

```
 
```
```
}
```
```
 
```
```
int size_of_hashtable()
```
```
{
```
```
	return size;
```
```
}
```
```
 
```
```
/* displays all elements of array */
```
```
void display()
```
```
{
```
```
	int i;
```
```
	for (i = 0; i < max; i++)
```
```
        {
```
```
		if (array[i].flag != 1)
```
```
                {
```

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

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

			printf("\n Array[%d] has elements \n Key (%d) and Value (%d) \n", i, array[i].item->key, array[i].item->value);

```
		}
```
```
	}
```
```
}
```
```
 
```
```
/* initializes array */
```
```
void init_array()
```
```
{
```
```
	int i;
```
```
	for(i = 0; i < max; i++)
```
```
        {
```
```
		array[i].item = NULL;
```
```
		array[i].flag = 0;
```
```
	}
```
```
	prime = get_prime();
```
```
}
```
```
 
```

/* returns largest prime number less than size of array */

```
int get_prime()
```
```
{
```
```
	int i,j;
```
```
	for (i = max - 1; i >= 1; i--)
```
```
        {
```
```
		int flag = 0;
```
```
		for (j = 2; j <= (int)sqrt(i); j++)
```
```
                {
```
```
			if (i % j == 0)
```
```
                        {
```
```
				flag++;
```
```
			}
```
```
		}
```
```
		if (flag == 0)
```
```
                {
```
```
			return i;
```
```
		}
```
```
	}
```
```
	return 3;
```
```
 
```
```
}
```
```
 
```
```
void main()
```
```
{
```
```
	int choice, key, value, n, c;
```
```
	clrscr();
```
```
 
```

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

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

		printf("Implementation of Hash Table in C with Double Hashing.\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 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_hashtable();
```

		      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

Note : Hash Table with Double Hashing consists of probing through array elements (looping back if necessary) but differs in the way that it calculates other hash code of given key and uses that in probing
hashcode2 = primeNum – (key % primeNum) , where primeNum is largest prime number less that array size
Probing formula after calculating hashcode2 -:
(hashcode1 + (h * hashcode2)) % arraySize , h = 1, 2, 3, 4 and so on.
1. Create a structure, item having a key and value representing data to be inserted in hash table.
2. Create another structure, hashtable_item with variable data (key and value) and flag as a status variable which informs about the status of array index.
flag = 1 : presence of some data at the array index.
flag = 0 : data not present in array index even once
flag = 2 : data had been removed from array index at least once
3. Now create an array of structure (hashtable_item) of some certain size(7, in this case). This array will be our hash table.
Note: array size should be taken a prime number to produce good results.
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 (using hashcode() function).
(c) Access the element at this calculated index in array.
(d) If there is no element at that particular array index, add straight way.
(e) If an element is present, check whether the given key matches the element’s key. If yes, then update it’s value and return. Otherwise probe through subsequent elements (looping back if necessary), to find free space. While probing
* if given key matches the element’s key, update its value and return.
* if a free space is found, add the data at that position.
Probing will stop until we reach the same element from where we began probing. Until then, if no free space is found, then add will fail.
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 (using hashcode() function).
(c) Access the element at the calculated array index.
(d) If an element is present, check whether the given key matches the element’s key. If yes, then delete the key and return decrementing the size. Otherwise probe through subsequent elements (looping back if necessary), to find free space with flag = 0. While probing
* if given key matches the element’s key, delete and return.
* if a free space is found (with flag = 2), continue to probe.
(e) If no free space (flag = 0) is found even after probing through all element it means, key does not exist in the hash table.
8. 3rd choice: Size of hash table
(a) Each time we add a new data item into the hash table, we increment it’s size by 1.
(b) Each time we remove a data item from the hash table, we decrement it’s size by 1.
(c) 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 accessing each element at that index of array.

Runtime Test Cases

 
Implementation of Hash Table in C with Double Hashing
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 with Double Hashing
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-:   12 	1
 
 Key (12) has been inserted
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C with Double Hashing
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-:   47 	1
 
 probing
 
 Key (47) has been inserted
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C with Double Hashing
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-:   61 	1
 
 probing
 
 Key (61) has been inserted
 
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C with Double Hashing
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-: 3
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C with Double Hashing
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 elements-:
47 (key) and 1 (value)
 
Array[2] has elements-:
61 (key) and 1 (value)
 
Array[3] has elements-:
 
 
Array[4] has no elements
 
Array[5] has elements-:
12 (key) and 1 (value)
 
Array[6] has no elements
 
 
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C with Double Hashing
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 in hash table
Enter the key to delete-: 61
 
 Key (61) has been removed
 
Do you want to continue-:(press 1 for yes) 1
Implementation of Hash Table in C with Double Hashing
MENU-:
1. Inserting item in the Hash Table
2. Removing item from the Hash Table
3. Check the size of Hash Table
4. Display a Hash Table
 
Please enter your choice-: 2
Deleting in hash table
Enter the key to delete-: 61
 
 This key does not exist
 
Do you want to continue-:(press 1 for yes) 2

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Search an Element in a Binary Search Tree

» Next - C Program to Implement Binomial Heap

Related Posts:

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

Recommended Articles: