Hash Table এবং Collisions Handling (Chaining, Open Addressing) গাইড ও নোট

Hash Table একটি ডেটা স্ট্রাকচার যা কী-ভ্যালু জোড়া ধারণ করে এবং এটি দ্রুত অনুসন্ধান, সঞ্চয় এবং অ্যাক্সেস করার জন্য ব্যবহৃত হয়। একটি হ্যাশ টেবিল একটি হ্যাশ ফাংশন ব্যবহার করে কী থেকে একটি ইনডেক্স তৈরি করে, যা ডেটা স্টোর করার অবস্থান নির্দেশ করে। তবে, যখন দুটি ভিন্ন কী একই হ্যাশ ইনডেক্স তৈরি করে তখন সংঘর্ষ (collision) ঘটে। এই সমস্যা সমাধানের জন্য বিভিন্ন কৌশল রয়েছে, যার মধ্যে Chaining এবং Open Addressing সবচেয়ে সাধারণ।

১. Hash Table

১.১ Hash Table এর গঠন

• কী (Key): একটি ইউনিক শনাক্তকারী যা মানের সাথে যুক্ত থাকে।
• মান (Value): কী দ্বারা সঞ্চিত তথ্য।
• হ্যাশ ফাংশন: কী থেকে ইনডেক্স তৈরি করে, যা হ্যাশ টেবিলে ডেটার অবস্থান নির্দেশ করে।

১.২ হ্যাশ ফাংশন উদাহরণ

unsigned int hash(const char *key) {
    unsigned int hash = 0;
    while (*key) {
        hash = (hash << 5) + *key++; // Shift left and add current character
    }
    return hash % TABLE_SIZE; // Return index
}

২. Collision Handling Techniques

২.১ Chaining

Chaining হল একটি পদ্ধতি যেখানে প্রতিটি ইনডেক্স একটি লিঙ্কড লিস্ট ধারণ করে। যখন দুটি কী একই হ্যাশ ইনডেক্সে পৌঁছে, তখন তারা একই লিস্টের মধ্যে সঞ্চয় হয়। এটি সংঘর্ষ মোকাবেলার একটি সহজ এবং কার্যকর পদ্ধতি।

২.১.১ Chaining এর সুবিধা

• সহজে বাস্তবায়নযোগ্য।
• ডেটা সঞ্চয় করতে অনেক স্থান পাওয়া যায়।
• একটি ইনডেক্সে একাধিক কী সঞ্চয় করা যায়।

২.১.২ C প্রোগ্রামে Chaining উদাহরণ

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

#define TABLE_SIZE 10

// Node structure for linked list
typedef struct Node {
    char *key;
    int value;
    struct Node *next;
} Node;

// Hash table structure
typedef struct HashTable {
    Node **table;
} HashTable;

// Hash function
unsigned int hash(const char *key) {
    unsigned int hash = 0;
    while (*key) {
        hash = (hash << 5) + *key++;
    }
    return hash % TABLE_SIZE;
}

// Create hash table
HashTable *createHashTable() {
    HashTable *ht = malloc(sizeof(HashTable));
    ht->table = malloc(sizeof(Node *) * TABLE_SIZE);
    for (int i = 0; i < TABLE_SIZE; i++) {
        ht->table[i] = NULL;
    }
    return ht;
}

// Insert key-value pair
void insert(HashTable *ht, const char *key, int value) {
    unsigned int index = hash(key);
    Node *newNode = malloc(sizeof(Node));
    newNode->key = strdup(key);
    newNode->value = value;
    newNode->next = ht->table[index];
    ht->table[index] = newNode;
}

// Search for a value by key
int search(HashTable *ht, const char *key) {
    unsigned int index = hash(key);
    Node *current = ht->table[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value;
        }
        current = current->next;
    }
    return -1; // Not found
}

// Free the hash table
void freeHashTable(HashTable *ht) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        Node *current = ht->table[i];
        while (current != NULL) {
            Node *temp = current;
            current = current->next;
            free(temp->key);
            free(temp);
        }
    }
    free(ht->table);
    free(ht);
}

int main() {
    HashTable *ht = createHashTable();
    insert(ht, "apple", 10);
    insert(ht, "banana", 20);
    insert(ht, "orange", 30);

    printf("Value for 'apple': %d\n", search(ht, "apple"));   // Output: 10
    printf("Value for 'banana': %d\n", search(ht, "banana")); // Output: 20
    printf("Value for 'grape': %d\n", search(ht, "grape"));   // Output: -1 (not found)

    freeHashTable(ht);
    return 0;
}

২.২ Open Addressing

Open Addressing হল একটি পদ্ধতি যেখানে সংঘর্ষের সময় কী-ভ্যালু জোড়াগুলিকে হ্যাশ টেবিলের অন্যান্য খালি ইনডেক্সে সঞ্চয় করা হয়। সংঘর্ষ ঘটলে, অন্য ইনডেক্স অনুসন্ধান করা হয় এবং সেখানে নতুন কী সন্নিবেশ করা হয়।

২.২.১ Open Addressing এর উপ-প্রকার

• Linear Probing: পরবর্তী খালি ইনডেক্সে সন্নিবেশ।
• Quadratic Probing: ইনডেক্সের মধ্যে কোয়াড্রাটিক প্রগতিতে সন্নিবেশ।
• Double Hashing: দ্বিতীয় হ্যাশ ফাংশন ব্যবহার করে পরবর্তী ইনডেক্স নির্ধারণ।

২.২.২ C প্রোগ্রামে Open Addressing উদাহরণ (Linear Probing)

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

#define TABLE_SIZE 10

typedef struct HashTable {
    char *keys[TABLE_SIZE];
    int values[TABLE_SIZE];
} HashTable;

// Hash function
unsigned int hash(const char *key) {
    unsigned int hash = 0;
    while (*key) {
        hash = (hash << 5) + *key++;
    }
    return hash % TABLE_SIZE;
}

// Create hash table
HashTable *createHashTable() {
    HashTable *ht = malloc(sizeof(HashTable));
    for (int i = 0; i < TABLE_SIZE; i++) {
        ht->keys[i] = NULL; // Initialize keys to NULL
    }
    return ht;
}

// Insert key-value pair
void insert(HashTable *ht, const char *key, int value) {
    unsigned int index = hash(key);
    while (ht->keys[index] != NULL) {
        // Linear probing
        index = (index + 1) % TABLE_SIZE; // Move to the next index
    }
    ht->keys[index] = strdup(key);
    ht->values[index] = value;
}

// Search for a value by key
int search(HashTable *ht, const char *key) {
    unsigned int index = hash(key);
    while (ht->keys[index] != NULL) {
        if (strcmp(ht->keys[index], key) == 0) {
            return ht->values[index]; // Return value if found
        }
        index = (index + 1) % TABLE_SIZE; // Move to the next index
    }
    return -1; // Not found
}

// Free the hash table
void freeHashTable(HashTable *ht) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        free(ht->keys[i]);
    }
    free(ht);
}

int main() {
    HashTable *ht = createHashTable();
    insert(ht, "apple", 10);
    insert(ht, "banana", 20);
    insert(ht, "orange", 30);

    printf("Value for 'apple': %d\n", search(ht, "apple"));   // Output: 10
    printf("Value for 'banana': %d\n", search(ht, "banana")); // Output: 20
    printf("Value for 'grape': %d\n", search(ht, "grape"));   // Output: -1 (not found)

    freeHashTable(ht);
    return 0;
}

৩. Collision Handling Techniques এর তুলনা