(Optional) A Faster Hash Table in C++

Read / writes are much faster than unordered_map. Its actual size is always a power of 2. The documentation is rather confusing, so I'll just summarize the most useful functions here.

1#include <ext/pb_ds/assoc_container.hpp>
2using namespace __gnu_pbds;

Unordered Set

gp_hash_table<K,null_type> functions similarly to unordered_set<K>.

Hacking

gp_hash_table is also vulnerable to hacking. The hash function mentioned in the blog:

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

is easily hackable (see neal's comment). To avoid this, we can replace chash with one of the custom hash functions mentioned previously.

Resizing

Unordered map has reserve. Calling this function before inserting any elements can result in a constant factor speedup.

We can modify the declaration of gp_hash_table so that it supports the resize function, which operates similarly.

1template<class K,class V> using ht = gp_hash_table<
2    K,
3    null_type,
4    hash<K>,
5    equal_to<K>,
6    direct_mask_range_hashing<>,
7    linear_probe_fn<>,
8    hash_standard_resize_policy<
9      hash_exponential_size_policy<>,
10      hash_load_check_resize_trigger<>,

These are the same template arguments as the default gp_hash_table, except false has been changed to true. This modification allows us to change the actual size of the hash table.

1int main() {
2    ht<int,null_type> g; g.resize(5);
3    cout << g.get_actual_size() << "\n"; // 8
4    cout << g.size() << "\n"; // 0
5}

When calling g.resize(x), x is rounded up to the nearest power of 2. Then the actual size of g is changed to be equal to x (unless x < g.size(), in which case an error is thrown).

Furthermore, if we construct g with the following arguments:

1ht<int,null_type> g({},{},{},{},{1<<16});

then the actual size of g is always at least 1<<16 (regardless of calls to resize). The last argument must be a power of 2 (or else errors will be thrown).

Solving 3SUM

Since all the values are quite small, you can use an array instead of a hashmap. But if you didn't read the constraints carefully enough, you're in luck!

Problems