C++ 实战：基于哈希表封装 unordered_map 与 unordered_set

2. 模拟实现 unordered_map 和 unordered_set

2.1 复用哈希表的框架设计

相比源码，我们对接口做了一些调整。unordered_map 和 unordered_set 的底层都是 HashTable，但由于 HashTable 是泛型的，它不知道传入的 T 到底是单纯的 K 还是 pair<K, V>。

在插入或查找时，我们需要对 Key 进行哈希计算和比较。对于 pair 类型，默认的比较逻辑可能涉及 value，但我们只关心 Key。因此，我们在 unordered_map 和 unordered_set 层分别实现一个仿函数 MapKeyOfT 和 SetKeyOfT，专门用于从存储对象中提取 Key，再传给 HashTable 使用。

// MyUnorderedSet.h
namespace My_UnorderedSet {
template<class K,class Hash= HashFunc<K>>
class unordered_set {
    struct SetKeyOfT {
        const K& operator()(const K& key) { return key; }
    };
public:
    bool insert(const K& key) { return _ht.Insert(key); }
private:
    hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
};
}

// MyUnorderedMap.h
namespace My_UnorderedMap {
template<class K,class V,class Hash= HashFunc<K>>
class unordered_map {
    struct MapKeyOfT {
        const K& operator()(const pair<K, V>& kv) { return kv.first; }
    };
public:
    bool insert(const pair<K, V>& kv) { return _ht.Insert(kv); }
private:
    hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht;
};
}

2.2 迭代器 (Iterator) 的实现

哈希表的迭代器实现起来比链表稍微复杂一点，因为它是单向遍历的。核心难点在于 operator++：当当前桶内的节点遍历完后，如何找到下一个不为空的桶？

参考 SGI-STL 的设计，迭代器内部除了保存当前节点的指针，还需要持有哈希表对象的指针。这样当当前桶走空时，可以通过哈希表对象计算出当前 Key 对应的桶位置，然后向后线性探测，直到找到下一个有数据的桶。

另外，unordered_set 的迭代器不支持修改 key，所以我们将第二个模板参数设为 const K；unordered_map 同理，key 不可变，value 可变，所以 pair 的第一个参数设为 const K。

// HashTable.h 中的迭代器实现片段
template<class K,class T,classRef,classPtr,classKeyOfT,classHash>
struct HTIterator {
    typedef HashNode<T> Node;
    typedef HashTable<K, T, KeyOfT, Hash> HT;
    Node* _node;
    const HT* _pht;

    Self& operator++() {
        if (_node->_next) {
            // 当前桶还没走完，直接指向下一个节点
            _node = _node->_next;
        } else {
            // 当前桶走完了，需要找下一个不为空的桶
            KeyOfT kot;
            Hash hs;
            size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
            hashi++;
            while (hashi < _pht->_tables.size()) {
                if (_pht->_tables[hashi]) {
                    _node = _pht->_tables[hashi];
                    break;
                }
                ++hashi;
            }
            if (hashi == _pht->_tables.size()) {
                // 所有桶都走完了，置为 end()
                _node = nullptr;
            }
        }
        return *this;
    }
    // ... 其他运算符重载 ...
};

2.3 map 支持 [] 操作符

要让 unordered_map 支持 [] 操作符，本质上是先尝试插入，如果存在则返回引用，不存在则插入并返回新元素的引用。这要求 insert 方法返回 pair<Iterator, bool>，以便我们判断是否插入成功。

V& operator[](const K& key) {
    pair<iterator,bool> ret = insert({ key, V() });
    return ret.first->second;
}

2.4 完整代码实现

下面是整合后的完整代码，包含了哈希表的核心逻辑、扩容机制以及容器的封装。

#pragma once
#include <iostream>
#include <vector>
using namespace std;

inline unsigned long __stl_next_prime(unsigned long n) {
    static const int __stl_num_primes = 28;
    static const unsigned long __stl_prime_list[__stl_num_primes] = {
        53,97,193,389,769,1543,3079,6151,12289,24593,49157,98317,
        196613,393241,786433,1572869,3145739,6291469,12582917,25165843,
        50331653,100663319,201326611,402653189,805306457,1610612741,
        3221225473,4294967291
    };
    const unsigned long* first = __stl_prime_list;
    const unsigned long* last = __stl_prime_list + __stl_num_primes;
    const unsigned long* pos = lower_bound(first, last, n);
    return pos == last ? *(last - 1) : *pos;
}

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

