6/12/141 /XX N: C U TC 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 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 ngm bămươ
u đi m c a b ng bămƯ
Cácch 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 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 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 m u tin th c hi n các thaoc ư
Thêm m u tin
X m u tin
Tìm m u tin theo khóa
Tìmch th c th c hi n m t cách hi u qu ?
6/12/145 /XX 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, kng th t ư
Thêm: thêm cu i nhanh O(1)
X: ch m do tìm r i xoá O(n)
Tìm ki m: tu n t ch m O(n)ế