C++ 哈希表原理与 STL 容器实现详解

unordered_multiset / unordered_multimap

这两个容器与 multiset/multimap 类似，主要区别在于支持 Key 冗余，其他差异同上。

哈希基础

哈希（Hash）又称散列，是一种组织数据的方式。本质就是通过哈希函数把关键字 Key 跟存储位置建立一个映射关系，查找时通过这个哈希函数计算出 Key 存储的位置，进行快速查找。

直接定址法

当关键字的范围比较集中时，比如一组关键字都在 [0, 99] 之间，那么开一个 100 个数的数组，每个关键字的值直接就是存储位置的下标。再比如一组关键字值都在 [a, z] 的小写字母，那么我们开一个 26 个数的数组，每个关键字 ASCII 码 - 字符 a 得到的值就是存储位置的下标。也就是说直接定址法本质即用关键字计算出一个绝对位置或者相对位置。

哈希冲突

使用直接定址法，当关键字的范围比较分散时，会很浪费内存甚至内存不够用。假设我们只有数据范围是 [0, 9999] 的 N 个值，要映射到一个 M 个空间的数组中（一般 M >= N），那么就要借助哈希函数 h(x)，关键字 key 被放到数组的 h(key) 位置，注意，h(key) 计算出的值必须在 [0, M) 之间。

这里存在的一个问题是，两个不同的 key 可能会映射到同一个位置，这种问题即哈希冲突，或者哈希碰撞。理想情况是找出一个好的哈希函数避免冲突，但是实际场景中，冲突是不可避免的，所以我们尽可能设计出优秀的哈希函数，减少冲突的次数，同时也要去设计出解决冲突的方案。

负载因子

假设哈希表中已经映射存储了 N 个值，哈希表的大小为 M，那么负载因子 = N/M。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低。

将关键字转为 size_t

将关键字映射到数组中位置，一般是整数好做映射计算，如果不是整数，我们要想办法转换成整数。源码中用仿函数 Hash 把 key 转换成 size_t。如果遇到像 string、Date 无法强转的，则自己实现，string 较为常用，可以特化模板。

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

template<>
struct HashFunc<string>
{
    size_t operator()(const string& s)
    {
        size_t hash = 0;
        for (auto& e : s)//可以有效避免"abcd"，"bcad"冲突的情况
        {
            hash += e;
            hash *= 131;
        }
        return hash;
    }
};

哈希函数设计

一个好的哈希函数应该让 N 个关键字被等概率且均匀地散列分布到哈希表的 M 个空间中，实际中很难做到，但是要尽量往这个方向去考量设计。

除法散列法 / 除留余数法

除法散列法也叫除留余数法，假设哈希表的大小为 M，key 除以 M 的余数作为映射位置的下标，即哈希函数为：h(key) = key % M。

使用除法散列法时，要尽量避免 M 为某些值，如 2 的幂，10 的幂等。如果是 2^x，key % 2^x 本质相当于保留 key 的后 X 位（把 key 转成二进制表示的位），那么后 x 位相同的值，计算出的哈希值都是一样的，就冲突了。如果是 10^x，保留的都是 10 进值的后 x 位，如：{112, 12312}，如果 M 是 100，也就是 10^2，那么计算出的哈希值都是 12。

所以，使用除法散列法时，建议 M 取不太接近 2 的整数次幂的一个素数。

sgi 版本的哈希表使用的方法，给了一个近似 2 倍的素数表。

inline unsigned long __stl_next_prime(unsigned long n)//会频繁调用，inline 修饰，减少消耗
{
    // Note: assumes long is at least 32 bits.
    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);//在下标[first,last)范围内，找大于等于 n 的数
    return pos == last ? *(last - 1) : *pos;
}

初始时哈希表的大小 M 可以为 __stl_next_prime(0)，即 M=53，此时 M 既不接近 2^5，也不接近 2^6，同时也是素数。扩容后 M=97，也实现了近似 2 倍扩容。

