C++进阶之哈希（unordered_map\u002Fset的使用及其模拟）

雪芙花

发布于 2022-10-31 18:20:28

5750

发布于 2022-10-31 18:20:28

文章被收录于专栏：雪芙花

持续创作，加速成长！这是我参与「掘金日新计划 · 10 月更文挑战」的第10天，点击查看活动详情

一：unordered_map/set的使用

unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的 value。
在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
它的迭代器是单向迭代器。

特殊接口的说明：

unordered_map的查询

函数声明	功能介绍
iterator find(const K& key)	返回key在哈希桶中的位置
size_t count(const K& key)	返回哈希桶中关键码为key的键值对的个数

注意：unordered_map中key是不能重复的，因此count函数的返回值最大为1

unordered_map的修改操作

函数声明	功能介绍
insert	向容器中插入键值对
erase	删除容器中的键值对
void clear()	清空容器中有效元素个数
void swap(unordered_map&)	交换两个容器中的元素

unordered_map的桶操作

函数声明	功能介绍
size_t bucket_count()const	返回哈希桶中桶的总个数

unordered_set 类似

二：哈希概念的介绍

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(N)，搜索的效率取决于搜索过程中元素的比较次数
理想的搜索方法是可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素，则复杂度为O(1)非常的高效，而计数排序用的即是这种思想

哈希的思想就是信息压缩的思想，可以将一些信息量庞大的数据通过特殊的哈希函数压缩成信息量比较小的数据，再通过哈希桶，位图等容器存储起来。

当向该结构中：插入元素

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

搜索元素

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表 (Hash Table)(或者称散列表)

1.哈希冲突

对于两个数据元素的关键字和 (i != j)，有 != ，但有：Hash( ) == Hash( )，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。发生哈希冲突该如何处理呢？

2. 哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0 到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单

常见哈希函数：

直接定制法--(常用)

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀缺点：需要事先

知道关键字的分布情况使用场景：适合查找比较小且连续的情况 2. 除留余数法--(常用)

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

3. 闭散列

闭散列也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去

线性探测：

从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止，即newindexi=（index+i)%capacity 线性探测实现非常简单，但是一旦发生哈希冲突，所有的冲突连在一起，容易产生数据堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低

二次探测：

从发生的冲突的位置开始，不逐个往后找，而是以平方个位置找，即计算位置为newindexi=（index+i^2)%capacity 二次探测可以较为有效的方式减小哈希冲突的概率

闭散列扩容

使用除留余数定制法时，对于扩容后的哈希表对应的哈希函数的除数的值会发生相应的改变，导致下一次查找定制的位置可能不同，所以需要对原来的数据进行再次映射到新的位置上

4 .开散列

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中

实现步骤：

插入通过哈希函数找到对应的映射位置，然后头插，但是在插入之前需要进行遍历桶节点查看是否存在与插入的值相同的节点，没有才进行头插。
删除/查找通过哈希函数映射到对应的位置，进行对该位置通的遍历再进行删除或查找
开散列增容桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容。开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容

除留余数法，最好模一个素数

代码实现：

//获取下一个质数（接近二倍开辟）,比较科学减少冲突的取扩容大小的方式
size_t GetNextPrime(size_t prime)
{
    const int PRIMECOUNT = 28;
    static const size_t primeList[PRIMECOUNT] =
    {
        53ul, 97ul, 193ul, 389ul, 769ul,
        1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
        49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
        1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
        50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
        1610612741ul, 3221225473ul, 4294967291ul
    };

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

    return primeList[i];
}

开散列代码实现：

//哈希储存的数据类型
template<class K,class V>
struct HashNode
{
    pair<K,V> _kv;
    HashNode* _next;

