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

Tài liệu học tập Data Structure and Algorithms (mã học phần: CO2003), chuyên đề Chapter 9 - Hash, được biên soạn bởi TS. Nguyễn Đức Dũng (Duc Dung Nguyen, PhD. - nddung@hcmut.vn) thuộc Khoa Khoa học và Kỹ thuật Máy tính, Trường Đại học Bách Khoa – ĐHQG TP.HCM (HCMUT). Học phần này giữ vị trí cốt lõi trong khối kiến thức cơ sở ngành thuộc chương trình đào tạo kỹ sư và cử nhân ngành Khoa học Máy tính và Kỹ thuật Máy tính.

Chuẩn đầu ra (Learning Outcomes) của tài liệu được xác định theo 5 mục tiêu cụ thể:

  • L.1: Trình bày chính xác các khái niệm nền tảng bao gồm bảng băm (hashing table), khóa (key), hiện tượng xung đột (collision) và phương pháp giải quyết xung đột (collision resolution).
  • L.2: Mô tả các hàm băm (hashing functions) bằng mã giả (pseudocode) và giải thích thuật toán qua các ví dụ minh họa từng bước.
  • L.3: Mô tả các phương pháp giải quyết xung đột bằng mã giả kèm ví dụ minh họa trực quan.
  • L.4: Hiện thực hóa cấu trúc bảng băm bằng ngôn ngữ lập trình C/C++.
  • L.5: Phân tích độ phức tạp thuật toán và phát triển chương trình thực nghiệm để đánh giá các phương pháp bảng băm; sử dụng ký hiệu Big-O để đặc trưng hóa độ phức tạp tính toán đối với các cấu trúc điều khiển tuần tự (sequence), rẽ nhánh (branching) và lặp (iteration - không đệ quy).

Tài liệu được cấu trúc theo phương pháp sư phạm diễn dịch: bắt đầu từ việc phân tích giới hạn hiệu năng của các giải thuật tìm kiếm truyền thống, đặt ra yêu cầu đạt độ phức tạp $O(1)$, từ đó xây dựng các hàm băm số học và phát triển các chiến lược xử lý xung đột không gian địa chỉ. Điểm đặc thù của bài giảng là tính toán học chặt chẽ, kết hợp trực tiếp giữa công thức giải tích, mã giả chuẩn mực và bảng số liệu thực nghiệm định lượng.

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

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

