万网网站建设万网网站建设,app软件制作,重庆万州网站建设找谁,免费一级域名注册网站文章目录一、unordered系列关联式容器二、哈希概念三、哈希冲突四、哈希函数五、解决哈希冲突1.闭散列——开放定址法2.代码实现3.开散列——开链法4.代码实现六、结语一、unordered系列关联式容器 在C98中#xff0c;STL提供了底层为红黑树结构的一系列关联式容器#xff0c…
文章目录一、unordered系列关联式容器二、哈希概念三、哈希冲突四、哈希函数五、解决哈希冲突1.闭散列——开放定址法2.代码实现3.开散列——开链法4.代码实现六、结语一、unordered系列关联式容器 在C98中STL提供了底层为红黑树结构的一系列关联式容器在查询时效率可达到 log2N即最差情况下需要比较红黑树的高度次当树中的节点非常多时查询效率也不理想。最好的查询是进行很少的比较次数就能够将元素找到因此在C11中STL又提供了4个unordered系列的关联式容器这四个容器与红黑树结构的关联式容器使用方式基本类似只是其底层结构不同 :unordered系列的关联式容器之所以效率比较高是因为其底层使用了哈希结构 unordered_set: 与set的区别在于不支持方向迭代器只是单向迭代器其他接口基本与set相似
int main()
{unordered_setint us;us.insert(10);us.insert(1);us.insert(10);us.insert(3);us.insert(4);us.insert(4);auto it us.begin();while (it ! us.end()){cout *it ;it;}cout endl;return 0;
}无序去重 unordered_map: 迭代器也是单向迭代器其他也基本与map相似
int main()
{unordered_mapstring, int countMap;string arr[] { 苹果,香蕉,苹果 };for (auto e : arr){auto it countMap.find(e);/*if (it countMap.end()){countMap.insert(make_pair(e, 1));}else{it-second;}*/countMap[e];}for (auto kv : countMap){cout kv.first : kv.second endl;}return 0;
}unordered_map的桶操作
函数声明功能介绍size_t bucket_count()const返回哈希桶中桶的总个数size_t bucket_size(size_t n)const返回n号桶中有效元素的总个数size_t bucket(const K key)返回元素key所在的桶号
实际运用
在长度 2N 的数组中找出重复 N 次的元素 给你一个整数数组 nums 该数组具有以下属性 nums.length 2 * n. nums 包含 n 1 个 不同的 元素 nums 中恰有一个元素重复 n 次 找出并返回重复了 n 次的那个元素。 class Solution {
public:int repeatedNTimes(vectorint nums) {unordered_mapint,int CountMap;//统计次数for(auto e:nums){CountMap[e];}//符合条件for(autokv:CountMap){if(kv.secondnums.size()/2)return kv.first;}return -1;}
};insert\find\erase性能比较随机数下unordered系列效率更高但是有序数的情况下就不行了
int main()
{const size_t N 1000000;unordered_setint us;setint s;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){v.push_back(rand());}size_t begin1 clock();for (auto e : v){s.insert(e);}size_t end1 clock();cout set insert: end1 - begin1 endl;size_t begin2 clock();for (auto e : v){us.insert(e);}size_t end2 clock();cout unordered_set insert: end2 - begin2 endl;size_t begin3 clock();for (auto e : v){s.find(e);}size_t end3 clock();cout set find: end3 - begin3 endl;size_t begin4 clock();for (auto e : v){us.find(e);}size_t end4 clock();cout unordered_set find: end4 - begin4 endl;cout s.size() endl;cout us.size() endl;size_t begin5 clock();for (auto e : v){s.erase(e);}size_t end5 clock();cout set erase: end5 - begin5 endl;size_t begin6 clock();for (auto e : v){us.erase(e);}size_t end6 clock();cout unordered_set erase: end6 - begin6 endl;return 0;
}二、哈希概念
顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即O( )搜索的效率取决于搜索过程中元素的比较次数。 理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。 如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素。
哈希映射key值跟存储位置建立关联关系
当向该结构中插入元素 根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放 搜索元素 对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功
该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表(Hash Table)(或者称散列表)
哈希函数设置为hash(key) key % capacity; capacity为存储元素底层空间总的大小:比如数据集合{176459} 三、哈希冲突
用该方法进行搜索不必进行多次关键码的比较因此搜索的速度比较快问题。但是当插入元素44会出现哈希冲突
哈希冲突不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞 比如44%104但是4的位置已经被占用了。 四、哈希函数
如果哈希函数设计的不够合理就会引发哈希冲突。
哈希函数设计原则 哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间 哈希函数计算出来的地址能均匀分布在整个空间中 哈希函数应该比较简单 常见哈希函数
直接定制法–(常用) 取关键字的某个线性函数为散列地址HashKey A*Key B 优点简单、均匀 缺点需要事先知道关键字的分布情况使用场景适合查找比较小且连续的情况除留余数法–(常用) 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数**Hash(key) key% p(pm),**将关键码转换成哈希地址平方取中法–(了解) 假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址 再比如关键字为4321对它平方就是18671041抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合不知道关键字的分布而位数又不是很大的情况折叠法–(了解) 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)然后将这几部分叠加求和并按散列表表长取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布适合关键字位数比较多的情况随机数法–(了解) 选择一个随机函数取关键字的随机函数值为它的哈希地址即H(key) random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法数学分析法–(了解) 设有n个d位数每一位可能有r种不同的符号这r种不同的符号在各位上出现的频率不一定相同可能在某些位上分布比较均匀每种符号出现的机会均等在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小选择其中各种符号分布均匀的若干位作为散列地址。
哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突 五、解决哈希冲突
解决哈希冲突两种常见的方法是闭散列和开散列
1.闭散列——开放定址法
闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢
线性探测
从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止
插入通过哈希函数获取待插入元素在哈希表中的位置 删除 :采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响其他元素的搜索 比如上述例子中如果删除27此时要在找38会发现在搜索过程就遇到了空影响到了38的查找。解决方案线性探测采用标记的伪删除法来删除一个元素 给每个位置加一个状态标识
在有限的空间内随着我们插入的数据越来越多冲突的概率也越来越大查找效率越来越低所以闭散列的冲突表不可能让它满了所以引入了负载因子
负载因子/载荷因子等于表中的有效数据个数/表的大小衡量表的满程度在闭散列中负载因子不可能超过11代表满了。一般情况下负载因子一般在0.7左右。负载因子越小冲突概率也越小但是消耗的空间越大负载因子越大冲突概率越大空间的利用率越高。
当负载因子大于0.7的时候就需要进行扩容了扩容不能进行直接拷贝映射的位置会随空间大小发生变化所以需要重新计算映射的位置.
线性探测优点逻辑简单实现也简单 线性探测缺点一旦发生哈希冲突所有的冲突连在一起容易产生数据“堆积”即不同关键码占据了可利用的空位置使得寻找某关键码的位置需要许多次比较直到找到空为止导致搜索效率降低
二次探测
线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位置的方式就是挨着往后逐个去找starti二次探测为了避免该问题找下一个空位置的方法为以i的2次方去进行探测starti^2: 但是本质上还是没有解决问题占用别人的空间
2.代码实现
#include vector
templateclass K//仿函数
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};
//特化
template
struct HashFuncstring
{size_t operator()(const string key){size_t hash 0;for (auto ch : key){hash * 131;//顺序abccbahash ch;}return hash;}
};
//闭散列
namespace closehash
{enum State{EMPTY,EXIST,DELETE,};templateclass K,class Vstruct HashData{pairK, V _kv;State _state EMPTY;};templateclass K,class V,class HashHashFuncKclass HashTable{typedef HashDataK,V Data;public:HashTable():_n(0){_tables.resize(10);}bool Insert(const pairK, V kv){if (Find(kv.first))return false;//负载因子if (_n * 10 / _tables.size() 7){HashTableK, V, Hash newHT;newHT._tables.resize(_tables.size()*2);for (auto e : _tables){if (e._state EXIST){newHT.Insert(e._kv);}}}Hash hf;//string?size_t hashi hf(kv.first) % _tables.size();while (_tables[hashi]._state EXIST){hashi;hashi % _tables.size();}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;}Data* Find(const K key){Hash hf;size_t hashi hf(key) % _tables.size();while (_tables[hashi]._state ! EMPTY){if (_tables[hashi]._state EXIST _tables[hashi]._kv.first key){return _tables[hashi];}hashi;hashi % _tables.size();}return nullptr;}bool Erase(const K key){Data* ret Find(key);if (ret){ret-_state DELETE;--_n;return true;}else{return false;}}private:vectorData _tables;size_t _n 0;};void TestHT1(){HashTableint, int ht;int a[] { 18, 8, 7, 27, 57, 3, 38, 18 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(17, 17));ht.Insert(make_pair(5, 5));cout ht.Find(7) endl;cout ht.Find(8) endl;ht.Erase(7);cout ht.Find(7) endl;cout ht.Find(8) endl;}void TestHT2(){string arr[] { 苹果, 西瓜, 香蕉, 草莓, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };//HashTablestring, int, HashFuncString countHT;HashTablestring, int countHT;for (auto e : arr){HashDatastring, int* ret countHT.Find(e);if (ret){ret-_kv.second;}else{countHT.Insert(make_pair(e, 1));}}HashFuncstring hf;cout hf(abc) endl;cout hf(bac) endl;cout hf(cba) endl;cout hf(aad) endl;}
}代码需注意的点
1.仿函数考虑到统计出现次数因为字符串不能够取模所以我们可以给HashTable增加一个仿函数Hash其可以将不能取模的类型转成可以取模的类型同时把string特化出来解决字符串不能取模的问题
2.字符串哈希求法考虑到顺序问题比如abc,cba如果只乘以131则结果是相同的所以我们可以加上ch在乘以131
3.开散列——开链法
开散列开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中 从上图可以看出开散列中每个桶中放的都是发生哈希冲突的元素,不一定要有序。
开散列增容问题 由于桶的个数是一定的随着元素的不断插入每个桶中元素的个数不断增多极端情况下可能会导致一个桶中链表节点非常多会影响的哈希表的性能因此在一定条件下需要对哈希表进行增容。 开散列最好的情况是每个哈希桶中刚好挂一个节点再继续插入元素时每一次都会发生哈希冲突。 所以在元素个数刚好等于桶的个数时可以给哈希表增容 。研究分析表明素数作为哈希表的长度可以尽可能减小哈希冲突。所以可提前定义一个素数表。 4.代码实现
//开散列
namespace buckethash
{templateclass K,class Vstruct HashNode{pairK, V _kv;HashNodeK, V* _next;HashNode(const pairK, V kv):_kv(kv), _next(nullptr){}};templateclass K,class V,class HashHashFuncKclass HashTable{typedef HashNodeK, V Node;public:HashTable():_n(0){_tables.resize(__stl_next_prime(0));}~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;}}bool Insert(const pairK, V kv){if (Find(kv.first)){return false;}if (_tables.size() _n){//消耗/*HashTableK, V, Hash newHT;newHT._tables.resize(_tables.size() * 2);for (auto cur : _tables){while (cur){newHT.Insert(cur-_kv);cur cur-_next;}}_tables.swap(newHT._tables);*/vectorNode* newTables;newTables.resize(__stl_next_prime(_tables.size()), nullptr);for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;size_t hashi Hash()(cur-_kv.first) % newTables.size();cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTables);}size_t hashi Hash()(kv.first) % _tables.size();Node* newnode new Node(kv);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;}Node* Find(const K key){size_t hashi Hash()(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){return cur;}else{cur cur-_next;}}return nullptr;}bool Erase(const K key){size_t hashi Hash()(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){if (cur _tables[hashi]){_tables[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;--_n;return true;}else{prev cur;cur cur-_next;}}return false;}inline unsigned long __stl_next_prime(unsigned long n){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};for (int i 0; i __stl_num_primes; i){if (__stl_prime_list[i] n){return __stl_prime_list[i];}}return __stl_prime_list[__stl_num_primes - 1];}private:vectorNode* _tables;size_t _n 0;};void TestHT1(){HashTableint, int ht;int a[] { 18, 8, 7, 27, 57, 3, 38, 18,17,88,38,28 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(5, 5));ht.Erase(17);ht.Erase(57);}void TestHT2(){string arr[] { 苹果, 西瓜, 香蕉, 草莓, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };//HashTablestring, int, HashFuncString countHT;HashTablestring, int countHT;for (auto e : arr){auto ret countHT.Find(e);if (ret){ret-_kv.second;}else{countHT.Insert(make_pair(e, 1));}}}}六、结语
开散列与闭散列比较 应用链地址法处理溢出需要增设链接指针似乎增加了存储开销。事实上 由于开地址法必须保持大量的空闲空间以确保搜索效率如二次探查法要求装载因子a 0.7而表项所占空间又比指针大的多所以使用链地址法反而比开地址法节省存储空间。
