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

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