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;
    }
};

常见哈希函数

直接定址法

数学上的单调函数，每个哈希值对应唯一映射位置，无冲突。但仅适用于数据集中的情况，若数据分散则浪费空间。

除留余数法

最常用的方法。取模运算 key % p，其中 p 为不大于表长且接近表长的质数。例如表长为 10，可选 p=7。

平方取中法

取关键字平方后的中间几位作为地址。例如 key=1234，平方为 1522756，取中间三位 227 作为地址。此法能较好打散连续键值。

基数转换法

将十进制转为其他进制（如十六进制），视作新数字后取模。若含字母则转 ASCII 码。

哈希冲突解决

负载因子（已插入数据个数 / 表大小）越大，冲突概率越高。负载因子通常控制在 0.7 以下。常见解决方案有两种：开放定址法和哈希桶。

开放定址法

冲突时向后偏移寻找空位。探测方式包括线性探测（逐个遍历）和二次探测（按平方数间隔）。

删除操作需注意标记状态。若直接清空，查找时会误判结束。因此需要 EMPTY（空）、EXIST（存在）、DELETE（已删除）三种状态。查找时需跳过 DELETE 继续向后，直到遇到 EMPTY。

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

template <class K, class V>
class HashTable {
private:
    std::vector<HashData<K, V>> _tables;
    size_t _n = 0;

public:
    bool insert(const std::pair<K, V> &kv) {
        if (_tables.empty() || (_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) return false;
        pdata->_state = HashData<K, V>::State::DELETE;
        --_n;
        return true;
    }

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

哈希桶（链地址法）

哈希桶本质上是一个数组，每个元素挂接一个链表。冲突时创建节点链入该位置。STL 的 unordered_map 和 unordered_set 均基于此结构。

在负载因子为 1 时，随机数据的桶长度通常保持在常数级别，效率优于开放定址法。

unordered_map 与 unordered_set 的复用

为了共用底层哈希桶模板类，设计者巧妙利用了模板参数：

• unordered_set 传入的 Value 类型为 Key。
• unordered_map 传入的 Value 类型为 pair<Key, T>。

这样，查找和删除只需 Key，而插入时根据 Value 类型不同自然适配。

// 哈希桶定义
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 {
    typedef HashBucket<Key, Key, ..., KeyOfValue, Hash, Pred> HT;
    HT _ht;
    struct KeyOfValue { const Key& operator()(const Key& key) { return key; } };
    // ... 调用 _ht.Insert(data) ...
};

// unordered_map 封装
template<class Key, class T, class Hash, class Pred>
class unordered_map {
    typedef HashBucket<Key, std::pair<Key, T>, ..., KeyOfValue, Hash, Pred> HT;
    HT _ht;
    struct KeyOfValue { const Key& operator()(const std::pair<Key, T>& kv) { return kv.first; } };
    // ... 调用 _ht.Insert(data) ...
};

自定义类型键的处理

对于自定义类型，无法直接取模。需通过第五个模板参数 Hash 提供哈希值计算策略。同时，查找时需要比较两个对象是否相等，因此提供第六个模板参数 Pred（Equal 仿函数）。

底层插入伪代码如下：

insert(const Value &data) {
    KeyOfT key;
    int hashi = key(data) % _tables.size(); // 利用提取的 Key 计算哈希
    Node* newnode = new Node(data);
    newnode->_next = _tables[hashi];
    _tables[hashi] = newnode;
}

综上，哈希表的设计核心在于平衡空间与时间复杂度，而 STL 的实现则通过泛型编程最大化了复用性与灵活性。