关联容器

发表于 | 分类于 | 阅读次数: |

关联容器

无序的关联容器（链式哈希表）O(1)

  • unordered_set : 无序集合 只存储key，不允许key重复的
  • unordered_multiset ： 无序多重集合 只存储key，允许key重复
  • unordered_map : 无序映射表 存储key-value，不允许key重复
  • unordered_multimap：无序多重映射表 存储key-value，允许key重复

有序的关联容器（红黑树）O(logn)

  • set : 无序集合 只存储key，不允许key重复的
  • multiset ： 无序多重集合 只存储key，允许key重复
  • map : 无序映射表 存储key-value，不允许key重复
  • multimap：无序多重映射表 存储key-value，允许key重

使用场景判断：基本上使用的都是无序的关联容器，只有在对key值的有序性有要求的应用场景，才需要用到有序的关联容器

写完没保存，全没了，心态崩了.jpg

哈希表（散列表）：如果一组数据，通过一种映射方式，能够找到该数据存储的位置，那么支持这种映射关系存储数据的数据结构（表）。

哈希表：除留余数法=》哈希函数/散列函数

怎么解决哈希冲突？

1.线性探测法

2.链地址法（拉链法）=》链式哈希表 无序关联容器

如果桶里面的链表太长，定位到哈希桶以后，还得在链表的搜索上耗费时间。

（1）所选择的哈希函数一定要能够把元素离散均匀的放到各个桶中

（2）有一个衡量哈希表使用情况的参数，称作加载因子loadfactor

当已被占用的桶的个数/桶的总数>0.75，哈希表就需要扩容了

哈希表扩容以后，原来哈希表中的元素需要重新扩容吗？

需要，代价还是挺高的，但是直接把链表的节点摘下来连到新的节点上，这样看代价也不是很高。

写了个框架，后面补完。。。（已更新）

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
#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <string>
using namespace std;

template<typename K,typename V>
struct Pair{
    Pair(const K &k=K(),const V &v=V())
    :first(k),second(v)
    {}
    K first;
    V second;
};

template<typename K,typename V>
class hashmap
{
public:
    //构造函数
    hashmap(int sizee=3,double loadfactor=0.75)
        :mloadfactor(loadfactor)
        ,musedbucketnum(0)
    {
        //不仅仅按照size开辟空间了，还给vector添加了size个list默认构造的容器
        mhashmap.resize(sizee);
    }
    //插入元素 Insert({123,"张三"})key不能重复
    void Insert(const Pair<K,V> &pairr)
    {
        double x=musedbucketnum*1.0/mhashmap.size();
        if(x>mloadfactor){
            expand();
        }
        //idx就是下标
        int idx=pairr.first%mhashmap.size();
        list<Pair<K,V>> &mylist=mhashmap[idx];
        if(mylist.empty()){
            musedbucketnum++;
        }
        else{
            for(auto &item : mylist){
                if(item.first==pairr.first){
                    //key已经存在，不会重复插入元素
                    return ;
                }
            }
        }
        mylist.push_back(pairr);
    }
    //传入key,删除key-value对
    void Erase(const K &key)
    {
        //idx就是下标
        int idx=key%mhashmap.size();
        auto &mylist=mhashmap[idx];
        if(!mylist.empty()){
            for(auto it=mylist.begin();it!=mylist.end();++it){
                if(it->first==key){
                    mylist.erase(it);//迭代器已经失效了，需要更新迭代器it才能继续使用
                    if(mylist.empty()){//如果桶唯一的元素被删除掉，这里需要更新已使用桶的数
                        musedbucketnum--;
                    }
                    return;
                }
            }
        }
    }
    //传入key，返回包含key的k-v对迭代器
    Pair<K,V>*findd(const K &key){
        int idx=key%mhashmap.size();
        auto&mylist=mhashmap[idx];
        if(!mylist.empty()){
            for(auto &item:mylist){
                if(item.first==key){
                    return &item;
                }
            }
        }
        return nullptr;
    }
    //map[123]="张三" 增加key-value 覆盖旧值    查询功能
    V& operator[](const K &key)
    {
        int idx=key%mhashmap.size();
        list<Pair<K,V> >&mylist =mhashmap[idx];
        if(mylist.empty()){
            musedbucketnum++;
        }
        else{
            for(auto &item:mylist){
                if(item.first==key){
                    return item.second;
                }
            }
        }
        //最好直接调用insert方法，这样新插入元素，就会适时地扩容哈希表
        mylist.push_back({key,V()});
        //把mylist尾结点的second值返回
        return mylist.back().second;
    }
private:
    //链式哈希表结构
    vector<list<Pair<K,V> > > mhashmap;
    //加载因子 默认0.75
    double mloadfactor;
    //记录已经使用的桶的个数
    int musedbucketnum;
    //扩容函数
    void expand()
    {
        vector<list<Pair<K,V> > >oldhashmap;
        mhashmap.swap(oldhashmap);
        mhashmap.resize(oldhashmap.size()*2+1);
        musedbucketnum=0;
        //遍历oldhashmap的每一个不空桶，把里面的list节点splice摘下来，放入新的哈希表mhashmap中
        for(auto &mylist:oldhashmap){
            while(!mylist.empty()){
                Pair<K,V>&pairr=mylist.front();
                int idx=pairr.first%mhashmap.size();
                auto&newlist=mhashmap[idx];
                if(newlist.empty()){
                    musedbucketnum++;
                }
                newlist.splice(newlist.begin(),mylist,mylist.begin());
            }
        }
    }
};
int main()
{
    hashmap<int,string>map1;
    map1.Insert({111,"zhangwei"});
    map1.Insert({222,"dali"});
    cout<<map1[111]<<endl;
    map1.Erase(111);
    //cout<<map1[111]<<endl;
    auto it=map1.findd(111);//O(1)
    if(it==nullptr){
        cout<<"111 not exist"<<endl;
    }
    else{
        cout<<"key:"<<it->first<<" value:"<< it->second<<endl;
    }
    return 0;
}