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

লিস্ট হেড চেইনিং

এই পদ্ধতিতে প্রতিটি হ্যাশ বাকেটে একটি ListHead নোড থাকে যা চেইনের হেড কাজ করে। নতুন নোড চেইনের শেষে যোগ করা হয়।

অ্যালগরিদম

ইনসার্ট (Insert)

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

সার্চ (SearchKey)

Function SearchKey(int k):
    hash_v = HashFunc(k)
    if (ht[hash_v] == NULL) return -1
    en = ht[hash_v]
    while (en != NULL AND en->k != k) en = en->n
    if (en == NULL) return -1
    else return en->v

ডিলিট (Remove)

Function Remove(int k):
    hash_v = HashFunc(k)
    if (ht[hash_v] != NULL):
        en = ht[hash_v], p = NULL
        while (en->n != NULL AND en->k != k): p = en; en = en->n
        if (en->k == k):
            if (p == NULL): n = en->n; delete en; ht[hash_v] = n
            else: n = en->n; delete en; p->n = n

উদাহরণ কোড

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

class ListHead {
public:
    int k, v;
    ListHead *n;
    ListHead(int k, int v) : k(k), v(v), n(NULL) {}
};

class HashMapTable {
    ListHead **ht;
public:
    HashMapTable() {
        ht = new ListHead*[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() { /* ... মেনু ড্রাইভেন ইন্টারফেস ... */ }

আউটপুট নমুনা

Elements at key 6 : 7
Entry Removed

বিশেষতা: লিস্ট হেড প্যাটার্নে চেইন ম্যানেজমেন্ট সহজ এবং মেমরি ওভারহেড কম।