从前慢现在也慢

这个屌丝很懒，什么也没留下！

热门标签

C++之unordered_map和unordered_set以及哈希详解_c++ unorderdmap unorderset

作者：从前慢现在也慢 | 2024-04-02 04:28:49

踩

c++ unorderdmap unorderset

unordered_map和unordered_set的使用

map和set底层是红黑树实现的，map是KV模型，set是K模型，而unordered_map和unordered_set底层是哈希表实现的，unordered_set是K模型，unordered_map是KV模型

unordered_map和unordered_set的命名体现特点，在功能和map/set是一样的，区别在于，它遍历出来是无序的，另外，它们的迭代器是单向迭代器

unordered_map的文档

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和unordered_set的使用：

#include<iostream>
#include<unordered_set>
#include<unordered_map>
using namespace std;

void test_unordered_set()
{
    unordered_set<int> s;
    s.insert(3);
    s.insert(4);
    s.insert(5);
    s.insert(3);
    s.insert(1);
    s.insert(2);
    s.insert(6);
    unordered_set<int>::iterator it = s.begin();
    while (it != s.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

int main()
{
    test_unordered_set();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

可以看到它遍历出来是无序的，并且相同的数只会插入一次

#include<iostream>
#include<unordered_map>
using namespace std;
void test_unordered_map()
{
    unordered_map<string, string> dict;
    dict.insert(make_pair("string", "字符串"));
    dict.insert(make_pair("sort", "排序"));
    dict.insert(make_pair("string", "字符串"));
    dict.insert(make_pair("string", "字符串"));
    auto it = dict.begin();
    while (it != dict.end())
    {
        cout << it->first << ":" << it->second << endl;
        it++;
    }
}
int main()
{
    test_unordered_map();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

它遍历出来也是无序的，并且相同的数只会插入一次

unordered_set和unordered_map的两个OJ题

两个数组的交集

题目思路：

用unordered_set对nums1中的元素去重，然后用unordered_set对nums2中的元素去重，最后遍历s1，如果s1中某个元素在s2中出现过，即为交集

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // 用unordered_set对nums1中的元素去重
        unordered_set<int> s1;
        for (auto e : nums1)
        s1.insert(e);
        // 用unordered_set对nums2中的元素去重
        unordered_set<int> s2;
        for (auto e : nums2)
        s2.insert(e);
        // 遍历s1，如果s1中某个元素在s2中出现过，即为交集
        vector<int> vRet;
        for (auto e : s1)
        {
        if (s2.find(e) != s2.end())
        vRet.push_back(e);
        }
        return vRet;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

两个数组的交集二

题目思路：

1、两个位置的值相等，则是交集，同时++

2、两个位置的值不相等，则不是交集值，小的++

set和undered_set的性能比较

void test_op()
{
    set<int> s;
    unorder_set<int> us;
    const int n = 100000;
    vector<int> v;
    srand(time(0));
    for(size_t i = 0;i<n;++i)
    {
        v.push_back(rand());
    }
    //插入性能比较
    size_t begin1 = clock();
    for(auto e:v)
    {
        us.insert(e);
    }
    size_t end1 = clock();
    cout<<end1-begin1<<endl;
    
    size_t begin2 = clock();
    for(auto e:v)
    {
        s.insert(e);
    }
    size_t end2 = clock();
    cout<<end2-begin2<<endl;
    
    //查找性能比较
    size_t begin3 = clock();
    for(auto e:v)
    {
        us.find(e);
    }
    size_t end3 = clock();
    cout<<end1-begin1<<endl;
    
    size_t begin4 = clock();
    for(auto e:v)
    {
        s.find(e);
    }
    size_t end4 = clock();
    cout<<end2-begin2<<endl;
    
    //删除效率比较
    size_t begin5 = clock();
    for(auto e:v)
    {
        us.erase(e);
    }
    size_t end5 = clock();
    cout<<end5-begin5<<endl;
    
    size_t begin6 = clock();
    for(auto e:v)
    {
        s.erase(e);
    }
    size_t end6 = clock();
    cout<<end6-begin6<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

发现不管运行多少次，都是哈希表比较优，unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

哈希

哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经
过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log₂N)，搜索的效率取决
于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过
某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函
数可以很快找到该元素。

当向该哈希结构中：

插入元素

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

搜索元素

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

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

例如：我们有数据集合{1，7，6，4，5，9}；

哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快问题：按照上述哈希方式，向集合中
插入元素44，会出现什么问题？发现4这个位置已经被占用了

哈希冲突

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

常见哈希函数

直接定址法

缺点：需要事先知道关键字的分布情况

使用场景：适合查找比较小且连续的情况

除留余数法

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

哈希冲突的解决

解决哈希冲突两种常见的方法是：闭散列和开散列

闭散列

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

线性探测：index+i (i = 1,2,3,4…)

从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止

二次探测：index+i^2(i = 1,2,3,4…)

线性探测的缺陷是产生冲突的数据堆积在一块，相比线性探测的好处，如果一个位置有很多值映射，冲突剧烈，那么它们存储时相对会比较分散，不会引发一片一片的冲突

开散列

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

闭散列的实现

我们实现哈希表，那么数据怎么存储呢？数据的结构又是什么呢？数据的存储很好想到，可以用一个vector存就好了，那么数据的结构出来存储数据还需要什么呢？比如我们有以下数据：

我们查找一个值时，按照哈希函数求得位置，如果当前位置不是，则可能遇到了冲突，所以一直往后找，当遇到空位置时说明这个值肯定不存在了，因为如果存在，肯定存储在了第一个空位置，那么当我们删除一个值，直接删除的话这个位置变成了空，但是这样有问题：使得查找一个值提早遇到空，那么就找不到这个值

比如删除333，直接删除后变成了空位置，我们再查找14会怎么样？我们先求得14的位置是4，发现4这个位置是空，所以直接就返回不存在，导致14存在，但是查找不到14

解决方案：每个位置存储值得同时再存储一个状态标记：空、满、删除

如果一个值删除了，将该位置标记为删除，查找一个值如果遇到了删除，那么不停止继续查找，插入一个值时遇到了空和删除都可以插入

所以还需要该存储位置的当前状态：

EMPTY(空数据的位置)
EXIST(已存储数据)
DELETE(以前有数据，但是删除了)

enum Status
{
    EMPTY,//空
    EXIST,//存在
    DELETE//删除
};
1
2
3
4
5
6

数据的存储结构

我们实现KV模型，所以数据弄成pair，另外还需要状态：

template<class K,class V>
struct HashData
{
    pair<K,V> _kv;
    Status _status = EMPTY; //状态
}
1
2
3
4
5
6

哈希表的结构

vector来存储HashData，_n用来存储有效数据的个数

template<class K,class V>
class HashTable
{
public:
private:
    vector<HashData<K,V>> _tables;//vector来存储HashData
    size_t _n = 0;//存储有效数据的个数
};
1
2
3
4
5
6
7
8

哈希表的插入

我们为了避免哈希冲突变多，我们引入一个负载因子，当负载因子过大时需要对哈希表进行增容

如果哈希表中已经存在该键值对，则插入失败返回false
判断该哈希表的大小以及负载因子，确定是否需要增容
将键值对插入哈希表
++_n

首先我们解决增容的问题，首先我们确定的是_table.size() == 0时需要增容，其次我们设置负载因子=有效数据/表的大小，如果负载因子大于0.7时就增容。

那么怎么增容呢？

有一种方法是创建一个新vector，resize新空间大小，然后将旧表中的数据复制到新表当中

//方法一
size_t newSize = _table.size()==0? 10:_table.size()*2;
vector<HashData<K,V>> newTable;
newTable.resize(newSize);
for(size_t i =0;i<_tables.size();++i)
{
    if(_table[i]._status == EXIST)
    {
        //将存在的数据复制到新表中
        size_t index = _table[i]._kv.first % newTable.size();
        //...
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

比较好的方法是建立一个临时新表，给新表开扩容后的空间，然后遍历旧表将旧表的数据插入新表，最后将新表和旧表交换：

//方法二：
size_t newSize = _table.size()==0? 10 : _table.size()*2;
HashTable<K,V> newHT;//建立一个临时新表
newHT._tables.resize(newSize);//给新表开扩容后的空间
for(auto& e:_tables)
{
    if(e._status == EXIST)
    {
        newHT.Insert(e._kv);//将旧表的数据插入新表
    }
}
_table.swap(newHT._tables);//将新表和旧表交换
1
2
3
4
5
6
7
8
9
10
11
12

插入哈希表的代码(首先计算出插入的位置，如果该位置存在的话就遍历后面的位置，遍历的过程中如果等于的表的末尾，则返回起始位置继续遍历，直到遇到空或者删除)：

size_t start = kv.first % _tables.size();
size_t i = 0;
size_t index = start + i;
while(_table[index]._status == EXIST)
{
    ++i;
    //index = start+i;//线性探测
    index = start+i*i;//二次探测

    if(index == _tables.size())
    {
        //当index到达最后的时候,让它回到起始
        index = 0;
    }
}
//走到这里要么是空要么是删除
_tables[index]._kv = kv;
_tables[index]._status = EXIST;
++_n;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

插入的完整代码：

//插入
bool Insert(const pair<K,V>& kv)
{
    if(Find(kv.first))
    {
        return false;
    }
    if(_table.size() == 0 || (double)(_n / _table.size()) > 0.7)
    {
        //扩容
        size_t newSize = _table.size()==0? 10 : _table.size()*2;
        HashTable<K,V> newHT;//建立一个临时新表
        newHT._tables.resize(newSize);//给新表开扩容后的空间
        for(auto& e:_tables)
        {
            if(e._status == EXIST)
            {
                newHT.Insert(e._kv);//将旧表的数据插入新表
            }
        }
        _table.swap(newHT._tables);//将新表和旧表交换
    }

    size_t start = kv.first % _tables.size();
    size_t i = 0;
    size_t index = start + i;
    while(_table[index]._status == EXIST)
    {
        ++i;
        //index = start+i;//线性探测
        index = start+i*i;//二次探测

        if(index == _tables.size())
        {
            //当index到达最后的时候,让它回到起始
            index = 0;
        }
    }
    //走到这里要么是空要么是删除
    _tables[index]._kv = kv;
    _tables[index]._status = EXIST;
    ++_n;

    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

哈希表的查找

哈希表的查找逻辑很简单：先计算出查找的key的位置，当这个位置不等于空时，判断key值是不是相等并且状态位存在，如果是的话返回，不是的话进行线性探测或者二次探测，直到遇到位置为空状态

HashData<K,V>* Find(const K& key)
{
    if(_table.size() == 0)
    {
        //防止除0错误
        return nullptr;
    }
    size_t start = key % _table.size();
    size_t i = 0;
    size_t index = start + i;
    while(_tables[index]._status != EMPTY)
    {
        if(_tabled[index]._kv.first == key && _table[index]._status == EXIST)
        {
            return &_tabled[index];
        }
        else
        {
            ++i;
            //index = start +i;
            index = start + i*i;//二次探测
            index %= _tables.size();
        }
    }
    return nullptr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

哈希表的删除

首先找到这个节点，进行伪删除，将该节点的状态设置成删除然后–_n即可

 bool Erase(const K& key)
 {
     HashData<K,V>* ret = Find(key);
     if(ret == nullptr)
     {
         //没有这个值
         return false;
     }
     else
     {
         //伪删除
         ret->_status = DELETE;
         _n--;
         return true;
     }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

哈希表闭散列的代码

#pargma once
namespace close_hash
{
    enum Status
    {
        EMPTY,//空
        EXIST,//存在
        DELETE//删除
    };
    template<class K,class V>
    struct HashData
    {
        pair<K,V> _kv;
      	Status _status = EMPTY; //状态
    }
    template<class K,class V>
   	class HashTable
    {
    public:
        bool Erase(const K& key)
        {
            HashData<K,V>* ret = Find(key);
            if(ret == nullptr)
            {
                //没有这个值
                return false;
            }
            else
            {
                //伪删除
                ret->_status = DELETE;
                _n--;
                return true;
            }
        }
        HashData<K,V>* Find(const K& key)
        {
            if(_table.size() == 0)
            {
                //防止除0错误
                return nullptr;
            }
            size_t start = key % _table.size();
            size_t i = 0;
            size_t index = start + i;
            while(_tables[index]._status != EMPTY)
            {
                if(_tabled[index]._kv.first == key && _table[index]._status == EXIST)
                {
                    return &_tabled[index];
                }
                else
                {
                    ++i;
                    //index = start +i;
                   	index = start + i*i;//二次探测
                    index %= _tables.size();
                }
            }
            return nullptr;
        }
        //插入
        bool Insert(const pair<K,V>& kv)
        {
            if(Find(kv.first))
            {
                return false;
            }
            if(_table.size() == 0 || (double)(_n / _table.size()) > 0.7)
            {
                //扩容
                //方法一
                size_t newSize = _table.size()==0? 10:_table.size()*2;
                vector<HashData<K,V>> newTable;
                newTable.resize(newSize);
                for(size_t i =0;i<_tables.size();++i)
                {
                    if(_table[i]._status == EXIST)
                    {
                        //将存在的数据复制到新表中
                        size_t index = _table[i]._kv.first % newTable.size();
                        //...
                    }
                }
                //方法二：
                size_t newSize = _table.size()==0? 10 : _table.size()*2;
                HashTable<K,V> newHT;//建立一个临时新表
                newHT._tables.resize(newSize);//给新表开扩容后的空间
                for(auto& e:_tables)
                {
                    if(e._status == EXIST)
                    {
                        newHT.Insert(e._kv);//将旧表的数据插入新表
                    }
                }
                _table.swap(newHT._tables);//将新表和旧表交换
            }
            
            size_t start = kv.first % _tables.size();
            size_t i = 0;
            size_t index = start + i;
            while(_table[index]._status == EXIST)
            {
                ++i;
                //index = start+i;//线性探测
                index = start+i*i;//二次探测
                
                if(index == _tables.size())
                {
                    //当index到达最后的时候,让它回到起始
                    index = 0;
                }
                //插满的时候会死循环
            }
            //走到这里要么是空要么是删除
            _tables[index]._kv = kv;
            _tables[index]._status = EXIST;
            ++_n;
            
            return true;
        }
    private:
        vector<HashData<K,V>> _tables;//vector来存储HashData
        size_t _n = 0;//存储有效数据的个数
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

我们上面的代码有些问题：

如果是key是string，上面的代码是编不过去的，因为key是string，无法计算位置，所以此时就用到了仿函数，仿函数通过重载方法将string转化为整形用来做key，这里运用了BKDR Hash思想来完成string到key的转换，发生冲突的概率很小

template<class K>
struct HashFunc
{
    size_t operator()(const K&key)
    {
        return key;
    }
};    
struct HashFuncString
{
    size_t operator()(const string& key)
    {
        //BKDR Hash思想
        size_t hash = 0;
        for(size_t i = 0;i<key.size();++i)
        {
            hash*=131;
            hash += key[i];//转成整形
        }
        return hash;
    }
};    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

如果我们写成这样我们创建string为key的哈希表的时候就需要这样写，将HashFuncString仿函数传进去：

HashTable<string, string, HashFuncString> dict;
1

而我们使用unordered_map时是不需要传这个仿函数进去的，这里用到了模板的特化：

template<class K>
struct HashFunc
{
    size_t operator()(const K&key)
    {
        return key;
    }
}; 
template<>
struct HashFunc<string>
{
    size_t operator()(const string& key)
    {
        //BKDR Hash思想
        size_t hash = 0;
        for(size_t i = 0;i<key.size();++i)
        {
            hash*=131;
            hash += key[i];//转成整形
        }
        return hash;
    }
};  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

此时哈希表的模板参数也就要发生变化：

template<class K, class V, class Hash = HashFunc<K>>
1

不传仿函数过去，它会自己推演，是K是int类型就调用HashFunc<int>，是string就调用更匹配的HashFunc<string>

哈希表闭散列的完整代码

#pargma once
namespace close_hash
{
    enum Status
    {
        EMPTY,//空
        EXIST,//存在
        DELETE//删除
    };
    template<class K,class V>
    struct HashData
    {
        pair<K,V> _kv;
      	Status _status = EMPTY; //状态
    };
    template<class K>
    struct HashFunc
    {
        size_t operator()(const K&key)
        {
            return key;
        }
    };    
    //特化
    template<>
    struct HashFunc<string>
    {
        size_t operator()(const string& key)
        {
            //BKDR Hash思想
            size_t hash = 0;
            for(size_t i = 0;i<key.size();++i)
            {
                hash*=131;
                hash += key[i];//转成整形
            }
            return hash;
        }
    };  
    template<class K,class V,class Hash = HashFunc<K>>
   	class HashTable
    {
    public:
        bool Erase(const K& key)
        {
            HashData<K,V>* ret = Find(key);
            if(ret == nullptr)
            {
                //没有这个值
                return false;
            }
            else
            {
                //伪删除
                ret->_status = DELETE;
                _n--;
                return true;
            }
        }
        HashData<K,V>* Find(const K& key)
        {
            if(_table.size() == 0)
            {
                //防止除0错误
                return nullptr;
            }
            Hash hf;
            size_t index = hf(key) % _table.size();
            size_t i = 0;
            size_t index = start + i;
            while(_tables[index]._status != EMPTY)
            {
                if(_tabled[index]._kv.first == key && _table[index]._status == EXIST)
                {
                    return &_tabled[index];
                }
                else
                {
                    ++i;
                    //index = start+i;//线性探测
                    index = start+i*i;//二次探测
                    index %= _tables.size();
                }
            }
            return nullptr;
        }
        //插入
        bool Insert(const pair<K,V>& kv)
        {
            if(Find(kv.first))
            {
                return false;
            }
            if(_table.size() == 0 || (double)(_n / _table.size()) > 0.7)
            {
                //扩容
                //方法二：
                size_t newSize = _table.size()==0? 10 : _table.size()*2;
                HashTable<K,V> newHT;//建立一个临时新表
                newHT._tables.resize(newSize);//给新表开扩容后的空间
                for(auto& e:_tables)
                {
                    if(e._status == EXIST)
                    {
                        newHT.Insert(e._kv);//将旧表的数据插入新表
                    }
                }
                _table.swap(newHT._tables);//将新表和旧表交换
            }
            Hash hf;
            size_t start = hf(kv.first) % _tables.size();
            //线性探测
            size_t i = 0;
            size_t index = start + i;
            while(_table[index]._status == EXIST)
            {
                ++index;
                if(index == _tables.size())
                {
                    //当index到达最后的时候,让它回到起始
                    index = 0;
                }
                //插满的时候会死循环
            }
            //走到这里要么是空要么是删除
            _tables[index]._kv = kv;
            _tables[index]._status = EXIST;
            ++_n;
            
            return true;
        }
    private:
        vector<HashData<K,V>> _tables;//vector来存储HashData
        size_t _n = 0;//存储有效数据的个数
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

开散列的实现

开散列概念

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

数据的存储结构

因为桶里面是单链表结构，所以需要有一个指向下一个节点的指针_next，还有一个pair来存储数据

template<class V,class V>
struct HashBucketNode
{
    HashBucketNode(const pair<K,V>& kv)
        : _next(nullptr), _kv(kv)
    {}
    HashBucketNode<K,V>* _next;
    pair<K,V> _kv;
};
1
2
3
4
5
6
7
8
9

哈希表的结构

vector里面需要存储Node*而不是Node，如果是Node会出现二义性：存节点了还是没有存，因为定义对象出现时节点都申请出来了，都进行了初始化。所以这里需要存储Node*，指向第一个节点

 class HashTable
 {
     typedef HashBucketNode<K,V> Node;
     private:
     size_t _n = 0;//哈希表中的有效数据
     vector<Node*> _tables;//会出现二义性：存节点了还是没有存,因为定义对象出现节点都申请出来了，都进行了初始化
 };
1
2
3
4
5
6
7

开散列是通过单链表链接分方式处理哈希冲突的，所以并不需要给每个节点设置状态，只需要将哈希地址相同的元素都放到同一个哈希桶里以单链表链接，开散列可以无限的插入，如果表的大小太小，那么每个桶中的单链表就会链接的节点越多，这样找一个节点时效率就会变低，所以开散列我们也要通过负载因子来判断是否增容，通过增容，每个哈希桶的链接的元素相对变少，效率也就好了些，所以我们需要一个_n变量来记录哈希表中的有效数据，来计算负载因子

注意：

负载因子 = 数据个数/表的大小，负载因子越低，冲突的概率越低，空间浪费越高，负载因子越高，冲突的概率越高，空间浪费越低

哈希表的插入

哈希表的插入步骤：

如果哈希表中已经存在该键值对，则插入失败返回false
判断该哈希表的大小以及负载因子，确定是否需要增容
将键值对插入哈希表
++_n

首先我们解决增容的问题，首先我们确定的是_table.size() == 0时需要增容，其次我们设置负载因子=有效数据/表的大小，如果负载因子大于1时就增容。

那么怎么增容呢？

可以这样扩容吗？直接扩2倍：

此时表的大小发生变化，所以需要重新计算位置，会导致处理十分混乱

需要这样扩容：创建一个新表，该哈希表是原来表的2倍，之后遍历旧哈希表，将旧哈希表的数据插入到新哈希表中，最后将新表和旧表交换即可：

将旧哈希表的数据插入到新哈希表中，如果像闭散列那样的方式写时，即通过复用Insert来插入数据时会有一个问题，闭散列表中就是存储数据的，而开散列表中不存储数据，存储的是节点的指针，通过复用Insert来插入数据时，相当于又创建了重复的节点，把已经存在的节点再创建一遍，到最后又要将旧表中和新表中重复的节点释放一次，是不是多此一举了

所以我们只需要通过遍历旧哈希表的哈希桶，将旧表哈希桶的数据头插到新表的哈希桶中，然后将旧表的头节点的next置为空，最后新表和旧表交换即可

bool Insert(const pair<K,V>& kv)
{
    //当负载因子到1时，进行扩容
    if(_n == _table.size())
    {
        size_t newSize = _tables.size() == 0?10:_tables.size()*2;
        vector<Node*> newtables;
        newtables.resize(newSize,nullptr);
        for(size_t i =0;i<_tables.size();i++)
        {
            //遍历旧表
            Node* cur = _tables[i];
            while(cur)
            {
                //桶里有数据
                Node* next = cur->_next;
                size_t index = cur->kv.first % newSize;//当前节点在新表中的位置
                //头插
                cur->_next = newtable[index];//插入节点的next指向新表的第一个节点
                newtable[index] = cur;//第一个节点变为cur

                cur = next;
            }
            _tables[i] = nullptr;
        }
        newtables.swap(_tables);
    }

    size_t index = kv.first % _tables.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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

哈希表插入效率很高，但是扩容影响了插入接口的效率，扩容的代价比较大

哈希表的查找

如果表的大小等于0，返回nullptr
找到桶的位置，然后进行遍历桶，比较值是否相等，相等则返回，不相等继续下一个节点
遍历完没找到返回nullptr

Node* Find(const K& key)
{
    if(_table.size() == 0)
    {
        return nullptr;
    }
    size_t index = key % _table.size();
    Node* cur = _table[index];//第一个节点的指针
    while(cur)
    {
        if(cur->_kv.first == key)
        {
            return cur;
        }
        else
        {
            cur = cur->_next;
        }
    }
    return nullptr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

哈希表的删除

如果表的大小等于0，返回false
找到桶的位置，需要注意删除节点需要保存节点的前一个节点，遍历桶找要删除的节点进行删除，需要注意头删和非头删，头删时prev为空，非头删prev不为空
删除完成–_n，返回true，否则返回false

 bool Erase(const K& key)
 {
     if(_table.size() == 0)
     {
         return false;
     }
     size_t index = key % _table.size();
     Node* prev = nullptr;
     Node* cur = _tables[index];
     while(cur)
     {
         if(cur->_kv.first == key)
         {
             //找到这个节点
             if(prev == nullptr)
             {
                 //cur是第一个节点
                 _table[index] = cur->_next;
                 delete cur;
             }
             else
             {
                 //不是头节点
                 prev->next = cur->_next;
                 delete cur;
             }
             --_n;
             return true;
         }
         else
         {
             prev = cur;
             cur = cur->_next;
         }
     }
     //没有这个值
     return false;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

开散列和闭散列一样，都得通过仿函数处理string的情况：

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return key;
	}
};
// 特化
template<>
struct HashFunc < string >
{
	size_t operator()(const string& key)
	{
		// BKDR Hash思想
		size_t hash = 0;
		for (size_t i = 0; i < key.size(); ++i)
		{
			hash *= 131;
			hash += key[i];
		}

		return hash;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

哈希表的大小尽可能是一个素数，这样效率会有提高，源码里面增加了一个素数表，还有一个GetNextPrime函数，获取下一个素数，我们可以用这个函数来获得newSize：

size_t GetNextPrime(size_t prime)
{
    const int PRIMECOUNT = 28;
    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];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

所以我们的扩容的newSize这样获取，这样可以获取比表大小大的素数，所以insert接口扩容大小这样写效率更高：

size_t newSize = GetNextPrime(_table.size());//获取比表大小大的素数
1

STL当中有桶的个数和最大桶的个数的接口：

哈希桶的析构函数

~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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

哈希表开散列的完整代码

namespace bucket_hash
{
	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)
		{}
	};

	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:

		// 拷贝 和 赋值 需要自己实现桶的拷贝

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

		bool Erase(const K& key)
		{
			if (_tables.size() == 0)
			{
				return false;
			}

			Hash hf;
			// 素数
			size_t index = hf(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[index];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					// 1、cur是头结点
					// 2、非头节点
					if (prev == nullptr)
					{
						_tables[index] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;
					--_n;

					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}

			return false;
		}

		Node* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}

			Hash hf;
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				else
				{
					cur = cur->_next;
				}
			}

			return nullptr;
		}

		bool Insert(const pair<K, V>& kv)
		{
			Hash hf;

			//当负载因子到1时，进行扩容
			if (_n == _tables.size())
			{
				//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				size_t newSize = GetNextPrime(_tables.size());

				//HashTable<K, V> newHT;
				vector<Node*> newtables;
				newtables.resize(newSize, nullptr);
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;

						size_t index = hf(cur->_kv.first) % newSize;
						cur->_next = newtables[index];
						newtables[index] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}

				newtables.swap(_tables);
			}

			size_t index = hf(kv.first) % _tables.size();
			Node* cur = _tables[index];
			while (cur)
			{
				if (cur->_kv.first == kv.first)
				{
					return false;
				}
				else
				{
					cur = cur->_next;
				}
			}

			Node* newnode = new Node(kv);
			newnode->_next = _tables[index];
			_tables[index] = newnode;

			++_n;

			return true;
		}

	private:
		vector<Node*> _tables;
		size_t _n = 0; // 存储多少有效数据
	};
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/350867

C++之unordered_map和unordered_set以及哈希详解_c++ unorderdmap unorderset

unordered_map和unordered_set的使用

文章目录

unordered_map的文档

unordered_set和unordered_map的两个OJ题

两个数组的交集

两个数组的交集二

set和undered_set的性能比较

哈希

哈希概念

哈希冲突

常见哈希函数

哈希冲突的解决

闭散列

开散列

闭散列的实现

数据的存储结构

哈希表的结构

哈希表的插入

哈希表的查找

哈希表的删除

哈希表闭散列的代码

哈希表闭散列的完整代码

开散列的实现

开散列概念

数据的存储结构

哈希表的结构

哈希表的插入

哈希表的查找

哈希表的删除

哈希桶的析构函数

哈希表开散列的完整代码