
6/12/141 /XX MÔN: C U TRÚC D LI UẤ Ữ Ệ GV: NGUY N XUÂN VINHỄ
HASH TABLE
Nguy n Xuân Vinhễ
nguyenxuanvinh@hcmuaf.edu.
vn
C U TRÚC D LI UẤ Ữ Ệ
DATA STRUCTURES
[214331]

6/12/142 /XX MÔN: C U TRÚC D LI UẤ Ữ Ệ GV: NGUY N XUÂN VINHỄ
2
N i dung ộ
•Gi i thi uớ ệ
•Các v n đ c b n v i ArrayList, Linked Listấ ề ơ ả ớ
•B ng băm “hoàn h o”ả ả
•Hàm băm hoàn h oả
•Ph ng pháp xây d ng hàm bămươ ự
•u đi m c a b ng bămƯ ể ủ ả
•Các cách gi i quy t xung đ t (collision)ả ế ộ
•Các b ng băm ph bi n (đ c them)ả ổ ế ọ
•Java Map Interface
•Map implementations in Java
•HashMap example

6/12/143 /XX MÔN: C U TRÚC D LI UẤ Ữ Ệ GV: NGUY N XUÂN VINHỄ
3
Gi i thi uớ ệ
T t c các ấ ả
thao tác
ph i so ả
sánh khoá!!!
Kh c ắ
ph c?ụ

6/12/144 /XX MÔN: C U TRÚC D LI UẤ Ữ Ệ GV: NGUY N XUÂN VINHỄ
4
V n đ c b nấ ề ơ ả
•Bài toán: c n l u tr các m u tin và th c hi n các thao tácầ ư ữ ẫ ự ệ
–Thêm m u tinẫ
–Xoá m u tinẫ
–Tìm m u tin theo khóaẫ
•Tìm cách th c th c hi n m t cách hi u qu ?ứ ự ệ ộ ệ ả

6/12/145 /XX MÔN: C U TRÚC D LI UẤ Ữ Ệ GV: NGUY N XUÂN VINHỄ
5
V n đ c b nấ ề ơ ả
•Unsorted array
–S d ng m ng đ l u m u tin, không có th tử ụ ả ể ư ẫ ứ ự
–Thêm: thêm cu i nhanh O(1)ố
–Xoá: ch m do tìm r i xoá O(n)ậ ồ
–Tìm ki m: tu n t ch m O(n)ế ầ ự ậ