# (Optional) A Faster Hash Table in C++

Author: Benjamin Qi

Introduces gp_hash_table.

Resources | ||||
---|---|---|---|---|

CF | Introduces gp_hash_table | |||

GCC | documentation | |||

Benq (from KACTL) |

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.

#include <ext/pb_ds/assoc_container.hpp>using 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:

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<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.

template<class K,class V> using ht = gp_hash_table<K,null_type,hash<K>,equal_to<K>,direct_mask_range_hashing<>,linear_probe_fn<>,hash_standard_resize_policy<hash_exponential_size_policy<>,hash_load_check_resize_trigger<>,true>>;

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.

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

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).

Resources | ||||
---|---|---|---|---|

GCC | documentation |

Furthermore, if we construct `g`

with the following arguments:

ht<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

Focus Problem – try your best to solve this problem before continuing!

View Internal SolutionSince 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!

Solution

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CSES | Normal | ## Show TagsSet |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!