Bài giảng Băm (hashing), bảng băm (hash table)

Băm (hashing), bảng băm (hash table) Introduction Mục tiêu của bài học này là xây dựng một cấu trúc dữ liệu để dễ dàng thực hiện thao tác thêm mới và tìm kiếm. Một số tiêu chí sẽ phải nhượng bộ. không cần các phần tử phải được sắp xếp theo thứ tự nào đó. Lý tưởng: O(1) nhưng phải biết trước về dl → độ phức tạp TB O(1) – kô đảm bảo trong trường hợp xấu nhất Nếu xét các cấu trúc đã học: → Mảng hợp lý hơn: thêm phần tử O(1), tìm kiếm O(n) Tuy nhiên vấn đề tìm kiếm vẫn cần được cải tiến kể cả khi mảng đã được sắp (O(logn) – thao tác thêm mới sẽ là O(n)) Ví dụ: Để insert(x) → lưu ở vị trí h(x)-1 của mảng. Tương tự để tìm x → kiểm tra vị trí h(x)-1. Nếu thời gian ước lượng hàm h là hằng số thì cả 2 thao tác insert và find đều là O(1). để xác định được h như thế nghĩa là phải có hiểu biết trước về tập. Khóa và hàm băm Thiết kế container lưu dãy mục dữ liệu của tập K → tập khóa K (dùng mảng) vị trí của khóa trong mảng được xác định bởi 1 hàm → hàm băm Tổng quát: kích thước của |K| lớn thậm chí vô hạn Ví dụ: tập khóa là số nguyên 32 bits hoặc có thể là xâu ký tự có độ dài bất kỳ Mong muốn: kích thước container 1 → h(x) chỉ lấy k bits cuối của dãy nhị phân bd x → kô tốt vì nó kô hoàn toàn phụ thuộc vào x Nên lấy M là nguyên tố Nhược điểm: các khóa liên tiếp ánh xạ thành các giá trị liên tiếp nhau → về mặt kô gian là kô tốt PP bình phương (middle square method) Tránh việc chia W=2w, w là độ dài từ máy M= 2k k  1 ~ Lấy k bits từ giữa của giá trị bình phương của khóa Các khóa liên tiếp sẽ được rải đều chỉ phụ thuộc vào một số bits ở giữa của x2 → có một số lớn gần 0 → xung đột PP nhân (multiplication method) Thay bằng một hằng số Chọn a tránh trường hợp xung đột gần 0 Nếu lấy a nguyên tố cùng nhau với W axa’ = aa’x=1x Fibonacci Golden ratio: Liên quan đến số fibonacci 2. Giải quyết xung đột Bảng băm Pp địa chỉ mở (open - addressing) Pp móc nối dây chuyền (separate chaining) Pp địa chỉ mở Đơn giản nhất là thử tuyến tính Xem xét vị trí bên cạnh vị trí đã bận, nếu trống thì đưa bản ghi mới vào Nếu có rồi → cuối bảng → quay về đầu → tìm thấy chỗ trống → overflow 21, 43, 12, 26, 95, 8, 69 0, 1, 5, 5, 4, 1, 6 Nhược điểm: tụ hội (clustering) các khóa chung quanh khóa kô đụng độ PP thử ngẫu nhiên (random probing) hi = (H + G(i)) mod m G(i) hàm ngẫu nhiên giá trị lần lượt là các số nguyên khác nhau trong [1, m-1] Thường lấy g(i)= i2 → thử cầu phương (quadratic probing) Ưu điểm: tránh được hiện tượng tụ hội Nhược điểm: kô cho xét quá m/2 vị trí khác nhau do i2 = (m-i)2 → tưởng over nhưng kô phải. PP móc nối dây chuyền