Tổng quan về giáo trình

Tài liệu bài giảng "Tìm Hiểu Bảng Băm Trong Cấu Trúc Dữ Liệu và Giải Thuật" được biên soạn bởi tác giả Bùi Tiến Lên (ngày 01/01/2017), thuộc khuôn khổ học phần Cấu trúc dữ liệu và Giải thuật (Data structure & Algorithm - học kỳ Spring 2017). Trong chương trình đào tạo đại học các ngành Khoa học máy tính và Công nghệ thông tin, cấu trúc dữ liệu bảng băm (hash table) là một chuyên đề trọng tâm thuộc khối kiến thức cơ sở ngành, cung cấp nền tảng về tổ chức và truy xuất dữ liệu với chi phí thời gian tối ưu.

Mục tiêu học tập của bài giảng tập trung vào các chuẩn đầu ra cụ thể:

  • Nắm vững cơ sở toán học của kỹ thuật băm dựa trên lý thuyết đồng dư và số học mô-đun.
  • Hiểu rõ định nghĩa, bản chất và các tham số kỹ thuật của bảng băm (tập khóa $U$, kích thước bảng $m$, hệ số tải $\alpha$, hiện tượng đụng độ - collision).
  • Nắm vững kỹ thuật chuyển kiểu dữ liệu khóa (từ chuỗi sang số nguyên, băm đa thức, mã kiểm tra toàn vẹn và mật mã như CRC32, MD5, SHA1, SHA2).
  • Phân tích và cài đặt các hàm băm phổ biến (họ hàm băm số nguyên tố, họ hàm băm thao tác bit, hàm băm nhân Knuth).
  • Làm chủ các phương pháp giải quyết đụng độ: Phương pháp nối kết (Separate chaining), Phương pháp địa chỉ mở (Open addressing với các chiến lược dò tìm: tuyến tính, nhị phân, bậc hai, băm kép) và Phương pháp băm hoàn hảo (Perfect hashing).
  • Đánh giá chi phí thuật toán và số lần dò tìm trung bình qua lý thuyết và số liệu thực nghiệm.

Cách tiếp cận của giáo trình đi từ nền tảng toán học thuần túy (lý thuyết đồng dư) đến mô hình hóa cấu trúc dữ liệu, phân tích thuật toán bằng giả mã (pseudocode) và kết thúc bằng đánh giá hiệu năng định lượng. Điểm đặc thù của tài liệu là liên kết chặt chẽ giữa toán học rời rạc và việc thiết kế thuật toán trong khoa học máy tính thực nghiệm.

Nội dung kiến thức cốt lõi

Các chương/chủ đề chính

Cấu trúc nội dung bài giảng được tổ chức theo trình tự logic chặt chẽ qua 6 chủ đề chính:

Chủ đề 1: Lý thuyết đồng dư (Modular Arithmetic)

  • Định nghĩa 1: Cho $n \in \mathbb{N}^*$, hai số nguyên $a, b \in \mathbb{Z}$ được gọi là đồng dư theo mô-đun $n$ nếu cả hai có cùng số dư khi chia cho $n$, ký hiệu là $a \equiv b \pmod n$.
  • Tính chất quan hệ tương đương: Thỏa mãn tính phản xạ ($a \equiv a \pmod n$), tính đối xứng ($a \equiv b \pmod n \Rightarrow b \equiv a \pmod n$) và tính bắc cầu ($a \equiv b \pmod n \land b \equiv c \pmod n \Rightarrow a \equiv c \pmod n$).
  • Tính chất đại số: Nếu $a_1 \equiv b_1 \pmod n$ và $a_2 \equiv b_2 \pmod n$, thì:
    • $a_1 + a_2 \equiv b_1 + b_2 \pmod n$
    • $a_1 - a_2 \equiv b_1 - b_2 \pmod n$
    • $a_1 a_2 \equiv b_1 b_2 \pmod n$
    • $a_1^k \equiv b_1^k \pmod n$
  • Ứng dụng tính toán số học:
    • Tìm phần dư của $3^{32} \pmod{17}$: Tách lũy thừa bậc hai liên tiếp qua các bước mod 17 ($3^2 \equiv 9$, $9^2 \equiv 81 \equiv 15$, $15^2 \equiv 225 \equiv 4$, $4^2 \equiv 16$, $16^2 \equiv 256 \equiv 1$), suy ra $3^{32} \equiv 1 \pmod{17}$.
    • Tìm 2 chữ số cuối cùng của $7^{16}$: Tính $7^{16} \pmod{100}$ thông qua chuỗi bình phương liên tiếp ($7^2 \equiv 49$, $49^2 \equiv 2401 \equiv 1 \pmod{100}$), cho kết quả là $01$.

