{"id":741,"date":"2024-10-19T13:52:01","date_gmt":"2024-10-19T08:22:01","guid":{"rendered":"https:\/\/codexplained.in\/?p=741"},"modified":"2025-11-24T15:34:08","modified_gmt":"2025-11-24T10:04:08","slug":"implement-hash-table-using-chaining","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=741","title":{"rendered":"Implement Hash Table using Chaining"},"content":{"rendered":"
\n#include <stdio.h>\n#include <stdlib.h>\n\n\/\/ Define the structure for the nodes in the linked list\nstruct Node {\n    int data;\n    struct Node* next;\n};\n\n\/\/ Function to create a new node with given data\nstruct Node* createNode(int data) {\n    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\n    newNode->data = data;\n    newNode->next = NULL;\n    return newNode;\n}\n\n\/\/ Function to insert a value into the hash table\nvoid insert(struct Node* hashTable[], int key, int tableSize) {\n    int index = key % tableSize;\n    struct Node* newNode = createNode(key);\n    newNode->next = hashTable[index];\n    hashTable[index] = newNode;\n}\n\n\/\/ Function to search for a value in the hash table\nint search(struct Node* hashTable[], int key, int tableSize) {\n    int index = key % tableSize;\n    struct Node* temp = hashTable[index];\n    while (temp) {\n        if (temp->data == key) {\n            return 1; \/\/ Key found\n        }\n        temp = temp->next;\n    }\n    return 0; \/\/ Key not found\n}\n\n\/\/ Function to delete a value from the hash table\nvoid delete(struct Node* hashTable[], int key, int tableSize) {\n    int index = key % tableSize;\n    struct Node* temp = hashTable[index];\n    struct Node* prev = NULL;\n\n    \/\/ Traverse the linked list at that index\n    while (temp != NULL && temp->data != key) {\n        prev = temp;\n        temp = temp->next;\n    }\n\n    \/\/ If the key is not present\n    if (temp == NULL) {\n        printf("Key %d not found.\\n", key);\n        return;\n    }\n\n    \/\/ Key is present at the head of the linked list\n    if (prev == NULL) {\n        hashTable[index] = temp->next;\n    } else {\n        prev->next = temp->next;\n    }\n\n    free(temp);\n    printf("Key %d deleted.\\n", key);\n}\n\n\/\/ Function to display the hash table\nvoid display(struct Node* hashTable[], int tableSize) {\n    for (int i = 0; i < tableSize; i++) {\n        printf("HashTable[%d]: ", i);\n        struct Node* temp = hashTable[i];\n        while (temp) {\n            printf("%d -> ", temp->data);\n            temp = temp->next;\n        }\n        printf("NULL\\n");\n    }\n}\n\n\/\/ Main function\nint main() {\n    int tableSize = 10; \/\/ Define size of the hash table\n    struct Node* hashTable[tableSize];\n\n    \/\/ Initialize the hash table\n    for (int i = 0; i < tableSize; i++) {\n        hashTable[i] = NULL;\n    }\n\n    \/\/ Insert elements into the hash table\n    insert(hashTable, 5, tableSize);\n    insert(hashTable, 15, tableSize);\n    insert(hashTable, 25, tableSize);\n    insert(hashTable, 35, tableSize);\n\n    printf("Hash table after insertion:\\n");\n    display(hashTable, tableSize);\n\n    \/\/ Search for a key in the hash table\n    int searchKey = 15;\n    if (search(hashTable, searchKey, tableSize)) {\n        printf("Key %d found.\\n", searchKey);\n    } else {\n        printf("Key %d not found.\\n", searchKey);\n    }\n\n    \/\/ Delete a key from the hash table\n    delete(hashTable, 15, tableSize);\n    printf("Hash table after deletion:\\n");\n    display(hashTable, tableSize);\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
Explanation<\/h3>\n\n\n\n
    \n
  1. Structure of Node<\/strong>:\n
      \n
    • The struct Node<\/code> represents each node in a linked list.<\/li>\n\n\n\n
    • Each node stores an integer data<\/code> and a pointer next<\/code> to the next node.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
    • Creating a Node<\/strong>:\n
        \n
      • The createNode<\/code> function allocates memory for a new node, assigns the data, and initializes the next<\/code> pointer to NULL<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
      • Hash Function<\/strong>:\n
          \n
        • The hash function used here is a simple modulus operation (key % tableSize<\/code>), which calculates the index where a particular key should be stored.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • Insert Function<\/strong>:\n
            \n
          • The insert<\/code> function calculates the index using the hash function.<\/li>\n\n\n\n
          • It creates a new node with the given key and inserts it at the beginning of the linked list at that index.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
          • Search Function<\/strong>:\n
              \n
            • The search<\/code> function calculates the index and traverses the linked list at that index.<\/li>\n\n\n\n
            • If a node with the key is found, it returns 1<\/code> (key found).<\/li>\n\n\n\n
            • Otherwise, it returns 0<\/code> (key not found).<\/li>\n<\/ul>\n<\/li>\n\n\n\n
            • Delete Function<\/strong>:\n
                \n
              • The delete<\/code> function calculates the index and searches for the node with the given key.<\/li>\n\n\n\n
              • If the node is found, it adjusts the pointers to remove the node from the linked list and frees its memory.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
              • Display Function<\/strong>:\n
                  \n
                • The display<\/code> function iterates through the hash table.<\/li>\n\n\n\n
                • For each index, it prints the keys stored in the linked list at that index.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                • Main Function<\/strong>:\n
                    \n
                  • It initializes the hash table with a given size.<\/li>\n\n\n\n
                  • It inserts values into the hash table, displays it, searches for a value, deletes a value, and displays the updated hash table.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
                    Output<\/h3>\n\n\n\n
                    Hash table after insertion:\nHashTable[0]: NULL\nHashTable[1]: NULL\nHashTable[2]: NULL\nHashTable[3]: NULL\nHashTable[4]: NULL\nHashTable[5]: 35 -> 25 -> 15 -> 5 -> NULL\nHashTable[6]: NULL\nHashTable[7]: NULL\nHashTable[8]: NULL\nHashTable[9]: NULL\n\nKey 15 found.\nKey 15 deleted.\n\nHash table after deletion:\nHashTable[0]: NULL\nHashTable[1]: NULL\nHashTable[2]: NULL\nHashTable[3]: NULL\nHashTable[4]: NULL\nHashTable[5]: 35 -> 25 -> 5 -> NULL\nHashTable[6]: NULL\nHashTable[7]: NULL\nHashTable[8]: NULL\nHashTable[9]: NULL\n<\/code><\/pre>\n\n\n\n
                    Summary<\/h3>\n\n\n\n
                    This implementation of a hash table using chaining effectively handles collisions by storing keys in a linked list at each index. It allows for efficient insertion, searching, and deletion of keys. By chaining, we can manage cases where multiple keys hash to the same index without loss of data.<\/p>\n