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

Author: Benjamin Qi

### Prerequisites

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 – read through this problem before continuing!

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!

Solution

## Problems

### 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!

## Give Us Feedback on (Optional) A Faster Hash Table in C++!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.