C++ 哈希表原理及 unordered_set/map 应用

unordered_multiset/unordered_multimap

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)
{
    // 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);
    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;

        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>>
    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(key); }
        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)
    {
        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)
    {
        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())
    {
        cout << it->first << "：" << it->second << endl;
        ++it;
    }
    cout << endl;
    print(dict);
    return 0;
}