- 微信
- 微博
  
  分享文章到微博
- 复制链接
  
  复制链接到剪贴板

【C++】使用哈希表模拟实现STL中的unordered_set和unordered_map

YIN_尹发表于 2023/12/23 21:13:12 2023/12/23

【摘要】 @[TOC]前言前面的文章我们学习了unordered_set和unordered_map的使用以及哈希表，并且我们提到了unordered_set和unordered_map的底层结构其实就是哈希表。那这篇文章我们就对之前我们实现的哈希表（拉链法实现的那个）进行一个改造，并用它模拟实现一下unordered_set和unordered_map。那在...

@[TOC]

前言

前面的文章我们学习了unordered_set和unordered_map的使用以及哈希表，并且我们提到了unordered_set和unordered_map的底层结构其实就是哈希表。那这篇文章我们就对之前我们实现的哈希表（拉链法实现的那个）进行一个改造，并用它模拟实现一下unordered_set和unordered_map。

那在模拟实现之前要声明一下：

我们这里的模拟实现里面所做的操作和前面红黑树模拟实现mapset基本上是一样的，增加和改造的那些模板参数的意义基本都是一样的。所以这里有些地方我们就不会特别清楚的去说明了，如果某些地方大家看的不能太明白，建议先搞懂这篇文章——使用红黑树模拟实现STL中的map与set 这里面我们是讲的比较清楚的。

一.哈希表模板改造+封装unordered_set和unordered_map

首先可以带大家再来简单看一下库里面的哈希表的源码：

我们来看一下这几个模板参数第一个value就决定了哈希表里面每个data里面存的数据类型，第二个参数key就是用来获取单独的键值key，因为unordered_map进行查找这些操作的时候是用key进行散列的，需要比较的话也是用key，但他里面存的是pair。第三个这个HashFcn就是接收一个仿函数，用来将比如字符串这些类型转换为整型的。第四个的作用就和红黑树封装那里的KeyOfT一样，用来提取key的。那我们先看这么多。

接下来我们对我们的拉链法的哈希表进行一些改造，因为我们当时是按照KV模型实现的，而现在要变成通用的。

1. 哈希表结构修改

首先结点的结构要改一下：

这样对于unordered_setT就是单独一个key，对于unordered_map就是一个pair。

然后哈希表的结构：

之前Node里面是KV，现在由T决定结点里面存什么那下面相关的地方都要改一下那大家看这个地方是不是就需要使用keyOfT那个仿函数了因为data有可能是单独一个key，也有可能是一个pair，而像查找这些地方要使用Key去查找。增加一个模板参数

2. unordered_set和unordered_map增加KeyOfT仿函数

然后我们把unordered_set/map能写的先写一写：

3. insert封装及测试

那我们先把insert搞一下，然后测试一下

unordered_map

测试一下：

unordered_set的插入没问题然后，unordered_map的插入没问题。

4. 哈希表迭代器的实现

接着我们来实现一下哈希表的迭代器

我们来思考一下它的迭代器应该怎么搞：

那按照我们以往的经验，它的迭代器应该还是对结点指针的封装，然后顺着每个不为空的哈希桶（链表）进行遍历就行了。那大家思考一下：比如现在底层的哈希表是这样的，it在2这个结点的位置。那++it怎么走？ 🆗，其实很简单嘛，node->next不为空，就直接走到下一个结点就行了。那如果为空呢？比如走到1002这个结点如果node->next为空，就说明当前这个桶遍历完了，所以就往后寻找下一个不为空的桶，然后it指向这个桶的第一个结点。库里面其实也是这样搞的。所以，对于哈希表的迭代器来说，还是结点指针的封装，但是还要包含另一个成员即哈希表。因为我们遍历哈希表去依次找桶。

那我们自己来实现一下

先定义一下结构：

然后常用成员函数我们实现一下：

这些都没什么难度

然后++我们实现一下：

思路我们上面分析过了，来写一下代码

5. begin和end

迭代器搞的差不多，我们把begin和end搞一下

首先begin是返回第一个位置的迭代器，那第一个位置怎么找？ 🆗，是不是第一个非空的哈希桶的第一个结点啊注意我们这里的迭代器的构造 是用结点的指针和表的指针，而this就是当前哈希表的指针。 然后end用空构造就行了

6. unordered_set和unordered_map的迭代器封装

那哈希表的迭代器实现好，我们就可以封装unordered_set和unordered_map的迭代器了

先来unordered_set：

来试一下报了好多错误。

我们来解决一下：

