TIỂU LUẬN - Phân tích và thiết kế thuật toán (Bảng băm) | Cộng đồng Kỹ thuật cơ điện Việt Nam EBOOKBKMT

Tập hợp là một khái niệm cơ bản trong khoa học máy tính cũng như trong toán học. Về mặt toán học, các tập hợp là không thay đổi. Nhưng trong khoa học máy tính, dưới tác động của các thuật toán, các tập hợp thường xuyên thay đổi (các phần tử trong tập hợp có thể nhiều lên hoặc ít lại). Chúng ta gọi những tập hợp thường xuyên thay đổi là những tập hợp động (dynamic sets).
Các thuật toán có thể đòi hỏi rằng một số phép toán khác nhau phải được thực hiện trên tập hợp. Chẳng hạn, nhiều thuật toán chỉ cần các phép toán như: chèn một số phần tử vào tập hợp, xóa một số phần tử từ tập hợp, và kiểm tra xem phần tử nào đó có thuộc tập hợp. Một tập hợp động hỗ trợ những phép toán vừa nêu được gọi là một từ điển.

Nhiều ứng dụng yêu cầu một tập hợp động chỉ hỗ trợ các phép toán trên từ điển là INSERT (chèn), SEARCH (tìm kiếm), và DELETE (xóa). Chẳng hạn, một trình biên dịch của một ngôn ngữ máy sẽ duy trì một bảng ký hiệu, trong đó các khóa của các phần tử là những chuỗi ký tự tùy ý tương ứng với các định danh (identifiers) trong ngôn ngữ máy.
Có một số cấu trúc dữ liệu được sử dụng để biểu diễn (implement) các tập hợp động. Và trong số đó, bảng băm (hash table) là một cấu trúc dữ liệu tốt dùng cho các từ điển. Mặc dù thao tác tìm kiếm một phần tử trong một bảng băm có thể có độ phức tạp tương đương với việc tìm kiếm trên một danh sách liên kết (độ phức tạp O(n) trong trường hợp xấu nhất), nhưng với những giả thiết hợp lý, thời gian tìm kiếm một phần tử trong một bảng băm là O(1).
Bảng băm là sự tổng quát hóa từ khái niệm đơn giản của một mảng thông thường. Việc định địa chỉ trực tiếp vào một mảng thông thường sẽ rất hiệu quả khi chúng ta tiến hành kiểm tra một vị trí bất kỳ trong mảng với thời gian O(1). Phần 2.1 sẽ trình bày chi tiết hơn về kỹ thuật định địa chỉ trực tiếp. Việc định địa chỉ trực tiếp vào một mảng sẽ thích hợp khi chúng ta có khả năng xác định rõ mảng đó có một vị trí tương ứng với mọi khóa có thể (possible key).
Khi số lượng khóa thực tế được lưu trữ là nhỏ hơn so với tổng số khóa có thể, bảng băm trở thành một lựa chọn thay thế hiệu quả cho phương án định địa chỉ trực tiếp vào một mảng, bởi vì bảng băm thường sử dụng một mảng có kích thước cân xứng với số khóa thực tế được lưu trữ. Phần 2.2 sẽ trình bày chi tiết về bảng băm, trong đó tập trung vào kỹ thuật dây chuyền (chaining), kỹ thuật đơn giản nhất dùng để giải quyết các xung đột. Phần 2.3 giải thích cách tính chỉ số mảng từ các khóa bằng cách dùng các hàm băm. Trong Phần 2.4, chúng ta sẽ khảo sát chi tiết một kỹ thuật giải quyết xung đột khác mang tên định địa chỉ mở (open addressing). Phần cuối cùng trình bày về kỹ thuật băm hoàn hảo (perfect hashing), cho phép chúng ta thực hiện phép toán SEARCH với độ phức tạp O(1) trong trường hợp xấu nhất, khi tập hợp các khóa được lưu trữ ở trạng thái tĩnh (không thay đổi).
Nội dung của tiểu luận được dịch từ Chương 11 - Hash Tables trong cuốn sách Introduction to Algorithms, một công trình lớn của các tác giả Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest và Clifford Stein. Tuy nhiên, vì giới hạn về mặt thời gian cũng như hạn chế về kỹ năng dịch, nên tiểu luận chắc chắn sẽ không tránh khỏi những thiếu sót. Rất mong ý kiến đóng góp của Thầy và các bạn để chúng tôi hoàn thiện tiểu luận.
Xin chân thành cảm ơn TS. Hoàng Quang đã giúp đỡ chúng tôi hoàn thành tiểu luận này.

NỘI DUNG:

1. Mở đầu 3
2. Nội dung 5
2.1. Các bảng địa chỉ trực tiếp (direct-address tables) 5
2.2. Bảng băm (hash tables) 6
2.2.1. Giải quyết xung đột bằng kỹ thuật dây chuyền 7
2.2.2. Phân tích kỹ thuật băm bằng dây chuyền 8
2.3. Hàm băm (hash functions) 10
2.3.1. Phương pháp chia 11
2.3.2. Phương pháp nhân 12
2.3.3. Kỹ thuật phổ băm 12
2.4. Định địa chỉ mở (open addressing) 16
2.4.1. Phương pháp thăm dò tuyến tính 18
2.4.2. Phương pháp thăm dò bậc hai 18
2.4.3. Kỹ thuật băm đôi 19
2.4.4. Phân tích kỹ thuật băm địa chỉ mở 20
2.5. Kỹ thuật băm hoàn hảo (perfect hashing) 23
3. Kết luận 28

LINK DOWNLOAD