1. Các khái niệm liên quan

Băm (Hashing)

Là kỹ thuật chuyển đổi dữ liệu thông qua một thuật toán cụ thể (hàm băm) thành giá trị cố định (giá trị băm).

Hàm băm:

• Định nghĩa: Hàm băm là cốt lõi của kỹ thuật băm, nó ánh xạ dữ liệu bất kỳ sang giá trị cố định.
• Tính chất:
  • Xác định: Dữ liệu đầu vào giống nhau luôn tạo ra giá trị băm như nhau.
  • Hiệu quả: Quá trình tính toán phải nhanh để đảm bảo hiệu suất khi xử lý dữ liệu lớn.
  • Phân bố đều: Giá trị băm nên phân bố đồng đều trên không gian giá trị để giảm thiểu va chạm.
  • Không thể đảo ngược: Khó hoặc không thể suy ra dữ liệu ban đầu từ giá trị băm.

Bảng băm:

• Định nghĩa: Bảng băm là cấu trúc dữ liệu sử dụng hàm băm để lưu trữ và truy xuất dữ liệu nhanh chóng (O(1)).
• Nguyên tắc hoạt động: Khi lưu trữ một phần tử, trước tiên tính giá trị băm của nó rồi xác định vị trí lưu trữ trong mảng. Nếu xảy ra va chạm, cần có phương pháp giải quyết.

2. Các loại hàm băm phổ biến

2.1 Phương pháp địa chỉ trực tiếp

Địa chỉ trực tiếp sử dụng giá trị key để xác định vị trí lưu trữ, thường thêm một phép biến đổi đơn giản.

Giá trịBăm(Key) = A * Key + B (A, B là hằng số)

• Ưu điểm: Đơn giản, không xảy ra va chạm nếu key duy nhất.
• Hạn chế: Phù hợp với tập dữ liệu tập trung, không phù hợp với tập dữ liệu phân tán.

2.2 Phương pháp chia dư

Chọn một số nguyên tố p gần m (số lượng địa chỉ cho phép), tính giá trị băm bằng cách lấy phần dư của key chia p.

Giá trịBăm(key) = key % p (p <= m)

• Ưu điểm: Tính toán nhanh, phân bố tương đối đều.
• Hạn chế: Khó tránh hoàn toàn va chạm, phụ thuộc nhiều vào lựa chọn p.

3. Xử lý va chạm trong bảng băm

Khi các giá trị khác nhau nhưng có cùng giá trị băm, hiện tượng này gọi là va chạm.

3.1 Phương pháp đóng kín (Open Addressing)

Khi xảy ra va chạm, tìm kiếm vị trí trống kế tiếp trong bảng băm để lưu trữ.

3.1.1 Phương pháp dò tuyến tính

Sau khi phát hiện va chạm, kiểm tra tuần tự các vị trí kế tiếp cho đến khi tìm được vị trí trống.

template<class K, class V, class HashFunc = HashType<K>>
class BangBam {
public:
    enum TrangThai { TRONG, CO, DA_XOA };

    struct Node {
        std::pair<K, V> KV;
        TrangThai tt = TRONG;
    };

    BangBam() {}

    Node* tim(const K& key);
    bool them(std::pair<K, V> kv);
    bool xoa(const K& key);

private:
    std::vector<Node> _mang;
    double _tyLeTaiTrong;
    size_t _soLuong;
    HashFunc _hamBam;
};

3.1.2 Phương pháp dò bình phương

Sử dụng công thức i*i để dò tìm vị trí trống thay vì dò tuyến tính.

size_t index = (indexCu + i * i) % _mang.capacity();

3.2 Phương pháp mở rộng (Chaining)

Mỗi bucket chứa một danh sách liên kết để lưu trữ các phần tử có cùng giá trị băm.

template<class K, class V, class HashFunc = HashType<K>>
class BangBam {
public:
    struct Node {
        std::pair<K, V> KV;
        Node* tiep;

        Node(const std::pair<K, V>& KV = std::make_pair(K(), V())) : KV(KV), tiep(nullptr) {}
    };

    BangBam() {}
    ~BangBam();

    size_t soLuong() const;
    Node* tim(const K& key);
    bool them(std::pair<K, V> kv);
    bool xoa(const K& key);

private:
    std::vector<Node*> _mang;
    double _tyLeTaiTrong;
    HashFunc _hamBam;
    size_t _soLuong;
};