第一个迭代器的类里面无法访问私有成员_table 那解决方法呢我们可以写Get方法，当然这里也可以用友元解决。那我们用一下友元吧然后再运行就可以了。当然范围for肯定也支持了。

那unordered_set搞好了，unordered_map的迭代器我们也来封装一下：

来测试一下没有问题。

然后我们可以再用统计次数那个测试一下：

但是我们还没给unordered_map重载[]

7. unordered_map的[]重载

来写一下：

那通过前面的学习我们知道要实现[]的话，关键在于insert的返回值。 insert要返回一个pair 插入有成功和失败两种情况，因为键值不允许冗余；它返回的是一个pair，第一个模板参数为迭代器，第二个为bool。当插入成功的时候，pair的first为指向新插入元素的迭代器，second为true，当插入失败的时候（其实就是插入的键已经存在了），那它的first为容器中已存在的那个相同的等效键元素的迭代器，second为false。所以后面这个bool其实是标识插入成功还是失败。这都是我们前面讲过的。

那我们前面实现的insert返回bool，所以我们要修改一下：

首先find我们先改一下，我们之前返回NOde*，现在应该返回对应位置的迭代器然后insert返回一个pair 还有unordered_map/set里面的insert我们也改一下

然后我们给unordered_map封装一个[]：

再来测试：

就可以了。

8. 补充完善：find、erase

unordered_set和unordered_map的find和erase我们也搞一下吧，其实就是套一层壳嘛：

9. 存储自定义类型元素

如果我们现在想让unordered_map里面的key为日期类

class Date
{
public:
    Date(int year = 1900, int month = 1, int day = 1)
        : _year(year)
        , _month(month)
        , _day(day)
    {}
    bool operator<(const Date& d)const
    {
        return (_year < d._year) ||
            (_year == d._year && _month < d._month) ||
            (_year == d._year && _month == d._month && _day < d._day);
    }
    bool operator>(const Date& d)const
    {
        return (_year > d._year) ||
            (_year == d._year && _month > d._month) ||
            (_year == d._year && _month == d._month && _day > d._day);
    }
    friend ostream& operator<<(ostream& _cout, const Date& d);
private:
    int _year;
    int _month;
    int _day;
};
ostream& operator<<(ostream& _cout, const Date& d)
{
    _cout << d._year << "-" << d._month << "-" << d._day;
    return _cout;
}

我们写这样一段代码：

我们现在直接运行肯定是有问题的因为date类的数据无法转换成整型，所以我们要传那个keyToInt的仿函数。

那我们的哈希表是有这个模板参数的，但是我们现在得给unordered_set和unordered_map增加这个模板参数：

那哈希表里面这个缺省参数我们就不用传了。而是搞到unordered_set和unordered_map这里

现在我们增加了这个模板参数，也有缺省值，但是对于date还是不行，因为它无法转换为整型，所以我们要自己写一个针对date类的仿函数：

但是这里类外无法访问date的私有成员，那我们还用友元解决吧然后我们也可以用个BKDR哈希

然后我们再运行

会发现这里又有一个报错。是因为我们的日期类没有重载==，我们加一下然后再运行就没问题了

另外呢我们看到：

最开始的时候带大家看库里面的源码，它的哈希表还有一个模板参数我们没有介绍就是这个EqualKey，他其实就是接收一个仿函数或函数指针去实现比较key是否相等的，必要的时候我们可以自己传。 我们这里没有用，因为这里的date类我们可以自己手动给它重载==，但是如果一个类不支持但是我们不能修改它或者某种类型的key可以比较==，但是不是我们想要的，比如date*，那像这种情况我们就可以写一个仿函数去传这个参数，不过我们这里没加。

10. const迭代器的实现及unordered_set元素可以修改问题的解决

还有一个问题就是我们的unordered_set里面的元素现在是可以修改的，但是正常情况key是不能修改的，而且他是哈希函数里面的操作数，随意改散列就出问题了：

那我们来处理一下：

那其实解决方法和set那里是一样的，库里面也是一样的方法，让unordered_set的迭代器都是哈希表的const迭代器。

那首先我们得实现一下const迭代器：

先得给哈希表实现一下，还是之前的方法，通过增加两个模板参数

然后const版本的begin和end：

那然后我们把set的迭代器重新封装一下：

然后再运行：

就不能修改了但是又有了新的问题。 那这个问题其实还是跟我们之前封装mapset那里一样，因为这里不支持普通迭代器构造const迭代器 所以要解决的话加一个可以支持普通迭代器构造const迭代器的构造函数就行了 同样的方法然后就可以了。

