C++ 哈希表原理与 STL 底层实现解析

hash_combine

冲突率低，推荐使用。常用于多成员结构体。

template <typename T>
void hash_combine(std::size_t& seed, const T& val) {
    seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

struct Person {
    std::string name;
    int age;
    bool operator==(const Person& p) const {
        return name == p.name && age == p.age;
    }
};

struct PersonHash {
    std::size_t operator()(const Person& p) const {
        std::size_t seed = 0;
        hash_combine(seed, p.name);
        hash_combine(seed, p.age);
        return seed;
    }
};

哈希函数

直接定址法

这是一种单调性函数，每个哈希值对应唯一的映射位置，理论上无冲突。但缺点是如果数据分散，会浪费大量空间。仅适用于数据集中的场景。

除留余数法

最常用的方法。对哈希表大小 m 取模，得到一个不大于 m 且接近 m 的质数 p 作为模数。例如表大小为 10，可选模数 7。键值 12, 13, 1 分别模 7 得到映射区域。

平方取中法

取关键字平方后的中间几位作为地址。例如键值 1234，平方为 1522756，取中间三位 227 作为地址。该方法能较好地打散连续键值，避免除留余数法因取值不当加剧冲突的问题。

基数转换法

将十进制数转换为其他进制（如十六进制），将结果视为十进制后再取模。若含字母则转为 ASCII 码。例如 255 转十六进制 FF，视为十进制 7070，再对表大小取模。

哈希冲突

上述方法（除直接定址法外）都可能产生冲突，即两个不同键值映射到同一地址。负载因子（已插入数据个数 / 表大小）越大，冲突概率越高，效率越低。

缓解冲突主要有两种方案：开放定址法、哈希桶。

开放定址法

当冲突发生时，键值对向后偏移寻找空位。探测规律包括线性探测（一格一格往后）和二次探测（按平方数跳跃）。

负载因子通常需小于 0.7，否则探测次数过多，时间复杂度可能逼近 O(n)。

以下是开放定址法的模拟实现，注意删除操作需标记为 DELETE 状态，以便查找时继续向后探测。

template <class K, class V>
class HashData {
public:
    enum State { EMPTY, EXIST, DELETE };
    pair<K, V> _kv;
    State _state;
};

template <class K, class V>
class HashTable {
public:
    bool insert(const pair<K, V> &kv) {
        if (_tables.size() == 0 || (_n * 10) / _tables.size() >= 7) {
            UpMemory();
        }
        if (Find(kv.first)) return false;

        int hashi = kv.first % _tables.size();
        while (_tables[hashi]._state == HashData<K, V>::State::EXIST) {
            hashi++;
            hashi %= _tables.size();
        }
        _tables[hashi]._kv = kv;
        _tables[hashi]._state = HashData<K, V>::State::EXIST;
        _n++;
        return true;
    }

    HashData<K, V> *Find(const K &key) {
        int hashi = key % _tables.size();
        int tmp = hashi;
        while (_tables[hashi]._state != HashData<K, V>::EMPTY) {
            if (_tables[hashi]._state == HashData<K, V>::EXIST && 
                _tables[hashi]._kv.first == key) {
                return &_tables[hashi];
            }
            hashi++;
            hashi %= _tables.size();
            if (hashi == tmp) return nullptr;
        }
        return nullptr;
    }

    bool Erase(const K &key) {
        HashData<K, V> *pdata = Find(key);
        if (pdata == nullptr) return false;
        pdata->_state = HashData<K, V>::DELETE;
        --_n;
        return true;
    }

private:
    void UpMemory() {
        int newsize = (_tables.size() == 0) ? 5 : 2 * _tables.size();
        HashTable<K, V> NewHT;
        NewHT._tables.resize(newsize);
        for (int i = 0; i < _tables.size(); i++) {
            if (_tables[i]._state == HashData<K, V>::EXIST) {
                NewHT.insert(_tables[i]._kv);
            }
        }
        _tables.swap(NewHT._tables);
    }

private:
    vector<HashData<K, V>> _tables;
    size_t _n = 0;
};

哈希桶

哈希桶本质上是一个挂有链表的数组。数组元素称为桶，冲突时将数据节点链入链表。相比开放定址法，哈希桶在负载因子为 1 时性能更优，查找通常为常数级时间复杂度。 C++ 标准库中的 unordered_map 和 unordered_set 底层均采用哈希桶。

unordered_map 和 unordered_set 如何共用哈希桶模板类

为了复用底层结构，设计者巧妙利用了模板参数：

• unordered_set 的第二个模板参数传 Key。
• unordered_map 的第二个模板参数传 pair<Key, T>。

这样，查找和删除只需关注 Key，而插入时根据实际类型自动适配。外层调用时，unordered_set 传入 Key，unordered_map 传入 pair，底层 Insert 接收 Value 类型数据。

STL 哈希桶中 Insert 如何得到键值

查找和删除依赖 Key，但插入时 Key 的提取方式不同。为此，哈希桶提供了第四个模板参数 ExtractKey（仿函数），用于从 Value 中提取 Key。

• unordered_set 传入的 KeyOfValue 直接返回 Key。
• unordered_map 传入的 KeyOfValue 返回 pair 的 first。

// 哈希桶定义示例
template<class Key, class Value, class Alloc, class ExtractKey, class Hash, class __Pred, .....>
class HashBucket {
    // ... Find, Erase, Insert 等接口
};

// unordered_set 使用
template<class Key, class Hash, class Pred.....>
class unordered_set {
    struct KeyOfValue {
        const K &operator()(const K &key) { return key; }
    };
    typedef HashBucket<Key, Key, Alloc, KeyOfValue, Hash, Pred> HT;
    // ...
};

// unordered_map 使用
template<class Key, class T, class Hash, class Pred.....>
class unordered_map {
    struct KeyOfValue {
        const K& operator()(const pair<K, V> &_kv) { return _kv.first; }
    };
    typedef HashBucket<Key, pair<Key, T>, Alloc, KeyOfValue, Hash, Pred> HT;
    // ...
};

键为自定义类型的处理

对于任意自定义类型作为键，前提是实现向整形转化的仿函数（Hash）以及相等比较仿函数（Pred）。

哈希桶底层插入时，先用 Hash 仿函数将自定义类型转为哈希值，再取模定位桶。由于哈希值有限，不同对象可能哈希值相同，因此查找时必须用原生比较（Pred）确认是否真正相等。

以上涵盖了哈希表的核心原理及 STL 底层实现细节。