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

以下是完整的哈希表实现及封装示例，涵盖了从底层结构到上层接口的完整逻辑。

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

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>
    class HashTable;

    // 迭代器定义
    template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
    struct HTIterator {
        typedef HashNode<T> Node;
        typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> 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) {}

        // 支持普通迭代器转 const 迭代器
        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;
                    } else {
                        ++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;
            // 负载因子为 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.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;
    };
}