Chương trình C++ băm với chaining (xử lý va chạm)

Băm (Hashing) là phương pháp ánh xạ dữ liệu độ dài bất kỳ thành khóa (key) kích thước cố định. Băm hoạt động theo cặp key-value.

Hàm băm là hàm thực hiện ánh xạ trong bảng băm. Các phần tử dữ liệu đầu vào cho hàm băm có thể nhận cùng khóa băm. Trong trường hợp này các phần tử có thể chồng chéo. Để tránh chồng chéo của các phần tử có cùng khóa băm, khái niệm chaining (xâu chuỗi) được giới thiệu.

Tạo bảng băm

Để tạo bảng băm, cần hàm băm xác định chỉ số của phần tử dữ liệu.

Ta có bảng băm với n bucket. Để chèn nút vào bảng băm, ta có hàm băm:

hashIndex = key % số_bucket

Ta dùng hàm băm này tính hashIndex của mọi giá trị chèn vào bảng băm.

• Chèn phần tử: tính hashIndex của khóa, chèn nút mới vào cuối danh sách.

• Xóa nút: tính hash index, tìm phần tử trong bucket tương ứng và xóa.

Ví dụ mã C++

#include <iostream> 
#include <list> 
using namespace std; 

class Hash { 
    int BUCKET; 
    list<int> *table; 
    public: 
    Hash(int V); 
    void insertItem(int x); 
    void deleteItem(int key); 
    int hashFunction(int x) { 
        return (x % BUCKET); 
    } 
    void displayHash(); 
}; 

Hash::Hash(int b) { 
    this->BUCKET = b; 
    table = new list<int>[BUCKET]; 
} 

void Hash::insertItem(int key) { 
    int index = hashFunction(key); 
    table[index].push_back(key); 
} 

void Hash::deleteItem(int key) { 
    int index = hashFunction(key); 
    list<int>::iterator i; 
    for (i = table[index].begin(); i != table[index].end(); i++) { 
        if (*i == key) 
            break; 
    } 
    if (i != table[index].end()) 
        table[index].erase(i); 
} 

void Hash::displayHash() { 
    for (int i = 0; i < BUCKET; i++) { 
        cout << i; 
        for (auto x : table[i]) 
            cout << " --> " << x; 
        cout << endl; 
    } 
} 

int main() { 
    int a[] = { 5, 12, 67, 9, 16 }; 
    int n = 5; 
    Hash h(7); 
    for (int i = 0; i < n; i++) 
        h.insertItem(a[i]); 
    h.deleteItem(12); 
    h.displayHash(); 
    return 0; 
}

Kết quả

0 
1 
2 --> 9 --> 16 
3 
4 --> 67 
5 --> 5 
6