Bản chất Toán học & Bài toán Ánh xạ

Ở học phần trước, chúng ta đã biết:

• Mảng: Truy cập $O(1)$ nếu biết chỉ số số nguyên (arr[0], arr[1]).

• Tìm kiếm: Mất $O(N)$ (tuyến tính) hoặc $O(\log N)$ (nhị phân trên mảng đã sắp xếp) nếu tìm theo giá trị / khóa (Key).

Bài toán đặt ra: Làm sao để tìm kiếm một dữ liệu bất kỳ (chuỗi chữ, chuỗi số, hoặc đối tượng phức tạp) bằng một Khóa (Key) với thời gian tức thì $O(1)$ giống như truy cập chỉ số mảng?

Giải pháp: Sử dụng Bảng băm (Hash Table) kết hợp với Hàm băm (Hash Function).

    Khóa (Key)          Hàm băm h(Key)          Chỉ số Mảng (Index)      Mảng lưu trữ (RAM)
  "Chanh"      --------> [ Hash Func ] -------->       index 2        -------->  [ 0 ] None
  "Cam"        --------> [ h(k) % M  ] -------->       index 0        -------->  [ 1 ] None
  "Xoài"       -------->               -------->       index 4        -------->  [ 2 ] "Chanh"
                                                                                 [ 3 ] None
                                                                                 [ 4 ] "Xoài"

Yêu cầu toán học của một Hàm băm tốt $h(k)$:

1. Tính xác định (Deterministic): Cùng một Khóa $k$ đưa vào phải luôn ra cùng một giá trị băm $h(k)$.

2. Tính đồng đều (Uniformity): Phân bổ các giá trị băm đều khắp không gian bộ nhớ (từ $0$ đến $M-1$) để giảm thiểu đụng độ.

3. Hiệu năng cao: Tính toán kết quả $h(k)$ phải nhanh ($O(1)$).

1. TẠI SAO LẠI CẦN BẢNG BĂM? (BÀI TOÁN TỔ CHỨC BỘ NHỚ)

Hãy hình dung ta quản lý danh sách thông tin của các loại quả trong xưởng chế biến.

• Nếu dùng Mảng (Array) hay Danh sách (List):

  Muốn tìm thông tin của "Chanh", máy tính bắt buộc phải so sánh từng ô: arr[0] == "Chanh"?, arr[1] == "Chanh"?... Nếu có 1.000.000 ô, máy tính phải duyệt tối đa 1.000.000 lần ($O(N)$).

• Ngược lại, nếu truy cập qua chỉ số số nguyên (Index):

  Máy tính nhảy thẳng tới ô RAM đó qua công thức địa chỉ: arr[2] $\rightarrow$ Mất đúng 1 phép tính ($O(1)$).

Câu hỏi đặt ra: Làm sao để biến một Chuỗi chữ bất kỳ (như "Chanh", "Cam", "Xoài") thành một Chỉ số số nguyên (Index) để nhảy thẳng tới vị trí lưu trữ trên RAM?

Câu trả lời: Đó chính là nhiệm vụ của Hàm băm (Hash Function).

2. NGUYÊN LÝ HOẠT ĐỘNG 2 BƯỚC CỦA HÀM BĂM

Hàm băm là một "máy nghiền dữ liệu" nhận vào một dữ liệu bất kỳ (Khóa - Key) và thực hiện 2 bước chuyển đổi:

[ Dữ liệu Khóa (Key) ] 
          │
          ▼
   1. Đổi sang Số nguyên (Hash Value)
          │  (Ví dụ: Mã ASCII / Phép toán Bit)
          ▼
   2. Ép vào Kích thước Mảng (Modulo Operation)
          │  ( Hash Value % Capacity )
          ▼
[ Index trên RAM (0, 1, 2, ..., Capacity-1) ]

Bước 1: Đổi chuỗi chữ thành một số nguyên (Hash Value)

Máy tính xử lý mọi ký tự dưới dạng mã số (ASCII/Unicode). Hàm băm sẽ cộng hoặc nhân mã của các ký tự theo một công thức toán học.

Ví dụ: Lấy mã ASCII đơn giản của từng chữ cái:

• "Cam" = 'C' (67) + 'a' (97) + 'm' (109) = 273

