Báo Cáo Phân tích và thiết kế thuật toán

MỤC LỤC

Trang

I. MỞ ĐẦU 3
II. CÁC KHÁI NIỆM CHÍNH 3
1. Hàm băm (Hash Function) 3
2. Hàm Băm sử dụng Phương pháp chia. 4
3. Hàm Băm sử dụng Phương pháp nhân. 4
4. Phép băm phổ quát (universal hashing) 5
II. BẢNG BĂM (Hash Table - Direct-address table) 5
1. Mô tả dữ liệu. 5
2. Các phép toán trên bảng băm 5
3. Các Bảng băm thông dụng. 6
4. Ưu điểm của các Bảng băm: 6
III. BẢNG BĂM BẰNG PHƯƠNG PHÁP KẾT NỐI TRỰC TIẾP (Direct chaining Method) 7
1. Khai báo cấu trúc bảng băm 9
2. Các phép toán. 9
3. Màn hình chương trình phần mềm mô phỏng. 15
3. Nhận xét bảng băm dùng phương pháp kết nối trực tiếp. 16
IV. TÀI LIỆU THAM KHẢO 17

I. MỞ ĐẦU
Phép băm (key transformation) – hay còn gọi là phép biến đổi khoá là một phương pháp tham khảo trực tiếp các phần tử trong một bảng thông qua việc biến đổi số học trên những khoá (key) để có được địa chỉ tương ứng của những phần tử ở trong bảng. Tổng quát hơn, phép băm là một ánh xạ thích hợp H từ tập khoá K vào tập địa chỉ A:
H: K -------> A
Trong phép băm, thông thường tập các khoá lớn hơn rất nhiều so với tập các địa chỉ bộ nhớ (chỉ số của mảng). Như vậy hàm H là một hàm nhiều – một (Many – to – one function).
Phép băm được đề xuất và hiện thực trên máy tính từ những năm 50 của thế kỷ 20. Nó dựa trên ý tưởng: biến đổi giá trị khóa thành một số (xử lý băm) và sử dụng số này để đánh chỉ số cho bảng dữ liệu.
Các phép toán trên các cấu trúc dữ liệu như danh sách, cây nhị phân, phần lớn được thực hiện bằng cách so sánh các phần tử của cấu trúc, do vậy thời gian truy xuất không nhanh và phụ thuộc vào kích thước của cấu trúc. Vì vậy chúng ta cần phải nghiên cứu một cấu trúc mới được gọi là bảng băm (hash table). Các phép toán trên bảng băm sẽ giúp hạn chế số lần so sánh, và vì vậy sẽ cố gắng giảm thiểu được thời gian truy xuất. Độ phức tạp của các phép toán trên bảng băm thường có bậc là O(1) và không phụ thuộc vào kích thước của bảng băm