Bài giảng Thiết kế và đánh giá thuật toán: Bảng băm - TS. Lê Nguyên Khôi

Thiết Kế & Đánh Giá Thuật Toán<br /> Bảng Băm<br /> TS. Lê Nguyên Khôi<br /> Trường Đại Học Công Nghệ - ĐHQGHN<br /> <br /> Nội Dung<br /> Phương pháp băm<br />
Hàm băm<br />
Giải quyết va chạm<br />
<br /> <br /> 1<br /> <br /> Bài Toán Từ Điển<br /> Dùng tập động cài đặt từ điển<br />
Mỗi phần tử là cặp (khóa, dữ liệu)<br />
<br /> <br /> Có thể tìm theo khóa<br />
Được sắp xếp hoặc không<br />
<br /> <br />
<br /> <br /> Chỉ quan tâm tới<br /> Tìm kiếm SEARCH (, )<br />
Chèn INSERT (, )<br />
Xóa DELETE (, )<br />
<br /> <br />
<br /> <br /> Tổ chức cấu trúc dữ liệu  như thế nào?<br /> 2<br /> <br /> Bài Toán Từ Điển<br />
<br /> <br />
<br /> <br /> Nếu khóa của dữ liệu là số nguyên không âm<br /> trong khoảng 0 … − 1 , phân biệt<br />
Có thể sử dụng mảng cỡ <br />
Dữ liệu khóa  lưu tại  <br />
Tìm kiếm, chèn, xóa trong thời gian (1)<br /> Thực tế không khả thi<br />
Số phần tử dữ liệu có thể rất nhỏ so với <br /> 64-bit thể hiện 2 (18 × 10 ) khóa khác nhau<br />
Xâu ký tự thậm chí còn lớn hơn<br />
số<br /> <br /> Khóa có thể không phải số nguyên<br /> Tận dụng phép truy cập trực tiếp của mảng<br />
<br /> <br />
<br /> <br /> 3<br /> <br /> Phương Pháp Băm<br />
<br />
<br /> <br /> Lưu dữ liệu trong mảng  0 …  − 1<br /> Hàm băm ℎ: ánh xạ mỗi giá trị khóa  của dữ<br /> liệu tới một chỉ số  (0 ≤  < )<br />
<br />
<br /> <br /> Dữ liệu sẽ được lưu trong []<br /> ℎ:  → {0, 1, … ,  − 1}<br /> 0<br /> 1<br /> <br /> Tính<br /> địa chỉ<br /> Hàm băm ℎ<br /> <br /> …<br /> i<br /> <br /> …<br /> −1<br /> <br /> Tập các giá trị khoá<br /> Mảng <br /> <br /> 4<br /> <br />