Giảng viên: TS. Ngo Huu Phuc
Tel: 0438 326 077
Mob: 098 5696 580
Email: ngohuuphuc76@gmail.com
Cấu trúc dữ liệu và giải thuật
Bài 22: Hàm băm
1@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
Bài 22: Hàm băm
Nội dung:
22.1. Bài toán.
22.2. Hàm băm.
22.3. Giải quyết xung đột.
22.4. Một số ví dụ sử dụng hàm băm.
2@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
22.1. Bài toán (1/9)
Giả sử cần lưu trữ một số bản ghi và thực hiện các thao tác:
Thêm: thêm một bản ghi
Xóa: xóa một bản ghi
Tìm kiếm: tìm kiếm một bản ghi
Hãy đưa ra cách tổ chức để thực hiện hiệu quả các công việc
trên.
3@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
22.1. Bài toán (2/9) – Sử dụng mảng
Sử dụng mảng không được sắp xếp
Thêm: thêm vào cuối mảng->O(1)
Xóa: mất nhiều thời gian tìm vị trí cần xóa và dồn mảng->O(n)
Tìm kiếm: tìm kiếm tuần tự->O(n)
Sử dụng mảng được sắp xếp
Thêm: phải tìm vị trí thêm vào->O(n)
Xóa: mất nhiều thời gian tìm vị trí cần xóa và dồn mảng->O(n)
Tìm kiếm: tìm kiếm nhị phân->O(log(n))
4@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
22.1. Bài toán (3/9) – Sử dụng DSLK
Thêm: thêm vào vị trí bất kỳ nhanh->O(1)
Xóa: nhanh trong tổ chức các nút, nhưng chậm trong tìm kiếm
nút cần khóa->O(n)
Tìm kiếm: tìm kiếm tuần tự->O(n)
5@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University