哈希函数还有其他方法，如乘法散列法、全域散列法等。

处理哈希冲突：开放定址法

在开放定址法中，所有的元素都放到哈希表，当一个关键字 key 用哈希函数计算出的位置冲突了，则按照某种规则找到一个没有存储数据的位置进行存储。规则有三种：线性探测、二次探测、双重探测。开放定址法要求负载因子小于 1。

线性探测

1. 从发生冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，则回绕到哈希表头的位置。
2. h(key)=hash0=key % M，hash0 位置冲突了，则线性探测公式为：hc(key,i)=hashi=(hash0+i) % M，i={1，2，3……M-1}。由于负载因子小于 1，哈希表中一定有空位置，所以最多探测 M-1 次，一定能找到一个存储 key 的位置。
3. 如果 hash0 位置连续冲突，hash0，hash1，hash2 位置已经存储数据，后续映射到 hash0，hash1，hash2，hash3 的值都会争夺 hash3 位置，这种现象叫做群集/堆积。二次探测可在一定程度上改善。

二次探测

1. 从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找到下一个没有存储数据的位置为止，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置。
2. h(key)=hash0=key % M，hash0 位置冲突了，则二次探测公式为：hc(key,i)=hashi=(hash0 ± i^2) % M，i={1，2，3……M/2}。
3. 当 hashi=(hash0 - i^2) % M 时，若 hashi<0，则 hashi+=M。

开放定址法线性探测代码实现

要给每个存储位置加一个状态标识，否则删除一些值以后，会影响后面冲突的值的查找。例如删除 30，查找 20，用哈希函数求得映射下标为 9，但是下标为 9 的位置已经为空，没找到，但哈希表中其实又是有 20 的。

给每个存储位置加一个标识状态 {EXIST, DELETE, EMPTY}。查找一个 key，求得映射位置 h(key)，发现状态为 EMPTY，说明整个哈希表中没有 key。如果哈希表的其他位置存在 key，表明因为冲突，h(key) 位置已经被别的值占了，则 h(key) 位置的状态应是 EXIST 或 DELETE，矛盾，所以整个哈希表中绝对没有 key。

控制负载因子到 0.7 时扩容。

如果 key 不能取模则用仿函数转成 size_t。

#include <vector>
enum State { EXIST, EMPTY, DELETE };

template<class K, class V>
struct HashData
{
    pair<K, V> _kv;
    State _state = EMPTY;
};

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

template<>
struct HashFunc<string>
{
    size_t operator()(const string& s)
    {
        size_t hash = 0;
        for (auto& e : s)
        {
            hash += e;
            hash *= 131;
        }
        return hash;
    }
};

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

namespace open_address
{
    template<class K, class V, class Hash = HashFunc<K>>
    class HashTable
    {
    public:
        HashTable() :_tables(__stl_next_prime(0)),_n(0){}

        bool Insert(const pair<K, V>& kv)
        {
            if (Find(kv.first)) return false;
            if (_n * 10 / _tables.size() >= 7)//扩容
            {
                HashTable<K, V, Hash> newht;
                newht._tables.resize(__stl_next_prime(_tables.size() + 1));
                for (auto& e : _tables)
                {
                    if (e._state == EXIST) newht.Insert(e._kv);
                }
                _tables.swap(newht._tables);
            }
            Hash hash;
            size_t hash0 = hash(kv.first) % _tables.size();
            size_t hashi = hash0;
            size_t i = 1;
            while (_tables[hashi]._state == EXIST)
            {
                hashi = (hash0 + i) % _tables.size();
                i++;
            }
            _tables[hashi]._kv = kv;
            _tables[hashi]._state = EXIST;
            ++_n;
            return true;
        }

        HashData<K, V>* Find(const K& key)
        {
            Hash hash;
            size_t hash0 = hash(key) % _tables.size();
            size_t hashi = hash0;
            size_t i = 1;
            while (_tables[hashi]._state != EMPTY)
            {
                if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
                    return &_tables[hashi];
                hashi = (hash0 + i) % _tables.size();
                i++;
            }
            return nullptr;
        }

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