如果大家有地方看不太懂的还是建议去看一下之前红黑树模拟实现map与set那里，那里讲的比较仔细，它们的逻辑是一样的。

11. unordered_map const迭代器的封装

而对于unordered_map：

它的普通迭代器就是普通迭代器，const迭代器器就是const迭代器，区别在于value是否可以修改，而key是无论如何不能修改的 这个通过传模板参数就可以控制。

那我们把它的const迭代器也搞一下吧：

const版本的begin和end：

来试一下：

🆗，我们看到普通迭代器可以修改value key是不行的。 如果换成const迭代器，value也不能修改。 key肯定依然不能修改。

二. 源码

1. HashTable.h

#pragma once
#include <stdbool.h>

template<class T>
struct HashNode
{
    T _data;
    HashNode<T>* _next;

    HashNode(const T& data)
        :_data(data)
        , _next(nullptr)
    {}
};

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

//对string类型进行特化
template<>
struct keyToIntFunc<string>
{
    size_t operator()(const string& key)
    {
        size_t sum = 0;
        for (auto& e : key)
        {
            sum = sum * 31 + e;
        }
        return sum;
    }
};

namespace HashBucket
{

    //前置声明,__HashIterator在哈希表上面，但里面用了哈希表
    template<class K, class T, class keyOfT, class keyToInt>
    class HashTable;

    template<class K, class T, class Ref, class Ptr, class keyOfT, class keyToInt>
    struct __HashIterator
    {
        typedef HashNode<T> Node;
        typedef HashTable<K, T, keyOfT, keyToInt> HashTable;
        typedef __HashIterator<K, T, Ref, Ptr, keyOfT, keyToInt> self;
        typedef __HashIterator<K, T, T&, T*, keyOfT, keyToInt> Iterator;

        Node* _node;
        HashTable* _ht;

        __HashIterator(Node* node, HashTable* ht)
            :_node(node)
            , _ht(ht)
        {}

        __HashIterator(const Iterator& it)
            :_node(it._node)
            , _ht(it._ht)
        {}

        Ref operator*()
        {
            return _node->_data;
        }

        Ptr operator->()
        {
            return &_node->_data;
        }

        bool operator!=(const self& it)
        {
            return _node != it._node;
        }

        self& operator++()
        {
            if (_node->_next != nullptr)
            {
                _node = _node->_next;
            }
            else//向后寻找非空的桶
            {
                //计算当前桶的位置
                size_t hashi = keyToInt()(keyOfT()(_node->_data)) % _ht->_table.size();
                //++走到下一个桶
                ++hashi;
                while (hashi < _ht->_table.size())
                {
                    //不为空
                    if (_ht->_table[hashi])
                    {
                        _node = _ht->_table[hashi];
                        break;
                    }
                    else
                    {
                        ++hashi;
                    }
                }
                //如果hashi == _ht->_table.size()，说明走到结束后面也没有非空桶
                if (hashi == _ht->_table.size())
                {
                    _node = nullptr;
                }
            }
            return *this;
        }

    };

    template<class K, class T, class keyOfT,class keyToInt>
    class HashTable
    {
        template<class K, class T, class Ref, class Ptr, class keyOfT, class keyToInt>
        friend struct __HashIterator;

        typedef HashNode<T> Node;
    public:
        typedef __HashIterator<K, T, T&, T*, keyOfT, keyToInt> iterator;
        typedef __HashIterator<K, T, const T&, const T*, keyOfT, keyToInt> const_iterator;


        iterator begin()
        {
            Node* cur = nullptr;
            for (size_t i = 0; i < _table.size(); i++)
            {
                if (_table[i])
                {
                    cur = _table[i];
                    break;
                }
            }
            return iterator(cur, this);
        }

        iterator end()
        {
            return iterator(nullptr, this);
        }

        const_iterator begin()const
        {
            Node* cur = nullptr;
            for (size_t i = 0; i < _table.size(); i++)
            {
                if (_table[i])
                {
                    cur = _table[i];
                    break;
                }
            }
            return const_iterator(cur, this);
        }

        const_iterator end()const
        {
            return const_iterator(nullptr, this);
        }

        ~HashTable()
        {
            for (auto& cur : _table)
            {
                while (cur)
                {
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
                cur = nullptr;
            }
        }

        size_t GetNextPrime(size_t prime)
        {
            // SGI
            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
            };

            size_t i = 0;
            for (; i < __stl_num_primes; ++i)
            {
                if (__stl_prime_list[i] > prime)
                    return __stl_prime_list[i];
            }

            return __stl_prime_list[i];
        }

