是否错误使用unordered_map？哈希函数致查找复杂度未达O(1)

我怀疑自己错误使用了unordered_map，因为未获得预期的平均O(1)复杂度，反而趋近于O(n)。

当前我定义的map如下：

unordered_map<my_class , double> objects_to_values;

关键在于my_class的定义。

my_class目前由三个整数a、b、c标识，其结构框架如下：

class my_class  {
private:
        int _a, _b, _c;

public:
        my_class(int _a, int _b, int _c) {
                this->_a = _a;
                this->_b = _b;
                this->_c = _c;
        }

        int a() const {
                return _a;
        }

        int b() const {
                return _b;
        }

        int c() const {
                return _c;
        }

        bool operator==(const my_class& obj) const {
                return ((a() == obj.a()) && (b() == obj.b()) && (c() == obj.c()));
        }
};

此外，我还定义了：

struct hash<my_class> {
public:
        size_t operator()(const my_class& k) const {
                return ( (hash<int>()(k.c())) ^ (( ((hash<int>()(k.a()))^ (hash<int>()(k.b())
                                << 1) >> 1) << 1) >> 1) );
        }
};

我观察到，随着unordered_map的规模增大，代码运行明显变慢，这可能是因为我的find操作未达到预期的平均O(1)复杂度。

请问我是否使用有误？是否需要优化哈希函数（我承认当前哈希函数效果不佳）？针对取值范围0-100000左右的三个整数，有没有更优的哈希组合方式？

你的核心问题确实出在哈希函数设计太差，导致大量哈希冲突，unordered_map退化成链表遍历，性能趋近O(n)。下面拆解问题并给出优化方案：

1. 当前哈希函数的问题 #

你写的哈希函数用了多次移位和异或，但实际效果等于把三个整数的哈希值简单异或，而且移位操作还丢失了b的高位信息——(hash(b) <<1) >>1其实就是把hash(b)的最高位清零，完全是无效操作。这种设计会导致大量不同的my_class对象算出相同的哈希值，冲突率极高。

2. 针对三个整数的最优哈希组合方式 #

方式一：利用标准库风格的哈希组合 #

这是工业界常用的哈希组合方式，通过常数和移位避免简单异或的冲突：

struct hash<my_class> {
    size_t operator()(const my_class& k) const {
        size_t h1 = hash<int>()(k.a());
        size_t h2 = hash<int>()(k.b());
        size_t h3 = hash<int>()(k.c());
        
        // 用黄金比例常数打乱哈希值，减少冲突
        h1 ^= h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2);
        h1 ^= h3 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2);
        return h1;
    }
};

0x9e3779b9是一个经过验证的黄金比例常数，能有效分散哈希值的分布。

方式二：实现完全无冲突的哈希（取值范围明确时） #

因为三个整数的取值都是0-100000，我们可以直接将它们映射为唯一的大整数，从根源上避免冲突：

struct hash<my_class> {
    size_t operator()(const my_class& k) const {
        // 用100001作为基数，确保每个(a,b,c)组合对应唯一数值
        const size_t base = 100001;
        return static_cast<size_t>(k.a()) * base * base + 
               static_cast<size_t>(k.b()) * base + 
               static_cast<size_t>(k.c());
    }
};

64位系统下100001^3约为1e15，远小于size_t的上限（2^64），完全不会溢出。

方式三：简化的移位异或组合 #

如果不想引入复杂常数，也可以通过移位错开三个哈希值的位分布：

struct hash<my_class> {
    size_t operator()(const my_class& k) const {
        size_t ha = hash<int>()(k.a());
        size_t hb = hash<int>()(k.b());
        size_t hc = hash<int>()(k.c());
        return ha ^ (hb << 16) ^ (hc << 32);
    }
};

这种方式让三个哈希值的位段不重叠，比你原来的设计冲突率低很多。

3. 其他性能优化建议 #

• 你的operator==实现是正确的，三个成员都做了完整比较，符合unordered_map的要求。
• 如果提前知道unordered_map的元素数量，调用reserve()预分配空间，避免频繁扩容带来的性能损耗。比如预计存10000个元素，就调用objects_to_values.reserve(15000)（预留1.5倍空间是常规操作）。

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