Nội dung chuyên đề Bảng băm (Chapter 9 - Hash) được tổ chức thành các khối chủ đề liên kết logic:

  1. Khái niệm cơ bản và Động lực thiết kế:

    • So sánh chi phí tìm kiếm giữa Tìm kiếm tuần tự (Sequential Search) với độ phức tạp trung bình và xấu nhất $O(n)$ và Tìm kiếm nhị phân (Binary Search) với độ phức tạp $O(\log_2 n)$. Bảng đối chuẩn hiệu năng được tài liệu lượng hóa từ kích thước dữ liệu $N = 16$ đến $N = 1.000.000$:
      • Với $N = 16$: Binary search tốn 4 phép so sánh, Sequential search tốn 8 (trung bình) và 16 (tệ nhất).
      • Với $N = 1.000$: Binary search tốn 10 phép so sánh, Sequential search tốn 500 (trung bình) và 1.000 (tệ nhất).
      • Với $N = 1.000.000$: Binary search tốn 20 phép so sánh, Sequential search tốn 500.000 (trung bình) và 1.000.000 (tệ nhất).
    • Đặt vấn đề thiết kế thuật toán tìm kiếm đạt độ phức tạp $O(1)$.
    • Các định nghĩa chuẩn:
      • Home address: Địa chỉ gốc sinh ra bởi hàm băm.
      • Prime area: Vùng bộ nhớ chứa toàn bộ các địa chỉ gốc.
      • Synonyms: Tập hợp các khóa khác nhau được ánh xạ về cùng một địa chỉ.
      • Collision: Tình trạng vị trí dữ liệu cần chèn đã bị chiếm bởi dữ liệu đồng nghĩa (synonym).
      • Ideal hashing: Trạng thái băm lý tưởng thỏa mãn hai điều kiện: không xảy ra xung đột địa chỉ và không gian địa chỉ nhỏ gọn (compact address space).

  2. Các phương pháp xây dựng hàm băm (Hash Functions):

    • Direct Hashing: Địa chỉ chính là giá trị của khóa: $hash(Key) = Key$. Phương pháp này triệt tiêu xung đột nhưng đòi hỏi kích thước không gian lưu trữ phải bằng kích thước không gian khóa.
    • Modulo Division: $Address = Key \pmod{listSize}$. Tài liệu chỉ rõ số lượng xung đột sẽ giảm thiểu nếu $listSize$ được chọn là một số nguyên tố. Ví dụ hệ thống quản lý 1.000.000 nhân viên lưu trong không gian 300 phần tử, chọn $listSize = 307$: $hash(121267) = 121267 \pmod{307} = 2$.
    • Digit Extraction: Trích xuất các chữ số ở vị trí xác định từ khóa (ví dụ: $379452 \to 394$, $121267 \to 112$, $045128 \to 051$).
    • Mid-square: Bình phương khóa và lấy các chữ số ở giữa ($9452^2 = 89340304 \to 3403$). Khi $Key^2$ quá lớn, sử dụng biến thể lấy bình phương của một phần khóa ($379^2 = 143641 \to 364$).
    • Folding: Chia khóa thành các phần bằng kích thước địa chỉ:
      • Fold shift: Cộng trực tiếp các phần ($123 + 456 + 789 = 1368 \to 368$).
      • Fold boundary: Đảo ngược các phần ở biên trước khi cộng ($321 + 456 + 987 = 1764 \to 764$).
    • Rotation: Xoay vòng chữ số của khóa trước khi băm để phân tán các khóa chỉ khác nhau ở ký tự cuối (ví dụ chuỗi $600101 \dots 600105$ xoay thành $160010 \dots 560010$), kết hợp với fold shift để dàn đều dữ liệu trên không gian địa chỉ.
    • Pseudo-random: Sử dụng công thức tuyến tính đồng dư $Address = (a \cdot Key + c) \pmod{listSize}$, trong đó $a$ và $c$ là các số nguyên tố. Ví dụ: $Key = 121267, a = 17, c = 7, listSize = 307 \implies (17 \times 121267 + 7) \pmod{307} = 41$.

  3. Kỹ thuật giải quyết xung đột (Collision Resolution):

    • Ngoại trừ Direct Hashing, tất cả các hàm băm đều không phải ánh xạ $1-1$, bắt buộc phải áp dụng các kỹ thuật xử lý va chạm: Open addressing, Linked list resolution, và Bucket hashing.
    • Địa chỉ mở (Open Addressing): Tìm một phần tử còn trống trong bảng để đặt phần tử mới. Hàm băm mở rộng tích hợp bước thăm dò: $$hp: U \times {0, 1, \dots, m - 1} \to {0, 1, \dots, m - 1}$$ Tập hợp ${hp(k, 0), hp(k, 1), \dots, hp(k, m - 1)}$ phải là một hoán vị của tập địa chỉ ${0, 1, \dots, m - 1}$.
    • Bốn phương pháp thăm dò trong Open Addressing:
      • Linear Probing: $hp(k, i) = (h(k) + i) \pmod m$.
      • Quadratic Probing: $hp(k, i) = (h(k) + i^2) \pmod m$.
      • Double Hashing: $hp(k, i) = (h_1(k) + i \cdot h_2(k)) \pmod m$.
      • Key Offset: $offset = \lfloor Key / listSize \rfloor$; công thức bước nhảy: $hp(k, i) = (hp(k, i - 1) + \lfloor k / m \rfloor) \pmod m$.

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

  • Lý thuyết ánh xạ và không gian địa chỉ: Định nghĩa hàm ánh xạ từ không gian khóa vũ trụ $U$ vào không gian địa chỉ rời rạc ${0, 1, \dots, m-1}$.
  • Lý thuyết số ứng dụng: Ứng dụng số nguyên tố (prime numbers) trong việc tối ưu hóa chu kỳ của phép chia lấy dư và hàm giả ngẫu nhiên nhằm giảm thiểu hiện tượng tập trung khóa (clustering).
  • Phân tích thuật toán: Vận dụng ký hiệu Big-O để đánh giá các thuật toán thao tác dữ liệu cơ bản:
// Thuật toán chèn vào bảng băm địa chỉ mở
Algorithm hashInsert(ref T <array>, val k <key>)
    i = 0
    while i < m do
        j = hp(k, i)
        if T[j] = nil then
            T[j] = k
            return j
        else
            i = i + 1
        end
    end
    return error: "hash table overflow"
End hashInsert

