tailieunhanh - Bài giảng Phân tích thiết kế và giải thuật - Chương 4: Bảng băm

Bài giảng "Phân tích thiết kế và giải thuật - Chương 4: Bảng băm" cung cấp cho người học các kiến thức: Giới thiệu bài toán, hàm băm, các phương pháp xử lý đụng độ. | Bài giảng Phân tích thiết kế và giải thuật - Chương 4 Bảng băm BẢNG BĂM 1 Nội dung Giới thiệu bài toán Hàm băm Các phương pháp xử lý đụng độ 2 ĐẶT VẤN ĐỀ Cho S là tập hợp n phần tử trong 1 cấu trúc dữ liệu được đặc trưng bởi 1 giá trị khóa Tìm 1 phần tử có hay không trong S Tìm tuyến tính O n chưa được sắp xếp Tìm nhị phân O log2n đã được sắp xếp Có hay chăng 1 thuật toán tìm kiếm với O 1 Có song ta phải tổ chức lại dữ liệu Dữ liệu được tổ chức lại là Bảng băm 3 Giới thiệu về Bảng Băm Là CTDL trong đó các phần tử của nó được lưu trữ sao cho việc tìm kiếm sẽ được thực hiện bằng cách truy xuất trực tiếp thông qua từ khóa. Bảng băm có M vị trí được đánh chỉ mục từ 0 đến M-1 M là kích thước của bảng băm. Các phương pháp băm PP kết nối trực tiếp PP kết nối hợp nhất PP dò tuyến tính PP dò bậc 2 PP băm kép 4 Hàm băm Hash functions Hàm băm biến đổi khóa thành chỉ mục trên bảng băm Khóa có thể là dạng số hay dạng chuỗi Chỉ mục được tính từ với M là số chỉ mục của bảng băm Hàm băm thường dùng key M với M là độ lớn của bảng băm Hàm băm tốt phải thoả yêu cầu Giảm thiểu xung đột Phân bố đều trên M địa chỉ khác nhau của bảng băm 5 Mô tả dữ liệu K tập các khoá set of keys M tập các địa chỉ set of addresses . HF k hàm băm dùng để ánh xạ một khoá k từ tập các khoá K thành một địa chỉ tương ứng trong tập M. Thông thường HF k k mod M 6 Ưu điểm bảng băm Dung hòa tốt giữa thời gian truy xuất và dung lượng bộ nhớ Nếu không giới hạn bộ nhớ one-to-one truy xuất tức thì Nếu dung lượng bộ nhớ có giới hạn thì tổ chức một số khóa có cùng địa chỉ lúc này thời gian truy xuất có bị suy giảm đôi chút. Bảng băm ứng dụng nhiều trong thực tế thích hợp tổ chức dữ liệu có kích thước lớn và lưu trữ ngoài 7 Cách xây dựng bảng băm Dùng hàm băm để ánh xạ khóa K vào 1 vị trí trong bảng băm. Vị trí này như là 1 địa chỉ khi tìm kiếm. Bảng băm thường là mảng danh sách liên kết file danh sách đặc 8 Ví dụ một bảng băm đơn giản Khóa k sẽ được lưu trữ tại vị trí k mod M M kích thước mảng Ví dụ Thêm phần .