        pair<iterator, bool> Insert(const T& data)
        {
            iterator it = Find(keyOfT()(data));
            if (it != end())
            {
                return make_pair(it, false);
            }

            //负载因子==1进行扩容
            if (_n == _table.size())
            {
                //size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
                size_t newsize = GetNextPrime(_table.size());

                vector<Node*> newtable(newsize, nullptr);
                for (auto& cur : _table)
                {
                    while (cur)
                    {
                        Node* next = cur->_next;
                        size_t hashi = keyToInt()(keyOfT()(cur->_data)) % newtable.size();

                        //把结点头插到新表
                        cur->_next = newtable[hashi];
                        newtable[hashi] = cur;

                        cur = next;
                    }
                }
                _table.swap(newtable);
            }

            //计算散列地址
            size_t hashi = keyToInt()(keyOfT()(data)) % _table.size();

            //链到散列地址对应的单链表上（头插）
            Node* newNode = new Node(data);
            newNode->_next = _table[hashi];
            _table[hashi] = newNode;

            ++_n;
            return make_pair(iterator(newNode, this), true);
        }

        iterator Find(const K& key)
        {
            if (_table.size() == 0)
            {
                return end();
            }
            size_t hashi = keyToInt()(key) % _table.size();
            Node* cur = _table[hashi];

            while (cur)
            {
                if (keyOfT()(cur->_data) == key)
                {
                    return iterator(cur, this);
                }
                cur = cur->_next;
            }
            return end();
        }

        bool Erase(const K& key)
        {
            size_t hashi = keyToInt()(key) % _table.size();
            Node* prev = nullptr;
            Node* cur = _table[hashi];

            while (cur)
            {
                if (key == keyOfT()(cur->_data))
                {
                    //头删
                    if (prev == nullptr)
                    {
                        _table[hashi] = cur->_next;
                    }
                    //非头删
                    else
                    {
                        prev->_next = cur->_next;
                    }
                    delete cur;
                    return true;
                }
                else
                {
                    prev = cur;
                    cur = cur->_next;
                }
            }
            return false;
        }

        size_t MaxBucketSize()
        {
            size_t max = 0;
            for (auto& cur : _table)
            {
                size_t size = 0;
                while (cur)
                {
                    ++size;
                    cur = cur->_next;
                }
                if (size > max)
                {
                    max = size;
                }
            }
            return max;
        }

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

2. UnorderedSet.h

#pragma once

#include "HashTable.h"

template<class K, class KeyToInt = keyToIntFunc<K>>
class UnorderedSet
{
public:
    struct setKeyOfT
    {
        const K& operator()(const K& key)
        {
            return key;
        }
    };
    typedef typename HashBucket::HashTable<K, K, setKeyOfT, KeyToInt>::const_iterator iterator;
    typedef typename HashBucket::HashTable<K, K, setKeyOfT, KeyToInt>::const_iterator 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()
    {
        return _ht.Find();
    }
    bool erase()
    {
        return _ht.Erase();
    }

private:
    HashBucket::HashTable<K, K, setKeyOfT, KeyToInt> _ht;
};

void UnorderedSet_test1()
{
    int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15,106 };
    UnorderedSet<int> m;
    m.insert(1);
    m.insert(7);
    m.insert(5);
    m.insert(2);
    m.insert(8);
    for (auto e : arr)
    {
        m.insert(e);
    }

    UnorderedSet<int>::iterator it = m.begin();
    while (it != m.end())
    {
        //(*it)++;
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    for (auto e : m)
    {
        cout << e << " ";
    }
    cout << endl;

}

3. UnorderedMap.h

#pragma once

#include "HashTable.h"

template<class K, class V, class KeyToInt = keyToIntFunc<K>>
class UnorderedMap
{
public:
    struct MapKeyOfT
    {
        const K& operator()(const pair<K,V>& kv)
        {
            return kv.first;
        }
    };

    typedef typename HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, KeyToInt>::iterator iterator;
    typedef typename HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, KeyToInt>::const_iterator 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 = insert(make_pair(key, V()));
        return ret.first->second;
    }
    iterator find()
    {
        return _ht.Find();
    }
    bool erase()
    {
        return _ht.Erase();
    }
private:
    HashBucket::HashTable<K, pair<const K,V>, MapKeyOfT, KeyToInt> _ht;
};

void UnorderedMap_test1()
{
    UnorderedMap<int, int> m;
    m.insert(make_pair(1, 1));
    m.insert(make_pair(7, 7));
    m.insert(make_pair(5, 5));
    m.insert(make_pair(2, 2));
    m.insert(make_pair(8, 8));

    UnorderedMap<int, int>::const_iterator it = m.begin();
    while (it != m.end())
    {
        //it->first++;
        cout << it->first << ":" << it->second << " ";
        ++it;
    }
    cout << endl;
}

void UnorderedMap_test2()
{
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };

