Skip to content

Unordered Associative Containers

Overview

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

Usage for compilers not supporting C++11

Before C++11, unordered associative containers were part of the TR1 extension of C++. Therefore, if the compiler does not support C++11, you need to add the tr1/ prefix to the header file name and use the std::tr1 namespace. For example, #include <unordered_map> should be changed to #include <tr1/unordered_map>; std::unordered_map should be changed to std::tr1::unordered_map (or tr1::unordered_map if using using namespace std;).

These containers share many similarities with their corresponding associative containers in terms of functionality and member functions. The most significant difference is that ordinary associative containers are typically implemented using red-black trees, with elements sorted in a specific order; whereas these unordered associative containers store elements using hashing, and the internal elements are not sorted in any particular order, so there is no guarantee regarding the access order when iterating over elements.

The hash-based storage characteristic allows unordered associative containers to complete most operations (including lookup, insertion, and deletion) in constant time complexity on average, which is more efficient compared to the logarithmic time complexity relative to container size of associative containers.

Warning

In the worst case, the time complexity of operations such as insertion, deletion, and lookup on unordered associative containers can become linear with respect to the container size! This situation usually occurs when there are a large number of hash collisions within the container.

Additionally, since operations on unordered associative containers often have significant constant factors, their efficiency may not be much better than that of ordinary associative containers in some cases.

Therefore, use unordered associative containers with caution and avoid misuse (for example, lazily using unordered_map<int, int> as an infinite ordinary array without discretization).

Since unordered associative containers share many commonalities with their corresponding associative containers in terms of usage and operations, the various operations of unordered associative containers will not be introduced here. Readers can refer to Associative Containers for these details.

Creating Hash Collisions

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

Given a fixed hash function, it is possible to construct data that causes a large number of hash collisions within the container, reaching the upper bound of complexity.

In the standard library implementation, the hash value of each element is obtained by taking the value modulo a prime number. More specifically, it is one of the prime numbers from this list (for g++ 6 and earlier versions, this prime is usually \(126271\); for g++ 7 and later versions, it is usually \(107897\)).

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

Custom Hash Functions

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

To use a custom hash function, you need to define a structure and overload the () operator within it, like this:

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

Of course, to ensure that the hash function is not easily cracked (for example, when hacking submissions using unordered associative containers on Codeforces), you can try adding some randomization functions (such as time) to the hash function to increase the difficulty of cracking.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 the custom hash function, you can pass it to the container by defining unordered_map<int, int, my_hash> my_map; or unordered_map<pair<int, int>, int, my_hash> my_pair_map;.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用