Chủ đề 2: Các định nghĩa nền tảng về Bảng băm

  • Định nghĩa 2 (Bảng băm): Là cấu trúc dữ liệu chứa các phần tử có địa chỉ, thường được biểu diễn bằng mảng $T$ gồm $m$ phần tử. Bảng băm giúp giảm chi phí thời gian tìm kiếm từ phụ thuộc kích thước dữ liệu (so sánh khóa trên danh sách, cây nhị phân) xuống mức $O(1)$.
  • Định nghĩa 3 (Hàm băm): Ánh xạ từ không gian khóa $U$ vào tập chỉ số địa chỉ ${0, 1, \dots, m-1}$: $$h: U \to {0, 1, \dots, m-1}, \quad k \mapsto h(k)$$ Giá trị $h(k)$ được gọi là hash code hoặc địa chỉ.
  • Định nghĩa 4 (Hệ số tải - Load factor): $$\alpha = \frac{|U|}{m} = \frac{n}{m}$$
  • Định nghĩa 5 (Đụng độ - Collision): Đối với hàm băm $h(x)$, hai khóa phân biệt $x \neq y$ xảy ra đụng độ khi $h(x) = h(y)$. Xác suất xảy ra đụng độ ký hiệu là $\Pr[h(x) = h(y)]$.

Chủ đề 3: Kỹ thuật chuyển kiểu khóa và các họ hàm băm

  • Chuyển kiểu khóa (Pre-hashing): Khóa gốc được chuẩn hóa sang chuỗi nhị phân rồi chuyển thành số nguyên không dấu. Định nghĩa hàm chuyển kiểu $f: S \to {0, 1, \dots, 2^n-1}$. Các chuẩn phổ biến được đề cập gồm CRC32 (32-bit), MD5 (128-bit), SHA1 (160-bit), SHA2 (256-bit).
  • Băm đa thức (Polynomial Hashing): Chuyển mảng ký tự $s[0 \dots m-1]$ với tham số cơ số $b$: $$f(s) = (\dots((s_0 b + s_1)b + s_2)\dots b + s_{m-1}) \bmod 2^n$$
  • Tiêu chí hàm băm tốt: Tính tất định (deterministic), phân tán đều để ít xảy ra đụng độ, và tốc độ tính toán nhanh.
  • Các cấu trúc hàm băm tiêu biểu:
    1. Họ hàm băm số nguyên tố: Cho $p \ge |U|$, định nghĩa $h_r(x) = (xr \bmod p) \bmod m$, tạo nên họ $H = {h_1, h_2, \dots}$.
    2. Họ hàm băm dịch bit: Với $|U| \le 2^w$ và số nguyên dương lẻ $r \le 2^w$: $$g_r(x) = \frac{(rx) \bmod 2^w}{2^{w-\ell}}$$
    3. Định lý 1: Khi chọn ngẫu nhiên một hàm băm $h_r(x) \in H$ hoặc $g_r(x) \in G$, xác suất đụng độ có bậc xấp xỉ $\frac{1}{m}$.
    4. Hàm băm nhân Knuth: $$h(k) = \lfloor m \cdot (k \cdot A \bmod 1) \rfloor$$ Trong đó $k$ là khóa, $m = 2^p$, hằng số tỉ lệ vàng $A = \frac{\sqrt{5}-1}{2} \approx 0.61803398874989$. Ví dụ: Với $k = 12345, m = 2^{10} = 1024 \Rightarrow h(12345) = 644$.

Chủ đề 4: Các thao tác cơ bản trên Bảng băm

