C++ প্রোগ্রাম: কুয়াড্র্যাটিক প্রোবিং সহ হ্যাশ টেবিল ইমপ্লিমেন্টেশন

হ্যাশ টেবিল হলো একটি ডেটা স্ট্রাকচার যা কি-ভ্যালু পেয়ার স্টোর করতে ব্যবহৃত হয়। হ্যাশ ফাংশন হ্যাশ টেবিলে ব্যবহার হয় একটি অ্যারের মধ্যে ইনডেক্স কম্পিউট করতে যেখানে এলিমেন্ট ইনসার্ট বা সার্চ হবে। কুয়াড্র্যাটিক প্রোবিং ওপেন অ্যাড্রেসড হ্যাশ টেবিলে একটি কলিশন রেজোলভিং টেকনিক। এটি অরিজিনাল হ্যাশ ইনডেক্স নেয় এবং একটি আর্বিট্রারি কুয়াড্র্যাটিক পলিনোমিয়ালের সাকসেসিভ ভ্যালু যোগ করে যতক্ষণ না একটি ওপেন স্লট পাওয়া যায়।

এটি কুয়াড্র্যাটিক প্রোবিং সহ হ্যাশ টেবিল ইমপ্লিমেন্ট করার একটি C++ প্রোগ্রাম।

অ্যালগরিদম

কি ভ্যালু সার্চ করার জন্য:

শুরু
    SearchKey(int k, HashTable *ht) ফাংশন ডিক্লেয়ার করো
        int pos = HashFunc(k, ht->s)
        collisions = 0 ইনিশিয়ালাইজ করো
        while (ht->t[pos].info != Emp and ht->t[pos].e != k)
            pos = pos + 2 * ++collisions - 1
            if (pos >= ht->s)
                pos = pos - ht->s
        return pos
শেষ।

ইনসার্ট করার জন্য:

শুরু
    Insert(int k, HashTable *ht) ফাংশন ডিক্লেয়ার করো
        int pos = SearchKey(k, ht)
        if (ht->t[pos].info != Legi)
            ht->t[pos].info = Legi
            ht->t[pos].e = k
শেষ।

ডিসপ্লে করার জন্য:

শুরু
    display(HashTable *ht) ফাংশন ডিক্লেয়ার করো
        for (int i = 0; i < ht->s; i++)
            int value = ht->t[i].e
            if (!value)
                print "Position: "
                প্রিন্ট করো বর্তমান পজিশন
                print " Element: Null"
            অন্যথায়
                print "Position: "
                প্রিন্ট করো বর্তমান পজিশন
                print " Element: "
                প্রিন্ট করো এলিমেন্ট।
শেষ।

রিহ্যাশ ফাংশন:

শুরু
    Rehash(HashTable *ht) ফাংশন ডিক্লেয়ার করো
        int s = ht->s
        HashTableEntry *t = ht->t
        ht = initiateTable(2 * s)
        for (int i = 0; i < s; i++)
            if (t[i].info == Legi)
                Insert(t[i].e, ht)
        free(t)
        return ht
শেষ।

উদাহরণ কোড

#include <iostream> 
#include <cstdlib> 
#define T_S 10 
using namespace std; 
enum EntryType { 
    Legi, Emp, Del
}; 
struct HashTableEntry { 
    int e; 
    enum EntryType info; 
}; 
struct HashTable { 
    int s; 
    HashTableEntry *t; 
}; 
bool isPrime(int n) { 
    if (n == 2 || n == 3) 
        return true; 
    if (n == 1 || n % 2 == 0) 
        return false; 
    for (int i = 3; i * i <= n; i += 2) 
        if (n % i == 0) 
            return false; 
    return true; 
} 
int nextPrime(int n) { 
    if (n <= 0) 
        n == 3; 
    if (n % 2 == 0) 
        n++; 
    for (; !isPrime(n); n += 2); 
    return n; 
} 
int HashFunc(int k, int s) { 
    return k % s; 
} 
HashTable *initiateTable(int s) { 
    HashTable *ht; 
    if (s < T_S) { 
        cout << "Table Size is Too Small" << endl; 
        return NULL; 
    } 
    ht = new HashTable; 
    if (ht == NULL) { 
        cout << "Out of Space" << endl; 
        return NULL; 
    } 
    ht->s = nextPrime(s); 
    ht->t = new HashTableEntry[ht->s]; 
    if (ht->t == NULL) { 
        cout << "Table Size is Too Small" << endl; 
        return NULL; 
    } 
    for (int i = 0; i < ht->s; i++) { 
        ht->t[i].info = Emp; 
        ht->t[i].e = NULL; 
    } 
    return ht; 
} 
int SearchKey(int k, HashTable *ht) { 
    int pos = HashFunc(k, ht->s); 
    int collisions = 0; 
    while (ht->t[pos].info != Emp && ht->t[pos].e != k) { 
        pos = pos + 2 * ++collisions - 1; 
        if (pos >= ht->s) 
            pos = pos - ht->s; 
    } 
    return pos; 
} 
void Insert(int k, HashTable *ht) { 
    int pos = SearchKey(k, ht); 
    if (ht->t[pos].info != Legi) { 
        ht->t[pos].info = Legi; 
        ht->t[pos].e = k; 
    } 
} 
HashTable *Rehash(HashTable *ht) { 
    int s = ht->s; 
    HashTableEntry *t = ht->t; 
    ht = initiateTable(2 * s); 
    for (int i = 0; i < s; i++) { 
        if (t[i].info == Legi) 
            Insert(t[i].e, ht); 
    } 
    free(t); 
    return ht; 
} 
void display(HashTable *ht) { 
    for (int i = 0; i < ht->s; i++) { 
        int value = ht->t[i].e; 
        if (!value) 
            cout << "Position: " << i + 1 << " Element: Null" << endl; 
        else 
            cout << "Position: " << i + 1 << " Element: " << value << endl; 
    } 
} 
int main() { 
    int v, s, pos, i = 1; 
    int c; 
    HashTable *ht; 
    while (1) { 
        cout << "1. Initialize size of the table" << endl; 
        cout << "2. Insert element into the table" << endl; 
        cout << "3. Display Hash Table" << endl; 
        cout << "4. Rehash The Table" << endl; 
        cout << "5. Exit" << endl; 
        cout << "Enter your choice: "; 
        cin >> c; 
        switch (c) { 
            case 1: 
                cout << "Enter size of the Hash Table: "; 
                cin >> s; 
                ht = initiateTable(s); 
                cout << "Size of Hash Table: " << nextPrime(s); 
                break; 
            case 2: 
                if (i > ht->s) { 
                    cout << "Table is Full, Rehash the table" << endl; 
                    continue; 
                } 
                cout << "Enter element to be inserted: "; 
                cin >> v; 
                Insert(v, ht); 
                i++; 
                break; 
            case 3: 
                display(ht); 
                break; 
            case 4: 
                ht = Rehash(ht); 
                break; 
            case 5: 
                exit(1); 
            default: 
                cout << "\nEnter correct option\n"; 
        } 
    } 
    return 0; 
}

আউটপুট

1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 1
Enter size of the Hash Table: 4
Table Size is Too Small
Size of Hash Table: 5
1.Initialize size of the table
...
(মেনু চালু থাকে, ইনসার্ট, ডিসপ্লে, রিহ্যাশ অপারেশন দেখানো হয়েছে)
...
Enter your choice: 5