Bài giảng Cấu trúc dữ liệu: Chương 4 Bảng băm, cung cấp cho người học những kiến thức như: Khái niệm bảng băm; Hàm băm; Một vài loại hàm băm; Sự đụng độ (Collision); Các phương pháp xử lý đụng độ; Phương pháp nối kết trực tiếp; .Mời các bạn cùng tham khảo! | 11 07 2020 11 07 2020 1 1 Hàm băm Các phương pháp giải quyết đụng độ 11 07 2020 2 2 1 11 07 2020 Đặt vấn đề Phương pháp tìm kiếm trong các chương trước chủ yếu dựa vào khóa Mảng Danh sách liên kết Cây nhị phân tìm kiếm Tìm kiếm bằng cách so sánh lần lượt các phần tử Thời gian tìm kiếm không nhanh và phụ thuộc N số phần tử 11 07 2020 3 3 Khái niệm bảng băm Bảng băm hash table là một cấu trúc dữ liệu lưu trữ các khóa trong bảng T danh sách đặc sử dụng một hàm băm hash function để ánh xạ khoá key với một địa chỉ lưu trữ 11 07 2020 4 4 2 11 07 2020 Hàm băm Hàm băm hash function là hàm biến đổi khóa k thành địa chỉ trong bảng băm Phép biến đổi khóa là một ánh xạ khoá thành địa chỉ ℎ 0 1 1 ℎ Trong đó U là tập các khóa 0 1 m 1 là tập các địa chỉ trên bảng băm Giá trị h k gọi là hash code hoặc địa chỉ 11 07 2020 5 5 Hàm băm 11 07 2020 6 6 3 11 07 2020 Một vài loại hàm băm Chia modulo ℎ Với Tsize tốt nhất nên là số nguyên tố Sinh viên có thể tham khảo thêm các hàm băm Folding gấp số Mid-Square Function 11 07 2020 7 7 Sự đụng độ Collision Sự đụng độ hay xung đột địa chỉ Một cách lý tưởng hàm băm sẽ ánh xạ mỗi khoá vào một slot riêng biệt của bảng T Tuy nhiên điều này trong thực tế khó đạt được vì m 11 07 2020 Sự đụng độ Đụng độ là ℎ ℎ 11 07 2020 9 9 Các phương pháp xử lý đụng độ Phương pháp nối kết separate chaining Phương pháp nối kết trực tiếp Phương pháp nối kết hợp nhất Phương pháp địa chỉ mở open addressing SV tham khảo tài liệu 2 3 11 07 2020 10 10 5 11 07 2020 Phương pháp nối kết trực tiếp Khai báo define M 101 Lưu ý chọn giá trị M phù hợp để quản lý một bảng băm có tổng số phần tử struct Node là n int key M phải là số nguyên tố Node next M tương đương hoặc nhỏ hơn giá trị n 10 Mảng danh sách đặc heads M khi Node heads M khai báo có khả năng đủ vùng nhớ Node z để cấp phát 11 07 2020 12 12 Phương pháp nối kết trực tiếp Khởi tạo void init z new Node z- gt next z for int i 0 i lt M i heads i z 11 07 2020 13 13 6 11 07 2020 Phương pháp nối kết trực tiếp Thêm một phần tử
