unordered_map

index > STL > unordered_map

简介

内部实现哈希的map，相对于一般map来说，理论上更快。

应用基本和普通map类似，甚至有时候会让人觉得unordered_map更符合我们的需求，因为我们unordered_map的修改查询很快，但遍历很慢，一般我们开map也不用到遍历。

unordered_map对key的要求是需要实现其哈希过程，默认的哈希支持整数类型的key。

缺陷与改进

理论上更快的，但有例外，而且很可能会影响到一些特定样例的运行时间。

因为一般的编译器，给unordered_map默认的哈希表是固定的，当然细节挺复杂，详细可以看参考里的那篇博客。

笔者就说一个很简陋的理解：

默认的哈希在处理冲突的时候，是借助固定的哈希表来偏移的，冲突越多需要的时间越多。当有针对性地hack时，最差会退化成$O(N^2)$ 的过程。

为了解决这个问题，一般都会自写哈希过程，下面是大佬的优秀实现：

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        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);
    }
};

unordered_map<long long, int, custom_hash> safe_map;