C++ unordered 系列容器使用与模拟实现

3. unordered_map 与 map 的差异

逻辑与上述类似。unordered_map 不保证 Key 有序，仅支持等于比较；map 则保持 Key 有序。性能上 unordered_map 通常更优，因为避免了树结构的平衡维护开销。

4. 哈希相关接口

日常开发中主要关注以下接口：

注意 rehash 会改变元素的迭代顺序，当负载因子即将超过阈值时容器会自动执行。reserve 则是针对元素数量的优化建议。

用哈希表封装 my_stl::unordered_map 和 my_stl::unordered_set

1. 源码框架分析

SGI-STL 早期版本（C++11 之前）实现了非标准的 hash_map/hash_set，核心结构复用同一个 hashtable。unordered_map 和 unordered_set 本质上是对通用哈希表的二次封装：

• hash_set：传给 hashtable 的是两个 key（实际存储 value，提取 key 用于索引）。
• hash_map：传给 hashtable 的是 pair<const Key, Value>。

我们在模拟实现时，可以沿用这一思路，但统一命名风格，使其更符合现代 C++ 规范。

2. 模拟实现核心步骤

2.1 构建通用哈希表框架

我们需要一个通用的 HashTable 类，支持泛型 T，并通过 KeyOfT 仿函数提取键值。这样无论是存 K 还是存 pair<K, V>，都能正确计算哈希值。

// MyStlHashTable.h
namespace my_stl {
    template<class K> struct HashFunc {
        size_t operator()(const K& key) { return (size_t)key; }
    };
    
    // 特化 string 类型的哈希
    template<> struct HashFunc<string> {
        size_t operator()(const string& key) {
            size_t hash = 0;
            for (auto e : key) {
                hash *= 131;
                hash += e;
            }
            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 Hash>
        class HashTable;

        // 单向迭代器
        template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
        struct HTIterator {
            typedef HashNode<T> Node;
            typedef HTIterator Self;
            Node* _node;
            const HashTable<K, T, KeyOfT, Hash>* _pht;

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

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

            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]) break;
                        ++hashi;
                    }
                    if (hashi == _pht->_tables.size()) {
                        _node = nullptr;
                    } else {
                        _node = _pht->_tables[hashi];
                    }
                }
                return *this;
            }
        };

        // 哈希表主体
        template<class K, class T, class KeyOfT, class Hash>
        class HashTable {
            friend struct HTIterator<K, T, T*, T&, KeyOfT, Hash>;
            friend struct HTIterator<K, T, const T*, const T&, KeyOfT, Hash>;
            
            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); }

            // 扩容质数选择
            inline unsigned long __stl_next_prime(unsigned long n) {
                static const unsigned long 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 = primes;
                const unsigned long* last = primes + sizeof(primes)/sizeof(primes[0]);
                const unsigned long* pos = lower_bound(first, last, n);
                return pos == last ? *(last - 1) : *pos;
            }

            HashTable() { _tables.resize(__stl_next_prime(_tables.size()), nullptr); }
            ~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 make_pair(it, false);

                Hash hs;
                size_t hashi = hs(kot(data)) % _tables.size();

                // 负载因子==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 new_hashi = hs(kot(cur->_data)) % newtables.size();
                            cur->_next = newtables[new_hashi];
                            newtables[new_hashi] = cur;
                            cur = next;
                        }
                        _tables[i] = nullptr;
                    }
                    _tables.swap(newtables);
                    hashi = hs(kot(data)) % _tables.size();
                }

                Node* newnode = new Node(data);
                newnode->_next = _tables[hashi];
                _tables[hashi] = newnode;
                ++_n;
                return make_pair(Iterator(newnode, this), true);
            }

            Iterator Find(const K& key) {
                KeyOfT kot;
                Hash hs;
                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) {
                KeyOfT kot;
                Hash hs;
                size_t hashi = hs(key) % _tables.size();
                Node* prev = nullptr;
                Node* cur = _tables[hashi];
                while (cur) {
                    if (kot(cur->_data) == key) {
                        if (!prev) _tables[hashi] = cur->_next;
                        else prev->_next = cur->_next;
                        delete cur;
                        --_n;
                        return true;
                    }
                    prev = cur;
                    cur = cur->_next;
                }
                return false;
            }

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

2.2 封装 unordered_set 和 unordered_map

有了哈希表基础，只需定义 KeyOfT 仿函数并适配模板参数即可。

// MyUnorderedSet.h
namespace my_stl {
    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;
    };
}

// MyUnorderedMap.h
namespace my_stl {
    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); }
        
        // operator[] 实现依赖于 insert 返回值
        V& operator[](const K& key) {
            pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
            return ret.first->second;
        }

        iterator Find(const K& key) { return _ht.Find(key); }
        bool Erase(const K& key) { return _ht.Erase(key); }

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

3. 关键实现细节解析

1. KeyOfT 仿函数：这是泛型设计的关键。HashTable 内部不知道 T 是 K 还是 pair<K, V>，必须通过 KeyOfT 提取出真正的 Key 进行哈希计算和比较。unordered_set 直接返回 Key，unordered_map 则取 pair 的 first。
2. 迭代器遍历：哈希表迭代器是单向的。operator++ 不仅要移动到同桶的下一个节点，还要在桶空时向后寻找下一个非空桶。这需要迭代器持有哈希表指针以访问 buckets 数组。
3. 扩容重哈希：当负载因子达到 1 时，需要创建更大的质数大小数组，并将旧节点逐个迁移到新位置。注意迁移过程中要重新计算哈希值，否则数据会错乱。
4. const 正确性：unordered_set 的 Key 不可修改，所以内部存储为 const K。unordered_map 允许修改 Value，但 Key 不可变，所以 pair 中 Key 部分设为 const。

通过这种方式，我们不仅复用了底层哈希表，还清晰地分离了数据结构与业务逻辑，便于维护和扩展。