C++ 哈希表封装：模拟实现 unordered_map 和 unordered_set

1.2.2 stl_hash_map

// stl_hash_map
template <class Key, class T, class HashFcn = hash<Key>, class EqualKey = equal_to<Key>, class Alloc = alloc>
class hash_map {
private:
    typedef hashtable<pair<const Key, T>, Key, HashFcn, select1st<pair<const Key, T> >, EqualKey, Alloc> ht;
    ht rep;
public:
    typedef typename ht::key_type key_type;
    typedef T data_type;
    typedef T mapped_type;
    typedef typename ht::value_type value_type;
    typedef typename ht::hasher hasher;
    typedef typename ht::key_equal key_equal;
    typedef typename ht::iterator iterator;
    typedef typename ht::const_iterator const_iterator;
};

1.2.3 stl_hashtable.h

// stl_hashtable.h
template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
class hashtable {
public:
    typedef Key key_type;
    typedef Value value_type;
    typedef HashFcn hasher;
    typedef EqualKey key_equal;
private:
    hasher hash;
    key_equal equals;
    ExtractKey get_key;
    typedef __hashtable_node<Value> node;
    vector<node*, Alloc> buckets;
    size_type num_elements;
public:
    typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;
    pair<iterator, bool> insert_unique(const value_type& obj);
    const_iterator find(const key_type& key) const;
};
template <class Value> struct __hashtable_node {
    __hashtable_node* next;
    Value val;
};

通过源码可以看到，结构上 hash_map 和 hash_set 跟 map 和 set 完全类似，复用同一个 hashtable 实现 key 和 key/value 结构。hash_set 传给 hash_table 的是两个 key，hash_map 传给 hash_table 的是 pair<const key, value>。

需要注意的是源码里面跟 map/set 源码类似，命名风格比较乱。下面我们会自己实现一下，统一按自己的风格来。

2. 模拟实现 unordered_map 和 unordered_set

2.1 设计思路

2.1.1 复用哈希表的框架

参考源码框架，unordered_map 和 unordered_set 复用之前实现的哈希表。这里相比源码调整一下，key 参数就用 K，value 参数就用 V，哈希表中的数据类型使用 T。

因为 HashTable 实现了泛型不知道 T 参数导致是 K，还是 pair<K,V>，那么 insert 内部进行插入时要用 K 对象转换成整形取模和 K 比较相等。因为 pair 的 value 不参与计算取模，且默认支持的是 key 和 value 一起比较相等，我们需要的是任何时候只需要比较 K 对象。所以我们在 unordered_map 和 unordered_set 层分别实现一个 MapKeyOfT 和 SetKeyOfT 的仿函数传给 HashTable 的 KeyOfT，然后 HashTable 中通过 KeyOfT 仿函数取出 T 类型对象中的 K 对象，再转换成整形取模和 K 比较相等。

2.1.2 迭代器实现

iterator 实现的大框架跟 list 的 iterator 思路一致，用一个类型封装结点的指针，再通过重载运算符实现，迭代器像指针一样访问的行为。要注意的是哈希表的迭代器是单向迭代器。

难点在于 operator++ 的实现。iterator 中有一个指向结点的指针，如果当前桶下面还有结点，则结点的指针指向下一个结点即可。如果当前桶走完了，则需要想办法计算找到下一个桶。这里的难点是结构设计的问题，参考上面的源码，我们可以看到 iterator 中除了有结点的指针，还有哈希表对象的指针，这样当前桶走完了，要计算下一个桶就相对容易多了，用 key 值计算出当前桶位置，依次往后找下一个不为空的桶。

begin() 返回第一个桶中第一个节点指针构造的迭代器，end() 返回迭代器可以用空表示。

unordered_set 的迭代器不支持修改，把 unordered_set 的第二个模板参数改成 const K 即可：

HashTable<K, const K, SetKeyOfT, Hash>_ht;

unordered_map 的 iterator 不支持修改 key 但是可以修改 value，我们把 unordered_map 的第二个模板参数 pair 的第一个参数改成 const K 即可：

HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;

当然，支持完整的迭代器还有很多细节需要修改。

2.1.3 map 支持 []

unordered_map 要支持 [] 主要需要修改 insert 返回值支持，修改 HashTable 中的 insert 返回值为：