• "Chanh" = 'C' (67) + 'h' (104) + 'a' (97) + 'n' (110) + 'h' (104) = 482

Bước 2: Ép số nguyên đó vào phạm vi Mảng lưu trữ (Phép chia lấy dư %)

Giả sử bộ nhớ của ta là một mảng có 5 ô trống (chỉ số từ 0 đến 4).Ta dùng phép chia lấy dư (Modulo %) cho dung lượng mảng ($M = 5$):

• "Cam": $273 \pmod 5 = \mathbf{3}$ $\rightarrow$ Lưu thông tin của "Cam" vào ô số 3.

• "Chanh": $482 \pmod 5 = \mathbf{2}$ $\rightarrow$ Lưu thông tin của "Chanh" vào ô số 2.

3. MÔ HÌNH LƯU TRỮ VÀ TRA CỨU TRỰC QUAN

Giả sử ta khởi tạo một Bảng băm gồm 5 vị trí: [None, None, None, None, None]

Mảng RAM (Capacity = 5):

Index 0: [ None ]
Index 1: [ None ]
Index 2: [ "Chanh": 20 kg ]  <-- h("Chanh") % 5 = 2
Index 3: [ "Cam":   50 kg ]  <-- h("Cam")   % 5 = 3
Index 4: [ None ]

Khi ta thực hiện lệnh Tra cứu: get("Cam")

1. Máy tính đưa chuỗi "Cam" qua Hàm băm $\rightarrow$ Tính ra Index = 3.

2. Máy tính nhảy thẳng vào ô số 3 trên RAM và lấy ra giá trị 50 kg.

3. Kết quả: Không cần tìm kiếm, không cần duyệt qua "Chanh" hay các ô khác. Độ phức tạp là $O(1)$.

4. TẠI SAO LẠI CÓ ĐỤNG ĐỘ BĂM (HASH COLLISION)?

Bây giờ, giả sử ta muốn chèn thêm loại quả thứ ba: "Xoài".

1. Mã ASCII của "Xoài" (giả định tính ra tổng) là 128.

2. Ép vào mảng 5 ô: $128 \pmod 5 = \mathbf{3}$.

Vấn đề xuất hiện: Ô số 3 đã bị "Cam" chiếm giữ từ trước! Hai khóa khác nhau ("Cam" và "Xoài") lại tính ra cùng một vị trí Index 3. Đây gọi là Đụng độ băm (Collision).

Cách khắc phục phổ biến nhất: Tách chuỗi (Separate Chaining)

Thay vì lưu trực tiếp 1 phần tử tại mỗi ô, ta biến mỗi ô của mảng thành một Danh sách liên kết (Linked List):

Index 0: None
Index 1: None
Index 2: [ "Chanh", 20kg ] -> None
Index 3: [ "Cam", 50kg ]   -> [ "Xoài", 80kg ] -> None   (Đụng độ được nối tiếp vào đuôi)
Index 4: None

Khi tra cứu "Xoài":

1. Máy tính tính băm ra Index 3.

2. Máy tính đến Index 3 và duyệt danh sách ngắn ở ô đó: thấy "Cam" không phải $\rightarrow$ chuyển sang ô tiếp theo thấy "Xoài" $\rightarrow$ Trả về 80kg.

5. BA ĐẶC TÍNH CỐT LÕI CỦA MỘT HÀM BĂM CHUẨN XÁC

Để Bảng băm hoạt động mượt mà, Hàm băm bắt buộc phải thỏa mãn 3 điều kiện:

1. Tính xác định (Deterministic): Nhập "Cam" lần thứ 1 hay lần thứ 1.000 đều phải ra kết quả Index là 3. Nếu ra kết quả ngẫu nhiên, ta sẽ bị mất dấu dữ liệu.

2. Phân bổ đồng đều (Uniform Distribution): Rải dữ liệu đều vào các ô (0, 1, 2, 3, 4) thay vì dồn tất cả vào 1 ô, giúp danh sách nối ở mỗi ô ngắn nhất có thể.

3. Tốc độ tính toán siêu nhanh ($O(1)$): Phép tính băm phải cực kỳ nhẹ để không làm chậm chương trình.