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

1. unordered 系列关联式容器

首先来看哈希，主要关注关联式容器 unordered_map 和 unordered_set。它们底层基于哈希表实现，用法与 map/set 类似，但存在关键区别：unordered 系列使用单向迭代器（没有 rbegin/rend），且遍历时数据无序。相比之下，红黑树实现的 map/set 是有序的。

它主要用于去重，不支持排序，当然也有 multi 版本。再看 unordered_map 的表现：

2. 哈希基础

什么是哈希？回顾之前的搜索方式：暴力查找效率低；有序数组二分查找虽快但增删改不便；平衡搜索树解决了部分问题。哈希（散列）则是另一种思路，本质是在存储的值与存储位置之间建立映射关系。

看一个计数排序的样例：

最小值 15 映射到第一个位置，最大值 30 映射到最后一个，中间依次对应。这就是直接定址法，适用于值分布集中的场景。但如果数据分散，空间消耗会过大。此时若数据比较分散，我们采用除留余数法：

假设空间大小为 20，key % 20 确定位置。但这会引发哈希冲突，即不同值映射到同一位置。例如 27 和 47 模 20 都是 7：

解决冲突主要有两种方式：闭散列（开放定址法）和拉链法（哈希桶）。闭散列是在冲突时按规则找下一个空位；拉链法则是该位置存指针，用链表链接多个值。

3. 闭散列——开放定址法

以线性探测为例，空间大小设为 10：

当插入 111 和 44 发生冲突时，向后探测直到找到空位：

如果遍历完没找到空位怎么办？比如只剩 19 个位置，来了个 29 越界了？不需要立刻扩容，可以绕回开头继续找：

查找逻辑也需注意。查 44 时，算出位置 4 无值，需继续往后找直到遇到空位或目标值：

删除操作更需谨慎。直接抹成 0 会影响后续查找（如 44 会被误判为不存在）。因此需要状态标记：EXIST（存在）、EMPTY（空）、DELETE（已删除）。删除时将状态设为 DELETE，查找时跳过 DELETE 直到 EMPTY：

代码实现上，定义 KV 结构并枚举状态。使用 vector 存储 HashData，额外维护有效数据个数 n：

插入时计算起始位置 key % size。注意这里模的是 size 而非 capacity，避免下标越界：

若位置被占，继续探测；遇到 DELETE 状态也可填入新值：

负载因子控制很重要。不能等满了再扩容，否则查找效率下降。通常负载因子达到 0.7 左右触发扩容：

扩容逻辑：若 table 为空则初始化，否则若 n / size >= 0.7 则扩容 2 倍。关键点在于重新映射，不能直接 resize，需遍历旧表重新插入新表：

复用 insert 函数可简化逻辑，最后交换新旧表：

查找返回 HashData 指针，删除时修改状态并减少 n：

关于 Key 类型，整型可直接取模，字符串等非整型需仿函数转换：

默认仿函数处理整型，特化版本处理 string（累加 ASCII 值并乘以 131 以减少冲突）：

模板特化可让接口更简洁，无需手动传仿函数：

4. 二次探测及拉链法

线性探测可能导致聚集效应。二次探测通过 i^2 步长分散冲突：

拉链法（哈希桶）将数组改为指针数组，冲突时挂链表：

框架搭建：vector<Node*> _table，记录有效数据 n。构造时 resize 初始大小：

插入时头插法，先算位置，新节点 next 指向原头结点，更新表头：

扩容时建议直接迁移节点而非重建，节省内存开销：

析构函数需释放所有节点，因为 vector 只管理指针数组：

5. 完整代码

//HashTable.h
#pragma once
#include <vector>
#include <string>
#include <stdio.h>

template<class K>
struct DefaultHashFunc {
    size_t operator()(const K& key) { return (size_t)key; }
};

template<>
struct DefaultHashFunc<string> {
    size_t operator()(const string& str) {
        size_t hash = 0;
        for (auto ch : str) {
            hash *= 131;
            hash += ch;
        }
        return hash;
    }
};

namespace open_address {
    enum STATE { EXIST, EMPTY, DELETE };
    template<class K, class V>
    struct HashData {
        pair<K, V> _kv;
        STATE _state = EMPTY;
    };
    // ... (省略部分实现细节以保持篇幅)
}

6. 封装

开始封装 set 和 map。set 中元素类型为 K，map 为 pair<K,V>。需引入 KeyOfT 仿函数提取 Key：

迭代器封装是关键。需支持 ++ 操作跨越桶边界，并处理 const 正确性：

operator++ 逻辑：若当前节点有 next 则走链表，否则找下一个非空桶：

需保存哈希表指针以便访问 _table：

const 迭代器需限制返回值不可修改，通过模板参数区分普通与 const 迭代器：

Map 的 operator[] 需支持插入新键值对：

7. 最终完整代码

//unordered_map.h
#pragma once
#include "HashTable.h"
namespace yxx {
    template<class K, class V>
    class unordered_map {
        struct MapKeyOfT {
            const K& operator()(const pair<const K, V>& kv) { return kv.first; }
        };
    public:
        typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
        typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator const_iterator;
        iterator begin() { return _ht.begin(); }
        iterator end() { return _ht.end(); }
        pair<iterator, bool> insert(const pair<K, V>& kv) { return _ht.Insert(kv); }
        V& operator[](const K& key) {
            pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
            return ret.first->second;
        }
    private:
        hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT> _ht;
    };
}

//unordered_set.h
#pragma once
#include "HashTable.h"
namespace yxx {
    template<class K>
    class unordered_set {
        struct SetKeyOfT {
            const K& operator()(const K& key) { return key; }
        };
    public:
        typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator iterator;
        typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator const_iterator;
        iterator begin() const { return _ht.begin(); }
        iterator end() const { return _ht.end(); }
        pair<iterator, bool> insert(const K& key) {
            pair<typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);
            return pair<const_iterator, bool>(ret.first, ret.second);
        }
    private:
        hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
    };
}

//HashTable.h (核心实现)
#pragma once
#include <vector>
#include <string>
#include <stdio.h>

template<class K>
struct DefaultHashFunc {
    size_t operator()(const K& key) { return (size_t)key; }
};

template<>
struct DefaultHashFunc<string> {
    size_t operator()(const string& str) {
        size_t hash = 0;
        for (auto ch : str) {
            hash *= 131;
            hash += ch;
        }
        return hash;
    }
};

namespace hash_bucket {
    template<class T>
    struct HashNode {
        T _data;
        HashNode<T>* _next;
        HashNode(const T& data) :_data(data), _next(nullptr) {}
    };

    template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
    class HashTable {
        typedef HashNode<T> Node;
        template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
        friend struct HTIterator;
    public:
        typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
        typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;

        iterator begin() {
            for (size_t i = 0; i < _table.size(); i++) {
                Node* cur = _table[i];
                if (cur) return iterator(cur, this);
            }
            return iterator(nullptr, this);
        }
        iterator end() { return iterator(nullptr, this); }

        pair<iterator, bool> Insert(const T& data) {
            KeyOfT kot;
            iterator it = Find(kot(data));
            if (it != end()) return make_pair(it, false);
            HashFunc hf;
            if (_n == _table.size()) {
                size_t newSize = _table.size() * 2;
                vector<Node*> newTable(newSize, nullptr);
                for (size_t i = 0; i < _table.size(); i++) {
                    Node* cur = _table[i];
                    while (cur) {
                        Node* next = cur->_next;
                        size_t hashi = hf(kot(cur->_data)) % newSize;
                        cur->_next = newTable[hashi];
                        newTable[hashi] = cur;
                        cur = next;
                    }
                    _table[i] = nullptr;
                }
                _table.swap(newTable);
            }
            size_t hashi = hf(kot(data)) % _table.size();
            Node* newnode = new Node(data);
            newnode->_next = _table[hashi];
            _table[hashi] = newnode;
            ++_n;
            return make_pair(iterator(newnode, this), true);
        }

        iterator Find(const K& key) {
            HashFunc hf; KeyOfT kot;
            size_t hashi = hf(key) % _table.size();
            Node* cur = _table[hashi];
            while (cur) {
                if (kot(cur->_data) == key) return iterator(cur, this);
                cur = cur->_next;
            }
            return end();
        }

        bool Erase(const K& key) {
            HashFunc hf; KeyOfT kot;
            size_t hashi = hf(key) % _table.size();
            Node* prev = nullptr; Node* cur = _table[hashi];
            while (cur) {
                if (kot(cur->_data) == key) {
                    if (prev == nullptr) _table[hashi] = cur->_next;
                    else prev->_next = cur->_next;
                    delete cur; --_n; return true;
                }
                prev = cur; cur = cur->_next;
            }
            return false;
        }

    private:
        vector<Node*> _table;
        size_t _n = 0;
    };
}