Hash Table Mạnh Như Thế Nào Trong Policy Based Data Structures?

Hash Table Mạnh Như Thế Nào Trong Policy Based Data Structures?

Policy Based Data Structures là một họ các cấu trúc dữ liệu không nằm trọng thư viện chuẩn của C++. Có thể với nhiều bạn sẽ khá là mới mẻ với các cấu trúc dữ liệu này, tuy nhiên họ này cung cấp các cấu trúc dữ liệu với sức mạnh đáng kinh ngạc mà mình tin rằng sau khi tìm hiểu về nó các bạn sẽ thực sự bị thuyết phục và sử dụng nó như một công cụ đắc lực trong việc giải quyết các bài toán đặc biệt là trong lập trình thi đấu. 

Cấu trúc dữ liệu mình muốn nhắc tới ngày hôm nay đó là Policy Hash Table.

1. Giới thiệu chung

Policy Hash Table có sức mạnh vượt trội cực kì đáng nể với tốc độ nhanh hơn 3 đến 6 lần đối với các lệnh thêm và xóa, 4 đến 10 lần đối với đọc/ghi. Nghe có vẻ khó tin đúng không? Dưới đây là benmarks so sánh tốc độ xử lí của Policy Hash Table với unordered_map.

Code benmarks tại: https://ideone.com/ZkNMbH

2. Cách sử dụng:

Như đã nói ở đầu,  Policy Based Data Structures không nằm trong thư viện chuẩn của C++ vậy nên để sử dụng được cấu trúc dữ liệu này ta cần thêm 2 dòng sau đây ở đầu file. 

Khai báo: Phần khai báo của Hash Table trong Policy Based Data Structures cũng tương tự cách khai báo như map, unordered_map gồm có cặp key, value và có thể có thêm các 1 vài tham số khác nhưng ít được sử dụng nên mình không đề cập ở đây. 

3. Ví dụ

Nhìn vào các số liệu có thể thấy được Policy Hash Table sở hữu những số liệu ấn tượng, thậm chí là vượt trội so với unordered_map. Tuy vậy, số liệu chỉ là một phần, hãy thử đi vào các bài toán thực sự để xem Policy Hash Table phát huy như thế nào nhé.

Ví dụ 1:

https://codeforces.com/gym/101911/problem/A (Time Limit: 2s)

Solution 2: Sử dụng unodered_map

https://codeforces.com/gym/101911/submission/77241437 (AC: 1075ms)

Solution 3: Sử dụng gp_hash_table của Policy Hash Table

https://codeforces.com/gym/101911/submission/77241624 (AC: 405ms)

Ví dụ 2:

https://codeforces.com/contest/1041/problem/C (Time limit 2s)

Solution 2: Sử dụng unordered_map

https://codeforces.com/contest/1041/submission/77242413 (AC: 654 ms)

Solution 3: Sử dụng gp_hash_table:

https://codeforces.com/contest/1041/submission/61297714 (AC: 467ms)

Ví dụ 3: 

https://codelearn.io/training/detail?id=126100 (Time limit 0.5s)

Solution 1: Sử dụng unordered_map

https://pastebin.com/K9GRXJCB (AC: 0.07s)

Solution 2: Sử dụng gp_hash_table

https://pastebin.com/0Q78vEiN (AC: 0.04s) 

Như các bạn có thể thấy, gp_hash_table có tốc độ thực thi nhanh hơn đáng kể (thậm chí nhanh gấp 2.5 lần so với unordered_map trong ví dụ đầu tiên).

Nếu vẫn chưa đủ sức thuyết phục thì thử xét đến ví dụ sau: 

https://codeforces.com/contest/264/problem/C (Time limit 5s)

Solution 1: Sử dụng unordered_map

https://codeforces.com/contest/264/submission/40542899 (TLE ở test 8)

Solution 2: Sử dụng gp_hash_table:

https://codeforces.com/contest/264/submission/77243454 (AC : 3150ms)

Một ví dụ điển hình để thấy được sức mạnh vượt trội của gp_hash_table như thế nào. Đây liệu đã đủ để khiến bạn thử sử dụng nó?

4. Điểm yếu

