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

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"; // 84 cout << g.size() << "\n"; // 05}

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:

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

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

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

CSES | Normal | View Solution |