Unluckily, C++ doesn't provide a hashing operator for pairs by default. Thus, you need to define your own. I've typically done it like this.

struct chash {
    int operator()(pii x) const { return x.first* 31 + x.second; }
};
gp_hash_table<pii, int, chash> table;

For unordered_map, simply defining the operator in the std namespace seems to work. However, for policy hash table, since it's in a different namespace, it seems like we need to pass it in manually.

gp_hash_table continues to perform great with pairs.

unordered_map linear insertion:                                 1.44404
cc_hash_table linear insertion:                                 1.49816
gp_hash_table linear insertion:                                 0.749987

unordered_map linear read/write:                                1.94124
cc_hash_table linear read/write:                                1.91796
gp_hash_table linear read/write:                                1.49307

unordered_map random insertion:                                 3.99146
cc_hash_table random insertion:                                 4.10996
gp_hash_table random insertion:                                 0.804868

unordered_map random read/write:                                5.76351
cc_hash_table random read/write:                                0.915423
gp_hash_table random read/write:                                1.06964

EDIT: Updated with gp_hash_table results. EDIT2: Updated with proper way of defining custom hashes.

As an alternative solution you can use nested hash tables, for example:

gp_hash_table<first, gp_hash_table<second, value>> table;

The first key is the first element in a pair. The value is a hash table that uses the key as the second element in a pair with the final value of the value of pair.

It is much easier and faster to implement it, and you don't need to think about the pair hashing function.

But it actually will be interesting how this approach will affect time and memory efficiency, comparing to custom hashing function.

Cc_hash_table is a chained hash table, while gp_hash_table is an open address hash table. I have some benchmarks in the post.

It seems like in practice, gp_hash_table has far superior performance for insertions/deletions, while cc has marginally better performance for reads/writes.

TL;DR: The C++ standard requires certain unnecessary things that make unordered_map implementations very slow.

So I was pretty curious about this too. Reading around, it seems like it's because the C++ standard requires some bizarre things from unordered_map, namely, that you can iterate over buckets, as well as being able to iterate through elements in a bucket.

I found this comment on HN: "A bigger issue IMO is that the existence of some methods in various standard classes/templates really murder performance, no matter how good the implementation is. One particularly bad example is the bucket() method, local_iterator types, etc. in c++11's unordered_map (probably the rest of the unordered family too). These force the table to be implemented in such a way that every insertion requires a heap allocation, and iteration requires much more pointer chasing than would otherwise be necessary (e.g. with a probed implementation), which is... unfortunate for the cache."

Also, there's this talk which cites the same point. I linked to the relevant portion here

Due to the C++ standard, unordered_map's elements must be stored in what is basically a linked list. I don't think there's any real use in accessing the elements in a bucket, nor is there an use in iterating through the buckets, so the policy hash map seems strictly superior to me.

In my opinion, this is the easiest way to avoid hacks. Why is it necessary to xor with a random string?

const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    int operator()(int x) const { return x ^ RANDOM; }
};
gp_hash_table<int, int, chash> table;

I wrote the definition to do so in the PS (the important thing is the last 2 trues). It didn't seem to do much for me. After using that typedef, you can call table.resize() and table.set_load_factor(). set_load_factor takes a pair (min_load_factor and max_load_factor).

The benchmarks don't seem to vary that much to me (except for the performance of cc_hash_table on your machine). Gp_hash_table outperforms unordered_map by 2-5x somewhat consistently, and is fairly close to your custom implementation for insertion/deletion.

One more thing. If you're interested in playing around with the settings to see if there's a faster version, check out their benchmarks here: https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/assoc_performance_tests.html

See my comment here: http://mirror.codeforces.com/blog/entry/60737?#comment-446357

you can't lower_bound in hash table.you may want to use map.

I don't think you can.

55 test case contains only powers of two, so, hash function from Chilli does not help. I changed hash function in your code, try to use this. Source code. Maybe someone can suggest even better hash function.

UPD: Try to use this variant of hash function too.

Thanks for the heads up!

I did realize that after writing the section, which is the main purpose of the "A Better Hash Function" section (I also chose (x<<16) ^ RANDOM as my "good" hash function...) Looking back at it, I should probably have put the hash function stuff together... I'll also update the code with a better hash.

I use a fairly jank hash function I found online at some point, but I'd definitely like to know more!

Looking forward to your blog post!

table.find(x) != table.end() should work.

God bless you man, I was searching it for so long

Use hashing function

From what I can see you are using gp_hash_table<int, ll> m; instead of gp_hash_table<int, ll, custom_hash> m;. There is probably some anti hash test case on G, so you need to use the custom_hash to not get TLE.