DSA Tutorial

🔐 Hash Maps in DSA (Using C)

A Hash Map (also known as a Hash Table) is a data structure that stores key-value pairs. It allows for fast access to values based on a unique key. Hash Maps are widely used due to their efficiency in retrieving, inserting, and deleting elements in constant time.

🧠 What is a Hash Map?

A Hash Map is a collection of key-value pairs, where each key is unique. The value associated with a key can be any type, and the key is used to index and access the value efficiently. Hash Maps are implemented using hash tables, which provide average time complexity of O(1) for insertion, deletion, and searching.

Key Features of Hash Maps:

• Stores key-value pairs.
• Allows fast access using keys.
• Handles collisions using methods like chaining or open addressing.
• Does not maintain any specific order of elements.

💻 C Code: Basic Hash Map Implementation

#include <stdio.h>
#include <stdlib.h>

#define SIZE 10

struct HashMap {
    int key;
    int value;
    int isOccupied;
};

struct HashMap hashMap[SIZE];

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

void init() {
    for (int i = 0; i < SIZE; i++) {
        hashMap[i].isOccupied = 0;
    }
}

void insert(int key, int value) {
    int index = hashFunction(key);

    while (hashMap[index].isOccupied && hashMap[index].key != key) {
        index = (index + 1) % SIZE;  // Linear probing
    }

    hashMap[index].key = key;
    hashMap[index].value = value;
    hashMap[index].isOccupied = 1;
}

int get(int key) {
    int index = hashFunction(key);

    while (hashMap[index].isOccupied) {
        if (hashMap[index].key == key)
            return hashMap[index].value;  // Value found
        index = (index + 1) % SIZE;
    }
    return -1;  // Key not found
}

void display() {
    for (int i = 0; i < SIZE; i++) {
        if (hashMap[i].isOccupied) {
            printf("Key: %d, Value: %d\\n", hashMap[i].key, hashMap[i].value);
        }
    }
}

int main() {
    init();
    insert(10, 100);
    insert(20, 200);
    insert(30, 300);

    printf("Value for key 20: %d\\n", get(20)); // Should return 200
    printf("Value for key 40: %d\\n", get(40)); // Should return -1 (Key not found)

    display();
    return 0;
}
  

📤 Sample Output

Value for key 20: 200
Value for key 40: -1
Key: 10, Value: 100
Key: 20, Value: 200
Key: 30, Value: 300
  

🔁 Collision Handling in Hash Maps

When two keys hash to the same index, a collision occurs. In Hash Maps, collisions can be handled using various techniques:

• Chaining: Store multiple key-value pairs in a linked list at the same index.
• Open Addressing: Find the next available index (e.g., linear probing, quadratic probing).