tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Bảng băm - Nguyễn Văn Toàn (ĐH Công nghệ Thông tin8
Bài giảng "Cấu trúc dữ liệu và giải thuật: Bảng băm" cung cấp cho người học các kiến thức: Dẫn nhập, cách lựa chọn hàm băm, ví dụ về hàm băm không hiệu quả, cài đặt, giải pháp sử dụng hàm băm. nội dung chi tiết. | Bảng băm Hash table Giáo viên Nguyễn Văn Toàn 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 1 Dan nhập Một số nhận xét khi tìm kiếm trên mảng I Nếu mảng chưa được sắp thứ tự tìm tuyển tính thời I gian sẽ là O n Nếu không tìm thấy chúng ta phải duyệt n phần tử Nếu tìm thấy trung bình sẽ duyệt n 2 phần tử Nếu mảng được sắp xếp tìm nhị phân Thời gian tìm kiếm O log n t í t Nếu tìm được hay không thì thời gian tìm kiếm gần như nhau Có phương án nào hay hơn Có phương pháp nào sẽ cho thời gian tìm kiếm là O 1 Câu trả lời là có nếu chúng ta tổ chức lại mảng theo cơ chế khác. 9-Apr-06 Nguyễn Văn Toàn - CTDL 2 2 Băm Hashing Giả sử chúng ta có một hàm đặc biệt magic function hàm có tham số là giá trị cần tìm x trả về một vị trí trên mảng i f x i a i x Tìm thấy a i x Không tìm thấy Các hàm băm thông dụng . .. .. Chia lấy dư. Ví dụ f x x 100 Dãy số tuần tự. Ví dụ f 123456789 258 9-Apr-06 Nguyễn Văn Toàn - CTDL 2
đang nạp các trang xem trước