Unordered Associative Containers

Overview

Since the C++11 standard, four unordered associative containers based on hashing have officially been included in the C++ Standard Template Library: unordered_set, unordered_multiset, unordered_map, and unordered_multimap.

They have many similarities with the corresponding associative containers in terms of functionality and functions. The biggest difference is that ordinary associative containers generally use red-black trees, with internal elements sorted in a particular order; these unordered associative containers instead store elements using hashing, and their internal elements are not sorted in any particular order, so the order of access when accessing elements in an unordered associative container is not guaranteed.

The use of hash-based storage means that on average, most operations on unordered associative containers (including lookup, insertion, and deletion) can be completed in constant time, which is better than the logarithmic time complexity with respect to the container size of associative containers.

Since unordered associative containers have many similarities with the corresponding associative containers in terms of usage and operations, the various operations of unordered associative containers are not introduced here. Readers can refer to associative containers for this content.

Creating hash collisions

As mentioned above, in the worst case, the time complexity of some operations on unordered associative containers is linear in the size of the container.

When the hash function is fixed, data can be constructed to create a large number of hash collisions in the container, causing the complexity to reach its upper bound.

In standard library implementations, the hash value of each element is obtained by taking the value modulo a prime number; more specifically, the prime numbers in this list (for g++ 6 and earlier, this prime is generally $126271$; for g++ 7 and later, it is generally $107897$).

Therefore, inserting multiples of these moduli into the container can create a large number of hash collisions.

Custom hash functions

Using a custom hash function can effectively avoid the large number of hash collisions caused by constructed data.

To use a custom hash function, define a struct and overload the () operator in the struct, as follows:

struct my_hash {
  size_t operator()(int x) const { return x; }
};

Of course, to ensure that the hash function cannot be cracked quickly (for example, by hacking submissions using unordered associative containers on Codeforces), you can try adding some randomization function (such as time) to the hash function to increase the difficulty of cracking it.

For example, this blog post gives the following hash function:

struct my_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }

  // Hash function for std::pair<int, int> as the key type
  size_t operator()(pair<uint64_t, uint64_t> x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x.first + FIXED_RANDOM) ^
           (splitmix64(x.second + FIXED_RANDOM) >> 1);
  }
};

After writing a custom hash function, pass it to the container by defining it as unordered_map<int, int, my_hash> my_map; or unordered_map<pair<int, int>, int, my_hash> my_pair_map;.