Trong Python, Bảng băm chính là bản chất bên dưới của hai cấu trúc dữ liệu cực kỳ phổ biến:

1. Dictionary (dict): Ánh xạ Khóa - Giá trị (Key-Value pair).

2. Set (set): Tập hợp các phần tử duy nhất, không trùng lặp.

Mã nguồn Cài đặt Bảng Băm Đơn giản (Chaining Method)

class HashTable:

    def __init__(self, capacity=10):
        self.capacity = capacity
        # Mảng chứa các Bucket, mỗi Bucket là một list (Danh sách liên kết đơn giản)
        self.table = [[] for _ in range(self.capacity)]

    # Hàm băm đơn giản cho chuỗi ký tự - O(1)
    def _hash(self, key: str) -> int:
        hash_value = 0
        for char in key:
            hash_value += ord(char)  # Lấy mã ASCII
        return hash_value % self.capacity

    # Thêm hoặc cập nhật cặp (Key, Value) - O(1) Amortized
    def put(self, key: str, value):
        index = self._hash(key)
        bucket = self.table[index]

        # Kiểm tra nếu Key đã tồn tại thì cập nhật
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return

        # Nếu chưa có thì thêm vào Bucket
        bucket.append((key, value))

    # Tra cứu Giá trị theo Khóa - O(1) trung bình
    def get(self, key: str):
        index = self._hash(key)
        bucket = self.table[index]

        for k, v in bucket:
            if k == key:
                return v
        return None  # Không tìm thấy


# Demo vận hành
ht = HashTable(capacity=5)
ht.put("Xoài", 50)
ht.put("Cam", 30)
ht.put("Chanh", 20)

print("Giá Cam:", ht.get("Cam"))  # Output: 30
print("Giá Táo:", ht.get("Táo"))  # Output: None

BÀI TOÁN KINH ĐIỂN: TWO SUM (LeetCode #1)

Phát biểu bài toán:

Cho một mảng số nguyên nums và một số nguyên target. Hãy tìm chỉ số (index) của hai số trong mảng sao cho tổng của chúng bằng target.

• Cách 1 (Brute Force - 2 vòng lặp): Duyệt mọi cặp số $\rightarrow O(N^2)$ thời gian.

• Cách 2 (Tối ưu với Bảng Băm): Duyệt mảng đúng 1 lần. Với mỗi số x, ta tìm xem phần bù complement = target - x đã xuất hiện trong Hash Table chưa $\rightarrow \mathbf{O(N)}$ thời gian, $O(N)$ bộ nhớ.

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}  # Hash Table lưu giá trị: chỉ số (Key: num, Value: index)

    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

    return []


# Demo
print(two_sum([2, 7, 11, 15], 9))  # Output: [0, 1] (vì 2 + 7 = 9)

BÀI TẬP CỦNG CỐ 

Bài tập 1: Phân tích Tư duy Kỹ thuật

Khi số lượng phần tử chèn vào Hash Table tăng lên quá nhiều làm các Bucket bị quá tải (Hệ số tải - Load Factor $\alpha = \frac{N}{M} > 0.75$), hiệu năng tra cứu sẽ suy giảm từ $O(1)$ xuống tiệm cận $O(N)$.

Để khắc phục hiện tượng này, các ngôn ngữ lập trình sẽ tự động thực hiện thao tác Rehash (Băm lại). Anh hãy dự đoán thao tác Rehash này vận hành ra sao trong bộ nhớ?

Bài tập 2: Thử thách Thực hành Code

Viết một hàm Python first_non_repeating_char(s: str) -> str trả về ký tự đầu tiên không bị trùng lặp trong một chuỗi s. Nếu tất cả ký tự đều bị lặp lại, trả về None.

Yêu cầu: Sử dụng Bảng băm (dict) để đạt độ phức tạp thời gian $O(N)$.

Ví dụ:

• first_non_repeating_char("actuarial") $\rightarrow$ 'c'

• first_non_repeating_char("aabb") $\rightarrow$ None