Bài tập bảng băm phương pháp nối kết trực tiếp năm 2024
[toc] ## Khái niệm - Bảng băm là một CTDL thường được sử dụng như một từ điển: mỗi phần tử trong bảng băm là một cặp Show
Uploaded byvincevo 0% found this document useful (0 votes) 308 views 22 pages Copyright© Attribution Non-Commercial (BY-NC) Available FormatsPDF, TXT or read online from Scribd Share this documentDid you find this document useful?Is this content inappropriate?0% found this document useful (0 votes) 308 views22 pages Bang Bam - Hash TableUploaded byvincevo Jump to Page You are on page 1of 22 Search inside document Reward Your CuriosityEverything you want to read. Anytime. Anywhere. Any device. No Commitment. Cancel anytime. Bảng băm hay HashTable là một cấu trúc mà khi người dùng thực hiện truy xuất một phần tử qua khóa thì nó sẽ được ánh xạ vào thông qua hàm băm (Hash function). Quá trình ánh xạ khóa vào bảng băm được thực hiện thông qua hàm băm (Hashing). Một bảng băm tốt cần phải có hàm băm tốt. Bảng băm là một mảng có M vị trí được đánh số từ 0 đến M – 1. Có rất nhiều cách cài đặt kết nối của bảng băm như trực tiếp, dò tuyến tính, dò bậc hai, băm kép… Trong bài viết này mình sẽ giới thiệu đến các bạn phương pháp kết nối dò trực tiếp. Nhưng trước tiên, ta cần tìm hiểu hàm băm trước đã vì như mình đã nói, một bảng băm tốt khi nó có hàm băm tốt. Trước khi vào bài, phương pháp kết nối trực tiếp là phương pháp sử dụng danh sách liên kết đơn, do đó, bạn nào chưa biết gì về danh sách liên kết đơn thì hãy xem lại bài Danh sách liên kết đơn trong C++ để hiểu rõ hơn nha. Hàm băm hay là Hash function là hàm thực hiện việc ánh xạ khóa k nào đó vào trong bảng băm (h(k)). Một hàm băm tốt thỏa mản các tiêu chí sau:
Mình sẽ giới thiệu đến các bạn các phép băm thường được sử dụng nhất là phương pháp chia và nhân. Đối với phương pháp chia, mình sẽ ánh xạ khóa theo hàm h(k) = k % M, với k là khóa và M là kích thước của bảng băm. Đối với phương pháp nhân, hàm ánh xạ h(k) = M * (k*A % 1), với k là khóa, M là kích thước bảng băm và A là số thực 0 < A < 1. Theo phương pháp nhân này, sự hiệu quả phụ thuộc vào việc lựa chọn A, theo như nhà khoa học máy tính Knuth, chọn A = (sqrt(5) – 1) / 2 là hiệu quả nhất (xấp xỉ 0.618033987). Thông thường, mình sử dụng phương pháp chia cho dễ cài đặt. Tuy nhiên, không thể nào tránh khỏi đụng độ dù có dùng hàm băm nào đi nữa, do đó, chúng ta cần giải quyết đụng độ. Giải quyết đụng độĐối với việc sử dụng phương pháp kết nối trực tiếp, các phần tử bị đụng độ sẽ được thêm vào danh sách liên kết tại h(k) trong bảng băm. Như bạn có thể thấy trong hình, các khóa như 7, 17 đụng độ nhau thì chúng sẽ được thêm vào danh sách liên kết ở h(k) = M. Tương tự các khóa 4, 19 cũng bị đụng và được thêm vào danh sách liên kết ở h(k) = 2… Bây giờ chúng ta hãy cùng bắt đầu cài đặt bảng băm vào trong trong C++ nha. Cấu trúc một nút trong bảng bămNhư đã nói, phương pháp kết nối trực tiếp dùng danh sách liên kết đơn, các phần tử bị đụng độ tại phần tử i trong bảng băm thì sẽ được thêm vào danh sách liên kết đơn tại i trong bảng băm. Do đó, một phần tử trong bảng băm có cấu trúc như một nút trong danh sách liên kết đơn.
Cấu trúc bảng băm và hàm khởi tạoMột bảng băm là một mảng chứa các nút, giả sử mình có 100 phần tử, vậy mình sẽ định nghĩa một HashTable như sau:
Như vậy, chúng ta có thể khai báo một bảng băm như sau:
Các bạn có thể dễ dàng thấy một nút trong bảng là một con trỏ trỏ đến một Node, như vậy, chúng ta cần phải khởi tạo chúng bằng NULL để tránh gặp lỗi. Mình sẽ có hàm khởi tạo bảng như sau:
Hàm bămNhư đã nói ở trên, để đơn giản mình sẽ sử dụng hàm băm theo phép chia:
Thêm một nút vào bảng bămĐể thêm một nút, ta cần xác định vị trí sẽ thêm qua hàm băm h(k), sau đó thêm vào danh sách liên kết ở vị trí h(k) đó. Việc đụng độ sẽ được giải quyết do nếu đụng độ thì khóa sẽ được tự thêm vào sau danh sách liên kết đơn. Mình sẽ có hàm thêm như sau:
Hàm AddTail thì trong danh sách liên kết đơn, mình đã có bài viết về nó rồi, các bạn có thể đọc lại.
Tìm kiếm một khóa trong bảng bămĐể tìm kiếm một khóa trong bảng băm, ta cũng thực hiện xác định vị trí h(k), sau đó ta thực hiện tìm kiếm trong danh sách liên kết tại vị trí h(k) trong bảng băm.
Xóa một nút ra khỏi bảng bămĐể xóa một phần tử ra khỏi bảng băm, đầu tiên ta cũng phải xác định h(k), sau đó tìm xem nó nằm ở đâu trong danh sách liên kết đơn tại vị trí h(k) đó rồi thực hiện xóa nó đi.
Hai hàm DeleteHead và DeleteAfter cũng đã được mình trình bày trong bài Danh sách liên kết đơn trong C++ rồi nên mình sẽ không giả thích gì thêm.
Duyệt qua bảng bămDuyệt qua bảng băm rất đơn giản, bạn chỉ cần duyệt qua mảng, mỗi phần tử của mảng là một danh sách liên kết đơn, vậy thì duyệt danh sách liên kết đơn nữa là xong.
0 Lưu ý về bảng bămĐối với dữ liệu lớn, việc cấp phát một mảng quá lớn sẽ gây lãng phí bộ nhớ không đáng có, tuy nhiên, việc M lớn đảm bảo việc đụng độ ít xảy ra do các khóa phân bố đều. Ngược lại, nếu M nhỏ để tiết kiệm bộ nhớ, việc này sẽ làm giảm hiệu suất của bảng băm do việc đụng độ xảy ra với tần suất cao hơn. Do vậy, khi thao tác với bảng băm, các bạn cần phải cân nhắc giữa hiệu suất và dung lượng lưu trữ. Tổng kếtNhư vậy là trong bài viết này, mình đã giới thiệu đến các bạn về bảng băm trong C++, cách cài đặt bảng băm bằng phương thức kết nối trực tiếp dùng danh sách liên kết đơn. Nếu các bạn có bất kỳ ý kiến, đóng góp nào, đừng ngần ngại comment phía bên dưới bài viết nha. Cảm ơn các bạn đã theo dõi bài viết! |