// Thuật toán tìm kiếm trong bảng băm địa chỉ mở
Algorithm hashSearch(val T <array>, val k <key>)
    i = 0
    while i < m do
        j = hp(k, i)
        if T[j] = k then
            return j
        else if T[j] = nil then
            return nil
        else
            i = i + 1
        end
    end
    return nil
End hashSearch

Kỹ năng phát triển

  • Kỹ năng kỹ thuật: Lập trình cấu trúc dữ liệu bảng băm trên C/C++, xử lý các phép toán số học cấp bit, trích xuất chuỗi và mảng ký tự phục vụ hàm băm.
  • Kỹ năng phân tích: Nhận diện và phân biệt hai hiện tượng tắc nghẽn hiệu năng:
    • Hiện tượng kết cụm nguyên phát (Primary Clustering): Xuất hiện trong Linear Probing khi các ô nhớ bị chiếm đóng có xu hướng nối dài liền kề nhau.
    • Hiện tượng kết cụm thứ phát (Secondary Clustering): Xuất hiện trong Quadratic Probing khi hai khóa có cùng địa chỉ gốc $h(k_1) = h(k_2)$ sẽ tạo ra chuỗi thăm dò hoàn toàn trùng lặp $hp(k_1, i) = hp(k_2, i)$.
  • Kỹ năng thực nghiệm: Thiết kế chương trình đo lường số lần thăm dò thực tế (probe counts) và kiểm thử tải bảng băm trong điều kiện bộ nhớ đầy (hash table overflow).

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

Giáo trình áp dụng mô hình tiếp cận định lượng:

Quy trình sư phạm và bài tập thực hành

  1. Phân tích ca học thuật (Case Studies): Giảng viên đưa ra các bài toán cụ thể về quy mô dữ liệu (ví dụ quản lý $1.000.000$ nhân viên trong không gian mảng $300$ phần tử) để minh họa cho sự cần thiết của hàm Modulo với số nguyên tố $307$.
  2. Bài tập tính toán từng bước:
    • Tính toán địa chỉ của chuỗi khóa thông qua các phép biến đổi Fold Shift ($123 + 456 + 789 = 1368 \to 368$) và Fold Boundary ($321 + 456 + 987 = 1764 \to 764$).
    • Phân tích hiệu ứng phân tán của kỹ thuật xoay khóa (Rotation) khi kết hợp fold shift để đưa các khóa liên tiếp ($600101 \dots 600105$) về các địa chỉ cách biệt ($26, 36, 46, 56, 66$).
    • Tính toán hàm băm giả ngẫu nhiên: $((17 \times 121267 + 7) \pmod{307} = 2061546 \pmod{307} = 41)$.
  3. Thực hành lập trình và Đánh giá:
    • Hiện thực hóa cấu trúc mảng và con trỏ cho các phương pháp giải quyết xung đột bằng C/C++.
    • Xây dựng chương trình thực nghiệm để kiểm chứng độ phức tạp thời gian khi bảng băm tiến dần đến hệ số tải cao.
  4. Hướng dẫn tự học:
    • Đọc hiểu và viết lại các thuật toán hashInsert và hashSearch theo cấu trúc lặp không đệ quy.
    • Viết mã nguồn kiểm tra tính chất hoán vị của hàm thăm dò: ${hp(k, 0), \dots, hp(k, m - 1)}$ phải phủ kín không gian ${0, \dots, m - 1}$.

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

Tài liệu thể hiện các đặc tính học thuật mang tính thực chứng và hệ thống hóa:

