DSA Tutorial

🔐 Hash Sets in DSA (Using C)

A Hash Set is a data structure that stores unique elements and provides efficient operations like insertion, deletion, and searching. Hash Sets are based on the concept of hash tables and are typically used when you want to store a collection of distinct values without duplicates.

🧠 What is a Hash Set?

A Hash Set is an unordered collection of unique elements. It is backed by a hash table and performs operations like adding, deleting, and searching for elements in O(1) average time.

Key Features of Hash Sets:

• Contains only unique elements (no duplicates).
• Allows fast lookups, insertions, and deletions.
• Unordered collection of elements.

💻 C Code: Basic Hash Set Implementation

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10

int hashSet[SIZE];

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

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

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

    while (hashSet[(index + i) % SIZE] != -1 && hashSet[(index + i) % SIZE] != key)
        i++;

    if (hashSet[(index + i) % SIZE] == -1)
        hashSet[(index + i) % SIZE] = key;
}

int contains(int key) {
    int index = hashFunction(key);
    int i = 0;

    while (hashSet[(index + i) % SIZE] != -1) {
        if (hashSet[(index + i) % SIZE] == key)
            return 1; // Element found
        i++;
    }
    return 0; // Element not found
}

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

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

    printf("Contains 20: %d\\n", contains(20)); // Should return 1 (True)
    printf("Contains 50: %d\\n", contains(50)); // Should return 0 (False)

    display();
    return 0;
}
  

📤 Sample Output

Contains 20: 1
Contains 50: 0
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 Handling in Hash Sets

Collisions occur when two elements hash to the same index. In Hash Sets, collisions can be handled using techniques such as:

• Linear Probing: Keep searching for the next empty slot.
• Chaining: Use a linked list to handle multiple elements at the same index.