    private:
        vector<HashData<K, V>> _tables;
        size_t _n;//记录数据个数
    };
}

测试

#include "HashTable.h"
int main()
{
    open_address::HashTable<int, int> ht;
    int a[] = {19, 30, 5, 36, 13, 20, 21, 12};
    for (auto e : a)
    {
        ht.Insert({ e,e });
    }
    if (ht.Find(13)) ht.Erase(13);
    else cout << "没找到" << endl;
    return 0;
}

如果 key 为日期类，则要自己实现仿函数。

struct Date
{
    int _year;
    int _month;
    int _day;
    Date(int year = 1, int month = 1, int day = 1) :_year(year),_month(month),_day(day){}
    bool operator==(const Date& d)
    {
        return _year == d._year && _month == d._month && _day == d._day;
    }
};

struct DateHashFunc
{
    size_t operator()(const Date& d)
    {
        size_t hash = 0;
        hash += d._year; hash *= 131;
        hash += d._month; hash *= 131;
        hash += d._day; hash *= 131;
        return hash;
    }
};

int main()
{
    string a1[] = {"sort", "insert", "abcd", "bcad", "aadd"};
    open_address::HashTable<string, string> ht;
    for (auto& e : a1) ht.Insert({ e,e });
    int a2[] = {-19, -30, 5, 36, 13, 20, 21, 12};
    open_address::HashTable<int, int> ht1;
    for (auto& e : a2) ht1.Insert({ e,e });
    open_address::HashTable<Date, int, DateHashFunc> ht2;
    ht2.Insert({{2026,1,2},1});
    ht2.Insert({{2026,2,1},2});
    return 0;
}

处理哈希冲突：链地址法

开放定址法中所有的元素都放到哈希表里，链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，则把这些冲突的数据链接成一个链表，挂在哈希表这个位置下面，链地址法也叫做拉链法或者哈希桶。

链地址法对负载因子没有要求，我们把负载因子控制在 1，如果某个桶特别长时，当桶的长度大于 8，就把链表转成红黑树。

代码实现

namespace hash_bucket
{
    template<class K, class V>
    struct HashNode
    {
        pair<K, V> _kv;
        HashNode<K, V>* _next;
        HashNode(const pair<K,V>& kv):_kv(kv),_next(nullptr){}
    };

    template<class K, class V, class Hash = HashFunc<K>>
    class HashTable
    {
        typedef HashNode<K, V> Node;
    public:
        HashTable() :_tables(__stl_next_prime(0)),_n(0){}

        //拷贝构造
        HashTable(const HashTable<K, V, Hash>& ht)
        {
            _tables.resize(ht._tables.size());
            for (int i = 0; i < ht._tables.size(); i++)
            {
                Node* htcur = ht._tables[i];
                while (htcur)
                {
                    Node* newnode = new Node(htcur->_kv);//尾插
                    Node* cur = _tables[i];
                    if (cur == nullptr) _tables[i] = newnode;
                    else
                    {
                        while (cur->_next) cur = cur->_next;
                        cur->_next = newnode;
                    }
                    htcur = htcur->_next;
                }
            }
            _n = ht._n;
        }

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

        bool Insert(const pair<K, V>& kv)
        {
            if (Find(kv.first)) return false;
            Hash hash;
            if (_n == _tables.size())//扩容
            {
                vector<Node*> newTable(__stl_next_prime(_tables.size() + 1));
                for (int i = 0; i < _tables.size(); i++)
                {
                    Node* cur = _tables[i];
                    while (cur)
                    {
                        Node* next = cur->_next;
                        size_t hashi = hash(kv.first) % newTable.size();//找到新表的映射位置
                        //头插
                        cur->_next = newTable[hashi];
                        newTable[hashi] = cur;
                        cur = next;
                    }
                    _tables[i] = nullptr;
                }
                _tables.swap(newTable);
            }
            size_t hashi = hash(kv.first) % _tables.size();
            Node* newnode = new Node(kv);//头插
            newnode->_next = _tables[hashi];
            _tables[hashi] = newnode;
            ++_n;
            return true;
        }