pair<Iterator, bool> Insert(const T& data);

有了 insert，支持 [] 实现就很简单了。

2.2 完整代码示例与实践演示

HashTable.h

#pragma once
#include<vector>
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 };
inline unsigned long __stl_next_prime(unsigned long n) {
    const unsigned long* first = __stl_prime_list;
    const unsigned long* last = __stl_prime_list + __stl_num_primes;
    // >= n
    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) {
        return (size_t)key;
    }
};
// 特化
template<> struct HashFunc<string> {
    size_t operator()(const string& key) {
        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,class KeyOfT,class Hash> class HashTable;
    template<class K, class T, class Ref,class Ptr,class KeyOfT, class Hash>
    // 六个模板参数
    struct HTIterator {
        typedef HashNode<T> Node;
        typedef HashTable<K, T, KeyOfT, Hash> HT;
        typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
        Node* _node;
        const HT* _pht;
        HTIterator(Node* node, const HT* pht) :_node(node), _pht(pht) {}
        Ref operator*() { return _node->_data; }
        Ptr operator->() { return &_node->_data; }
        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;
                    }
                    else {
                        ++hashi;
                    }
                }
                if (hashi == _pht->_tables.size()) // 最后一个桶走完了，要++到 end() 位置
                {
                    // end() 中，_node 是空
                    _node = nullptr;
                }
            }
            return *this;
        }
        bool operator!=(const Self & s) const { return _node != s._node; }
        bool operator==(const Self & s) const { return _node == s._node; }
    };
    template<class K,class T,class KeyOfT,class Hash> class HashTable {
        // 友元声明
        template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
        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() :_tables(__stl_next_prime(1),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;
            }
            _n = 0;
        }
        pair<Iterator, bool> Insert(const T& data) {
            KeyOfT kot;
            if (auto it = Find(kot(data)); it != End()) return { it,false };
            Hash hs;
            // 负载因子 == 1 就开始扩容
            if (_n == _tables.size()) {
                std::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) {
            KeyOfT kot;
            Hash hs;
            size_t hashi = hs(key) % _tables.size();
            Node* cur = _tables[hashi];
            while (cur) {
                if (kot(cur->_data) == key) { return { cur,this }; }
                cur = cur->_next;
            }
            return { nullptr,this };
        }
        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 == nullptr) {
                        // 哈希桶中的第一个节点
                        _tables[hashi] = cur->_next;
                    }
                    else {
                        prev->_next = cur->_next;
                    }
                    --_n;
                    // _n 是有效数据个数，每次删除之后都要减减
                    delete cur;
                    return true;
                }
                prev = cur;
                cur = cur->_next;
            }
            return false;
        }
    private:
        std::vector<Node*> _tables; // 指针数组
        size_t _n; // 存储的有效数据个数
    };
}

unordered_set.h

#pragma once
#include"HashTable.h"
namespace jqj {
    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;
    };
}

unordered_map.h

#pragma once
#include"HashTable.h"
namespace jqj {
    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); }
        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;
    };
}

Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<unordered_map>
using namespace std;
#include"unordered_map.h"
#include"unordered_set.h"
void Print(const jqj::unordered_set<int>& s) {
    jqj::unordered_set<int>::const_iterator it = s.begin();
    while (it != s.end()) {
        // it* = 1; // 迭代器不能被修改
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}
int main() {
    jqj::unordered_set<int> us;
    us.insert(3);
    us.insert(1000);
    us.insert(2);
    us.insert(102);
    us.insert(2111);
    us.insert(22);
    jqj::unordered_set<int>::iterator it = us.begin();
    while (it != us.end()) {
        //*it = 1; // 不能被修改
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    Print(us);
    jqj::unordered_map<string, string> dict;
    dict.insert({ "string","" });
    dict.insert({ "string","" });
    dict.insert({ "left","左边" });
    dict.insert({ "right","右边" });
    // 修改
    dict["left"] = "左边";
    // 插入
    dict["insert"];
    // 插入并且修改
    dict["map"] = "地图";
    for (auto& [k, v] : dict) {
        //k += 'x'; //v += 'x';
        cout << k << ":" << v << endl;
    }
    return 0;
}

运行结果正常输出插入和查找的数据。