Cấu trúc dữ liệu và Giải thuật Bài 45: Hệ số tải (Load Factor) và kỹ thuật Rehashing để duy trì hiệu năng O(1).

Bất kể Hiếu sử dụng Chaining hay Open Addressing để xử lý đụng độ, sức chịu đựng của Bảng băm (Hash Table) luôn có giới hạn. Khi một mảng có sức chứa 10 ô nhớ phải gồng gánh đến 50 phần tử, tỷ lệ đụng độ sẽ lên tới 100%. Các chuỗi Linked List sẽ dài lê thê, hoặc các vòng lặp thăm dò (Probing) sẽ phải chạy cạn kiệt mảng. Tốc độ $O(1)$ tự hào của hệ thống sẽ sụp đổ hoàn toàn về $O(n)$.

Để duy trì hiệu năng siêu tốc, Bảng băm không thể giữ mãi một kích thước. Nó phải biết tự động "phình to" ra trước khi sự chật chội phá hỏng mọi thứ. Quá trình lột xác đó được điều khiển bởi hai khái niệm cốt lõi: Hệ số tải (Load Factor) và Rehashing.

1. Mức báo động đỏ: Hệ số tải (Load Factor)

Hệ số tải (thường ký hiệu là $\alpha$) là một thước đo mật độ chật chội của Bảng băm.

Công thức: Load Factor = Số lượng phần tử đã lưu (N) / Kích thước mảng (M)

• Nếu mảng có 10 ô, và bạn đã lưu 7 phần tử, $\alpha = 0.7$.

• Nếu $\alpha$ quá thấp (ví dụ 0.1): Hệ thống đang lãng phí bộ nhớ RAM nghiêm trọng.

• Nếu $\alpha$ quá cao (ví dụ > 0.8): Nguy cơ đụng độ tăng vọt, hiệu năng CPU suy giảm.

Mỗi ngôn ngữ lập trình thiết lập một ngưỡng chịu đựng (Threshold) riêng cho $\alpha$. Khi vượt qua ngưỡng này, Bảng băm sẽ tự động kích hoạt chiến dịch mở rộng.

• Trong Java (HashMap): Ngưỡng mặc định là 0.75.

• Trong Golang (Map): Ngưỡng giới hạn được thiết lập ở mức trung bình 6.5 phần tử / 1 bucket.

2. Kỹ thuật Rehashing (Băm lại từ đầu)

Khi $\alpha$ chạm ngưỡng, hệ thống không thể chỉ đơn giản là nối thêm bộ nhớ vào đuôi mảng cũ như thao tác append của Slice. Lý do nằm ở công thức định vị cốt lõi:

Index = HashCode % Kích_thước_mảng

Nếu kích thước mảng thay đổi từ 10 lên 20, phép chia lấy dư % 20 sẽ cho ra một kết quả hoàn toàn khác so với % 10. Nếu chỉ copy dữ liệu cũ sang mảng mới, hệ thống sẽ vĩnh viễn mất dấu dữ liệu vì sai lệch Index.

Quá trình Rehashing buộc phải diễn ra theo 3 bước vô cùng tốn kém:

1. Cấp phát: Yêu cầu hệ điều hành cấp phát một mảng mới với kích thước gấp đôi mảng cũ.

2. Quét (Scan): Duyệt qua từng phần tử một đang tồn tại trong Bảng băm cũ.

3. Băm lại (Rehash): Đem Key của từng phần tử băm lại từ đầu, tính toán lại Index dựa trên kích thước mảng mới, và ghi vào vị trí mới.

Go

// Mô phỏng logic Rehashing cơ bản
func (h *HashTable) checkAndRehash() {
    loadFactor := float64(h.count) / float64(h.capacity)
    
    // Nếu vượt ngưỡng 75%, kích hoạt Rehashing
    if loadFactor > 0.75 {
        newCapacity := h.capacity * 2
        newBuckets := make([]*HashNode, newCapacity)
        
        // Băm lại toàn bộ dữ liệu từ mảng cũ sang mảng mới
        for _, headNode := range h.buckets {
            current := headNode
            for current != nil {
                // Tính toán lại Index với newCapacity
                newIndex := hashFunction(current.Key) % newCapacity
                
                // Trích xuất Node và đưa vào newBuckets (giản lược logic nối chuỗi)
                nextNode := current.Next
                current.Next = newBuckets[newIndex]
                newBuckets[newIndex] = current
                
                current = nextNode
            }
        }
        
        // Cập nhật lại trạng thái của Hash Table
        h.buckets = newBuckets
        h.capacity = newCapacity
    }
}

