文章目录
unordered系列关联式容器
有unordered_mapunordered_setunordered_multimapunordered_multiset
这些是用哈希表是实现的 用法的话跟eg:set那种几乎相同 --接口都差不多
他们可以用范围for去遍历哈
跟set那些的区别:
1.unordered系列的容器的迭代器是单向迭代器
2.unordered系列中序遍历出来不是有序的
3.unordered系列的容器的性能比eg:set那些要稍微好些;但是升序或降序的数据插入的话，set好些其实
引申:比较性能要在release下面比较
哈希
哈希也叫做散列，是存储的值跟存储位置建立出的一个对应关系 跟计数排序很像很像
自己模拟实现的哈希不要存同一个key进去！！！
哈希是以牺牲空间为代价，提高查询的效率
建立对应关系的时候有两个常用的方法:
1.直接定址法(值分布范围集中得时候用这个)
比如:统计字符串中字符出现的次数–可以把字符跟下标一一对应
2.除留余数法(适用于值分布范围分散的)
eg:值%n，把这个东西放在对应下标下面
哈希冲突
其实就是不同的值映射到了相同的位置上–这个位置存不下了
解决哈希冲突的方案:
1.闭散列–也叫做开放定址法
做法:当前位置被占用了，按规则去找下一个位置存着
其中又分为1.线性探测 2.二次探测 …
2.开散列–也叫做链地址法–自己一般叫哈希桶
闭散列的模拟实现
这里的话个人搭配的是除留余数法加上线性探测
二次探测的方法跟线性探测的区别就是:
线性探测是这个位置满了去下一个位置找(也就是下标加i去找–这个解释是用来配合下面理解的)
二次探测是这个位置满了,下标加上i^2去找,比如:本来应该在0下标，但是满了，去1,4,9这样
enumSTATE{ EXIST, EMPTY, DELETE };template<classK,classV>structHashData{ pair<K, V> _kv; STATE _state = EMPTY;};template<classK>structDefaultHashFunc{ size_t operator()(const K& key){return(size_t)key;}//这个就是全部转变成无符号整数去搞--用其他的方法也是可以的哈};//引申:关于字符串的话，是专门有个字符串哈希算法的template<classK,classV,classHashFunc= DefaultHashFunc<K>>classHashTable{public:HashTable(){ _table.resize(10);//先给他一点空间,不然下面扩容那里不行}boolInsert(const pair<K, V>& kv){// 扩容if(_n*10/ _table.size()>=7)//这个表不能让他满{ size_t newSize = _table.size()*2;// 遍历旧表，重新映射到新表 HashTable<K, V, HashFunc> newHT; newHT._table.resize(newSize);// 遍历旧表的数据插入到新表for(size_t i =0; i < _table.size(); i++){if(_table[i]._state == EXIST){ newHT.Insert(_table[i]._kv);//这个用法好，在Insert里面用Insert}} _table.swap(newHT._table);}// 线性探测 HashFunc hf; size_t hashi =hf(kv.first)% _table.size();while(_table[hashi]._state == EXIST){++hashi; hashi %= _table.size();//如果到头了直接重头再来//这里要用size，不是capacity，因为下面要用[]，而[]底层又是断言的size} _table[hashi]._kv = kv; _table[hashi]._state = EXIST;++_n;returntrue;} HashData<const K, V>*Find(const K& key)//注意这个是怎么实现的{// 线性探测 HashFunc hf;//类的实例化 size_t hashi =hf(key)% _table.size();while(_table[hashi]._state != EMPTY){if(_table[hashi]._state == EXIST && _table[hashi]._kv.first == key){return(HashData<const K, V>*)&_table[hashi];}++hashi; hashi %= _table.size();}returnnullptr;}boolErase(const K& key){ HashData<const K, V>* ret =Find(key);if(ret){ ret->_state = DELETE;--_n;returntrue;}returnfalse;}private: vector<HashData<K, V>> _table; size_t _n =0;// 存储有效数据的个数 --跟size和capacity还是有区别哈};
这里的话是用了EXISTEMPTYDELETE 去做了状态标记
这个DELETE就巧妙的解决了想删除数，但是又不止填啥进去的问题
注意:在扩容的时候,DELETE的是不用搞到新表里面的哈
线性探测的Find的实现:这个位置是EXIST并且值是key的话才要–如果到空了还没找到的话就是没有–开始的话就是从key%_n那个位置开始找
用开放定址法的话不能让这个存数据的vector太满了，不然在插入那些的时候会很费时间–有些的位置要往后找:
所以
负载因子越大，冲突概率越大，但是空间利用率越高
负载因子越小，冲突概率越小，但是空间利用率越低
–当然这个方法也保证了哈希表不会满出来，一直都会有空位
引申:类模板的模板参数有const和无const都属于两个类型
跟变量带和不带const是不一样的
引申:类模板的按需编译
类模板实例化出来之后，里面的成员函数只有在被用了的才会编译出来，其他的不会–也就是其他的错了都检测不出来
开散列的模拟实现
template<classK,classT,classKeyOfT,classHashFunc= DefaultHashFunc<K>>//这个DefaultHashFunc跟前散列那里的一样classHashTable{typedef HashNode<T> Node;// 友元声明template<classK,classT,classPtr,classRef,classKeyOfT,classHashFunc>friendstructHTIterator;public:typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;typedef HTIterator<K, T,const T*,const T&, KeyOfT, HashFunc> const_iterator; iterator begin(){// 找第一个桶for(size_t i =0; i < _table.size(); i++){ Node* cur = _table[i];if(cur){returniterator(cur,this);}}returniterator(nullptr,this);} iterator end(){returniterator(nullptr,this);} const_iterator begin()const{// 找第一个桶for(size_t i =0; i < _table.size(); i++){ Node* cur = _table[i];if(cur){returnconst_iterator(cur,this);}}returnconst_iterator(nullptr,this);} const_iterator end()const{returnconst_iterator(nullptr,this);}HashTable(){ _table.resize(10,nullptr);}~HashTable(){for(size_t i =0; i < _table.size(); i++){ Node* cur = _table[i];while(cur){ Node* next = cur->_next;delete cur; cur = next;} _table[i]=nullptr;}}boolInsert(const T& data){ KeyOfT kot; iterator it =Find(kot(data));if(it !=end()){returnmake_pair(it,false);} HashFunc hf;// 负载因子到1就扩容if(_n == _table.size()){ size_t newSize = _table.size()*2; vector<Node*> newTable; newTable.resize(newSize,nullptr);// 遍历旧表，把节点牵下来挂到新表for(size_t i =0; i < _table.size(); i++){ Node* cur = _table[i];while(cur){ Node* next = cur->_next;// 头插到新表 size_t hashi =hf(kot(cur->_data))% newSize; cur->_next = newTable[hashi]; newTable[hashi]= cur; cur = next;} _table[i]=nullptr;//这个没用其实也行} _table.swap(newTable);} size_t hashi =hf(kot(data))% _table.size();// 头插 Node* newnode =newNode(data); newnode->_next = _table[hashi]; _table[hashi]= newnode;++_n;returnmake_pair(iterator(newnode,this),true);} Node*Find(const K& key){ HashFunc hf; KeyOfT kot; size_t hashi =hf(key)% _table.size(); Node* cur = _table[hashi];while(cur){if(kot(cur->_data)== key){returniterator(cur,this);} cur = cur->_next;}returnend();//不要搞nullptr,因为需要的类型可能不合适}boolErase(const K& key){ HashFunc hf; KeyOfT kot; size_t hashi =hf(key)% _table.size(); Node* prev =nullptr; Node* cur = _table[hashi];while(cur){if(kot(cur->_data)== key){if(prev ==nullptr){ _table[hashi]= cur->_next;}else{ prev->_next = cur->_next;}--_n;delete cur;returntrue;} prev = cur; cur = cur->_next;}--_n;returnfalse;}private: vector<Node*> _table;// 指针数组//没必要用vector<list>类型，因为用不了那么多功能而且到时候哈希表的迭代器不好模拟实现 size_t _n =0;// 存储了多少个有效数据};
这个vector<Node*> _table里面存的是指针哈,然后有需要插一个位置的话，就头插到这个位置
这个哈希桶的打印的话，最好是vector里面的一个"链表"打成一行这样好看些
哈希桶的DefaultHashFunc跟前散列那里的一样的方法其实
哈希桶走到尽头了的话是不会重头再走的!
关于这个哈希桶的扩容问题:
等负载因子到1就扩容(一般是这样的)–不扩容的话效率会有点低
新旧表的转移跟闭散列那个有点不一样–这里是把旧的节点搞到新表上(一个一个拆)
有些地方的扩容说法是:扩容成素数
给里面一个素数表，然后超过当前容量了，就扩容到下一个素数那么多–有些人觉得这个很好，但是有些人觉得又不好
关于这个哈希桶的删除问题:(prev就是这个"链表"当前节点的前节点)
分两种情况 1.删除的这个节点没有prev就直接把vector里面的改成cur->_next
哈希桶的节点其实可以从链表结构换成树结构:（其实这也是种优化方法）
eg:节点"连接"的东西长度超过一定数量时，把他改成树结构，然后节点里面存根节点的指针，这样就不错
关于T里面会有K，但是又传K过来:
因为传K过来才好统一写Find和Erase
引申:1.如果友元是模板的话eg:类模板 那么友元声明的时候需要把模板参数带上
eg:
哈希桶里面迭代器的模拟实现
template<classK,classT,classPtr,classRef,classKeyOfT,classHashFunc>structHTIterator{typedef HashNode<T> Node;typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> Iterator;//这个的话其实也就在HTIterator(const Iterator& it)这里用到过 Node* _node; HashTable<K, T, KeyOfT, HashFunc>* _pht;HTIterator(Node* node,const HashTable<K, T, KeyOfT, HashFunc>* pht):_node(node),_pht(pht){}HTIterator(const Iterator& it):_node(it._node),_pht(it._pht){}//这个的话可以让iterator隐式转换成const_iterator//对iterator来说，是拷贝构造函数//对const_iterator来说是构造函数 Ref operator*(){return _node->_data;} Ptr operator->(){return&_node->_data;} Self&operator++(){if(_node->_next){// 当前桶还没完 _node = _node->_next;}else{ KeyOfT kot; HashFunc hf; size_t hashi =hf(kot(_node->_data))% _pht->_table.size();// 从下一个位置查找查找下一个不为空的桶++hashi;while(hashi < _pht->_table.size()){if(_pht->_table[hashi]){ _node = _pht->_table[hashi];return*this;}else{++hashi;}} _node =nullptr;}return*this;}booloperator!=(const Self& s){return _node != s._node;}booloperator==(const Self& s){return _node == s._node;}};
问题:迭代器里面要用到哈希表，哈希表里面也要用到迭代器，怎么办?
解决方法:用前置声明
eg: 如果迭代器在哈希表前面就
unordered_set的封装
这里的话自己用的是哈希桶实现的哈希表
namespace renshen {template<classK>classunordered_set{structSetKeyOfT{const K&operator()(const K& key){return key;}};public:typedeftypenamehash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;typedeftypenamehash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator; iterator begin(){return _ht.begin();} iterator end(){return _ht.end();} pair<const_iterator,bool>insert(const K& key){ pair<typenamehash_bucket::HashTable<K, K, SetKeyOfT>::iterator,bool> ret = _ht.Insert(key);return pair<const_iterator,bool>(ret.first, ret.second);}private: hash_bucket::HashTable<K, K, SetKeyOfT> _ht;};}
unordered_map的封装
这里的话自己用的是哈希桶实现的哈希表
namespace renshen {template<classK,classV>classunordered_map{structMapKeyOfT{const K&operator()(const pair<K, V>& kv){return kv.first;}};public:typedeftypenamehash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedeftypenamehash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::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 = _ht.Insert(make_pair(key,V()));return ret.first->second;//这里要注意是->second 因为自己模拟实现的迭代器也是类似指针}private: hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT> _ht;};}
位图
就是用数的比特位去表达信息
这个位图其实在库里面也是有实现的，那个函数也叫bitset
接口的话，常用的也就三个:testsetreset
跟下面的模拟实现其实差不多
应用
面试题:
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。【腾讯】
这个题的话用set或者排序＋二分查找的话需要的空间都是很大的–因为有40亿个数
所以的话需要采取位图的方法–这里的话就是eg:一个int类型的数有32个比特位，比如:第一个比特位表示1这个数在还是不在这样
注意的是，要有size_t范围个比特位，而不是单单40亿个比特位哈
实现代码:template<size_t N>classbitset{public:bitset(){ _a.resize(N /32+1);}//N的话传这个类型的最大值就够了，因为+1可以帮忙把0需要的那个位置留出来//size_t的最大值的话直接bitset<-1>就行了，-1正好轮过去就是最大值// x映射的那个标记成1voidset(size_t x){ size_t i = x /32; size_t j = x %32; _a[i]|=(1<< j);}// x映射的那个标记成0voidreset(size_t x){ size_t i = x /32; size_t j = x %32; _a[i]&=(~(1<< j));}booltest(size_t x){ size_t i = x /32; size_t j = x %32;return _a[i]&(1<< j);}private: vector<int> _a;};
引申:
比特位是从右到左排的–位运算的角度
跟大端小端没关系–大端小端影响的只是在内存中的存储
引申:1B（字节）=8b（比特位）
1 KB = 1024 B
1 MB = 1024 KB
1 GB = 1024 MB
1TB = 1024GB
从小到大就是 b B KB MB GB TB
给定100亿个无符号整数，设计算法找到只出现一次的整数(没说明的话一般是32位的)
这个的话100亿个整数其实没这么多，顶多也就size_t那么多,也就42亿多点
就用两个位图存就行了，两个位图的同一个位置表示数的二进制就行了
给两个文件，分别有100亿个整数，我们只有一个G的内存，如果找到两个文件的交集
用一个位图存42亿多个的整数的话要512MB，正好够存用两个位图的空间
可以把两个文件分别映射到两个位图，如果对应位置都是1的话，这个数就是交集
或者一个文件存位图里，遍历另一个文件去比对，放入交集的值在位图里面要reset掉
注意理解这里的交集
布隆过滤器
就是把一个东西他的特性用类似哈希函数的方法放入位图里面，如果这些位置都为1的话，说明这个东西可能存在，反之，则这个东西一定不在这里面
–布隆过滤器是一种利用多个独立哈希函数 + 位图实现的高效存在性判断结构
应用场景:用于那些不需要精确的场景
比如:快速判断昵称是否注册过
如果想精确的话，就查询出来是在的时候去数据库里再查一遍–这样照样可以减轻数据库查询的压力，提高效率
布隆过滤器的模拟实现
template<size_t N,classK=....,classHash1=...,classHash2=...,classHash3=...>//这里的话就是几个独立的哈希函数classBloomFilter{public:voidSet(const K& key){ size_t hash1 =Hash1()(key)% N;//Hash1()这样会创建一个临时对象 _bs.set(hash1); size_t hash2 =Hash2()(key)% N; _bs.set(hash2); size_t hash3 =Hash3()(key)% N; _bs.set(hash3);}boolTest(const K& key){ size_t hash1 =Hash1()(key)% N;if(_bs.test(hash1)==false)returnfalse; size_t hash2 =Hash2()(key)% N;if(_bs.test(hash2)==false)returnfalse; size_t hash3 =Hash3()(key)% N;if(_bs.test(hash3)==false)returnfalse;returntrue;}private: bitset<N> _bs;};
关于这个K的话，一定要让他是唯一的
如果没有唯一信息的话，可以用不同信息的组合来让他唯一
注意:布隆过滤器一般不支持删除操作,支持删除的话会导致本来在的检查出来发现不在
如果硬要加上删除操作的话，需要:多个位标识一个值，然后使用引用计数–标记这个位被标记了多少次
关于布隆过滤器的优化:
k是哈希函数个数，m是布隆过滤器长度,n是插入的元素个数
这样的话,k和m取的才是适合业务的
这里哈希函数举例:structBKDRHash{ size_t operator()(const string& str){ size_t hash =0;for(auto ch : str){ hash = hash *131+ ch;}return hash;}};
哈希切割
也就是运用哈希函数把一个大文件的数据根据特征分到好几个小文件里面
哈希切割的应用
给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法
query在这里是待处理的字符串、数据项
近似算法的话就是:用布隆过滤器
精确算法的话:用哈希切割–这俩个文件用相同的哈希函数分，但是结果不存同一个文件里面(eg:一个存到A1.A2，一个存到B1.B2去这样)–两个文件相同的query肯定会进到"相同编号"去(比如:A1和A2)
–分成多少个小文件的话要看情况
使用哈希切割发生的冲突太多了怎么办,内存只有1G不够用啊:
这时的内存不够用有两种场景:1.相同的query太多了 2.冲突的太多了
解决方法:
先把小文件的query读到set里面，如果set的insert报错抛异常(抛的bad_alloc)，那么久说明冲突的太多了;如果能够全部存进入，就说明是相同的太多了
–有大量冲突的话，就要换一个哈希函数，进行二次切分
跟上面类似的题目:给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址以及求最多的K个地址
–关于求最多的K个地址的话，自己的想法:
每一个小文件中的前k多的地址保留到堆和map里面，最后再终极比较
文件是存磁盘里的哈，不占内存 --内存和CPU高速缓存也要区分
作业部分
散列函数有一个共同性质，即函数值应按（）取其值域的每一个值。 ©
A.最大概率
B.最小概率
C.同等概率
D.平均概率
解决散列法中出现冲突问题常采用的方法是(D)
A.数字分析法、除余法、平方取中法
B.数字分析法、除余法、线性探测法
C.数字分析法、线性探测法、多重散列法
D.线性探测法、多重散列法、链地址法
引申: 常见哈希冲突处理：闭散列（线性探测、二次探测）、开散列(链地址法)、多重散列
已知有一个关键字序列：（19，14,23,1,68,20,84,27,55,11,10,79）散列存储在一个哈希表中，
若散列函数为H（key）=key%7，并采用链地址法来解决冲突，则在等概率情况下查找成功的平均查找长度为(A)
A.1.5
B.1.7
C.2.0
D.2.3
//注意:要拿总查找长度除以元素个数而不是7
已知某个哈希表的n个关键字具有相同的哈希值，
如果使用二次探测再散列法将这n个关键字存入哈希表，至少要进行（E）次探测。
A.n-1
B.n
C.n+1
D.n(n+1)
E.n(n+1)/2
F.1+n(n+1)/2
力扣 350. 两个数组的交集 II
力扣 350. 两个数组的交集 II
这个题的话主要核心就是怕前面的数已经给了vectorv，但是后面又给重复统计进去了
这时就需要，在给v之后，把hash1,hash2里面的这个值对应的东西记为0就行了
代码展示:classSolution{public: vector<int>intersect(vector<int>& nums1, vector<int>& nums2){ unordered_map<int,int>hash1; unordered_map<int,int>hash2; vector<int> v;for(auto e: nums1) hash1[e]++;for(auto e: nums2) hash2[e]++;for(auto e: nums1){if(hash1.count(e)&&hash2.count(e)){for(int i =0;i<min(hash1[e],hash2[e]);i++){ v.push_back(e);} hash1[e]=0; hash2[e]=0;}}return v;}};
下面关于位图说法错误的是（D）
A.位图就是用比特比特位表示一个数据的状态信息
B.通过位图可以求两个集合的交集
C.位图实际是哈希变形思想的一种应用
D.位图可以很方便的进行字符串的映射以及查找
//一般不用位图处理字符串,字符串转换成整型容易冲突
力扣 884. 两句话中的不常见单词
力扣 884. 两句话中的不常见单词
引申:""代表的是空字符串,没有’'这个东西!!!
只有multi_map和multi_set的count会返回对应出现的次数
set map unordered_set unordered_set都是返回的1或者0
代码展示:classSolution{public: vector<string>uncommonFromSentences(string s1, string s2){ unordered_map<string,int>hash1; unordered_map<string,int>hash2; vector<string>v; string a;for(int i =0;i<s1.size();i++){if(s1[i]==' '){ hash1[a]++; a ="";}else a+=s1[i];} hash1[a]++; a ="";for(int i =0;i<s2.size();i++){if(s2[i]==' '){ hash2[a]++; a ="";}else a+=s2[i];} hash2[a]++; a ="";for(int i =0; i<s1.size();i++){if(s1[i]==' ')//{if(hash1[a]==1&&hash2.count(a)==0) v.push_back(a); a ="";}else a+=s1[i];}if(hash1[a]==1&&hash2.count(a)==0) v.push_back(a); a ="";for(int i =0; i<s2.size();i++){if(s2[i]==' '){if(hash2[a]==1&&hash1.count(a)==0) v.push_back(a); a ="";}else a+=s2[i];}if(hash2[a]==1&&hash1.count(a)==0) v.push_back(a); a ="";return v;}};
关于unordered_map和unordered_set说法错误的是（D） A.它们中存储元素的类型不同，unordered_map存储键值对，而unordered_set中只存储key B.它们的底层结构相同，都使用哈希桶 C.它们查找的时间复杂度平均都是O(1)//这个是对的 D.它们在进行元素插入时，都得要通过key的比较去找待插入元素的位置