    HashNode(const pair<K,V>&amp; kv)
        :_kv(kv)
        , _next(nullptr)
    {}
};
//取值比较仿函数及其特化
template<class K>
struct HashFunc
{
    size_t operator()(const K&amp; key)
    {
        return key;
    }
};
template<>
struct HashFunc<string>
{
    size_t operator()(const string&amp; str)
    {
        size_t hash = 0;
        for (int i = 0; i < str.size(); i++)
        {
            hash = hash * 131 + str[i];
        }
        return hash;
    }
};
//获取下一个质数（接近二倍开辟）,比较科学减少冲突的取扩容大小的方式
size_t GetNextPrime(size_t prime)
{
    const int PRIMECOUNT = 28;
    static const size_t primeList[PRIMECOUNT] =
    {
        53ul, 97ul, 193ul, 389ul, 769ul,
        1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
        49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
        1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
        50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
        1610612741ul, 3221225473ul, 4294967291ul
    };

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

    return primeList[i];
}
template<class K, class V, class Hash=HashFunc<K>>
class HashTable
{
    typedef HashNode<K,V> Node;
public:
    typedef HashTable<K, V, Hash> HT;
    HashTable()
        :_n(0)
    {}
    HashTable(const HT&amp; ht)//拷贝构造
        :_n(ht._n)
    {
        if (ht._table.size() == 0)//空栈
            return;

        _table.resize(ht._table.size(), nullptr);//开辟空间并初始化
        for (int i = 0; i < ht._table.size(); i++)//遍历深拷贝
        {
            Node* cur = ht._table[i];
            while (cur)//遍历桶
            {
                Node* newnode = new Node(cur->_kv);
                newnode->_next = _table[i];//头插
                _table[i] = newnode;

                cur = cur->_next;
            }
        }
    }
    HT&amp; operator=(const HT&amp; ht)//赋值重载（现代式）
    {
        if (&amp;ht != this)
        {
            HT temp(ht);//拷贝构造
            _table.swap(temp._table);
            _n = ht._n;
        }
        return *this;
    }
    ~HashTable()//析构-释放资源
    {
        for (int i = 0; i < _table.size(); i++)
        {
            Node* cur = _table[i];
            while (cur)
            {
                Node* next = cur->_next;
                delete cur;
                cur = next;
            }
            _table[i] = nullptr;//置空
        }
        _n = 0;
    }
    bool Insert(const pair<K,V>&amp; kv)
    {
        Hash hf;
        //空哈希或者负载因子达到1时进行扩容
        if (_table.size() == _n)
        {
            //size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
            size_t newsize = GetNextPrime(_table.size());//获取新的扩容大小
            vector<Node*> newdata;
            newdata.resize(newsize, nullptr);//开新的数组并扩容
            //将原数组中的节点重新映射插入到新数组
            for (size_t i = 0; i < _table.size(); ++i)
            {
                Node* cur = _table[i];
                while (cur)//挂有节点
                {
                    Node* next = cur->_next;//记录下一个节点
                    size_t index = hf(cur->_kv.first) % newsize;//重新计算下标
                    
                    cur->_next = newdata[index];//头插
                    newdata[index] = cur;

                    cur = next;//移动
                }
                _table[i] = nullptr;//原数组置空
            }
            _table.swap(newdata);
        }

        size_t index = hf(kv.first) % _table.size();
        Node* cur = _table[index];//遍历查看桶数据知否相等
        while (cur)
        {
            if (cur->_kv.first == kv.first)//相等
                return false;
            else
                cur = cur->_next;
        }
        //头插
        Node* newnode = new Node(kv);
        newnode->_next = _table[index];
        _table[index] = newnode;
        ++_n;
        return true;
    }
    Node* Find(const K&amp; key)
    {
        //空哈希
        if (_table.size() == 0)
            return nullptr;
        Hash hf;
        size_t index = hf(key) % _table.size();
        Node* cur = _table[index];
        while (cur)
        {
            if (cur->_kv.first == key)
                return cur;
            else
                cur = cur->_next;
        }
        return nullptr;
    }
    bool Erase(const K&amp; key)
    {
        //空哈希
        if (_table.size() == 0)
            return false;
        Hash hf;
        size_t index = hf(key) % _table.size();
        Node* cur = _table[index];
        Node* parent = nullptr;
        while (cur)
        {
            if (cur->_kv.first == key)
            {
                if (parent == nullptr)//头结点进行头删
                    _table[index] = cur->_next;
                else
                    parent->_next = cur->_next;
                delete cur;
                --_n;
                return true;
            }
            else
            {
                parent = cur;
                cur = cur->_next;
            }
        }
        return false;
    }
private:
    vector<Node*> _table;
    size_t _n;
};

三：模拟实现

namespace ymh
{
    template<class K , class Hash = HashFunc<K>>
    class unordered_set
    {
        struct SetOfKey
        {
            const K&amp; operator()(const K&amp; key)const
            {
                return key;
            }
        };
        typedef HashNode<K> Node;
    public:
        typedef HashTable<K, K, Hash, SetOfKey> HT;
        typedef typename HT::Iterator iterator;
        iterator begin()
        {
            return _ht.begin();
        }
        iterator end()
        {
            return _ht.end();
        }
        pair<iterator, bool> insert(const K&amp; key)
        {
            return _ht.Insert(key);
        }
        /*V&amp; operator[](const K&amp; key)
        {
            auto ret = insert(make_pair(key, V()));
            return ret.first->second;
        }*/
        Node* find(const K&amp; key)
        {
            return _ht.Find(key);
        }
        bool erase(const K&amp; key)
        {
            return _ht.Erase(key);
        }
    private:
        HT _ht;
    };
    void test_unordered_set()
    {
        unordered_set<int> set;
        int arr[] = { 1,2,22,34,3,4,54,4,2,6,18,48,56,16,45,16,23,156,49,153,45,81,6,6,16,16,151,84894,11,6 };
        for (auto e : arr)
        {
            set.insert(e);
        }
        for (auto&amp; e : set)
        {
            cout << e << endl;
        }
        auto ret = set.find(4);
        cout << ret << endl;
        set.erase(4);
        for (auto&amp; e : set)
        {
            cout << e << endl;
        }
        for (auto e : arr)
        {
            set.erase(e);
        }
        for (auto&amp; e : set)
        {
            cout << e<< endl;
        }
    }
}

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=1iamvly0ep96k

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-10-08，如有侵权请联系 cloudcommunity@tencent.com 删除

serverless