(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 – 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 | |
---|---|---|---|---|---|
CSES | Normal | Show TagsSet |