C++ 哈希表底层原理与完整实现

插入时，先计算哈希位置。如果该位置是 EXIST，则线性探测下一个位置。如果是 EMPTY 或 DELETE，则可以填入新数据并更新状态为 EXIST。

扩容时，不能直接用 resize 拷贝数据，因为索引会失效。正确做法是创建一个新表，遍历旧表，只提取 EXIST 状态的数据，调用插入函数重新放入新表。这样能自动处理新的哈希映射和冲突检测。

开散列实现细节：哈希桶

拉链法避免了探测带来的'聚集'问题，每个桶是一个链表。冲突时直接将节点挂到链表上。

核心结构

底层是一个指针数组，每个元素指向一个链表头结点。

template<class T>
struct HashNode {
    T _data;
    HashNode<T>* _next;
    // 构造函数等...
};

扩容优化

闭散列扩容需要重新计算所有元素的哈希值。拉链法扩容时，我们可以直接把旧表的节点'迁移'到新表，而不需要重新构造对象。遍历旧链表，根据新表大小重新计算哈希位置，将节点头插到新表中即可。这样减少了内存分配和析构的开销。

删除与析构

删除时需要找到前驱节点来修改指针。由于底层是动态分配的节点，析构函数必须手动释放链表内存，否则会造成内存泄漏。vector 本身只会释放指针数组的空间，不会递归释放节点内容。

迭代器的封装

哈希表的迭代器需要能够跨越不同的桶进行遍历。当当前桶的链表遍历完后，需要找到下一个非空的桶。

• 前置声明：由于迭代器依赖哈希表类，而哈希表类又包含迭代器定义，需要使用模板前置声明避免循环依赖。
• const 正确性：普通迭代器返回可修改的引用，const 迭代器返回 const 引用。对于 unordered_map，Key 是不可修改的，Value 是可修改的。
• 类型转换：为了兼容不同场景，普通迭代器可以隐式转换为 const 迭代器，这需要在构造函数中支持跨类型构造。

通用封装：unordered_map 与 set

最后，我们将哈希表封装成标准的关联容器。

• unordered_set：内部存储 Key，KeyOfT 仿函数直接返回 Key。
• unordered_map：内部存储 pair<const K, V>，KeyOfT 仿函数返回 first。

通过模板特化，我们可以针对 string 等类型优化哈希函数，例如使用多项式累加而非简单的首字符映射，以减少冲突概率。

完整代码示例

以下是整合后的哈希表及封装类实现，包含了开放定址法和拉链法的框架，以及完整的迭代器支持。

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

using namespace std;

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

    template<class K, class V, class HashFunc = DefaultHashFunc<K>>
    class HashTable {
    public:
        HashTable() {
            _table.resize(10);
        }

        bool Insert(const pair<K, V>& kv) {
            if (Find(kv.first)) {
                return false;
            }
            // 负载因子控制，大于 0.7 扩容
            if (_n * 10 / _table.size() >= 7) {
                size_t newSize = _table.size() * 2;
                HashTable<K, V, HashFunc> newHT;
                newHT._table.resize(newSize);
                for (size_t i = 0; i < _table.size(); i++) {
                    if (_table[i]._state == EXIST) {
                        newHT.Insert(_table[i]._kv);
                    }
                }
                _table.swap(newHT._table);
            }

            HashFunc hf;
            size_t hashi = hf(kv.first) % _table.size();
            while (_table[hashi]._state == EXIST) {
                ++hashi;
                hashi %= _table.size();
            }
            _table[hashi]._kv = kv;
            _table[hashi]._state = EXIST;
            ++_n;
            return true;
        }

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

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

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

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 Ptr, class Ref, class KeyOfT, class HashFunc>
    struct HTIterator;

    template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
    struct HTIterator {
        typedef HashNode<T> Node;
        typedef HTIterator Self;
        typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> Iterator;
        
        Node* _node;
        const HashTable<K, T, KeyOfT, HashFunc>* _pht;

        HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht)
            :_node(node), _pht(pht) {}

        HTIterator(const Iterator& it)
            :_node(it._node), _pht(it._pht) {}

        Ref operator*() { return _node->_data; }
        Ptr operator->() { return &_node->_data; }

        Self& operator++() {
            if (_node->_next) {
                _node = _node->_next;
            } else {
                KeyOfT kot;
                HashFunc hf;
                size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
                ++hashi;
                while (hashi < _pht->_table.size()) {
                    if (_pht->_table[hashi]) {
                        _node = _pht->_table[hashi];
                        return *this;
                    }
                    ++hashi;
                }
                _node = nullptr;
            }
            return *this;
        }

        bool operator!=(const Self& s) { return _node != s._node; }
        bool operator==(const Self& s) { return _node == s._node; }
    };

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

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

        const_iterator end() const { return const_iterator(nullptr, this); }

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

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

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