Cài bảng băm bằng danh sách liên kết

#1

Trong lớp Cấu Trúc Dữ Liệu, thầy giảng Bảng Băm có nghĩa là lấy giá trị nhập vào chia cho size của mảng. Và lấy phần dư đó làm vị trí lưu giá trị đó. Vậy có nghĩa là Bảng băm chỉ sử dụng được trên mảng thôi ạ ?. Và khi học Thực Hành thì đề bài lại bảo cài Bảng Băm bằng Danh sách liên kết. Mà em nghĩ DSLK làm gì có size để chia lấy dư, cũng như k có vị trí cố định thì làm sao để làm ạ. Mọi người cho em xin hướng giải quyết với ạ

#2

Mảng là bắt buộc rồi, như vậy mới O(1) được. DSLK dùng để chứa các trường hợp đụng hash (collision).

3 Likes
#3

Em cũng nghĩ thế ạ. Em nghĩ là mỗi phần tử vẫn sẽ lưu vào mảng, khi nào trùng thì ngay vị trí đó cho thêm 1 danh sách liên kết. Nhưng k biết đúng không nên đăng lên hỏi ý mọi người

#4

Đúng vậy, đó là một cách giải quyết khi trùng hash :slight_smile:

4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?