Báo Cáo Giải quyết đụng độ trong phép biến đổi khoá băm bằng phương pháp địa chỉ mở

MỤC LỤC

[TABLE="class: cms_table"]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]Trang[/TD]
[/TR]
[TR]
[TD][/TD]
[TD]Mục lục[/TD]
[TD][/TD]
[TD]2[/TD]
[/TR]
[TR]
[TD][/TD]
[TD]Đặt vấn đề[/TD]
[TD][/TD]
[TD]3[/TD]
[/TR]
[TR]
[TD]Phần 1[/TD]
[TD]Giải quyết đụng độ trong phép biến đổi khoá băm
bằng phương pháp địa chỉ mở[/TD]
[TD][/TD]
[TD]5[/TD]
[/TR]
[TR]
[TD]1.1.[/TD]
[TD]Mô tả chung[/TD]
[TD][/TD]
[TD]5[/TD]
[/TR]
[TR]
[TD]1.2.[/TD]
[TD]Phương pháp thăm dò tuyến tính (Linear Probing)[/TD]
[TD][/TD]
[TD]6[/TD]
[/TR]
[TR]
[TD]1.3.[/TD]
[TD]Phương pháp thăm dò bậc hai (Quadrratic Probing)[/TD]
[TD][/TD]
[TD]10[/TD]
[/TR]
[TR]
[TD]1.4.[/TD]
[TD]Phương pháp thăm dò kép (Double Hashing)[/TD]
[TD][/TD]
[TD]13[/TD]
[/TR]
[TR]
[TD]Phần 2[/TD]
[TD]Phân tích phép biến đổi khoá
bằng phương pháp địa chỉ mở[/TD]
[TD][/TD]
[TD]16[/TD]
[/TR]
[TR]
[TD]3.1.[/TD]
[TD]Phân tích phép biến đổi khoá[/TD]
[TD][/TD]
[TD]16[/TD]
[/TR]
[TR]
[TD]3.2.[/TD]
[TD]Một số lưu ý khi sử dụng phương pháp thử[/TD]
[TD][/TD]
[TD]18[/TD]
[/TR]
[TR]
[TD]Phần 3[/TD]
[TD]Chương trình minh hoạ[/TD]
[TD][/TD]
[TD]19[/TD]
[/TR]
[TR]
[TD][/TD]
[TD]Tài liệu tham khảo[/TD]
[TD][/TD]
[TD]23[/TD]
[/TR]
[/TABLE]


BÀI TẬP
Môn học: Phân tích và thiết kế thuật toán
Người thực hiện: PHẠM HỒNG SƠN
Lớp: CH CNTT K17 - Học viện KTQS

GIẢI QUYẾT ĐỤNG ĐỘ TRONG PHÉP BIẾN ĐỔI KHOÁ BẰNG PHƯƠNG PHÁP ĐỊA CHỈ MỞ


ĐẶT VẤN ĐỀ

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.
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 lại chỉ cho bảng dữ liệu.
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 từ điển như INSERT, SEARCH, DELETE. Các phép toán này 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 trong trường hợp tối ưu 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.
Thông thường bảng băm được sử dụng khi cần xử lý các bài toán có dữ liệu lớn và được lưu trữ ở bộ nhớ ngoài.