### dx24816's blog

By dx24816, history, 6 months ago, ,

Hello,

Recently, I was doing Cow Run (http://www.usaco.org/index.php?page=viewproblem2&cpid=265), and I at first used the Policy Based Data Structure faster map (https://codeforces.com/blog/entry/60737), but I TLE'd on the last 4 test cases. I then switched back to using the unordered_map, and I passed all the test cases. Can anyone tell me the reason why the unordered_map was faster? I was under the impression that the PBDS map was faster. Thanks!

Code with unordered_map: https://ideone.com/Id7SZM Code using PBDS map: https://ideone.com/sA4UJG

To run this code, simply submit them in a file to the USACO website above, and use C++11.

-dx24816

• +4

 » 6 months ago, # |   +11 As I mentioned in the blog post, one downside of gp_hash_table is that it's significantly more fragile to weak hash functions (due to being open addressed and using power of 2 table sizes). I can't currently submit to USACO for whatever reason..., but I did run it on the test data.I use this hash function  unsigned hash_f(unsigned x) { x = ((x >> 16) ^ x) * 0x45d9f3b; x = ((x >> 16) ^ x) * 0x45d9f3b; x = (x >> 16) ^ x; return x; }  and I got 0.10 for gp_hash_table versus 0.30 for unordered_map.https://ideone.com/ikfX3EYou can also use cc_hash_table for a hash table that's a lot more resistant to weak hash functions.