template<>
struct HashFunc<string> {
    size_t operator()(const string& key) const {
        size_t hash = 0;
        for (auto ch : key) {
            hash += ch;
            hash *= 131;
        }
        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,classKeyOfT,classHash>
class HashTable {
    template<class K,class T,classRef,classPtr,classKeyOfT,classHash>
    friend struct HTIterator;
    
    typedef HashNode<T> Node;
public:
    typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
    typedef HTIterator<K, T,const T&,const T*, KeyOfT, Hash> ConstIterator;

    Iterator Begin() {
        if (_n == 0) return End();
        for (size_t i = 0; i < _tables.size(); i++) {
            if (_tables[i]) return Iterator(_tables[i], this);
        }
        return End();
    }
    Iterator End() { return Iterator(nullptr, this); }
    ConstIterator Begin() const {
        if (_n == 0) return End();
        for (size_t i = 0; i < _tables.size(); i++) {
            if (_tables[i]) return ConstIterator(_tables[i], this);
        }
        return End();
    }
    ConstIterator End() const { return ConstIterator(nullptr, this); }

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

    pair<Iterator, bool> Insert(const T& data) {
        KeyOfT kot;
        Iterator it = Find(kot(data));
        if (it != End()) return { it, false };

        Hash hs;
        // 负载因子到 1 扩容
        if (_n == _tables.size()) {
            vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);
            for (size_t i = 0; i < _tables.size(); i++) {
                Node* cur = _tables[i];
                while (cur) {
                    Node* next = cur->_next;
                    size_t hashi = hs(kot(cur->_data)) % newtables.size();
                    cur->_next = newtables[hashi];
                    newtables[hashi] = cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
            _tables.swap(newtables);
        }

        size_t hashi = hs(kot(data)) % _tables.size();
        Node* newnode = new Node(data);
        newnode->_next = _tables[hashi];
        _tables[hashi] = newnode;
        ++_n;
        return { Iterator(newnode, this), true };
    }

    Iterator Find(const K& key) {
        Hash hs;
        KeyOfT kot;
        size_t hashi = hs(key) % _tables.size();
        Node* cur = _tables[hashi];
        while (cur) {
            if (kot(cur->_data) == key) return Iterator(cur, this);
            cur = cur->_next;
        }
        return End();
    }

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

private:
    vector<Node*> _tables;
    size_t _n;
};

template<class K,class T,classRef,classPtr,classKeyOfT,classHash>
struct HTIterator {
    typedef HashNode<T> Node;
    typedef HashTable<K, T, KeyOfT, Hash> HT;
    Node* _node;
    const HT* _pht;

    HTIterator(Node* node, const HT* pht) : _node(node), _pht(pht) {}

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

    Ref operator*() { return _node->_data; }
    Ptr operator->() { return &_node->_data; }
    bool operator!=(const Self& s) const { return _node != s._node; }
    bool operator==(const Self& s) const { return _node == s._node; }
};
}

#include "HashTable.h"

namespace My_UnorderedSet {
template<class K,class Hash= HashFunc<K>>
class unordered_set {
    struct SetKeyOfT {
        const K& operator()(const K& key) { return key; }
    };
public:
    typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
    typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator 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 K& key) { return _ht.Insert(key); }
    iterator find(const K& key) { return _ht.Find(key); }
    bool erase(const K& key) { return _ht.Erase(key); }

private:
    hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
};
}

namespace My_UnorderedMap {
template<class K,class V,class Hash= HashFunc<K>>
class unordered_map {
    struct MapKeyOfT {
        const K& operator()(const pair<K, V>& kv) { return kv.first; }
    };
public:
    typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
    typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator 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); }
    iterator find(const K& key) { return _ht.Find(key); }
    bool erase(const K& key) { return _ht.Erase(key); }
    V& operator[](const K& key) {
        pair<iterator, bool> ret = insert({ key, V() });
        return ret.first->second;
    }

private:
    hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
}