Use Hashing to search an element in a linked list
Neelkanth_221$ cat hashing.c
/*********************************************************************
* Hashing is a technique that is used to uniquely identify a specific
* object from a group of similar objects. Some examples of how hashing
* is used in our lives include:
*
* In universities, each student is assigned a unique roll number that
* can be used to retrieve information about them.
* In libraries, each book is assigned a unique number that can be used
* to determine information about the book, such as its exact position
* in the library or the users it has been issued to etc.
* In both these examples the students and books were hashed to a
* unique number.
*********************************************************************/
/*********************************************************************
* WHAT BELOW CODE DOES ?
*
* Create a Linked List.
* Each node in a linked list, will have (Key, Data).
* Now, there is something called hash function, that will generate
* a hash from the "Key" present in each node in the Linked List.
* The generate hash value is an index of an array [An array of pointers
* to nodes in a linked list.]
* Now, instead of searching the data in a linked list , the
* search will be performed on the basis of hash value of the key.
*********************************************************************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define SIZE 20
/* Un-comment this to enable debug logs */
//#define DEBUG 1
/*********************************************************************
* GLOBAL DATA STRUCTURES
*********************************************************************/
typedef struct DataItem {
int data;
int key;
}data_item;
/********************************************************************
* Global Array of pointers pointing to the members of linked list
* i.e. hashArray[i] ---> data_item (members= key, data)
********************************************************************/
data_item* hashArray[SIZE];
data_item* dummyItem;
data_item* item;
/*****************************************************************************
Linked List
------- ------- ------- -------
|key 1| ------> |key 2| ------> |key42| ------> |key 4|
|Data | ------> |Data | ------> |Data | ------> |Data |
------- ------- ------- -------
^ ^ ^ ^
| | | |
hashArray[a] hashArray[b] hashArray[c] hashArray[d]
The search for the data is performed using the hash i.e. hashArray's index.
The index of hashArray is derived by hashing the key field in the node
of linked list.
***************************************************************************/
/********************************************************************
* USER DEFINED FUNCTIONS
********************************************************************/
int hashCode(int key) {
#ifdef DEBUG
printf("hashCode: Key: %d\n", key);
#endif
return key % SIZE;
}
/***********************************************************************
* Insert Element into Linked List. Also, update the array of pointer
* index with newly created node in the linked list based on the
* generated hash index value.
***********************************************************************/
void insert(int key,int data) {
data_item *item = (data_item*) malloc(sizeof(data_item));
item->data = data;
item->key = key;
#ifdef DEBUG
printf("----> Insert Key: %d and Data: %d\n", key, data);
#endif
/****************************************************************************
* Get the hash i.e the hash the key value in the node of a linked list
* to get the hash. Now, The "hash" is the index of "hashArray" global array,
* that points to corresponding node in the linked list.
****************************************************************************/
int hashIndex = hashCode(key);
#ifdef DEBUG
printf("insert: hashIndex initial: %d\n", hashIndex);
#endif
/***********************************************************************
* Move in array in circular manner, until an empty or deleted cell.
***********************************************************************/
while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
/* Go to next cell */
++hashIndex;
/******************************************************************
* When hashIndex == SIZE(20),
* then use modulo to wrap around the index. i.e 21%20= 1.
* So, it starts from 1st index again.
******************************************************************/
hashIndex %= SIZE;
}
#ifdef DEBUG
printf("insert: hashIndex final : %d\n", hashIndex);
#endif
hashArray[hashIndex] = item;
}
/*************************************************************************
* Delete the item from the Linked List.
*************************************************************************/
data_item* delete(data_item* item)
{
int key = item->key;
/**************************************************************************
* Get the hash i.e index of the array of pointer pointing to corresponding
* element in the linked list
**************************************************************************/
int hashIndex = hashCode(key);
/* Move in array until an empty. */
while(hashArray[hashIndex] != NULL) {
if(hashArray[hashIndex]->key == key) {
data_item* temp = hashArray[hashIndex];
/* Assign a dummy item at deleted position */
hashArray[hashIndex] = dummyItem;
return temp;
}
/* Go to next cell */
++hashIndex;
/* Wrap around the table */
hashIndex %= SIZE;
}
return NULL;
}
/*******************************************************************
* Search for the node in the linked list using HASHING !
*******************************************************************/
data_item *search(int key) {
/* Get the hash */
int hashIndex = hashCode(key);
/* Move in array until an empty */
while(hashArray[hashIndex] != NULL) {
if(hashArray[hashIndex]->key == key)
return hashArray[hashIndex];
/* Go to next cell */
++hashIndex;
/* Wrap around the table */
hashIndex %= SIZE;
}
return NULL;
}
/***********************************************************************
* Display Items in the linked list pointed by array of pointers.
* If a pointer doesn't point to anything, then print "EMPTY"
***********************************************************************/
void display() {
int i = 0;
for(i = 0; i<SIZE; i++) {
if(hashArray[i] != NULL)
printf(" (%d,%d)", hashArray[i]->key,hashArray[i]->data);
else
printf(" (EMPTY) ");
}
printf("\n");
}
int main() {
dummyItem = (data_item*) malloc(sizeof(data_item));
dummyItem->data = -1;
dummyItem->key = -1;
/* Insert new element in to linked list.
*
* insert(<key>, <data>)
* hash(key) is the index of the array of pointers.
* Searching is done on the basis of hash value rather than
* searching for the data.
*/
insert(1, 20);
insert(2, 70);
insert(42, 80);
insert(4, 25);
insert(12, 44);
insert(14, 32);
insert(17, 11);
insert(13, 78);
insert(37, 97);
printf("ALL ITEMS INSERTED INTO LINKED LIST\n");
/* Display all elements of the linked list*/
display();
/*****************************************************************
* Search the hash element 37 whose hash value is 97
*****************************************************************/
printf("\nSEARCH FOR ELEMENT 97 ON THE BASIS OF IT'S KEY 37\n");
item = search(37);
if(item != NULL) {
printf("Element found: %d\n", item->data);
} else {
printf("Element not found\n");
}
/* Delete all elements of a linked list. */
printf("\nNOW DELETE THE ITEM IN LINKED LIST HAVING DATA AS 97\n");
delete(item);
printf("\nSEARCH FOR ELEMENT 97 ON THE BASIS OF IT'S KEY 37\n");
item = search(37);
if(item != NULL) {
printf("Element found: %d\n", item->data);
} else {
printf("Element not found\n");
}
return 0;
}
Output
Neelkanth_221$ ./a.out
ALL ITEMS INSERTED INTO LINKED LIST
(EMPTY) (1,20) (2,70) (42,80) (4,25) (EMPTY) (EMPTY) (EMPTY) (EMPTY) (EMPTY) (EMPTY) (EMPTY) (12,44) (13,78) (14,32) (EMPTY) (EMPTY) (17,11) (37,97) (EMPTY)
SEARCH FOR ELEMENT 97 ON THE BASIS OF IT'S KEY 37
Element found: 97
NOW DELETE THE ITEM IN LINKED LIST HAVING DATA AS 97
SEARCH FOR ELEMENT 97 ON THE BASIS OF IT'S KEY 37
Element not found