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

Băm (hashing), bảng băm (hash table), bảng scatter 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ộ. Cộng thêm 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 < |K| Một hàm ánh xạ tập các giá trị trong container thành các chỉ số trong mảng kích thước M → hàm băm Hàm băm có thể là ánh xạ n – 1:  xy mà h(x)=h(y) → xung đột → vđề cần giải quyết Một hàm băm tốt: Tránh được xung đột Hướng phân bố đều các khóa dễ tính toán Tránh xung đột Lý tưởng: tập các khóa phân biệt,tập các giá trị băm kô có giá trị nào giống nhau Thực tế, trừ khi ta biết trước về dữ liệu, còn thì kô thể đảm bảo kô có xung đột Ví dụ: số telephone: mã vùng Các giá trị khóa phân bố đều : xác suất Hàm băm phân bố đều thỏa mãn Tuy nhiên để xác định sự phân bố của các gtrị băm cần phải biết trước sự phân bố của khóa In the absence of any information to the contrary, we assume that the keys are equiprobable. Let be the set of keys that map to the value i. I.e., . If this is the case, the requirement to spread the keys uniformly implies that . An equal number of keys should map into each array position. dễ tính toán Kô phải dễ dàng xác định hàm băm Kô phải dễ viết tt tính hàm → thời gian để thực hiện hàm băm là O(1) Các pp băm Quy ước: tập khóa là các số nguyên, các giá trị hàm băm rơi vào 0..M-1. Pp chia Pp bình phương PP nhân PP chia v