C++-এ লিনিয়ার প্রোবিং (Linear Probing) সহ হ্যাশ টেবিল বাস্তবায়ন

হ্যাশ টেবিল এবং লিনিয়ার প্রোবিং

হ্যাশ টেবিল একটি ডেটা স্ট্রাকচার যা কী-মান (key-value) জোড়া সংরক্ষণ করে। হ্যাশ ফাংশন ব্যবহার করে একটি অ্যারের ইনডেক্স নির্ণয় করা হয় যেখানে এলিমেন্টটি ইনসার্ট বা সার্চ করা হবে।

লিনিয়ার প্রোবিং (Linear Probing) হল একটি কলিশন রেজোলভশন (collision resolution) কৌশল, যা ওপেন অ্যাড্রেসড হ্যাশ টেবিলে ব্যবহৃত হয়। এই পদ্ধতিতে, প্রতিটি সেল একটি কী-মান জোড়া ধারণ করে। নতুন কী ম্যাপ করার সময় যদি সেলটি ইতিমধ্যে অকুপাইড থাকে, তবে লিনিয়ার প্রোবিং টেবিলে পরবর্তী খালি সেল খুঁজে নতুন কী সেখানে ইনসার্ট করে।

অ্যালগরিদম

ইনসার্ট (Insert)

Function Insert(int k, int v)
    hash_val = HashFunc(k)
    init = -1
    delindex = -1
    while (hash_val != init AND (ht[hash_val] == DelNode OR (ht[hash_val] != NULL AND ht[hash_val]->k != k)))
        if (init == -1) init = hash_val
        if (ht[hash_val] == DelNode) delindex = hash_val
        hash_val = HashFunc(hash_val + 1)
    if (ht[hash_val] == NULL OR hash_val == init)
        if (delindex != -1) ht[delindex] = new HashTable(k, v)
        else ht[hash_val] = new HashTable(k, v)
    if (init != hash_val)
        if (ht[hash_val] != DelNode)
            if (ht[hash_val] != NULL AND ht[hash_val]->k == k)
                ht[hash_val]->v = v
            else
                ht[hash_val] = new HashTable(k, v)

সার্চ (Search)

Function SearchKey(int k)
    hash_val = HashFunc(k)
    init = -1
    while (hash_val != init AND (ht[hash_val] == DelNode OR (ht[hash_val] != NULL AND ht[hash_val]->k != k)))
        if (init == -1) init = hash_val
        hash_val = HashFunc(hash_val + 1)
    if (ht[hash_val] == NULL OR hash_val == init) return -1
    else return ht[hash_val]->v

ডিলিট (Delete)

Function Remove(int k)
    hash_val = HashFunc(k)
    init = -1
    while (hash_val != init AND (ht[hash_val] == DelNode OR (ht[hash_val] != NULL AND ht[hash_val]->k != k)))
        if (init == -1) init = hash_val
        hash_val = HashFunc(hash_val + 1)
    if (hash_val != init AND ht[hash_val] != NULL)
        delete ht[hash_val]
        ht[hash_val] = DelNode::getNode()

উদাহরণ কোড

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

const int T_S = 5;

class HashTable {
public:
    int k, v;
    HashTable(int k, int v) { this->k = k; this->v = v; }
};

class DelNode : public HashTable {
private:
    static DelNode *en;
    DelNode() : HashTable(-1, -1) {}
public:
    static DelNode* getNode() {
        if (en == NULL) en = new DelNode();
        return en;
    }
};
DelNode *DelNode::en = NULL;

class HashMapTable {
private:
    HashTable **ht;
public:
    HashMapTable() {
        ht = new HashTable*[T_S];
        for (int i = 0; i < T_S; i++) ht[i] = NULL;
    }
    int HashFunc(int k) { return k % T_S; }
    void Insert(int k, int v) { /* ... লিনিয়ার প্রোবিং লজিক ... */ }
    int SearchKey(int k) { /* ... সার্চ লজিক ... */ }
    void Remove(int k) { /* ... ডিলিট লজিক ... */ }
    ~HashMapTable() { delete[] ht; }
};

int main() {
    HashMapTable hash;
    int k, v, c;
    while (1) {
        cout << "1.Insert element into the table" << endl;
        cout << "2.Search element from the key" << endl;
        cout << "3.Delete element at a key" << endl;
        cout << "4.Exit" << endl;
        cout << "Enter your choice: "; cin >> c;
        switch (c) {
            case 1: cout << "Enter element: "; cin >> v;
                    cout << "Enter key: "; cin >> k;
                    hash.Insert(k, v); break;
            case 2: cout << "Enter key to search: "; cin >> k;
                    if (hash.SearchKey(k) == -1) cout << "Not found" << endl;
                    else cout << "Element: " << hash.SearchKey(k) << endl; break;
            case 3: cout << "Enter key to delete: "; cin >> k;
                    hash.Remove(k); break;
            case 4: exit(1);
            default: cout << "Invalid option\n";
        }
    }
    return 0;
}

আউটপুট নমুনা

1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 10
Enter key at which element to be inserted: 2
...
Element at key 6 : 7
No element found at key 2

মূল পয়েন্ট: লিনিয়ার প্রোবিং সহজ কিন্তু ক্লাস্টারিং (clustering) সমস্যা তৈরি করতে পারে। ডিলিট করার সময় DelNodeмаркер ব্যবহার করা হয় যাতে সার্চ বা ইনসার্ট অপারেশন বাধা না পায়।