C Program to Implement Hash Tables Chaining with Binary Trees

This is a C Program to Implement Hash Tables Chaining with Binary Trees.

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. This program will implement hash table where at each array index, we will create a Binary tree, to prevent key collision. Key having same index will be stored in Binary tree as it can store multiple data.

Problem Solution

1. Create an array of Binary Trees (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 Binary Tree of a particular array index.
4. Using the generated index, extract the Binary Tree located in that array index.
5. In case of absence of a tree, create one and insert a data item (key and value) into it and increment the size of hash table.
6. In case the tree already exists, search for the key (given as input) in the Binary Tree, and add the data item (key and value) into it if key does not belong to the tree and increment the size, otherwise update the value of given (and already present) key in the Binary Tree.
7. To display all the elements of hash table, Binary Tree at each index is extracted and all the elements (key and value) are read and printed.
8. To remove a key from hash table, we will first calculate its index and extract its Binary Tree, find the key in tree 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 Binary Tree. 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<stdlib.h>
```
```
 
```

int max = 10;          /* determines the maximum capacity of Hash Table array */

int size = 0;          /* determines the number of elements present in Hash Table */

```
 
```

/* node for storing an item in a Binary Tree */

```
struct node 
```
```
{
```
```
	int key;
```
```
	int value;
```
```
	struct node *left;
```
```
	struct node *right;
```
```
};
```
```
 
```

/* for storing a Binary Tree at each index of Hash Table array */

```
struct bst 
```
```
{
```
```
	struct node *head;
```

	/* head pointing to the root of Binary Tree */

```
};
```
```
 
```
```
struct bst *array;
```
```
 
```

void insert_element(struct node *tree, struct node *item);

struct node* find(struct node *tree, int key);

struct node* remove_element(struct node *tree, int key);

```
void display_tree(struct node *tree);
```
```
 
```

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

```
int hashcode(int key)
```
```
{
```
```
	return (key % max);
```
```
}
```
```
 
```
```
void add(int key, int value)
```
```
{
```
```
	int index = hashcode(key);
```
```
 
```

	/* extracting Binary Tree at the given index */

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

```
 
```

	/* creating an item to insert in the hashtable */

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

```
	new_item->key = key;
```
```
	new_item->value = value;
```
```
	new_item->left = NULL;
```
```
	new_item->right = NULL;
```
```
 
```
```
	if (tree == NULL) 
```
```
        {
```

		/* absence of Binary Tree at a given index of Hash Table array */

```
 
```

		printf("Inserting %d(key) and %d(value)\n", key, value);

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

		/* a Binary Tree is present at given index of Hash Table */

```
 
```
```
		struct node *temp = find(tree, key);
```
```
		if (temp == NULL) 
```
```
                {
```
```
			/*
```

			 * Key not found in existing Binary Tree

			 * Adding the key in existing Binary Tree

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

			printf("Inserting %d(key) and %d(value) \n", key, value);

```
			insert_element(tree, new_item);
```
```
			size++;
```
```
 
```
```
		}
```
```
		else 
```
```
                {
```
```
			/*
```

			 * Key already present in existing Binary Tree

			 * Updating the value of already existing key

```
			*/
```
```
 
```
```
			temp->value = value;
```
```
 
```
```
		}
```
```
	}
```
```
 
```
```
}
```
```
 
```
```
 
```
```
/*
```

 * this function finds the given key in the Binary Tree

```
 * returns the node containing the key
```

 * returns NULL in case key is not present

```
*/
```

struct node* find(struct node *tree, int key)

```
{
```
```
	if (tree == NULL) 
```
```
        {
```
```
		return NULL;
```
```
	}
```
```
	if (tree->key == key)
```
```
        {
```
```
		return tree;
```
```
	}
```
```
	else if (key < tree->key)
```
```
        {
```
```
		return find(tree->left, key);
```
```
	}
```
```
	else 
```
```
        {
```
```
		return find(tree->right, key);
```
```
	}
```
```
 
```
```
}
```
```
 
```

/* this function inserts the newly created node in the existing Binary Tree */

void insert_element(struct node *tree, struct node *item)

```
{
```
```
	if (item->key < tree->key)
```
```
        {
```
```
		if (tree->left == NULL)
```
```
                {
```
```
			tree->left = item;
```
```
			return;
```
```
		}
```
```
		else 
```
```
                {
```
```
			insert_element(tree->left, item);
```
```
			return;
```
```
		}
```
```
	}
```
```
	else if (item->key > tree->key)
```
```
        {
```
```
		if (tree->right == NULL)
```
```
                {
```
```
			tree->right = item;
```
```
			return;
```
```
		}
```
```
		else
```
```
                {
```
```
			insert_element(tree->right, item);
```
```
			return;
```
```
		}
```
```
	}
```
```
}
```
```
 
```

/* displays the content of hash table */

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

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

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

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

```
			display_tree(tree);
```
```
		}