        Node* Find(const K& key)
        {
            Hash hash;
            size_t hashi = hash(key) % _tables.size();
            Node* cur = _tables[hashi];
            while (cur)
            {
                if (cur->_kv.first == key) return cur;
                cur = cur->_next;
            }
            return nullptr;
        }

        bool Erase(const K& key)
        {
            Hash hash;
            size_t hashi = hash(key) % _tables.size();
            Node* prev = nullptr;
            Node* cur = _tables[hashi];
            while (cur)
            {
                if (cur->_kv.first == key)//找到了
                {
                    if (prev == nullptr)//待删除节点为头节点
                        _tables[hashi] = cur->_next;
                    else//待删除节点为中间节点
                        prev->_next = cur->_next;
                    delete cur;
                    --_n;
                    return true;
                }
                else
                {
                    prev = cur;
                    cur = cur->_next;
                }
            }
            return false;
        }

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

测试

int main()
{
    int a[] = {19, 30, 5, 36, 13, 20, 21, 12, 24, 96};
    hash_bucket::HashTable<int, int> ht;
    for (auto& e : a)
    {
        ht.Insert({ e,e });
    }
    ht.Insert({100,100});
    ht.Insert({101,101});
    cout << ht.Find(19) << endl;
    cout << ht.Find(36) << endl;
    cout << ht.Find(96) << endl;
    cout << ht.Find(101) << endl << endl;
    ht.Erase(19);
    ht.Erase(36);
    ht.Erase(96);
    ht.Erase(101);
    cout << ht.Find(19) << endl;
    cout << ht.Find(36) << endl;
    cout << ht.Find(96) << endl;
    cout << ht.Find(101) << endl << endl;
    return 0;
}

哈希表封装 unordered_set 和 unordered_map

与红黑树封装 set 和 map 类似，HashTable 也实现了泛型，其中 HashTable 用链地址法实现，仿函数 KeyOfT 取出 T 类型对象的 Key 对象，仿函数 Hash 转成 size_t。

代码实现

//HashTable.h
#include <vector>
#include <string>
using namespace std;

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

template<>
struct HashFunc<string>
{
    size_t operator()(const string& s)
    {
        size_t hash = 0;
        for (auto& e : s)
        {
            hash += e;
            hash *= 131;
        }
        return hash;
    }
};

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

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* _ht;//用在 operator++

