(Optional) Hashmaps

Hashing

Hashing refers to assigning a unique code to every variable/object which allows insertions, deletions, and searches in $\mathcal{O}(1)$ time, albeit with a high constant factor, as hashing requires a large constant number of operations. However, as the name implies, elements are not ordered in any meaningful way, so traversals of an unordered set will return elements in some arbitrary order.

Custom Hashing

Copy
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;
#define f first
#define s second

struct hashPi {
	size_t operator()(const pi &p) const { return p.f ^ p.s; }
};

int main() { unordered_map<pi, int, hashPi> um; }

Copy
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;
#define f first
#define s second

namespace std {
template <> struct hash<pi> {
	size_t operator()(const pi &p) const { return p.f ^ p.s; }
};
}  // namespace std

int main() { unordered_map<pi, int> um; }

Copy
import java.io.*;
import java.util.*;

public class HashTest {
	public static void main(String[] args) {
		// uses custom hash function in class Pair
		Set<Pair> set = new HashSet<>();
	}

	static class Pair {

However, this hash function is quite bad; if we insert $(0,0), (1,1), (2,2) \ldots$ then they will all be mapped to the same bucket (so it would easily be hacked in a Codeforces contest).

Copy
import java.io.*;
import java.util.*;

public class HashTest {
	public static void main(String[] args) {
		// uses custom hash function in class Pair
		Set<Pair> set = new HashSet<>();
		for (int i = 0; i < 100000; ++i) {
			// Pair p = new Pair(i, 0); // ~0.2s on ide.usaco.guide
			Pair p = new Pair(i, -31 * i);  // >5s

A better way to hash pairs would be to use polynomial hashing with a randomized base (as described in this module).

Anti-Hash Tests

The built-in hashing algorithm for integers in C++ is vulnerable to pathological tests, causing abnormally slow runtimes. We describe the issue below and how to fix it. Java users are not affected (see this comment).

In order to make your unordered_map unhackable, the hash function $H$ you select must have the following property: it is hard to find integers $x$ and $y$ such that $x\neq y$ but $H(x)\equiv H(y) \pmod{P}$, where $P$ is the prime modulus corresponding to the number of buckets in your unordered map. Note that:

• The default hash function, $H(x)=x$, obviously does not satisfy this property, because you can simply choose $x=0$ and $y=P$.
• If open hacking is allowed, then any deterministic hash function does not satisfy this property, because a hacker could generate a test case specifically to break your solution. You should introduce randomness to ensure that your hash function changes from run to run.

Here is a drop-in replacement for unordered_map that seems to work well in practice:

Copy
struct chash {
	// any random-ish large odd number will do
	const uint64_t C = uint64_t(2e18 * PI) + 71;
	// random 32-bit number
	const uint32_t RANDOM =
	    chrono::steady_clock::now().time_since_epoch().count();
	size_t operator()(uint64_t x) const {
		// see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
		return __builtin_bswap64((x ^ RANDOM) * C);
	}
};
template <class K, class V> using cmap = unordered_map<K, V, chash>;
// example usage: cmap<int, int>

A Faster HashMap in C++

In C++, it's usually faster to use gp_hash_table<K, V> instead of unordered_map<K, V>. Read / writes are much faster than unordered_map. The documentation is rather confusing, so I'll just summarize the most useful functions here. If you need a replacement for unordered_set<K>, use gp_hash_table<K, null_type>.

Custom Hashing

Like unordered_map, gp_hash_table is vulernable to hash collisions if a cusetom hash function isn't used. We recommend using the same custom hash we used for unordered map above:

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

gp_hash_table<int, int, chash> table;

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.

Copy
template <class K, class V>
using ht = gp_hash_table<
    K, V, 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.

Copy
int main() {
	ht<int, null_type> g;
	g.resize(5);
	cout << g.get_actual_size() << "\n";  // 8
	cout << 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).

Furthermore, if we construct g with the following arguments:

Copy
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

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!

Copy
#include <bits/stdc++.h>  // see C++ Tips & Tricks
using namespace std;

using ll = long long;

using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

Problems