```
```
	}
```
```
}
```
```
 
```

/* displays content of binary tree of particular index */

```
void display_tree(struct node *tree)
```
```
{
```
```
    	if (tree == NULL)
```
```
        {
```
```
        	return;
```
```
    	}
```

    	printf("%d and %d \t", tree->key, tree->value);

```
 
```
```
    	if (tree->left != NULL)
```
```
        {
```
```
        	display_tree(tree->left);
```
```
    	}
```
```
    	if (tree->right != NULL)
```
```
        {
```
```
        	display_tree(tree->right);
```
```
    	}
```
```
 
```
```
}
```
```
 
```
```
/* for initializing the hash table */
```
```
void init()
```
```
{
```
```
    	int i = 0;
```
```
    	for(i = 0; i < max; i++)
```
```
        {
```
```
        	array[i].head = NULL;
```
```
    	}
```
```
 
```
```
}
```
```
 
```
```
/* returns the size of hash table */
```
```
int size_of_hashtable()
```
```
{
```
```
	return size;
```
```
}
```
```
 
```
```
/* to delete a key from hash table */
```
```
void delete(int key) 
```
```
{
```
```
    	int index = hashcode(key);
```

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

```
    	if (tree == NULL)
```
```
        {
```

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

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

        	struct node *temp = find(tree, key);

```
        	if (temp == NULL) 
```
```
                {
```

            		printf("%d Key not present.", key);

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

            		tree = remove_element(tree, key);

			printf("%d has been removed form the hash table\n", key);

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

struct node* remove_element(struct node *tree, int key)

```
{
```
```
    if (tree == NULL)
```
```
    {
```
```
        	return NULL;
```
```
    }
```
```
    if (key < tree->key) 
```
```
    {
```

        	tree->left = remove_element(tree->left, key);

```
        	return tree;
```
```
    }
```
```
    else if (key > tree->key) 
```
```
    {
```

        	tree->right = remove_element(tree->right, key);

```
        	return tree;
```
```
    }
```
```
    else {
```
```
		/* reached the node */
```

        	if (tree->left == NULL  &&  tree->right == NULL)

```
                {
```
```
            		size--;
```
```
            		return tree->left;
```
```
        	}
```

		else if (tree->left != NULL  &&  tree->right == NULL)

```
                {
```
```
            		size--;
```
```
            		return tree->left;
```
```
        	}
```

		else if (tree->left == NULL  &&  tree->right != NULL)

```
                {
```
```
            		size--;
```

                        return tree->right;

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

            		struct node *left_one = tree->left;

```
 
```

            		while (left_one->right != NULL)

```
                        {
```

                		left_one = left_one->right;

```
            		}
```
```
 
```
```
 		        tree->key = left_one->key;
```

               		tree->value = left_one->value;

             		tree->left = remove_element(tree->left, tree->key);

```
            		return tree;
```
```
         	}
```
```
    }
```
```
}
```
```
 
```
```
void main()
```
```
{
```
```
    	int choice, key, value, n, c;
```
```
	clrscr();
```
```
 
```

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

```
	init();
```
```
 
```
```
	do {
```

		printf("Implementation of Hash Table in C chaining with Binary Trees\n\n");

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

                              "\n2.Remove an 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);
```
```
		      add(key, value);
```
```
 
```
```
		      break;
```
```
 
```
```
		case 2:
```
```
 
```

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

```
		      scanf("%d", &key);
```
```
		      delete(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

1. Create a structure node(binary tree item) with key and value as data and left and right as a pointer variable which points the structure element of node type (left pointing to the left child of current node and right pointing to the right child of current node).
2. Create another structure(for binary tree) with head having the address of root element of binary tree.
3. Now create an array of binary tree 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 binary tree at the calculated array index.
(d) If binary tree is present, check whether the key already present in it by finding the node containing key using find() method which returns NULL if key is not present. In that case, we will create a data item and add it into binary tree. If key is already present in the tree, we will update the value of node containing key.
(e) If there is no tree at that particular array index, which means the key is not present in hash table, then create a data item and a binary tree and add the data item to it using insert_element() function.
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 binary tree at the calculated array index.
(d) If tree is present, find the node containing the key in binary tree using find() method which returns NULL if key not present. The key is removed using delete() method if it is present otherwise ‘Key not present’ message will get displayed.
(e) If there is no binary tree 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 binary tree at that index of array.
(d) As the content of each node of tree is displayed the variables left and right (pointers) is used to proceed further until all elements are displayed.

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
Inserting 1(key) and 10(value)
 
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 elements-:		1  10
array[1] has no elements
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
Element 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-: 1
1 has been removed from the Hash Table.
 
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.

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

« Prev - C Program to Implement Hash Tables with Linear Probing

» Next - C Program to Implement Hash Tables Chaining with Doubly Linked Lists

Related Posts:

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

Recommended Articles: