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

开散列实现：拉链法

拉链法将数组设计为指针数组，每个位置挂一个链表。冲突时直接在链表上添加节点，互不影响。

核心逻辑

1. 插入：计算 Hash 值，头插法将新节点加入链表。
2. 查找：遍历对应位置的链表。
3. 删除：找到节点后断开连接并释放内存。
4. 扩容：同样需要 Rehash，将旧链表节点迁移到新表。

// HashTable.h (Chaining Version)
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;

    public:
        HashTable() {
            _table.resize(10, nullptr);
        }

        ~HashTable() {
            for (size_t i = 0; i < _table.size(); i++) {
                Node* cur = _table[i];
                while (cur) {
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
                _table[i] = nullptr;
            }
        }

        pair<iterator, bool> Insert(const T& data) {
            KeyOfT kot;
            iterator it = Find(kot(data));
            if (it != end()) {
                return make_pair(it, false);
            }
            HashFunc hf;
            // 负载因子为 1 时扩容
            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;
    };
}

封装 unordered_map 与 unordered_set

为了模拟标准库行为，我们需要在哈希表之上封装 unordered_map 和 unordered_set，并实现迭代器。

迭代器设计

迭代器需要能够遍历整个哈希表，而不仅仅是单个链表。因此迭代器内部需要持有哈希表对象的指针，以便在链表遍历结束后跳转到下一个非空桶。

关键点：

1. 前置声明：由于迭代器和哈希表互相依赖，需要使用 class HashTable; 进行前置声明。
2. KeyOfT：为了统一处理 set（只有 Key）和 map（Key+Value），引入仿函数提取 Key。
3. Const 正确性：区分普通迭代器和常量迭代器，确保 Key 不可修改。

完整封装示例

// 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(); }
        const_iterator begin() const { return _ht.begin(); }
        const_iterator end() const { 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>::const_iterator iterator;
        typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_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;
    };
}

通过以上步骤，我们完成了从哈希表底层原理到上层容器封装的全过程。理解这些细节有助于在实际开发中更好地优化数据结构选择及排查性能问题。