tailieunhanh - Bài giảng Cơ sở dữ liệu giải thuật: Bài 9 - Bảng băm

Bài giảng Cơ sở dữ liệu giải thuật: Bài 9 - Bảng băm do giảng viên Hoàng Thị Điệp biên soạn cung cấp cho các bạn những kiến thức về phương pháp băm, các hàm băm - Hash function, các chiến lược giải quyết va chạm - Collision resolution. | Bài 9: B ng băm Gi ng viên: Hoàng Th i p Khoa Công ngh Thông tin – i h c Công Ngh M c tiêu bài h c • Phương pháp băm • Các hàm băm – Hash function • Các chi n lư c gi i quy t va ch m – Collision resolution diepht@vnu 2 T p • KDLTT t p – – – – – – – ng và T i n ng find insert remove/erase max min next previous • KDLTT t diepht@vnu i n 3 KDLTT t • Trư ng h p riêng c a t p ng khi ta ch quan tâm t i tìm ki m, xen, lo i – Là t p h p trong ó m i ph n t là m t c p (khóa, i tư ng) – Có th tìm ki m theo khóa – Có th ư c s p ho c không ư cs p • Các ph n t có th có cùng khóa • ng d ng – Ánh x t v ng – nghĩa – Ánh x tên mi n – a ch IP diepht@vnu i n • Các phép toán – find(k) tr v ph n t có khóa k. N u không t n t i ph n t như v y thì tr v NULL. – findAll(k) tr v danh sách các ph n t có khóa k. – insert(k, o) thêm ph n t (k, o) và tr v ph n t này – remove(e) lo i b ph n t e – entries() tr v danh sách t t c các ph n t – size() tr v s lư ng ph n t – isEmpty() ki m tra xem t i n r ng hay không 4 Cài KDLTT t i n b ng các CTDL ã h c • M ng ư c s p / không ư c s p • DSLK ơn/kép ư c s p / không ư c s p • Cây tìm ki m nh .