C++-এ ডাবল হ্যাশিং (Double Hashing) সহ হ্যাশ টেবিল বাস্তবায়ন

ডাবল হ্যাশিং কী?

ডাবল হ্যাশিং হল ওপেন অ্যাড্রেসড হ্যাশ টেবিলে কলিশন রেজোলভশনের একটি উন্নত কৌশল। কলিশন হলে দ্বিতীয় একটি হ্যাশ ফাংশন ব্যবহার করে স্টেপ সাইজ (step size) নির্ধারণ করা হয়, যা লিনিয়ার প্রোবিং-এর ক্লাস্টারিং সমস্যা কমিয়ে দেয়।

অ্যালগরিদম

সার্চ (SearchKey)

Function SearchKey(int k, HashTable *ht):
    hashVal = HashFunc1(k, ht->s)
    stepSize = HashFunc2(k, ht->s)
    while (ht->t[hashVal].info != EMPTY AND ht->t[hashVal].e != k):
        hashVal = (hashVal + stepSize) % ht->s
    return hashVal

ইনসার্ট (Insert)

Function Insert(int k, HashTable *ht):
    pos = SearchKey(k, ht)
    if (ht->t[pos].info != LEGIT):
        ht->t[pos].info = LEGIT
        ht->t[pos].e = k

রিহ্যাশ (Rehash)

Function Rehash(HashTable *ht):
    oldSize = ht->s
    oldTable = ht->t
    ht = initiateTable(2 * oldSize)
    for i = 0 to oldSize-1:
        if (oldTable[i].info == LEGIT):
            Insert(oldTable[i].e, ht)
    free(oldTable)
    return ht

উদাহরণ কোড

#include <iostream>
#include <cstdlib>
#define T_S 5
using namespace std;

enum EntryType { LEGIT, EMPTY };

struct HashTableEntry {
    int e;
    enum EntryType info;
};

struct HashTable {
    int s;
    HashTableEntry *t;
};

int HashFunc1(int k, int s) { return k % s; }
int HashFunc2(int k, int s) { return (k * s - 1) % s; }

HashTable* initiateTable(int s) { /* ... টেবিল ইনিশিয়ালাইজ ... */ }
int SearchKey(int k, HashTable *ht) { /* ... ডাবল হ্যাশিং সার্চ ... */ }
void Insert(int k, HashTable *ht) { /* ... ইনসার্ট ... */ }
void display(HashTable *ht) { /* ... ডিসপ্লে ... */ }
HashTable* Rehash(HashTable *ht) { /* ... রিহ্যাশ ... */ }

int main() {
    HashTable *ht = NULL;
    int c, s, v;
    while (1) {
        cout << "1.Initialize size\n2.Insert\n3.Display\n4.Rehash\n5.Exit\nChoice: ";
        cin >> c;
        switch (c) {
            case 1: cin >> s; ht = initiateTable(s); break;
            case 2: cin >> v; Insert(v, ht); break;
            case 3: display(ht); break;
            case 4: ht = Rehash(ht); break;
            case 5: exit(1);
        }
    }
}

আউটপুট নমুনা

Position: 1 Element: 10
Position: 2 Element: 1
...
Position: 10 Element: 9
After Rehash:
Position: 1 Element: Null
Position: 2 Element: 1
...
Position: 20 Element: Null

লाभ: ডাবল হ্যাশিং কলিশন কমিয়ে টেবিলের পারফরম্যান্স উন্নত করে। রিহ্যাশিং টেবিল ফুল হলে আকার বাড়াতে সাহায্য করে।