Bao gồm 4 thao tác thiết yếu: Khởi tạo bảng (Initialize), Tìm kiếm (Search/Lookup), Thêm phần tử (Insert/Put), và Loại bỏ phần tử (Delete/Remove).

Chủ đề 5: Các phương pháp giải quyết đụng độ

  1. Phương pháp kết nối (Separate Chaining):

    • Tổ chức mỗi ô bảng $T[h(x)]$ thành một danh sách liên kết.
    • Thuật toán thêm: PutToChainingTable(x, h, T) chèn $x$ vào danh sách $T[h(x)]$.
    • Thuật toán tìm kiếm: LookupChainingTable(x, h, T) duyệt tuyến tính trên danh sách $L \leftarrow T[h(x)]$.
    • Định lý 2: Chiều dài trung bình của danh sách $\ell(x)$ bằng hệ số tải $\alpha$; chiều dài dài nhất đạt cỡ $O\left(\frac{\log n}{\log \log n}\right)$.

  2. Phương pháp địa chỉ mở (Open Addressing):

    • Toàn bộ phần tử lưu trực tiếp bên trong mảng $T$, không dùng bộ nhớ ngoài. Khóa được định vị thông qua chuỗi phép dò gồm $m$ hàm băm hoán vị ${h_0(x), h_1(x), \dots, h_{m-1}(x)}$.
    • Thuật toán thêm: PutToOpenAddressingTable lặp tìm vị trí trống $T[h_i(x)] = \text{Null}$.
    • Thuật toán tìm: LookupOpenAddressingTable lặp kiểm tra $T[h_i(x)] = x$ hoặc dừng khi gặp $\text{Null}$.
    • Định lý 3:
      • Số lần dò trung bình khi tìm kiếm khóa không có trong bảng: $\frac{1}{1-\alpha}$.
      • Số lần dò trung bình khi tìm kiếm khóa có trong bảng: $\frac{1}{\alpha} \ln \frac{1}{1-\alpha}$.
      • Trường hợp xấu nhất số lần dò là $O(\log n)$.
    • Các kỹ thuật dò thực tế:
      • Dò tuyến tính (Linear Probing): $h_i(x) = (h(x) + i) \bmod m$. Dễ cài đặt nhưng bị hiện tượng dồn cụm (clustering), giảm hiệu năng nghiêm trọng khi $\alpha \to 1$.
      • Dò nhị phân: $h_i(x) = (h(x) \oplus i)$ với $m = 2^\ell$.
      • Dò bậc hai (Quadratic Probing): $h_i(x) = (h(x) + i^2) \bmod m$.
      • Dò băm kép (Double Hashing): $h_i(x) = (h(x) + i \cdot g(x)) \bmod m$, dùng hai hàm băm độc lập $h(x)$ và $g(x)$.

  3. Phương pháp băm hoàn hảo (Perfect Hashing):

    • Sử dụng cấu trúc bảng hai chiều $T$ và hai hàm băm ${h(x), g(x)}$ qua 2 pha:
      • Pha 1: Băm $x$ vào hàng $h(x)$, đếm số lượng phần tử $C[i]$ của mỗi hàng.
      • Pha 2: Cấp phát vùng nhớ kích thước $C[i]^2$ cho hàng $T[i]$ và băm bằng hàm $g(x) \bmod C[i]^2$.
    • Đụng độ phát sinh ở tầng 2 được quản lý bằng danh sách liên kết.
    • Cung cấp giải mã cụ thể cho thuật toán PutToPerfectTable và LookupPerfectTable.

Chủ đề 6: Đánh giá thực nghiệm và lý thuyết

Báo cáo tổng hợp số liệu thực nghiệm và công thức lý thuyết về số lần dò tìm trung bình qua 4 bảng so sánh (Bảng 1, Bảng 2, Bảng 3, Bảng 4) tại các mốc hệ số tải $\alpha$ (ví dụ: $\alpha = 0.5, \alpha = 0.99...$), chỉ ra sự khác biệt rõ rệt giữa phương pháp mở ngẫu nhiên và mở tuyến tính (khi $\alpha = 0.99$, dò tuyến tính lý thuyết không có trong bảng lên tới 5000 lần dò, thực nghiệm là 430 lần dò).

