C++-এ সিঙ্গলি লিংকড লিস্ট (Singly Linked List) চেইনিং সহ হ্যাশ টেবিল বাস্তবায়ন

চেইনিং সহ হ্যাশ টেবিল

চেইনিং (Chaining) হল হ্যাশ টেবিলে কলিশন হ্যান্ডল করার একটি পদ্ধতি যেখানে প্রতিটি বাকেট (bucket) একটি লিংকড লিস্ট হেড (head) ধারণ করে। একই হ্যাশ ভ্যালু वाले সব কী-মান জোড়া সেই লিস্টে সংযুক্ত থাকে।

অ্যালগরিদম

ইনসার্ট (Insert)

Function Insert(int k, int v):
    hash_v = HashFunc(k)
    p = NULL, en = ht[hash_v]
    while (en != NULL): p = en; en = en->n
    if (en == NULL):
        en = new HashTableEntry(k, v)
        if (p == NULL) ht[hash_v] = en
        else p->n = en
    else: en->v = v

ডিলিট (Remove)

Function Remove(int k):
    hash_v = HashFunc(k)
    en = ht[hash_v], p = NULL
    if (en == NULL OR en->k != k): print "Not found"; return
    while (en->n != NULL): p = en; en = en->n
    if (p != NULL) p->n = en->n
    delete en; print "Deleted"

সার্চ (SearchKey)

Function SearchKey(int k):
    hash_v = HashFunc(k)
    flag = false, en = ht[hash_v]
    if (en != NULL):
        while (en != NULL):
            if (en->k == k): flag = true
            if (flag): print "Found: " + en->v
            en = en->n
    if (!flag) print "Not found"

উদাহরণ কোড

#include <iostream>
const int T_S = 200;
using namespace std;

struct HashTableEntry {
    int v, k;
    HashTableEntry *n, *p;
    HashTableEntry(int k, int v) : k(k), v(v), n(NULL), p(NULL) {}
};

class HashMapTable {
    HashTableEntry **ht, **top;
public:
    HashMapTable() {
        ht = new HashTableEntry*[T_S];
        top = new HashTableEntry*[T_S];
        for (int i = 0; i < T_S; i++) ht[i] = top[i] = NULL;
    }
    int HashFunc(int key) { return key % T_S; }
    void Insert(int k, int v) { /* ... চেইনিং ইনসার্ট ... */ }
    void Remove(int k) { /* ... ডিলিট ... */ }
    void SearchKey(int k) { /* ... সার্চ ... */ }
    ~HashMapTable() { delete[] ht; }
};

int main() { /* ... মেনু ড্রাইভেন ইন্টারফেস ... */ }

আউটপুট নমুনা

Element found at key 6: 7
No Element found at key 7
Element Deleted

ব্যাখ্যা: সিঙ্গলি লিংকড লিস্ট চেইনিং সহজ এবং কার্যকর, কিন্তু ডিলিট অপারেশনটিতে প্রিভিয়াস নোড ট্র্যাক করার জন্য অতিরিক্ত লজিক প্রয়োজন।