如何将vector<int>设为unordered_map的key并解决哈希函数报错问题

你遇到的编译错误是因为C++标准库没有为std::vector<int>提供默认的哈希函数实现，而std::unordered_map的底层是哈希表，必须依赖对应key类型的哈希函数计算存储位置，因此直接将vector<int>作为key时会触发静态断言报错：

error: static assertion failed: hash function must be invocable with an argument of key type

你可以通过自定义vector<int>类型的哈希函数解决该问题，不需要改用时间复杂度O(log n)的std::map，平均访问复杂度仍可保持O(1)，具体实现如下：

• 首先自定义哈希结构体

#include <unordered_map>
#include <vector>
#include <functional>

struct VectorIntHash {
    size_t operator()(const std::vector<int>& vec) const {
        std::hash<int> int_hasher;
        size_t hash_seed = 0;
        // 遍历vector元素组合哈希值，采用通用的哈希混淆算法降低碰撞概率
        for (int num : vec) {
            hash_seed ^= int_hasher(num) + 0x9e3779b9 + (hash_seed << 6) + (hash_seed >> 2);
        }
        return hash_seed;
    }
};

• 声明unordered_map时传入自定义哈希类型作为第三个模板参数

// 模板参数说明：key类型vector<int>，value类型int，自定义哈希函数类型
std::unordered_map<std::vector<int>, int, VectorIntHash> target_map;

其他可选优化 #

• 如果你使用C++20及以上版本，且作为key的vector长度固定，可以改用std::array<int, 固定长度>作为key，标准库已为std::array提供默认哈希实现，不需要自定义哈希函数
• 如果你有特殊的相等判断需求，可以自定义相等比较结构体，作为unordered_map的第四个模板参数传入即可，默认的std::vector的==运算符已符合通用场景的相等判断要求，无需额外修改

• 自定义哈希函数要尽量降低碰撞概率，如果大量不同vector生成了相同的哈希值，会导致哈希表冲突变多，访问效率下降，最坏情况时间复杂度会退化到O(n)
• 不要直接对vector的内存地址做哈希，内容相同的不同vector对象内存地址不同，会导致相同内容的key被判定为不同对象，引发逻辑错误

内容的提问来源于stack exchange，提问作者Kaja