Kiến thức nền tảng được xây dựng

  • Toán học rời rạc: Lý thuyết số mô-đun, quan hệ tương đương, ước lượng xác suất xung đột.
  • Nguyên lý cấu trúc dữ liệu: Quản trị bộ nhớ mảng tĩnh, danh sách liên kết đơn, mảng hai chiều cấp phát động.
  • Phân tích thuật toán: Đánh giá độ phức tạp trung bình và trường hợp xấu nhất theo ký hiệu Big-O và hệ số tải $\alpha$.

Kỹ năng phát triển

  • Cài đặt cấu trúc dữ liệu bảng băm trên các ngôn ngữ lập trình.
  • Thiết kế và triển khai các hàm băm đa thức, hàm băm nhân số học.
  • Lựa chọn chiến lược giải quyết đụng độ phù hợp với yêu cầu hệ thống (tiết kiệm bộ nhớ với địa chỉ mở hoặc ổn định với kết nối).
  • Đo lường, đối soát hiệu năng thực tế của cấu trúc dữ liệu so với lý thuyết phân tích.

Phương pháp giảng dạy và học tập

Giáo trình áp dụng mô hình sư phạm kết hợp chặt chẽ giữa suy luận hình thức toán học và thiết kế thuật toán ứng dụng:

(Đồng dư mô-đun)        (Bảng băm, Hàm băm)     (Chaining, Dò tìm)      (Bảng số liệu đối soát)

Cách tiếp cận sư phạm

  • Trực quan hóa qua ví dụ cụ thể: Bắt đầu phần lý thuyết số bằng các ví dụ tính toán bước từng bước ($11 \equiv 8 \pmod 3$, $-2 \equiv 5 \pmod 7$, giải thuật bình phương liên tiếp tìm $3^{32} \bmod 17$), giúp người học nắm vững nguyên lý trước khi đi vào định nghĩa trừu tượng.
  • Chuẩn hóa giải thuật qua Pseudocode: Cung cấp mã giả chi tiết, tường minh cho từng thao tác (PutToChainingTable, LookupChainingTable, PutToOpenAddressingTable, LookupOpenAddressingTable, PutToPerfectTable).
  • So sánh đối chiếu định lượng: Trình bày trực tiếp số liệu từ 4 bảng đánh giá (Bảng 1 đến Bảng 4), minh họa tác động trực quan của hệ số tải $\alpha$ lên tốc độ dò tìm.

Hướng dẫn tự học và nghiên cứu

  • Học viên cần tự giải lại các bài toán đồng dư mẫu để làm quen với các phép toán rút gọn số dư trong hàm băm.
  • Đọc các chứng minh định lý toán học (Định lý 1, Định lý 2, Định lý 3) theo các tài liệu tham khảo được chỉ dẫn trong slide.
  • Tự cài đặt lại các thuật toán bằng mã nguồn thực tế (C/C++, Java hoặc Python), tiến hành đo thời gian chạy và đếm số phép so sánh thực tế tương ứng với các bảng thực nghiệm trong giáo trình.

Điểm nổi bật và cập nhật

  1. Tính toán học hóa chặt chẽ: Không chỉ dừng lại ở mô tả cơ chế bảng băm như một mảng dữ liệu, tài liệu xây dựng nền tảng từ lý thuyết đồng dư, thiết lập các định nghĩa chính xác về ánh xạ, họ hàm băm phổ quát và xác suất đụng độ $\frac{1}{m}$.
  2. Bao quát đầy đủ các kỹ thuật băm kinh điển: Trình bày chi tiết công thức hàm băm nhân của Donald Knuth với hằng số tỉ lệ vàng $A \approx 0.61803398874989$, chỉ rõ cơ chế lấy phần thập phân và nhân phần nguyên để ánh xạ đều khóa vào bảng kích thước $2^p$.
  3. Mô hình băm hoàn hảo 2 pha (Perfect Hashing): Phân tích sâu phương pháp băm 2 tầng bằng mảng 2 chiều và cấp phát kích thước $C[i]^2$, giải quyết triệt để vấn đề xung đột khóa tĩnh.
  4. Đối chiếu số liệu lý thuyết và thực nghiệm: Đưa vào các bảng dữ liệu đo lường số bước dò tìm trung bình tại các mức hệ số tải khác nhau, cung cấp cái nhìn thực tế về sự suy giảm hiệu năng khi dùng dò tuyến tính so với băm ngẫu nhiên hoặc băm kép.

