{"id":734,"date":"2024-10-19T13:54:09","date_gmt":"2024-10-19T08:24:09","guid":{"rendered":"https:\/\/codexplained.in\/?p=734"},"modified":"2025-11-24T15:31:59","modified_gmt":"2025-11-24T10:01:59","slug":"implement-hash-table-using-arrays","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=734","title":{"rendered":"Implement Hash Table using Arrays"},"content":{"rendered":"
\n#include <stdio.h>\n#include <stdlib.h>\n\n#define TABLE_SIZE 10\n\n\/\/ Define the structure of each element in the hash table\ntypedef struct {\n    int key;\n    int value;\n    int is_occupied; \/\/ 0 means empty, 1 means occupied\n} HashItem;\n\n\/\/ Initialize the hash table as an array\nHashItem hashTable[TABLE_SIZE];\n\n\/\/ Hash function to map keys to indices\nint hashFunction(int key) {\n    return key % TABLE_SIZE;\n}\n\n\/\/ Function to insert a key-value pair into the hash table\nvoid insert(int key, int value) {\n    int index = hashFunction(key);\n\n    \/\/ Use linear probing in case of collision\n    while (hashTable[index].is_occupied) {\n        if (hashTable[index].key == key) {\n            \/\/ If key already exists, update the value\n            hashTable[index].value = value;\n            printf("Updated key %d with value %d at index %d\\n", key, value, index);\n            return;\n        }\n        index = (index + 1) % TABLE_SIZE; \/\/ Move to the next index\n    }\n\n    \/\/ Insert the new key-value pair\n    hashTable[index].key = key;\n    hashTable[index].value = value;\n    hashTable[index].is_occupied = 1; \/\/ Mark as occupied\n    printf("Inserted key %d with value %d at index %d\\n", key, value, index);\n}\n\n\/\/ Function to search for a value by its key in the hash table\nint search(int key) {\n    int index = hashFunction(key);\n\n    \/\/ Use linear probing to search for the key\n    while (hashTable[index].is_occupied) {\n        if (hashTable[index].key == key) {\n            \/\/ If key is found, return the value\n            return hashTable[index].value;\n        }\n        index = (index + 1) % TABLE_SIZE; \/\/ Move to the next index\n    }\n\n    \/\/ If key is not found, return -1\n    return -1;\n}\n\n\/\/ Function to delete a key-value pair from the hash table\nvoid delete(int key) {\n    int index = hashFunction(key);\n\n    \/\/ Use linear probing to find the key\n    while (hashTable[index].is_occupied) {\n        if (hashTable[index].key == key) {\n            \/\/ Mark the slot as empty\n            hashTable[index].is_occupied = 0;\n            printf("Deleted key %d from index %d\\n", key, index);\n            return;\n        }\n        index = (index + 1) % TABLE_SIZE; \/\/ Move to the next index\n    }\n\n    printf("Key %d not found for deletion\\n", key);\n}\n\n\/\/ Function to display the hash table\nvoid display() {\n    printf("Hash Table:\\n");\n    for (int i = 0; i < TABLE_SIZE; i++) {\n        if (hashTable[i].is_occupied) {\n            printf("Index %d: Key %d, Value %d\\n", i, hashTable[i].key, hashTable[i].value);\n        } else {\n            printf("Index %d: Empty\\n", i);\n        }\n    }\n}\n\n\/\/ Main function to test the hash table\nint main() {\n    \/\/ Initialize the hash table slots as empty\n    for (int i = 0; i < TABLE_SIZE; i++) {\n        hashTable[i].is_occupied = 0;\n    }\n\n    \/\/ Insert some key-value pairs\n    insert(1, 10);\n    insert(11, 20);\n    insert(21, 30);\n    insert(31, 40);\n\n    \/\/ Display the hash table\n    display();\n\n    \/\/ Search for a key\n    int key = 11;\n    int result = search(key);\n    if (result != -1) {\n        printf("Value for key %d: %d\\n", key, result);\n    } else {\n        printf("Key %d not found in hash table\\n", key);\n    }\n\n    \/\/ Delete a key\n    delete(11);\n    display();\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
Explanation of the Code<\/h3>\n\n\n\n
    \n
  1. HashItem Structure<\/strong>:\n
      \n
    • key<\/code>: The key for the hash table.<\/li>\n\n\n\n
    • value<\/code>: The associated value.<\/li>\n\n\n\n
    • is_occupied<\/code>: A flag to indicate whether the slot is occupied (1) or empty (0).<\/li>\n<\/ul>\n<\/li>\n\n\n\n
    • hashFunction<\/strong>: It computes the index using the formula key % TABLE_SIZE<\/code> to ensure the index falls within the array bounds.<\/li>\n\n\n\n
    • Insertion (insert function)<\/strong>:\n
        \n
      • Compute the index using the hash function.<\/li>\n\n\n\n
      • Use linear probing if the computed index is occupied (i.e., continue checking the next slot until an empty slot is found).<\/li>\n\n\n\n
      • Insert the key-value pair at the first empty slot or update the value if the key already exists.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
      • Search (search function)<\/strong>:\n
          \n
        • Compute the index using the hash function.<\/li>\n\n\n\n
        • Use linear probing to find the key. If found, return its value; otherwise, return -1<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • Deletion (delete function)<\/strong>:\n
            \n
          • Compute the index using the hash function.<\/li>\n\n\n\n
          • Use linear probing to find the key and mark the slot as empty when found.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
          • Display (display function)<\/strong>: This function iterates over the hash table and prints the content of each slot.<\/li>\n\n\n\n
          • Main Function<\/strong>:\n
              \n
            • Initializes the hash table.<\/li>\n\n\n\n
            • Performs insertions, displays the table, searches for a key, deletes a key, and displays the table again to show changes.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
              Output of the Program<\/h3>\n\n\n\n
              Inserted key 1 with value 10 at index 1\nInserted key 11 with value 20 at index 2\nInserted key 21 with value 30 at index 3\nInserted key 31 with value 40 at index 4\nHash Table:\nIndex 0: Empty\nIndex 1: Key 1, Value 10\nIndex 2: Key 11, Value 20\nIndex 3: Key 21, Value 30\nIndex 4: Key 31, Value 40\nIndex 5: Empty\nIndex 6: Empty\nIndex 7: Empty\nIndex 8: Empty\nIndex 9: Empty\nValue for key 11: 20\nDeleted key 11 from index 2\nHash Table:\nIndex 0: Empty\nIndex 1: Key 1, Value 10\nIndex 2: Empty\nIndex 3: Key 21, Value 30\nIndex 4: Key 31, Value 40\nIndex 5: Empty\nIndex 6: Empty\nIndex 7: Empty\nIndex 8: Empty\nIndex 9: Empty\n<\/code><\/pre>\n