        HTIterator(Node* node, const HT* ht) :_node(node),_ht(ht){}

        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 hash;
                size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();//当前桶的位置
                hashi++;
                while (hashi < _ht->_tables.size())
                {
                    _node = _ht->_tables[hashi];
                    if (_node) break;
                    else hashi++;
                }
                if (hashi == _ht->_tables.size()) _node = nullptr;
            }
            return *this;
        }
    };

    template<class K, class T, class KeyOfT, class Hash = HashFunc<T>>//T 本身是 K，或含有 K
    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 (int i = 0; i < _tables.size(); i++)//找到哈希表中不为空的位置
            {
                Node* cur = _tables[i];
                if (cur) return Iterator(cur, this);
            }
            return End();
        }

        Iterator End()
        {
            return Iterator(nullptr, this);
        }

        ConstIterator Begin() const
        {
            if (_n == 0) return End();
            for (int i = 0; i < _tables.size(); i++)
            {
                Node* cur = _tables[i];
                if (cur) return ConstIterator(cur, this);
            }
            return End();
        }

        ConstIterator End() const
        {
            return ConstIterator(nullptr, this);
        }

        HashTable() :_tables(__stl_next_prime(0)),_n(0){}

        ~HashTable()
        {
            for (int 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;
            auto it = Find(kot(data));
            if (it != End()) return { it,false };
            Hash hash;
            if (_n == _tables.size())//扩容
            {
                vector<Node*> _newTable;
                _newTable.resize(__stl_next_prime(_tables.size() + 1));
                for (int i = 0; i < _tables.size(); i++)
                {
                    Node* cur = _tables[i];
                    while (cur)
                    {
                        Node* next = cur->_next;
                        size_t hashi = hash(kot(cur->_data)) % _newTable.size();//找到新表的映射位置
                        //头插
                        cur->_next = _newTable[hashi];
                        _newTable[hashi] = cur;
                        cur = next;
                    }
                }
                _tables.swap(_newTable);
            }
            size_t hashi = hash(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 hash;
            size_t hashi = hash(key) % _tables.size();
            Node* cur = _tables[hashi];
            while (cur)
            {
                if (kot(cur->_data) == key) return { cur,this };
                cur = cur->_next;
            }
            return End();
        }

        bool Erase(const K& key)
        {
            Hash hash;
            KeyOfT kot;
            size_t hashi = hash(key) % _tables.size();
            Node* cur = _tables[hashi];
            Node* prev = nullptr;
            while (cur)
            {
                if (kot(cur->_data) == key)//找到了
                {
                    if (prev == nullptr)//待删除节点为头节点
                    {
                        _tables[hashi] = cur->_next;
                    }
                    else//待删除节点为中间节点
                    {
                        prev->_next = cur->_next;
                    }
                    delete cur;
                    --_n;
                    return true;
                }
                else
                {
                    prev = cur;
                    cur = cur->_next;
                }
            }
            return false;
        }

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

//UnorderedSet.h
#include "HashTable.h"
namespace mine
{
    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();
        }
        bool erase(const K& key)
        {
            return _ht.Erase(key);
        }

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

    void print(const unordered_set<int>& us)//测试 const 迭代器
    {
        unordered_set<int>::const_iterator cit = us.begin();
        cout << typeid(us).name() << endl;
        while (cit != us.end())
        {
            cout << *cit << " ";
            ++cit;
        }
        cout << endl;
        for (auto e : us)
        {
            cout << e << " ";
        }
        cout << endl << endl;
    }
}

//UnorderedMap.h
#include "HashTable.h"
namespace mine
{
    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();
        }
        V& operator[](const K& key)
        {
            auto ret = insert({ key,V() });
            return ret.first->second;
        }
        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);
        }

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

    void print(const unordered_map<string, string>& um)//测试 const 迭代器
    {
        unordered_map<string, string>::const_iterator cit = um.begin();
        while (cit != um.end())
        {
            cout << cit->first << "：" << cit->second << endl;
            ++cit;
        }
        cout << endl;
        for (auto& e : um)
        {
            cout << e.first << "：" << e.second << endl;
        }
    }
}

测试 mine::unordered_set

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include "UnorderedSet.h"
#include "UnorderedMap.h"

int main()
{
    int a[] = {3, 11, 86, 7, 88, 82, 1, 881, 5, 6, 7, 6};
    mine::unordered_set<int> us;
    for (auto e : a)
    {
        us.insert(e);
    }
    auto it = us.begin();
    while (it != us.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    for (auto& e : us)
    {
        cout << e << " ";
    }
    cout << endl << endl;
    mine::print(us);
    return 0;
}

测试 mine::unordered_map

int main()
{
    mine::unordered_map<string, string> dict;
    dict.insert({"sort","排序"});
    dict.insert({"字符串","string"});
    dict.insert({"left","左"});
    dict.insert({"right","右"});
    for (auto& e : dict)
    {
        cout << e.first << "：" << e.second << endl;
    }
    cout << endl;
    dict["left"]="左，剩余";
    dict["insert"]="插入";
    dict["string"];
    auto it = dict.begin();
    while (it != dict.end())
    {
        //it->second += "x";
        cout << it->first << "：" << it->second << endl;
        ++it;
    }
    cout << endl;
    print(dict);
    return 0;
}