DSA Tutorial

🔐 Hash Tables in DSA (Using C)

A Hash Table is a data structure that stores key-value pairs using a technique called hashing. It offers fast insertion, deletion, and search operations — typically in constant time O(1).

🧠 What is Hashing?

Hashing is the process of converting a key into an index using a hash function. This index determines where the key-value pair will be stored in the table.

Hash Function Example:

index = key % table_size;
  

💻 C Code: Basic Hash Table with Linear Probing

#include <stdio.h>
#define SIZE 10

int hashTable[SIZE];

void init() {
    for (int i = 0; i < SIZE; i++)
        hashTable[i] = -1;
}

int hashFunction(int key) {
    return key % SIZE;
}

void insert(int key) {
    int index = hashFunction(key);
    int i = 0;

    while (hashTable[(index + i) % SIZE] != -1)
        i++;

    hashTable[(index + i) % SIZE] = key;
}

void display() {
    for (int i = 0; i < SIZE; i++)
        printf("Index %d: %d\\n", i, hashTable[i]);
}

int main() {
    init();
    insert(10);
    insert(20);
    insert(30);
    insert(23);
    insert(33);

    display();
    return 0;
}
  

📤 Sample Output

Index 0: -1
Index 1: -1
Index 2: 32
Index 3: 23
Index 4: 34
Index 5: -1
Index 6: -1
Index 7: -1
Index 8: -1
Index 9: 10
  

🔁 Collision Resolution

When two keys map to the same index, a collision occurs. Common techniques to resolve it:

• Linear Probing – find the next empty slot
• Chaining – use a linked list at each index
• Quadratic Probing – explore indices with square intervals