โปรแกรม C++ สำหรับการนำ Hash Tables มาใช้งานด้วย Double Hashing

ตารางแฮช (Hash Table) เป็นโครงสร้างข้อมูลสำหรับจัดเก็บคู่คีย์-ค่า ฟังก์ชันแฮชใช้คำนวณดัชนีในอาร์เรย์สำหรับการแทรกหรือค้นหาข้อมูล

Double Hashing เป็นเทคนิคแก้ไขการชนในตารางแฮชแบบเปิด (Open Addressing) โดยใช้ฟังก์ชันแฮชที่สองเมื่อเกิดการชน

นี่คือโปรแกรม C++ สำหรับการนำ Hash Tables มาใช้งานด้วย Double Hashing

อัลกอริทึม

การค้นหาคีย์ (Search Key):

Begin
    Declare Function SearchKey(int k, HashTable *ht)
        int hashVal = HashFunc1(k, ht->s)
        int stepSize = HashFunc2(k, ht->s)
        while (ht->t[hashVal].info != Emp and ht->t[hashVal].e != k)
            hashVal = hashVal + stepSize
            hashVal = hashVal % ht->s
        return hashVal
End

การแทรกข้อมูล (Insert):

Begin
    Declare Function 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
End

การแสดงผล (Display):

Begin
    Declare function display(HashTable *ht)
        for i = 0 to ht->s-1
            int v = ht->t[i].e
            if (!v) Print "Position: i Element: Null"
            else Print "Position: i Element: v"
End.

ฟังก์ชัน Rehash:

Begin
    Declare function Rehash(HashTable *ht)
        int s = ht->s
        HashTableEntry *t = ht->t
        ht = initiateTable(2*s)
        for i = 0 to s-1
            if (t[i].info == Legi) Insert(t[i].e, ht)
        free(t)
        return ht
End.

โค้ดตัวอย่าง

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

enum EntryType {Legi, Emp};

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) {
    HashTable *ht;
    if (s < T_S) { cout << "Table Size is Too Small" << endl; return NULL; }
    ht = new HashTable;
    if (!ht) { cout << "Out of Space" << endl; return NULL; }
    ht->s = s;
    ht->t = new HashTableEntry[ht->s];
    if (!ht->t) { 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 hashVal = HashFunc1(k, ht->s);
    int stepSize = HashFunc2(k, ht->s);
    while (ht->t[hashVal].info != Emp && ht->t[hashVal].e != k) {
        hashVal = hashVal + stepSize;
        hashVal = hashVal % ht->s;
    }
    return hashVal;
}

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;
    }
}

void display(HashTable *ht) {
    for (int i = 0; i < ht->s; i++) {
        int v = ht->t[i].e;
        if (!v) cout << "Position: " << i+1 << " Element: Null" << endl;
        else cout << "Position: " << i+1 << " Element: " << v << endl;
    }
}

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;
}

int main() {
    int v, s, 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 Hash 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); break;
            case 2: 
                if (/* table full */) { cout << "Table is Full, Rehash the table" << endl; continue; }
                cout << "Enter element to be inserted: "; cin >> v; Insert(v, ht); 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 Hash Table
5.Exit
Enter your choice: 1
Enter size of the Hash Table: 4
Table Size is Too Small
...
Enter your choice: 3
Position: 1 Element: 10
Position: 2 Element: 1
...
Position: 10 Element: 9
...
Enter your choice: 4
...
Enter your choice: 3
Position: 1 Element: Null
Position: 2 Element: 1
...
Position: 20 Element: Null
Enter your choice: 5