Cấu trúc dữ liệu và Giải thuật Bài 43: Bảng Băm (Hash Table) - Phép màu của truy xuất O(1) và Hàm Băm (Hash Function).

Cây Nhị Phân Tìm Kiếm (BST) và các biến thể tự cân bằng (AVL, Red-Black Tree) đã đưa tốc độ tra cứu dữ liệu chạm ngưỡng $O(\log n)$. Tuy nhiên, trong các hệ thống backend chịu tải hàng vạn request mỗi giây, khoảng thời gian quét qua 20 hay 30 tầng của một cái cây đôi khi vẫn là một sự lãng phí tài nguyên CPU.

Khát vọng của ngành Khoa học máy tính là tìm ra một cấu trúc dữ liệu có thể định vị chính xác một bản ghi giữa 1 tỷ bản ghi chỉ bằng đúng 1 bước nhảy vật lý duy nhất ($O(1)$). Cấu trúc duy nhất đạt được tốc độ viễn tưởng này chính là Bảng Băm (Hash Table).

1. Trở về với Mảng tuyến tính

Để đạt được tốc độ $O(1)$, Hash Table thực chất được xây dựng dựa trên cấu trúc nguyên thủy nhất: Mảng (Array).

Như Hiếu đã biết, nếu chúng ta cần tìm phần tử ở vị trí thứ 5 trong một mảng, CPU chỉ cần lấy địa chỉ của ô nhớ đầu tiên cộng thêm 5 lần kích thước của một phần tử để truy xuất thẳng vào dữ liệu. Đây là thao tác $O(1)$ tuyệt đối.

Tuy nhiên, Mảng chỉ chấp nhận chỉ mục (index) là các con số nguyên liên tiếp (0, 1, 2, 3...). Trong thực tế nghiệp vụ, chúng ta cần tra cứu dữ liệu bằng các khóa (Key) phức tạp hơn rất nhiều: một chuỗi UUID ("user_9b2a1"), một địa chỉ email ("admin@hasaki.vn"), hoặc một số điện thoại.

Hash Table giải quyết bài toán này bằng cách đặt một "phiên dịch viên" đứng giữa Key và Mảng. Phiên dịch viên này có nhiệm vụ biến đổi bất kỳ Key nào thành một con số nguyên đại diện cho chỉ mục của Mảng. Người phiên dịch đó chính là Hàm Băm (Hash Function).

2. Trái tim của hệ thống: Hàm Băm (Hash Function)

Hàm băm là một thuật toán toán học nhận vào một đầu vào có kích thước bất kỳ (một chuỗi, một object, một file) và nhả ra một con số nguyên (Hash Code). Con số này sau đó được đem chia lấy dư (Modulo %) cho kích thước của Mảng để tìm ra vị trí index chính xác.

Index = HashFunction(Key) % ArrayCapacity

Để một Bảng băm hoạt động ổn định và không biến thành một thảm họa về bộ nhớ, Hàm băm bắt buộc phải thỏa mãn 3 tiêu chuẩn khắt khe:

1. Tính Tất định (Deterministic): Với cùng một Key đầu vào, hàm băm phải luôn luôn trả về cùng một Hash Code. Nếu hôm nay "admin" băm ra số 5, ngày mai nó băm ra số 9, hệ thống sẽ vĩnh viễn mất dấu dữ liệu.

2. Tốc độ siêu tốc: Thao tác băm phải diễn ra chớp nhoáng ở mức chu kỳ xung nhịp CPU. Nếu hàm băm tính toán quá phức tạp (như các hàm băm mật mã bcrypt hay Argon2), thời gian băm còn lâu hơn cả việc duyệt mảng tuần tự.

3. Phân phối đồng đều (Uniform Distribution): Đây là yếu tố sống còn. Hàm băm phải rải đều các Key ra khắp các ô nhớ của mảng. Nếu hàm băm tồi, nó sẽ nhét tất cả các Key vào chung một vị trí index = 0, biến Hash Table thành một Danh sách liên kết chậm chạp $O(n)$.

