PHÉP BIẾN ĐỔI KHÓA – HÀM BĂM part 1

PHÉP BIẾN ĐỔI KHÓA – HÀM BĂMBăm là phương pháp rất thích hợp để cài đặt tập hợp có số phần tử lớn và thời gian cần thiết để thực hiện các phép toán từ điển, ngay cả trong trường hợp xấu nhất, là tỉ lệ với cỡ của tập hợp. Chúng ta sẽ đề cập tới hai phương pháp băm khác nhau. Một gọi là băm mở cho phép sử dụng một không gian không hạn chế để lưu giữ các phần tử của tập hợp. ...
Nội dung trích xuất từ tài liệu:
PHÉP BIẾN ĐỔI KHÓA – HÀM BĂM part 1 PHÉP BIẾN ĐỔI KHÓA – HÀM BĂMBăm là phương pháp rất thích hợp để cài đặt tập hợp có số phần tử lớn và thờigian cần thiết để thực hiện các phép toán từ điển, ngay cả trong trường hợp xấunhất, là tỉ lệ với cỡ của tập hợp.Chúng ta sẽ đề cập tới hai phương pháp băm khác nhau. Một gọi là băm mở chophép sử dụng một không gian không hạn chế để lưu giữ các phần tử của tập hợp.Phương pháp băm khác được gọi là băm đóng sử dụng một không gian cố định dođó tập hợp được cài đặt phải có cỡ vượt qua không gian cho phép$1. Khái niệm băm và hàm băm.1.1. Băm mở và hàm băm.a. Băm mở. Nội dung cơ bản của băm mở là phân chia tập hợp đã cho thành mộtsố cố định các lớp. Chẳng hạn ta muốn phân thành N lớp được đánh số 0,1,..,N-1.Ta sử dụng mảng T với chỉ số chạy từ 0 đến N-1. Mối thành phần T[i] cúa mảngđược nói đến như một rổ đựng các phần tử của tập hợp thuộc lớp thứ i. Các phầntử của tập hợp thuộc mỗi lớp tổ chức dưới dạng một danh sách liên kết. Do T[i] sẽchứa con trỏ trỏ đến danh sách của lớp i.b. Bảng băm. Ta gọi mảng T mà mỗi phần tử của nó như là một rổ đựng các phầntử của tập hợp thuộc lớp tương ứng là bảng băm.Việc phân chia các phần tử của tập hợp vào các lớp được thực hiện bởi hàm bămh.c. Hàm băm. Nếu x là một giá trị khoá của phần tử nào đó của tập hợp thì h(x) làchỉ số nào đó của mảng T và ta gọi h(x) là giá trị băm (hash value) của x. Như vậy hlà ánh xạ từ tập hợp các khoá K vào tập hợp { 0,1,…,N-1}.$.2. Các phương pháp lựa chọn, thiết kế hàm băm và giải quyết va chạm.2.1. Các phương pháp lựa chọn, thiết kế hàm bămCó hai tiêu chuẩn chính để lựa chọn hàm băm. Trước hết nó phải cho phép tínhđược dễ dàng và nhanh chóng giá trị băm của mỗi khoá. Thứ hai, nó phải phân bốđều các khóa vào các rổ. Trên thực tế tiêu chuẩn thứ hai rất khó được thực hiện.Sau đây chúng ta đưa ra một số phương pháp thiết kế hàm băm.a. Phương pháp cắt bỏ.Giả sử khoá là số nguyên (nếu khoá không phải là số nguyên, ta xét đến các mã sốcủa chúng). Ta sẽ bỏ đi một phần nào đó của khóa, và lấy phần còn lại lám giá trịbăm của khoá. Chẳng hạn nếu khoá là các số nguyên gồm 10 chữ số và bảng bămgồm 1000 thành phần, khi đó ta có thể lấy chữ số thứ nhất, thứ ba và thứ bảy từbên trái làm giá trị băm. Ví dụ: h(7103592810) = 720.Phương pháp cắt bỏ rất đơn giản nhưng nó thường không phân bố đều các khoá.b. Phương pháp gấp.Giả sử khoá là số nguyên. Ta phân chia khóa thành một số phần, sau đó kết hợpcác phần lại bằng một cách nào đó (phép cộng hoặc phép nhân) để nhận giá trịbăm. Nếu khoá là số nguyên 10 chữ số ta phân thành các nhóm ba ba hai hai chữsố từ bên trái, cộng các nhóm với nhau sau đó cắt cụt nếu cần thiết, ta sẽ nhậnđược giá trị của hàm băm. Ví dụ: số 7103592810 được biến đổi thành710+359+28+10 = 1107, do đó ta có giá trị băm là 107.Vì mọi thông tin trong khoá đều được phản ánh vào giá trị băm, nên phương pháp gấpcho phân bố đều các khoá hơn phương pháp cắt bỏ.c. Phương pháp sử dụng phép toán lấy dư.Giả sử khoá là số nguyên và ta muốn chia tập hợp các khoá thành n lớp. Chia sốnguyên cho n rồi lấy phần dư làm giá trị băm. Điều này trong Pascal được thựchiện bằng phép toán mod. Tính phân bố đều các khoá của hàm băm được xác địnhbằng phương pháp này phụ thuộc nhiều vào việc chọn n. Tốt nhất chọn n là sốnguyên tố. Chẳng hạn thay cho việc chọn n = 1000 ta sẽ chọn n = 997 hoặc n =1009.Ví dụ viết một hàm băm trong Pascal để băm các khoá là các xâu kí tự có độ dài 10thành các giá trị từ 0…n-1.Type keytype = string[10];Function h(x: keytype):0..n-1; Var i, sum:integer ; Begin Sum:=0; For i=1 to 10 do Sum=sum + ord(x[i]); h:= sum mod n; end.Trong hàm băm trên, ta đã chuyển đổi các xâu kí tự thánh các số nguyên bằngcách lấy tổng số của các mã số của từng kí tự trong xâu dùng hàm ord(c) để lấy mãsố của kí tự c. 0 1 22.2. Bảng băm đóng.Trong bảng băm mở, mỗi thành phần T[i] của bảng lưu trữ con trỏ trỏ tới danh sáchcác phần tử của tập hợp được đưa vào lớp thứ i (i = 0,…,N-1).a. Băm đóng. Khác với bảng băm mở, trong bảng băm đóng, mỗi phần tử của tậplưu giữ trong chính các thành phần T[i] của mảng. Do đó ta có thể khai báo kiểu dữliêụ từ điển được cài đặt bởi bảng băm đóng như sau: Type Dictionary = array [0..N-1] of keytype; Keytype là kiểu dữ liệu của khoá của các phần tử trong từ điển.2.3. Phân tích, đánh giá và minh họa phương pháp băm.a. Phân tich đánh giá. Trong tất cả những thuật toán được xét từ trước tới nay, việcđịnh vị một mục được xác định bởi một dãy các so sánh. Trong mỗi trường hợp,mục cần tìm được so sánh nhiều lần với các mục ở những vị trí nào đó trong cấutrúc. Đối với nhóm n mục, phép tìm kiếm tuyến tính đòi hỏi O(n) lần so sánh, trongkhi đó phép tìm kiếm nhị phân chỉ cần O(log n) lần so sánh. Trong một số trườnghợp, những thuật toàn này thực hiện còn quá chậm. Ví dụ, bả ...