Tiêu chí Nội dung chi tiết trong tài liệu
Hình thức hóa toán học Thiết lập không gian ánh xạ chuẩn xác: $h: U \to {0, \dots, m-1}$ và hàm thăm dò $hp: U \times {0, \dots, m-1} \to {0, \dots, m-1}$.
Phân tích đánh đổi (Trade-off) So sánh rõ ưu - nhược điểm của từng phương pháp: Direct Hashing (không xung đột nhưng tốn bộ nhớ); Linear Probing (dễ cài đặt, tối ưu đọc ghi đĩa do dữ liệu tập trung gần home address, nhưng gây primary clustering); Quadratic Probing (giảm va chạm tốt hơn nhưng tốn chi phí tính lũy thừa $i^2$ và gây secondary clustering).
Kỹ thuật xử lý chuyên sâu Giới thiệu kỹ thuật dịch chuyển khóa (Key Offset) với công thức bước nhảy phụ thuộc đồng thời vào giá trị khóa và kích thước bảng: $offset = \lfloor key / listSize \rfloor$.
Mối liên kết thực tế Liên hệ giữa cấu trúc lưu trữ của Linear Probing với đặc tính vật lý của ổ đĩa (disk addresses), nơi các khối dữ liệu đặt cạnh nhau giúp tối ưu thời gian truy xuất.

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

  • Sinh viên mục tiêu: Sinh viên đại học năm thứ hai hoặc năm thứ ba thuộc các ngành Khoa học Máy tính, Kỹ thuật Máy tính, Công nghệ Thông tin đang theo học học phần Cấu trúc dữ liệu và Giải thuật (mã môn CO2003).
  • Kiến thức tiên quyết (Prerequisites):
    • Ngôn ngữ lập trình C/C++ (thao tác mảng, con trỏ, cấp phát bộ nhớ).
    • Kiến thức toán rời rạc cơ bản: Số học đồng dư (modular arithmetic), tính chất số nguyên tố, hoán vị.
    • Khái niệm nền tảng về cấu trúc dữ liệu: Mảng (array), danh sách liên kết (linked list).
    • Khái niệm phân tích thuật toán: Ký hiệu Big-O cho các cấu trúc điều khiển cơ bản (tuần tự, rẽ nhánh, lặp).
  • Đối với Giảng viên: Tài liệu cung cấp khung bài giảng chuẩn hóa, hệ thống mã giả chính xác và các ví dụ số học chuẩn mực để xây dựng bài kiểm tra và bài tập lớn (assignments).
  • Tự học và Nghiên cứu: Phù hợp cho người học cần củng cố bản chất toán học của các hệ thống băm trước khi tiếp cận các cấu trúc nâng cao trong hệ quản trị cơ sở dữ liệu hoặc hệ thống phân tán.

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ế cho sinh viên ngành Khoa học và Kỹ thuật Máy tính học môn Cấu trúc dữ liệu và Giải thuật (CO2003), cùng các lập trình viên cần hiểu sâu về cơ chế hoạt động tầng thấp của cấu trúc Bảng băm.

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 kỹ thuật lập trình C/C++, cấu trúc dữ liệu mảng và danh sách liên kết, các phép toán số học cơ bản (phép chia lấy dư, số nguyên tố) và phương pháp đánh giá độ phức tạp thuật toán bằng ký hiệu Big-O.

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

Tài liệu tập trung vào việc mô hình hóa toán học các hàm băm và các phương pháp giải quyết xung đột bằng mã giả chuẩn xác (hashInsert, hashSearch), đi kèm phân tích cụ thể các hiện tượng kết cụm nguyên phát (primary clustering) và kết cụm thứ phát (secondary clustering).

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

Người học nên tự tính tay các ví dụ số học (như Modulo, Mid-square, Fold shift, Fold boundary, Pseudo-random), sau đó cài đặt hoàn chỉnh mã giả của thuật toán hashInsert và hashSearch trên C/C++ và chạy thử nghiệm đo số lần thăm dò (probe numbers).

5. Có tài liệu bổ trợ nào kèm theo không?

Tài liệu bao gồm 44 trang slide bài giảng chuẩn mực của học phần CO2003, hệ thống bài tập tính toán mẫu và kênh liên hệ học thuật trực tiếp với tác giả biên soạn (TS. Nguyễn Đức Dũng, Khoa Khoa học và Kỹ thuật Máy tính, Trường Đại học Bách Khoa – ĐHQG TP.HCM qua email nddung@hcmut.vn).

Kết luận

Chuyên đề Chapter 9 - Hash thuộc học phần Data Structure and Algorithms [CO2003] cung cấp hệ thống kiến thức toàn diện từ lý thuyết băm, các dạng hàm băm số học đến các chiến lược giải quyết xung đột không gian địa chỉ. Lộ trình học tập đề xuất bao gồm:

  1. Tiếp cận lý thuyết và phân tích chi phí tìm kiếm so với $O(n)$ và $O(\log_2 n)$.
  2. Nắm vững cơ chế và cách tính toán 7 dạng hàm băm cơ bản.
  3. Phân tích giải thuật và hiện thực hóa các phương pháp địa chỉ mở trên C/C++.
  4. Đo lường và đánh giá thực nghiệm độ phức tạp thuật toán.

Tài liệu là cơ sở học thuật trực tiếp phục vụ chương trình đào tạo kỹ sư công nghệ thông tin tại Trường Đại học Bách Khoa – ĐHQG TP.HCM.