3. Triển khai tư duy Hàm Băm bằng Golang

Dưới đây là mô phỏng một hàm băm đơn giản (Polynomial Rolling Hash) chuyên dùng để chuyển đổi một chuỗi (String) thành một chỉ mục Mảng.

Go

package main

import "fmt"

// Cấu trúc thô của một Hash Table
type HashTable struct {
    capacity int
    buckets  []string // Sử dụng mảng để lưu trữ dữ liệu
}

func NewHashTable(size int) *HashTable {
    return &HashTable{
        capacity: size,
        buckets:  make([]string, size),
    }
}

// Hàm Băm: Biến đổi chuỗi thành một con số nguyên
func (h *HashTable) hashFunction(key string) int {
    hashValue := 0
    prime := 31 // Sử dụng số nguyên tố để giảm tỷ lệ trùng lặp

    // Quét qua từng byte (ký tự ASCII) của chuỗi
    for i := 0; i < len(key); i++ {
        // Thuật toán băm: Nhân với số nguyên tố và cộng mã ASCII của ký tự
        hashValue = hashValue*prime + int(key[i])
    }

    // Đảm bảo số không bị âm
    if hashValue < 0 {
        hashValue = -hashValue
    }

    // Trả về vị trí index vừa vặn với kích thước mảng
    return hashValue % h.capacity
}

// Thao tác Insert siêu tốc O(1)
func (h *HashTable) Insert(key string, data string) {
    index := h.hashFunction(key)
    h.buckets[index] = data
    fmt.Printf("Ghi dữ liệu '%s' vào index %d\n", data, index)
}

4. Ứng dụng Bảng băm ở tầng Kiến trúc Hệ thống

Khả năng tra cứu $O(1)$ biến Hash Table thành nền tảng vô giá cho các hệ thống phần mềm hiệu năng cao:

• Redis (In-Memory Data Store): Toàn bộ kiến trúc cốt lõi của Redis là một Bảng băm khổng lồ. Khi bạn thực thi lệnh SET user:1 "John", Redis băm key user:1 và lưu thẳng vào RAM. Đó là lý do Redis có thể phản hồi hàng triệu request mỗi giây mà không bị nghẽn.

• Built-in Data Types (Map/Dict): Kiểu dữ liệu map trong Golang (hay dict trong Python, HashMap trong Java) chính là Bảng băm được ngôn ngữ tự động cấp phát và quản lý bên dưới. Golang sử dụng thuật toán băm cực nhanh (như AES Hash hoặc xxHash) kết hợp với một mảng các "Buckets" (mỗi bucket chứa tối đa 8 cặp key-value) để tối ưu hóa CPU Cache.

• Cơ chế Caching (Bộ nhớ đệm): Bất cứ khi nào hệ thống cần ghi nhớ một kết quả tính toán đắt đỏ từ Database để tái sử dụng, Hash Table luôn là lựa chọn đầu tiên để tra cứu xem dữ liệu đó đã tồn tại trong Cache hay chưa.

• Load Balancing (Consistent Hashing): Các hệ thống phân tán sử dụng một biến thể gọi là Băm Nhất Quán (Consistent Hashing) để quyết định xem request của user sẽ được điều hướng đến Server số mấy trong một cụm Cluster, đảm bảo khi thêm hoặc bớt server, luồng dữ liệu không bị đảo lộn toàn bộ.

Tốc độ $O(1)$ của Bảng băm giống như một ma thuật, nhưng ma thuật nào cũng có cái giá của nó. Bất chấp việc hàm băm được thiết kế hoàn hảo đến đâu, khi số lượng Key vượt quá sức chứa của Mảng, một nguyên lý toán học mang tên "Nguyên lý chuồng bồ câu" (Pigeonhole Principle) sẽ kích hoạt, gây ra hiện tượng 2 Key khác nhau cùng tranh giành chung một ô nhớ.