Những kỹ thuật nào dụng để xử lý collision trong Hashing
Giả sử, chúng ta muốn thiết kế một hệ thống lưu trữ hồ sơ nhân viên. Mỗi hồ sơ sẽ có một key (khóa) để định danh bằng cách dùng số điện thoại. Chúng ta muốn hệ thống đó phải thực hiện các thao tác sau một cách hiệu quả: Show
1. Tư tưởng của HashingVậy với các yêu cầu trên, chúng ta có thể nghĩ sẽ thiết kế hệ thống sử dụng các cấu trúc dữ liệu như dưới đây để lưu trữ số điện thoại kèm thông tin tương ứng:
Với Array và Linked List, trong thao tác tìm kiếm thì chúng ta cần phải tìm kiếm theo kiểu tuyến tính (Linear Search). Nếu danh sách đã được sắp xếp, số điện thoại có thể được tìm theo Binary Search, mà có độ phức tạp thời gian là O(log n). Nhưng chúng ta phải trả giá cho thao tác thêm mới và xóa, vì phải luôn duy trì thứ tự sắp xếp. Với Balanced Binary Search Tree, tất cả các thao tác tìm kiếm, thêm mới, xóa có thể được đảm bảo trong thời gian O(log n). Với Direct Access Table, chúng ta sẽ tạo ra một mảng lớn và sử dụng số điện thoại làm chỉ mục trong mảng. Mỗi mục trong mảng sẽ là NIL (0 hoặc null) nếu không có thông tin lưu trữ. Với cấu trúc dữ liệu này, Time Complexity sẽ tốt nhất so với tất cả các cấu trúc trên, chúng ta có thể thực hiện tất cả các thao tác trong thời gian O(1). Giải pháp Direct Access Table trong thực tế có rất nhiều hạn chế. Hạn chế dễ thấy nhất là bộ nhớ cần thiết để lưu trữ sẽ rất lớn. Hashing là một giải pháp để thay thế cho tất cả các cấu trúc dữ liệu trên khi làm thực tế. Hashing là một kỹ thuật cải tiến hơn so với Direct Access Table. Ý tưởng của Hashing là phân phối các cặp khóa/giá trị trên một mảng. Nó sử dụng một hash function (hàm băm) để chuyển đổi các khóa có giá trị lớn thành giá trị nhỏ hơn và sử dụng số nhỏ hơn đó làm chỉ mục trong một bảng gọi là hash table (bảng băm). 2. Hash functionHash function là một hàm ánh xạ một dữ liệu có kích thước tùy ý (một số nguyên lớn, một chuỗi,…) thành một số nguyên nhỏ để có thể sử dụng làm chỉ mục trong hash table. Giá trị trả về của hash function có thể gọi là hash values, hash codes hoặc đơn giản là hashes. Một Hash function tốt phải đạt được các yêu cầu sau:
Lưu ý: Dù việc cài đặt hash function tốt đến đâu đi chăng nữa, thì việc xảy ra va chạm (collisions) là điều không thể tránh khỏi. Vì vậy để duy trì một performance tốt cho hash table, điều quan trọng là phải xử lý các collisions thông qua các kỹ thuật khác nhau. Hash table (bảng băm) là một cấu trúc dữ liệu sử dụng mảng để lưu trữ các cặp khóa/giá trị. Mỗi vị trí trong mảng gọi là một bucket, có thể null, chứa một, hoặc chứa nhiều cặp khóa/giá trị. Nó sử dụng hash function (hàm băm) để tính toán một index trong mảng để chèn hoặc tìm kiếm phần tử. Bằng cách cài đặt một hash function tốt, chúng ta sẽ có một hash table hoạt động với performance tốt. Theo các giả thiết lý tưởng, thời gian trung bình cần thiết để tìm kiếm một phần tử trong hash table là O(1).
Giải thích hình minh họa:
Nếu các kết quả của hàm hash được phân bố đều, các bucket sẽ có kích thước xấp xỉ nhau. Giả sử số bucket đủ lớn, mỗi buckets sẽ chỉ có một vài phần tử trong chúng. Điều này làm cho việc tìm kiếm rất hiệu quả. 4. Độ phức tạpGọi:
Giá trị α = n / k được gọi là load factor (số phần tử trung bình được lưu ở mỗi bucket). Khi load factor nhỏ (xấp xỉ 1), và giá trị của hash function phân bố đều, thì độ phức tạp của các thao tác trên Hash table là O(1). 5. Collision HandlingVì hash function giúp chuyển đổi một khóa có giá trị lớn thành một số nhỏ nên sẽ có khả năng 2 khóa sẽ có cùng một giá trị băm (hash codes). Collision là một tình huống khi thêm mới một phần tử vào một vị trí mà đã tồn tại một phần tử khác trong hash table, lúc này ta phải xử lý va chạm bằng một số kỹ thuật: 5.1. Separate ChainingTư tưởng là cài đặt thêm các Linked List (danh sách liên kết) ở các bucket để lưu trữ các phần tử có cùng giá trị hash code. Ưu điểm:
Nhược điểm:
Độ phức tạp: Time Complexity để thực hiện các thao tác search/insert/delete là: O(1 + α)
Giải thích hình minh họa:
5.2. Open AddressingTư tưởng của Open Addressing là khi xảy ra Hash collision, ta lưu vào một vị trí tiếp theo trong hash table. Tức là, hash table phải đủ vị trí để lưu tất cả các phần tử. Vì vậy, kích thước của hash table luôn >= tổng số khóa, hay Load factor phải nhỏ hơn 1. Việc tìm vị trí tiếp theo để lưu khóa có thể được thực hiện bằng một số cách sau:
Minh họa việc tìm vị trí tiếp theo của khóa theo Linear Probing: Trong hình minh họa:
Đọc thêm: https://en.wikipedia.org/wiki/Hash_table https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/ https://www.geeksforgeeks.org/hashing-data-structure/ http://vnoi.info/wiki/algo/data-structures/hash-table #data-structures, #hashing-data-structure |