Đối tượng sử dụng giáo trình

  • Sinh viên đại học: Sinh viên năm thứ 2 hoặc năm thứ 3 chuyên ngành Khoa học Máy tính, Kỹ thuật Phần mềm, Hệ thống Thông tin, Kỹ thuật Máy tính đang học môn Cấu trúc dữ liệu và Giải thuật.
  • Yêu cầu tiên quyết (Prerequisites):
    • Kiến thức Toán rời rạc (lý thuyết số, quan hệ tương đương, xác suất cơ bản).
    • Kỹ năng lập trình cơ bản (thao tác mảng, con trỏ, danh sách liên kết, toán tử bitwise).
  • Giảng viên: Sử dụng tài liệu làm đề cương slide bài giảng chuyên đề, tài liệu hướng dẫn thảo luận bài tập và thiết kế bài thực hành thuật toán.
  • Kỹ sư phần mềm & Người tự học: Dùng làm tài liệu tham khảo để hiểu sâu cơ chế hoạt động bên dưới của các cấu trúc dữ liệu sẵn có như HashMap, HashSet, Dictionary trong các ngôn ngữ lập trình hiện đại.

Câu hỏi thường gặp

1. Giáo trình này phù hợp với ai?

Tài liệu được thiết kế phục vụ sinh viên đại học ngành Công nghệ Thông tin, Khoa học Máy tính theo học môn Cấu trúc dữ liệu & Giải thuật, cùng các kỹ sư cần nắm vững cơ chế định vị dữ liệu $O(1)$.

2. Cần kiến thức nền nào để học chuyên đề này?

Người học cần nắm vững toán rời rạc căn bản (phép chia dư mô-đun, hàm số, xác suất cơ bản) và thành thạo thao tác mảng, danh sách liên kết, thao tác bit trên một ngôn ngữ lập trình cụ thể.

3. Điểm khác biệt của tài liệu so với các bài giảng cấu trúc dữ liệu khác là gì?

Tài liệu khởi đầu bằng việc xây dựng lý thuyết đồng dư số học, đi sâu vào mô hình băm Knuth tỉ lệ vàng, họ hàm băm phổ quát, phương pháp băm hoàn hảo 2 pha, kèm bảng số liệu đối chiếu chi tiết giữa lý thuyết và thực nghiệm.

4. Làm sao để tự học nội dung này hiệu quả?

Cần thực hiện theo quy trình: Đọc hiểu lý thuyết toán học -> Tự tính tay các ví dụ băm ($3^{32} \bmod 17$, Knuth hash với $k=12345$) -> Viết mã hiện thực các hàm giả mã PutTo... và Lookup... -> Thực nghiệm đếm số lần dò tìm theo các mức hệ số tải $\alpha$.

5. Giáo trình có đề cập đến các hàm băm mở rộng nào khác không?

Có. Giáo trình giới thiệu các thuật toán chuyển kiểu khóa chuẩn mực trong công nghiệp và mật mã học như CRC32, MD5, SHA1, SHA2 và băm đa thức (Polynomial hashing).

Kết luận

Bài giảng "Tìm Hiểu Bảng Băm Trong Cấu Trúc Dữ Liệu và Giải Thuật" của tác giả Bùi Tiến Lên cung cấp hệ thống tri thức hoàn chỉnh về kỹ thuật băm trong khoa học máy tính. Bằng việc kết nối lý thuyết số học đồng dư với các cấu trúc lưu trữ và thuật toán xử lý đụng độ (Separate Chaining, Open Addressing, Perfect Hashing), tài liệu mang lại nền tảng phương pháp luận vững chắc cho người học.

Lộ trình học tập đề xuất là hoàn thiện cơ sở toán học mô-đun, hiện thực hóa các thuật toán xử lý đụng độ bằng ngôn ngữ lập trình và kiểm chứng lại bằng các bảng số liệu thực nghiệm được trình bày trong tài liệu.