Chương trình C++ cài đặt bảng băm với băm kép (Double Hashing)

Bảng băm lưu trữ cặp khóa-giá trị. Băm kép (Double Hashing) là kỹ thuật giải quyết va chạm trong bảng băm định địa chỉ mở, sử dụng hàm băm thứ hai để xác định bước nhảy (step size) khi xảy ra va chạm.

Thuật toán

Tìm kiếm khóa

Bắt đầu
    SearchKey(k, ht)
    hashVal = HashFunc1(k, ht->s)
    stepSize = HashFunc2(k, ht->s)
    Khi (ht->t[hashVal].info != Emp VÀ ht->t[hashVal].e != k)
        hashVal = (hashVal + stepSize) % ht->s
    Trả về hashVal
Kết thúc

Chèn

Bắt đầu
    Insert(k, ht)
    pos = SearchKey(k, ht)
    Nếu (ht->t[pos].info != Legi)
        ht->t[pos].info = Legi
        ht->t[pos].e = k
Kết thúc

Hiển thị

Bắt đầu
    display(ht)
    Với i từ 0 đến ht->s-1:
        v = ht->t[i].e
        Nếu (!v) in "Position: i+1 Element: Null"
        Ngược lại in "Position: i+1 Element: v"
Kết thúc

Rehash (mở rộng bảng)

Bắt đầu
    Rehash(ht)
    s = ht->s, t = ht->t
    ht = initiateTable(2*s)
    Với i từ 0 đến s-1:
        Nếu (t[i].info == Legi) Insert(t[i].e, ht)
    free(t)
    Trả về ht
Kết thúc

Mã nguồn

#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; } // bước nhảy phụ thuộc khóa

HashTable* initiateTable(int s) {
    if (s < T_S) { cout << "Table Size is Too Small" << endl; return NULL; }
    HashTable *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) % 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 = NULL;
    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 (!ht) { cout << "Table not initialized!" << endl; break; }
                cout << "Enter element to be inserted: "; cin >> v; Insert(v, ht); break;
            case 3: if (ht) display(ht); else cout << "Table not initialized!" << endl; break;
            case 4: if (ht) ht = Rehash(ht); else cout << "Table not initialized!" << endl; break;
            case 5: exit(1);
            default: cout << "\nEnter correct option\n";
        }
    }
    return 0;
}

Kết quả mẫu

1.Initialize size of the table
Enter size of the Hash Table: 4
Table Size is Too Small
Enter size of the Hash Table: 10
...
Enter your choice: 2
Enter element to be inserted: 1
...
Enter your choice: 3
Position: 1 Element: 10
Position: 2 Element: 1
Position: 3 Element: 11
Position: 4 Element: 3
Position: 5 Element: 4
Position: 6 Element: 5
Position: 7 Element: 6
Position: 8 Element: 7
Position: 9 Element: 8
Position: 10 Element: 9
Enter your choice: 4  // Rehash
Enter your choice: 3
Position: 1 Element: Null
Position: 2 Element: 1
Position: 3 Element: Null
Position: 4 Element: 3
...
Position: 11 Element: 10
Position: 12 Element: 11
Position: 13 Element: Null
...
Position: 20 Element: Null

Đặc điểm quan trọng

• HashFunc2 phải trả về giá trị khác 0 và nguyên tố cùng nhau với kích thước bảng để đảm bảo duyệt hết tất cả ô.
• Băm kép giảm thiểu primary clustering (cụm chính) so với dò tuyến tính.
• Chi phí: tính thêm hàm băm thứ hai, nhưng hiệu suất tốt hơn khi hệ số tải cao.
• Rehash cấp phát bảng mới gấp đôi, chèn lại tất cả phần tử hợp lệ – thao tác O(n) nhưng hiếm khi xảy ra.