Nãy giờ mình đã cho các bạn 1 số ví dụ để cho thấy sức mạnh của Policy Hash Table (cụ thể qua gp_hash_table) như thế nào rồi, vậy nó có điểm yếu gì không. Câu trả lời là có. Điểm yếu chí mạng của hash tables (cái này gồm cả unordered_map trong STL chứ không riêng gì Policy Hash Table)  là việc người ta có thể tìm ra các testcases để có tìm ra các va chạm băm ngoại tuyến và đẩy độ phức tạp hashmap của bạn lên nhiều lần. Các testcases kiểu đó người ta thường gọi là Anti-Hash test. 

Như trong ví dụ sau:

Bài : https://codeforces.com/contest/1234/problem/B2

Sử dụng gp_hash_table

https://codeforces.com/contest/1234/submission/77257717 (TLE ở test 20)

Sử dụng unordered_map

https://codeforces.com/contest/1234/submission/77381464 (TLE ở test 18)

Đây là một trong số những bài điển hình của anti-hash problem khi cả unordered_mapgp_hash_table đều gục ngã. Giải pháp cho việc này là bạn có thể viết custom hash function để kháng lại các test lợi dụng va chạm băm ngoại tuyến. Đây là 1 số hash function mà mình hay sử dung. Việc so sánh tốc độ của các hash function này còn tùy thuộc vào bộ tests của bài đó, vì trong quá trình mình sử dụng thì thấy độ ổn định không được tốt cho lắm, ở bài này thì hàm này thời gian nhỏ hơn nhưng bài khác thì thời gian lại lớn hơn.

 

Trong 3 hàm hash ở trên thì hàm custom_hash (hàm số 3) được mình sử dụng nhiều nhất và độ ổn định cũng tốt nhất, tuy nhiên nhược điểm của nó là hơi khó nhớ hơn so với 2 hàm còn lại.

Cách sử dụng, bạn truyền hash function vào như sau:

Áp dụng vào bài TLE ở trên ta có kết quả sau.

Sử dụng gp_hash_table (sử dụng hàm số 1)

https://codeforces.com/contest/1234/submission/61749745 (AC: 1715ms)

Sử dụng gp_hash_table (sử dụng hàm số 2)

https://codeforces.com/contest/1234/submission/77257564 (AC: 156ms)

Một điều nữa mà có thể nhiều bạn sẽ thắc mắc khi thấy phần benmarks có cc_hash_tablegp_hash_table nhưng trong code giải mẫu của các ví dụ mình chỉ sử dụng gp_hash_table. cả cc_hash_tablegp_hash_table đều thuộc Policy Hash Table nhưng gp_hash_table được sử dụng nhiều hơn do cơ chế mảng băm của cc_hash_tablegp_hash_table khác nhau, cc_hash_table sử dụng chained hash tables trong khi đó gp_hash_table sử dụng open addressed hash tables. Xem chi tiết điểm khác nhau tại: chained-hash-tables-vs-open-addressed-hash-tables.

gp_hash_table có tốc độ thêm phần tử, xóa phần tử, xóa toàn bộ nhanh hơn rất nhiều so với cc_hash_table

Một điểm yếu khác nữa là ngoài các kiểu dữ liệu cơ bản thì khi sử dụng các kiểu dữ liệu nâng cao thì bạn phải tự viết hàm hashing operator cho nó. 

1 kiểu dữ liệu mà mình hay sử dụng là pair<..> nên mình giới thiệu luôn đoạn snippet mà mình sử dụng để sử dụng pair<...> như là key. 

Sử dụng:

Lời kết

Okay, vậy là trên đây mình đã giới thiệu 1 cách sơ lược với các bạn về Policy Hash Table, mình thấy nó khá hay ho và thực ra từ khi biết đến nó thì mình ít khi dùng map, unordered_map luôn. À không dừng lại ở đó thì Policy Based Data Structures còn có thêm một vài cấu trúc dữ liệu nữa khá là hay ho nếu có thời gian các bạn có thể tìm hiểu thêm tại đây. Bài viết có thể có 1 số lỗi mong nhận được sự góp ý từ các bạn. Nếu thấy hay thì đừng quên vote cho mình 5* nhé. Cảm ơn các bạn nhiều.