Chào mừng bạn đến với Vimentor!

Hỏi đáp
Đăng ký

Giải quyết xung đột - Separate chaining

Kĩ thuật phân tách chuỗi (separate chaining)

Kĩ thuật phân tách chuỗi là một trong những kĩ thuật phổ biến nhất để giải quyết xung đột trong bảng băm. Kĩ thuật này thường được thực hiện bởi việc sử dụng các danh sách liên kết.

Với kĩ thuật này mỗi phần tử của bảng băm là một danh sách liên kết. Để chèn một phần tử vào bảng băm ta phải chèn nó vào trong một danh sách liên kết. Nếu có xung đột xảy ra như trường hợp hai phần tử có chung giá trị (hash code) thì ta sẽ chèn chúng vào chung một danh sách liên kết.

Giả sử ta có hàm băm chuyển đổi các khóa 50, 700, 76, 85, 92, 73, 101 bằng cách chia cho 7 rồi lấy số dư.

 

 

Để chèn một phần tử vào bảng băm, ta cần tìm chỉ số băm cho khóa đã cho. Giả sử chỉ số được tính toán theo công thức sau:

index = key % number_of_rows

Thao tác chèn: chuyển tới hàng tương ứng với chỉ số tính toán được theo công thức ở trên và chèn phần tử mới vào bảng như một node mới ở cuối danh sách liên kết.

Thao tác xóa: Để xóa một node khỏi bảng băm, đầu tiên ta cần tính toán chỉ số cho khóa, và chuyển đến hàng tương ứng với chỉ số đó, tìm kiếm phần tử với khóa đã cho trên danh sách liên kết và xóa nó nếu tìm thấy.

Chương trình thực hiện hashing với kỹ thuật phân tách chuỗi

Chương trình được thực hiện bằng ngôn ngữ C++, và dùng thư viện chuẩn của C++ cho các thao tác với danh sách liên kết.

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

class Hashing {
    private:
        int BUCKET;
        list<int> *sc;
    public:
        Hashing(int N);
        void insertKey(int key);
        void deleteKey(int key);
        int hashFunction(int okey);
        void printHashTable();
};

Hashing::Hashing(int N){
    this->BUCKET = N;
    sc = new list<int>[BUCKET];
}

int Hashing::hashFunction(int okey){
    return (okey % BUCKET);
}

void Hashing::insertKey(int key){
    int nkey = hashFunction(key);
    sc[nkey].push_back(key);
}

void Hashing::deleteKey(int key){
    int nkey = hashFunction(key);
    list<int>::iterator i;
    for (i = sc[nkey].begin(); i != sc[nkey].end(); i++){
        if(*i == key) {
            sc[nkey].erase(i);
        }
    }
}

void Hashing::printHashTable(){
    for(int i = 0; i < BUCKET; i++){
        cout << i ;
        list<int>::iterator j;
        for(j = sc[i].begin(); j != sc[i].end(); j++){
            cout << "-->" << *j ;
        }
        cout << endl;
    }
}

int main(){
    
    Hashing h(7);
    
    int Obj[] = {50, 700, 76, 85, 92, 73, 101};
    int obj_size = sizeof(Obj)/sizeof(Obj[0]);
    for(int i = 0; i < obj_size; i++){
        h.insertKey(Obj[i]);
    }
    h.printHashTable();
    return 0;
}

Kết quả chạy chương trình đã kiểm tra tại: https://www.onlinegdb.com/

Các ưu, nhược điểm của phương pháp phân tách chuỗi

Ưu điểm:

  • Cài đặt đơn giản

  • Không phải lo tới kích thước bảng băm, và ta luôn có thể thêm dữ liệu vào bảng bằng cách thêm vào các danh sách liên kết.

  • Phương thức này thường được sử dụng khi ta không biết tần suất dữ liệu được thêm vào và xóa ra khỏi bảng.

 

Nhược điểm:

  • Hiệu năng của phương pháp này không tốt bằng phương pháp đánh địa chỉ mở. bởi vì với phương pháp đánh địa chỉ mở thì mọi dữ liệu đều được chứa trong cùng một bảng băm mà không cần trỏ tới một vùng nhớ ngoài bảng.

  • Đôi khi lãng phí bộ nhớ (như ta nhìn thấy ở ví dụ trên, vị trí 2, 4 và 5 để trống, đôi khi không bao giờ sử dụng tới).

  • Khi mà chuỗi (danh sách liên kết) trở nên quá dài, lúc đó thời gian cho các thao tác tìm kiếm, xóa phần tử có thể rất tốn thời gian.

  • Cần thêm bộ nhớ cho các phần tử của danh sách liên kết.

Hiệu năng của phương pháp phân tách chuỗi

Sau đây là các thông số về hiệu năng của phương pháp phân tách chuỗi với giả định rằng mỗi khóa (key) được chèn đồng đều vào các khe chứa dữ liệu của bảng băm.

M = Số lượng khe dữ liệu trong bảng băm

N = Số lượng key được chèn vào bảng

Hê số tải a = N/M

Thời gian kỳ vọng cho thao tác tìm kiếm = O(1+a)

Thời gian kỳ vọng cho thao tác chèn và xóa dữ liệu = O(1+a)

Nếu a = 1 thì lúc đó ta coi thời gian cho các thao tác tìm kiếm, chèn và xóa dữ liêu là O(1)

Kết luận

Việc xung đột khi chèn dữ liệu vào bảng băm là điều rất khó để tránh khỏi. Việc chọn cách xử lý xung đột theo cách nào là vô cùng quan trọng, nó ảnh hưởng đến hiệu năng và tốc độ thực thi của cả chương trình. Hãy cùng đọc thêm về một phương pháp giải quyết xung đột khác để có sự so sánh và lựa chọn ra được phương pháp tránh xung đột tốt nhất (Đánh địa chỉ mở - Open Addresing).

** Nếu bạn muốn viết các nội dung đặt biệt thì hãy làm theo hướng dẫn sau

Xem thêm 10 bình luận
Viết blog mới của bạn
Báo lỗi trang
Đang tải