    UnorderedMap<string, int> m;
    for (auto e : arr)
    {
        m[e]++;
    }

    for (auto e : m)
    {
        cout << e.first << ":" << e.second << endl;
    }
}
class Date
{
public:
    Date(int year = 1900, int month = 1, int day = 1)
        : _year(year)
        , _month(month)
        , _day(day)
    {}
    bool operator<(const Date& d)const
    {
        return (_year < d._year) ||
            (_year == d._year && _month < d._month) ||
            (_year == d._year && _month == d._month && _day < d._day);
    }
    bool operator>(const Date& d)const
    {
        return (_year > d._year) ||
            (_year == d._year && _month > d._month) ||
            (_year == d._year && _month == d._month && _day > d._day);
    }
    bool operator==(const Date& d)const
    {
        return _year == d._year
            && _month == d._month
            && _day == d._day;
    }
    friend ostream& operator<<(ostream& _cout, const Date& d);
    friend struct dateToInt;
private:
    int _year;
    int _month;
    int _day;
};
ostream& operator<<(ostream& _cout, const Date& d)
{
    _cout << d._year << "-" << d._month << "-" << d._day;
    return _cout;
}

struct dateToInt
{
    size_t operator()(const Date& d)
    {
        size_t ret = 0;
        ret += d._year;
        ret *= 31;
        ret += d._month;
        ret *= 31;
        ret += d._day;
        ret *= 31;

        return ret;
    }
};

void UnorderedMap_test3()
{
    Date d1(2023, 3, 13);
    Date d2(2023, 3, 13);
    Date d3(2023, 3, 12);
    Date d4(2023, 3, 11);
    Date d5(2023, 3, 12);
    Date d6(2023, 3, 13);
    Date a[] = { d1, d2, d3, d4, d5, d6 };

    UnorderedMap<Date, int, dateToInt> countMap;
    for (auto e : a)
    {
        countMap[e]++;
    }
    for (auto& kv : countMap)
    {
        cout << kv.first << ":" << kv.second << endl;
    }
}

4. Test.cpp

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
using namespace std;
#include <vector>
#include "HashTable.h"
#include "UnorderedSet.h"
#include "UnorderedMap.h"
#include <string>
int main()
{
    //UnorderedSet_test1();
    UnorderedMap_test1();
    return 0;
}

点赞
收藏
关注作者

0/1000

抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认取消

加入云驻计划，成为创作者

华为云周边好礼
免费体验产品
特殊身份标识
线下官方门票
内部专家零距离
与10000+优质创作者共同成长

立即加入

【C++】使用哈希表模拟实现STL中的unordered_set和unordered_map

前言

一.哈希表模板改造+封装unordered_set和unordered_map

1. 哈希表结构修改

2. unordered_set和unordered_map增加KeyOfT仿函数

3. insert封装及测试

4. 哈希表迭代器的实现

5. begin和end

6. unordered_set和unordered_map的迭代器封装

7. unordered_map的[]重载

8. 补充完善：find、erase

9. 存储自定义类型元素

10. const迭代器的实现及unordered_set元素可以修改问题的解决

11. unordered_map const迭代器的封装

二. 源码

1. HashTable.h

2. UnorderedSet.h

3. UnorderedMap.h

4. Test.cpp

全部回复

设置昵称

关于作者

目录

加入云驻计划，成为创作者

【C++】使用哈希表模拟实现STL中的unordered_set和unordered_map

前言

一.哈希表模板改造+封装unordered_set和unordered_map

1. 哈希表结构修改

2. unordered_set和unordered_map增加KeyOfT仿函数

3. insert封装及测试

4. 哈希表迭代器的实现

5. begin和end

6. unordered_set和unordered_map的迭代器封装

7. unordered_map的[]重载

8. 补充完善：find、erase

9. 存储自定义类型元素

10. const迭代器的实现及unordered_set元素可以修改问题的解决

11. unordered_map const迭代器的封装

二. 源码

1. HashTable.h

2. UnorderedSet.h

3. UnorderedMap.h

4. Test.cpp

全部回复

设置昵称

关于作者

目录

加入云驻计划，成为创作者

推荐阅读

相关产品