怎样建网站才赚钱,泾川网站建设,定制企业网站建设哪家好,做网站一般是什么工作文章目录 unordered_map#xff0c;unorder_set和map #xff0c;set的差异哈希表的实现概念直接定址法哈希冲突哈希冲突举个例子 负载因子将关键字转为整数哈希函数除法散列法/除留余数法 哈希冲突的解决方法开放定址法线性探测二次探测 开放定址法代码实现 哈希表的代码 un… 文章目录 unordered_mapunorder_set和map set的差异哈希表的实现概念直接定址法哈希冲突哈希冲突举个例子 负载因子将关键字转为整数哈希函数除法散列法/除留余数法 哈希冲突的解决方法开放定址法线性探测二次探测 开放定址法代码实现 哈希表的代码 unordered_mapunorder_set和map set的差异 unordered_mapunordered_set在功能方面和mapset基本一致 unordered_map和unordered_set底层是哈希表遍历无序查找删除修改的效率为O(1) map和set底层是红黑树遍历有序查找删除修改的效率为O(logN) 功能迭代器之间也有差异set是双向迭代器unordered_set是单向迭代器set底层是红黑树走中序是有序的所以迭代器的遍历是有序去重unordered_set底层是哈希表迭代器遍历是无序去重效率unordered_set和set性能方面也有差异set是O(logN),unordered_set是O(1)使用要求对key的要求不同set要求key支持小于的比较unordered_set要求key转为整形且要支持等于的比较unordered_set,unordered_map和map,set要求基本一致unordered_multimap和unordered_multiset支持键值冗余key冗余效率上无序的比有序的总体上要好很多但是在排有序的数的时候有序的删除插入比无序的效率高但是查找效率还是无序的效率高
void set_test1()
{// 迭代器遍历setint s { 3,1,6,7,8,2};setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}// 3 1 6 7 8 2cout endl;
}int main()
{set_test1();return 0;
}哈希表的实现
概念
哈希表也叫散列表散列有散乱排列的意思。通过关键字Key跟存储位置建立一个映射关系
直接定址法
适合关键字的范围比较集中的直接定址法是非常高效的方法。比如给’a’ - z’的小写字母为范围通过直接映射或相对映射关键字的值就是存储位置的下标下面也有一道题是这样的。只适合整形字符串浮点数都不行
字符串中的第一个唯一字符
class Solution
{
public:int firstUniqChar(string s) {int hash[26] {0};for(auto ch : s){hash[ch - a];} for(int i 0;i s.size();i){if(hash[s[i] - a] 1)return i;}return -1;}
};哈希冲突
直接定址法的缺点非常明显当关键字比较分散时会浪费空间甚至空间会不够用。当有N个值要映射到M个空间中M N就要借助哈希函数关键字key要放到数组的h(key的位置h(key)计算的值要在[0,M)中。哈希冲突也叫哈希碰撞就是两个不同的key映射到同一个位置了我们要设计一个哈希函数来减少哈希冲突在实际问题中哈希冲突是不可避免的
哈希冲突举个例子
N 100 M 200,N个数要存到M个空间中 除法散列法h(key) key % M 哈希冲突3 % 200 3203 % 200 3
负载因子
哈希表中已经存了N个值哈希表的大小为M,负载因子 N/M,负载因子也叫装载因子/载荷因子负载因子越大哈希冲突越高空间利用率越高相反就越低。
将关键字转为整数
比如是浮点数转为整数或者有符号的整数负数要转为正数字符串转为整数。
哈希函数
一个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中但是实际中却很难做到但是我们要尽量往这个方向去考量设计。
除法散列法/除留余数法
除法散列表是最常用的哈希表的大小为M,通过key除以M的余数作为映射的下标h(key) key % M使用这个方法时要注意M不要为2的幂10的幂等。如果是2^X那么key%2 ^ X,相当于保留key的后X位那么key的后X位相同的值就哈希冲突了。比如63,31如果M是162 ^ 4,计算出的哈希值都是1500111111为6300011111为31后4位都是1111所以会哈希冲突。10进制的比如123和345123如果M 10 ^ 3,保留后三位都是123,也哈希冲突。当使用除留余数法时建议M取不太接近2的整数次幂的一个质数%其实用到了除除的效率比位运算的效率更低所以Java中用了位运算
Java中用了2的整数次幂作为哈希表的大小M
哈希冲突的解决方法
开放定址法
开放定址法哈希表是空的把所有元素放到哈希表中当关键字key用哈希函数找到了冲突位置就按照某种规则去找一个没有存储数据的位置进行储存。这里有三种规则线性探测二次探测双重探测
线性探测
现在给一组数据 {19,30,5,36,13,20,21,12} 等这一组值映射到M11的表中
h(19) 8h(30) 8h(5) 5h(36) 3 h(13) 2h(20) 9h(21) 10h(12) 1 上面这组数据在8位置就冲突了
线性探测从发生冲突的位置依次往后探测直到找到一个没有存储数据的位置为止如果走到哈希尾都没有找到则回绕到哈希头继续往后找h(key) hash0 key % M , hash0位置冲突了则线性探测公式为hc(key, i) hashi (hash0 i) % M i {1, 2, 3, …, M − 1}因为负载因子必须小于1因为要留一个位置不放数据不然会出问题则最多探测M-1次一定能找到一个存储key的位置。连续冲突hash0位置连续冲突你占我的位置我占你的位置这种现象叫做 群集/堆积二次探测可以改善这样的问题
二次探测
二次探测和线性探测非常类似 如果往左走回绕到哈希表尾用减比如3-9到5的位置停下-6 M,M 11, -6 M 5
// 二次探测
int flag 1;
while (_tables[hashi]._state EXIST)
{// 存在进行二次探测,删除和空就退出hashi (hash0 i*i*flag) % _tables.size();if (hashi 0)hashi _tables.size();if (flag 1){flag -1;}else{flag 1;i;}
}开放定址法代码实现
h(19) 8h(30) 8h(5) 5h(36) 3 h(13) 2h(20) 9h(21) 10h(12) 1 蓝色的四个位置连续冲突 查找的原则遇到删除存在才继续找遇到空就结束查找 状态标识存在空和删除空和删除可以放值空就线性探测 要注意给每个存储值的位置加一个状态标识否则删除一些值以后会影响后面冲突的值的查找。 如下图我们删除30会导致查找20失败当我们给每个位置加⼀个状态标识{EXIST,EMPTY,DELETE} 删除30就可以不用删除值而是把状态改为 DELETE 那么查找20时是遇到 EMPTY 才能停止就可以找到20。
哈希表的代码
#pragma once#includevector// 枚举状态
enum State
{EXIST,EMPTY,DELETE
};templateclass K,class V
struct HashData
{pairK, V _kv;State _state EMPTY;
};templateclass K,class V
class HashTable
{
public:// 构造HashTable()// 会取到53:_tables(__stl_next_prime(0)),// 11是数据个数()_n(0){}// 为了解决M是质数的问题inline unsigned long __stl_next_prime(unsigned long n){// Note: assumes long is at least 32 bits.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};const unsigned long* first __stl_prime_list;const unsigned long* last __stl_prime_list __stl_num_primes;const unsigned long* pos lower_bound(first, last, n);// lower_bound取表中大于等于first的数return pos last ? *(last - 1) : *pos;}// 插入bool Insert(const pairK, V kv){// 不支持冗余if (Find(kv.first)){return false;}// 负载因子大于等于0.7就扩容if (_n * 10 / _tables.size() 7){// 扩容//vectorHashTableK, V newtables(_tables.size()*2);//for (auto data : _tables)//{// // 把旧表的数据映射到新表// // 不能直接拷贝,因为映射关系还是原来的(会乱)// if (data._state EMPTY)// {// size_t hash0 data._kv.first % newtables.size();// // ...// }//}//_tables.swap(newtables);// 上面的方法代码过于冗余// 把新表和旧表交换HashTableK, V newht;// newht._tables.resize(_table.size() * 2);newht._tables.resize(__stl_next_prime(_table.size()));for (auto data : _tables){// 把旧表的数据映射到新表if (data._state EMPTY){// 相当于递归newht.Insert(data._kv);}}// 函数结束,newht销毁,数据交换给旧表_tables.swap(newht._tables);}// key / M , M哈希表的空间大小size_t hash0 kv.first % _tables.size();size_t hashi hash0;size_t i 1;while (_tables[hashi]._state EXIST){// 存在进行线性探测,删除和空就退出hashi (hash0 i) % _tables.size();i;}// 二次探测//int flag 1;//while (_tables[hashi]._state EXIST)//{// // 存在进行二次探测,删除和空就退出// hashi (hash0 i*i*flag) % _tables.size();// if (hashi 0)// hashi _tables.size();// if (flag 1)// {// flag -1;// }// else// {// flag 1;// i;// }//}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;}// 查找HashDataK, V* Find(const K key){size_t hash0 key % _tables.size();size_t hashi hash0;size_t i 1;// Find等于空就找不到了while (_tables[hashi]._state ! EMPTY){if (_tables[hashi]._state EXIST _tables[hashi]._kv.first key){return _tables[hashi];}// 存在进行线性探测,删除和空就退出hashi (hash0 i) % _tables.size();i;}return nullptr;}// 删除bool Erase(const K key){HashDataK, V* ret Find(key);if (key){ret-_state DELETE;return true;}else{return false;}}private:vectorHashDataK, V _tables;size_t _n;// 记录哈希表中的数据个数
};#includeHashTable.hint main()
{int a[] { 19,30,5,36,13,20,21,12 };HashTableint, int ha;for (auto e : a){ha.Insert({ e,e });}ha.Erase(20);if (ha.Find(30)){cout 找到了 endl;}if (ha.Find(20)){cout 找到了 endl;}else{cout 没有找到 endl;}return 0;
}