3. Khái niệm Thời gian Khấu hao (Amortized Time)

Ca phẫu thuật Rehashing tiêu tốn thời gian $O(n)$ vật lý. Điều này dẫn đến một hiện tượng: Bạn chèn 999 phần tử vào Map cực kỳ mượt mà với $O(1)$, nhưng đến phần tử thứ 1000, hệ thống đột ngột bị "khựng" lại một nhịp do phải thực hiện vòng lặp băm lại 999 phần tử trước đó.

Tuy nhiên, trong Khoa học máy tính, chúng ta vẫn kết luận thao tác chèn của Bảng băm là $O(1)$. Lý do là vì thao tác $O(n)$ này rất hiếm khi xảy ra. Khi chia đều (khấu hao) chi phí khổng lồ của một lần Rehashing cho hàng ngàn lần chèn $O(1)$ miễn phí trước đó, chi phí trung bình cho mỗi lần chèn vẫn xấp xỉ một hằng số. Thuật ngữ chuyên ngành gọi đây là $O(1)$ Amortized.

4. Kiến trúc "Sơ tán dần" (Incremental Evacuation) của Golang

Trong các hệ thống backend thiết yếu yêu cầu độ trễ siêu thấp (Low Latency), một cú "khựng" $O(n)$ khi Rehashing một Map chứa hàng triệu Key có thể gây quá thời gian (Timeout) cho một API Request.

Để bảo vệ server, Golang map áp dụng một kỹ thuật tuyệt đỉnh mang tên Incremental Evacuation (Sơ tán dần dần).

Khi Go map chạm ngưỡng tải, nó cấp phát mảng mới gấp đôi, nhưng không dời toàn bộ dữ liệu ngay lập tức. Thay vào đó, nó duy trì cùng lúc 2 mảng: oldbuckets và buckets.

Mỗi khi có một request thêm/xóa/sửa nhắm vào một bucket nào đó, Go sẽ tiện tay "khiêng" luôn 1 hoặc 2 bucket từ mảng cũ sang mảng mới. Quá trình sơ tán được chia nhỏ ra, hòa tan vào các thao tác thông thường. Nhờ vậy, Garbage Collector và CPU không bao giờ bị nghẽn đột ngột.

5. Bài học tối ưu bộ nhớ cốt lõi

Từ cơ chế Rehashing, một quy tắc bất di bất dịch khi thiết kế phần mềm hiệu năng cao được rút ra: Nếu biết trước số lượng dữ liệu, hãy luôn cấp phát dung lượng (Capacity) cho Map ngay từ đầu.

Go

// Tồi: Hệ thống sẽ phải cấp phát và Rehash liên tục từ 1 -> 2 -> 4 -> 8... -> 10000
users := make(map[string]User)

// Hoàn hảo: Hệ thống cấp phát một lần duy nhất, không bao giờ xảy ra Rehashing
users := make(map[string]User, 10000) 

Việc cung cấp gợi ý kích thước (Size Hint) cứu hệ thống khỏi những nhịp giật lag $O(n)$ vô ích và chặn đứng sự phân mảnh bộ nhớ Heap.

Chương 8 đã khép lại bằng việc làm chủ cấu trúc dữ liệu lưu trữ tuyến tính có tốc độ tuyệt đối nhất. Tuy nhiên, thế giới thực không chỉ có những dữ liệu lưu trữ tĩnh. Mạng lưới Internet, đường đi của các trạm Metro Line 1, hay thuật toán gợi ý bạn bè trên mạng xã hội đều đòi hỏi một cấu trúc liên kết đa chiều, nơi mọi điểm đều có thể kết nối với mọi điểm. Đó là lúc chúng ta bước vào thế giới toán học phức tạp nhất của Cấu trúc dữ liệu.