Cấu trúc dữ liệu và Giải thuật Bài 44: Xử lý đụng độ trong Bảng Băm (Hash Collisions) bằng Chaining và Open Addressing.

Sự hoàn hảo của tốc độ $O(1)$ trong Bảng băm phải đối mặt với một định lý toán học không thể chối cãi: Nguyên lý chuồng bồ câu (Pigeonhole Principle). Nếu bạn có 10 con bồ câu nhưng chỉ có 9 cái chuồng, chắc chắn sẽ có ít nhất 1 chuồng phải nhốt 2 con.

Trong Bảng băm, số lượng Key (ví dụ: mã thẻ từ AFC của hàng vạn hành khách Metro Line 1) luôn lớn hơn rất nhiều so với kích thước Mảng được cấp phát trên RAM. Khi hàm băm biến đổi hai mã thẻ hoàn toàn khác nhau thành cùng một chỉ mục (index), hiện tượng Đụng độ (Hash Collision) xảy ra. Nếu dữ liệu mới ghi đè lên dữ liệu cũ, hệ thống sẽ mất thông tin vĩnh viễn. Để giải quyết rủi ro này, các kỹ sư hệ thống sử dụng hai trường phái thiết kế kinh điển.

1. Separate Chaining (Phương pháp Xâu chuỗi)

Thay vì lưu trực tiếp dữ liệu vào ô nhớ của mảng, mỗi chỉ mục (index) của mảng sẽ đóng vai trò là một "Gốc" (Head) của một Danh sách liên kết (Linked List).

Khi một Key mới được băm ra và trỏ tới một index đã có dữ liệu:

1. Hệ thống không ghi đè, mà tạo ra một Node mới chứa Key và Value.

2. Nối Node mới này vào cuối (hoặc đầu) Danh sách liên kết tại index đó.

3. Khi cần tìm kiếm (Search), hệ thống nhảy đến index bằng hàm băm ($O(1)$), sau đó lội bộ qua Danh sách liên kết tại ô đó để tìm chính xác Key ($O(k)$ với $k$ là độ dài của chuỗi).

Triển khai cơ bản bằng Golang:

Go

// Node của Linked List lưu cả Key và Value để đối chiếu khi tìm kiếm
type HashNode struct {
    Key   string
    Value int
    Next  *HashNode
}

type ChainingHashTable struct {
    buckets []*HashNode // Mảng chứa các con trỏ Head
    size    int
}

func (h *ChainingHashTable) Insert(key string, value int) {
    index := hashFunction(key) % h.size
    newNode := &HashNode{Key: key, Value: value}

    if h.buckets[index] == nil {
        // Ô nhớ trống, đặt làm Head
        h.buckets[index] = newNode
    } else {
        // Đã có đụng độ, duyệt đến cuối Linked List để nối vào
        current := h.buckets[index]
        for current.Next != nil {
            if current.Key == key {
                current.Value = value // Cập nhật nếu Key đã tồn tại
                return
            }
            current = current
        }
        current.Next = newNode
    }
}

• Ưu điểm: Cực kỳ dễ cài đặt và không bao giờ bị "đầy" hoàn toàn (bộ nhớ cấp phát động cho Linked List).

• Nhược điểm: Mất đi lợi thế CPU Cache do các Node trong Linked List nằm rải rác trên RAM (Cache Miss). Nếu hàm băm tồi, một chuỗi có thể dài ra hàng ngàn Node, kéo hiệu năng về $O(n)$. Trong các hệ thống hiện đại như Java 8+, nếu chuỗi Chaining dài quá 8 phần tử, nó sẽ tự động "biến hình" thành một Red-Black Tree để ép thời gian tìm kiếm về $O(\log n)$.

2. Open Addressing (Định vị mở)

Trường phái này từ chối sử dụng Danh sách liên kết để giữ cho dữ liệu luôn nằm liên tục trên một mảng duy nhất, nhằm tối ưu hóa tối đa hiệu suất CPU Cache.

Quy tắc của Open Addressing rất thực tế: "Nếu chỗ này có người ngồi rồi, hãy đi tìm chiếc ghế trống tiếp theo". Quá trình đi tìm ghế trống được gọi là Probing (Thăm dò).

Có 3 chiến thuật thăm dò phổ biến:

1. Linear Probing (Thăm dò tuyến tính): Nếu index bị trùng, thử index + 1, rồi index + 2,... cho đến khi thấy ô trống.

   • Điểm yếu: Gây ra hiện tượng Clustering (Phân cụm). Các dữ liệu có xu hướng tụ tập thành một cục lớn liền kề nhau, làm chậm quá trình tìm ô trống cho các Key đến sau.

2. Quadratic Probing (Thăm dò bậc hai): Tránh phân cụm bằng cách nhảy xa hơn sau mỗi lần trùng: thử index + 1^2, index + 2^2, index + 3^2.

3. Double Hashing (Băm kép): Dùng thêm một hàm băm thứ 2 để quyết định "bước nhảy" sẽ dài bao nhiêu. Đây là cách giải quyết đụng độ hiệu quả nhất trong họ Open Addressing.

Thách thức của thao tác Xóa (Delete):

Trong Open Addressing, bạn không thể xóa hẳn một phần tử bằng cách làm rỗng ô nhớ đó. Nếu làm vậy, chuỗi thăm dò của các phần tử đằng sau sẽ bị đứt đoạn (hệ thống tìm thấy ô rỗng sẽ tưởng là không có dữ liệu và dừng lại). Để giải quyết, người ta phải đặt một "Bia mộ" (Tombstone flag) vào ô bị xóa để báo hiệu: "Dữ liệu ở đây đã bị xóa, nhưng hãy cứ đi tiếp để tìm các phần tử phía sau".

3. Kiến trúc Map trong Golang

Khi Hiếu thiết kế các API backend bằng Go, kiểu dữ liệu map built-in thực chất là một tuyệt tác kết hợp các kỹ thuật trên.

Go sử dụng mô hình Separate Chaining nhưng tối ưu bằng Mảng (Array-based Buckets) thay vì Linked List rời rạc. Mỗi "Bucket" trong Go map là một mảng tĩnh chứa được tối đa 8 cặp Key-Value. Khi một Bucket đầy 8 phần tử do đụng độ, Go mới cấp phát thêm một Overflow Bucket và dùng con trỏ nối vào. Nhờ cách thiết kế dồn 8 phần tử vào một khối liên tục, Go map giảm thiểu được tình trạng Cache Miss của Chaining truyền thống, đồng thời tránh được chi phí dọn dẹp "Bia mộ" phức tạp của Open Addressing.

Bất kể dùng Chaining hay Open Addressing, khi số lượng dữ liệu nhồi vào Bảng băm ngày càng lớn, tỷ lệ đụng độ sẽ tăng vọt khiến hiệu năng suy giảm. Để Bảng băm duy trì được tốc độ $O(1)$, hệ thống phải biết tự động nới rộng không gian và sắp xếp lại toàn bộ dữ liệu trước khi quá muộn.