安徽省建设安全监督站的网站,wordpress点击弹窗,怎么下载别人网站模板,站长工具综合查询系统✍作者#xff1a;阿润菜菜 #x1f4d6;专栏#xff1a;C 文章目录 前言一、哈希表的特性 - 哈希函数和哈希冲突1 哈希函数2. 哈希冲突 二、闭散列的实现 -- 开放地址法1. 定义数据结构2.insert()3.Find()4. Erase()5.仿函数处理key值不能取模无法映射 --- BKDRHash 三、开… ✍作者阿润菜菜 专栏C 文章目录 前言一、哈希表的特性 - 哈希函数和哈希冲突1 哈希函数2. 哈希冲突 二、闭散列的实现 -- 开放地址法1. 定义数据结构2.insert()3.Find()4. Erase()5.仿函数处理key值不能取模无法映射 --- BKDRHash 三、开散列的实现 --- 链地址法哈希桶1. 定义框架结构2.insert()3.Find()4.Erase() 四、封装实现unordered系列容器1.迭代器设计2.unordered_map的[ ]操作 前言
unordered系列关联式容器是C11中新增的一类容器包括unordered_mapunordered_setunordered_multimap和unordered_multiset。它们的底层实现是哈希表可以快速地查找和插入元素时间复杂度为O(1)。它们的元素是无序的因此遍历时元素的顺序是不确定的。它们的使用方式和红黑树结构的关联式容器如map和set基本类似只是需要包含不同的头文件unordered_map或unordered_set。它们支持直接访问操作符operator[]可以使用key作为参数直接访问value。哈希最大的作用就是查找效率很高的哈希并不具有排序的功能unordered_map和unordered_set仅仅只有去重的功能而已
一、哈希表的特性 - 哈希函数和哈希冲突
哈希表是一种数据结构它提供了快速的插入操作和查找操作无论哈希表中有多少条数据插入和查找的时间复杂度都是为O(1)。哈希表是通过把关键码值映射到表中一个位置来访问记录这个映射函数叫做散列函数或哈希函数。哈希表的元素是无序的因为散列函数的映射结果是随机的。哈希表可能会产生碰撞也叫哈希冲突就是不同的关键码值映射到同一个位置这时就需要采用一些方法来解决碰撞比如开放地址法或链表法同时。
1 哈希函数
直接定址法–(常用) 取关键字的某个线性函数为散列地址HashKey A*Key B常用的A是1B是0。 优点简单、均匀 缺点需要事先知道关键字的分布情况若分布较广则空间消耗比较高。 使用场景适合查找比较小且连续的情况除留余数法–(常用) 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数 按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址一般不这么干最常用的就是拿vector.size()作为除数每次扩容将vector.size()扩容二倍。但后面开散列的解决方式那里我们会仿照库用质数的集合作为vector.size()然后用其作为除数。
2. 哈希冲突
当多个关键码key在通过哈希函数映射之后得到了相同的哈希地址也就是多个key映射到同一个位置上时这种现象称为哈希冲突或哈希碰撞。解决哈希冲突的办法一般为两种一种是闭散列的方式解决即用线性探测或二次探测的方式向后寻找空的哈希位置一种是开散列的方式解决即将哈希冲突的元素通过单链表链接逻辑上像哈希表挂了一个个的桶所以这样的解决方式也可称为链地址法或哈希桶方式。 区别概念介绍一下闭散列和开散列
开散列和闭散列都是解决哈希冲突的方法也就是当不同的关键码值映射到同一个位置时如何处理的问题。开散列方法又叫链地址法它是把发生冲突的关键码存储在散列表主表之外每个位置对应一个链表链表的头节点存储在主表中。这样当查找一个关键码时先通过散列函数得到其位置然后在对应的链表中进行查找。闭散列方法又叫开放地址法它是把发生冲突的关键码存储在主表中另一个槽内。这样当查找一个关键码时如果发现其位置已经被占用就按照一定的规则寻找下一个空闲的位置直到找到或者遍历整个表。开散列和闭散列的区别是 开散列需要额外的空间来存储链表节点而闭散列不需要开散列可以容纳任意多的元素而闭散列的容量有限开散列的查找效率取决于链表的长度而闭散列的查找效率取决于探测规则开散列更适合关键码值分布不均匀的情况而闭散列更适合关键码值分布均匀且空间紧张的情况。
二、闭散列的实现 – 开放地址法
1. 定义数据结构
闭散列的实现我们以键值作为存储元素来讲解。 我们采用vector作为底层容器用vector来存储哈希结点哈希结点是一个结构体其中存储键值对和状态值_state用于标定哈希映射位置为空、存在、删除三种状态。 同时为了判断什么时候进行哈希表的扩容在hashTable类中多增加了一个无符号整型的_n变量表示当前哈希表中存储数据的个数方便我们用数据个数和vector.size()作除法看结果是否大于负载因子如果大于则扩容如果不大于则继续插入。
enum state
{EMPTY,EXIST,DELETE
};
template class K, class V
struct HashNode
{HashNode(): _state(EMPTY){}HashNode(const pairK, V kv):_kv(kv), _state(EMPTY){}pairK, V _kv; //数据enum state _state; //状态
};
//......
};2.insert()
负载因子 哈希表冲突越多效率越低 若表中位置都满了就需要扩容 我们利用负载因子进行判断何时扩容
负载因子的概念 负载因子 填入表的元素个数 / 表的长度 表示 表储存数量的百分比
填入表的元素个数 越大表示冲突的可能性越大 填入表的元素个数 越小表示冲突的可能性越小 所以在开放定址法时应该控制在0.7-0.8以下超过就会扩容
线性探测 哈希表的线性探测原理是一种解决哈希冲突的方法它的基本思想是当发生哈希冲突时就从当前位置开始顺序查找下一个空闲的位置然后将数据插入到该位置。
例如如果我们要将数据 88 插入到哈希表中经过哈希函数计算得到的数组下标是 16 但是在数组下标为 16 的位置已经有其他元素了那么就继续查找 17 18 直到找到一个空闲的位置然后将 88 插入到该位置。 在实现扩容时我们进行代码复用我们不再新建立vector而是新建立一个哈希表对新哈希表中的vector进行扩容然后调用哈希表的Insert函数将原vector中的键值对的关键码插入到新哈希表当中这样就不需要自己在写代码进行代码复用即可。最后将新哈希表中的vector和原哈希表的vector进行swap即可这样就完成了原有数据到新表中的挪动然后再插入要插入的kv即可。
bool Insert(const pairK, V kv)
{if (Find(kv.first))return false;//大于标定的负载因子进行扩容降低哈希冲突的概率if (_n * 10 / _tables.size() 7)//可能会出现除0错误{//旧表数据重新计算映射到新表/*vectorNode newtables;newtables.resize(2 * _tables.size()); */HashTableK, V, BKDRHashK newHT;newHT._tables.resize(2 * _tables.size());for (auto e : _tables){if (e._state EXIST){newHT.Insert(e._kv);//取原表中的数据插入到新表的vector里面键值对之间发生赋值重载。因为newHT是新开的初始化好的哈希表//递归通常是自己调用自己这里不是递归仅仅是代码复用而已。}}_tables.swap(newHT._tables);}size_t hashi Hash()(kv.first) % _tables.size();//这里不能%capacity某些位置不是可用的vector[]会对下标检查while (_tables[hashi]._state EXIST){//线性探测hashi;//二次探测//hashi hashi i * i;//降低冲突概率但还是有可能会冲突占其他位置hashi % _tables.size();}/*_tables[hashi] Node(kv);_tables[hashi]._state EXIST;*///在构造新表对象时默认构造已经初始化好哈希表里面的结点空间了你再开空间拷贝数据浪费。_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;
}3.Find()
查找的思想非常简单我们首先利用要查找的key值求出映射的哈希地址如果当前位置的状态为存在或者删除则继续找若在循环中找到了则返回对应位置的地址若没找到则返回nullptr遇见空则结束查找。
在线性探测中如果查找到尾部了则让hashi%vector的size即可让hashi回到开头的位置。但有一种极端特殊情况就是边插入边删除这样整个哈希表中的结点状态有可能都是delete或exist则在线性探测中不会遇到emptywhile会陷入死循环所以在while里面多加一层判断如果start等于hashi说明在哈希表中已经线性探测一圈了那此时就返回因为找了一圈都没找到key那就说明key不在哈希表里面。
Node* Find(const K key)
{size_t hashi Hash()(key) % _tables.size();size_t start hashi;while (_tables[hashi]._state ! EMPTY){if (_tables[hashi]._kv.first key _tables[hashi]._state EXIST){return _tables[hashi];}hashi;hashi % _tables.size();//防止越界if (start hashi)break;}return nullptr;
}4. Erase()
大部分数据结构容器的删除其实都是伪删除或者叫做惰性删除因为我们无法做到释放一大块空间的某一部分空间所以在数据结构这里的删除基本都是用标记的伪删除 ,哈希表的删除也一样我们在每个结点里面增加一个状态标记用状态来标记当前结点是否被删除。如果删除结点不存在则返回false。
bool Erase(const K key)
{Node* ret Find(key);if (ret nullptr)return false;ret-_state DELETE;--_n;return true;
}5.仿函数处理key值不能取模无法映射 — BKDRHash
上面代码中对于整型数据可以完成key值取模映射那如果我们的数据是string类型怎么解决string如何对vector的size取模呢此时就需要仿函数来完成自定义类型转换为整型的操作了只有转换为整型我们才能取模进而才能完成哈希映射的工作。 对于其他类型比如intcharshortdouble等我们直接强转为size_t这样就可以完成哈希映射。
字符串转换为整型的场景还是比较常见的网上有很多关于字符串哈希的算法我们取最优的算法思路就是将每一个字符对应的ascll码分别拆下来每次的hash值都为上一次的hash值×131后再加上字符的ascll码值遍历完字符串后最后的hash为字符串转成整型的结果这样每个字符串转换后的整型是极大概率不重复的是一个非常不错的哈希算法被人们称为BKDRHash。
template class K
struct BKDRHash
{size_t operator()(const K key){return (size_t)key;//只要这个地方能转成整型那就可以映射指针浮点数负数都可以但string不行}
};
template
struct BKDRHashstring
{size_t operator()(const string key){//return key[0];//字符串第一个字符是整型那就可以整型提升只要是个整型能进行%模运算完成映射即可。size_t hash 0;for (auto ch : key){hash hash * 131 ch;}return hash;}
};三、开散列的实现 — 链地址法哈希桶
开散列的哈希表是最常用的方式库里面的unordered_map和unordered_set用的也是哈希桶的方式实现的我们模拟实现的哈希桶也仿照库实现哈希结点node里面存储键值对和下一个结点指针。
1. 定义框架结构
在哈希表的模板参数中也多加了一个缺省仿函数类的参数也就是Hash因为我们需要Hash的仿函数对象或匿名构造将key转成整型。
template class K, class V
struct hashNode
{hashNode(const pairK,V kv):_kv(kv),_next(nullptr){}pairK, V _kv;hashNodeK, V* _next;
};
template class K, class V, class Hash BKDRHashK
class hashTable
{
public:typedef hashNodeK, V Node;…………省略
private:vectorNode* _table;size_t _n;
};
对于哈希桶我们必须写出析构函数因为编译器默认生成的析构函数会调用vector的析构而vector的析构仅仅只能将自己的空间还给操作系统如果某些节点指针指向了具体的节点则只归还vector的空间是不够的还需要归还那些申请的节点空间。 所以需要遍历每一个哈希桶将每一个桶里面的节点都还给操作系统这里就用到单链表的节点删除的知识了在删除前需要保留下一个位置要不然delete归还空间之后就找不到下一个节点的位置了。
2.insert()
为什么进行头插 对单链表进行尾插因为尾插还需要找尾那就需要遍历桶这样的效率太低并且桶中也不要求次序什么的所以我们直接进行头插即可头插的效率很高因为映射找到哈希地址之后即可进行头插。
哈希桶的负载因子官方默认值为1.0那就是_n和vector.size()相等的时候进行扩容扩容的目的还是重新建立映射关系缓解哈希冲突因为如果某一个哈希桶的结点个数过多在哈希映射之后还需要遍历哈希桶寻找结点会降低哈希查找的效率所以扩容就是多增加哈希桶的个数减少平均哈希桶中结点的个数提高哈希查找的效率。 2.注意我们遍历原表的每个结点指针将每个指针指向结点的key重新计算哈希映射关系头插到新的vector里面在每完成一个桶的重新映射关系后将原vector中的桶位置的指针置为空否则析构的时候结点会被析构两遍。等到原表的所有结点遍历完之后将新的vector和原来的vector一交换即可临时对象_newtable在离开函数栈帧时会被销毁调用vector的默认析构完成空间的归还即可
研究表明每次除留余数法最好模一个素数这会大概率降低哈希冲突的可能性。所以我们下面的扩容大小每次挑选小于2倍的最大素数作为扩容后的vector大小这里复用了一下stl库里面的素数表。
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 (size_t 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];
}
bool Insert(const pairK, V kv)
{if (Find(kv.first))//不允许重复元素return false;//负载因子控制在1超过就扩容if (_n _table.size()){vectorNode* _newtable;_newtable.resize(__stl_next_prime(_table.size()), nullptr);//resize开空间后默认值为Node*()的构造我们也可以自己写for (int i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;size_t hashi Hash()(cur-_kv.first) % _newtable.size();cur-_next _newtable[hashi];_newtable[hashi] cur;cur next;}_table[i] nullptr;}_table.swap(_newtable);}size_t hashi Hash()(kv.first) % _table.size();Node* newnode new Node(kv);newnode-_next _table[hashi];//newnode的next指向当前表哈希映射位置的结点地址_table[hashi] newnode;//让newnode做头_n;return true;
}3.Find()
哈希桶的查找和闭散列的哈希表很相似先通过key找到映射的哈希桶然后去对应的哈希桶里面找查找的结点即可找到返回结点地址未找到返回nullptr即可。
Node* Find(const K key)
{size_t hashi Hash()(key) % _table.size();Node* cur _table[hashi];while (cur){if (cur-_kv.first key)return cur;cur cur-_next;}return nullptr;
}4.Erase()
哈希桶的erase其实就是单链表结点的删除如果是头删那就是下一个指针作头如果是中间删除则记录前一个结点位置让前一个结点的next指向删除结点的next。然后归还结点空间的使用权即为delete结点指针。
bool Erase(const K key)
{Node* ret Find(key);if (!ret)return false;size_t hashi Hash()(key) % _table.size();Node* cur _table[hashi];if (cur-_kv.first key)//头删{_table[hashi] cur-_next;delete cur;cur nullptr;}else//中间删除{while (cur){Node* prev cur;cur cur-_next;if (cur-_kv.first key){prev-_next cur-_next;delete cur;cur nullptr;}}}--_n;return true;
}四、封装实现unordered系列容器
封装实现unordered系列容器所需硬件的哈希表结构以及哈希函数、插入、查找、删除这些接口我们直接复用开散列哈希桶的接口即可重点在于我们实现容器的迭代器操作只要实现了迭代器的操作那我们自己封装的unordered系列容器基本上就能跑起来了。
1.迭代器设计
迭代器需要定义一些模板参数包括键值类型、元素类型、哈希函数类、键值获取类等。其中元素类型对于unordered_set来说就是键值类型对于unordered_map来说就是pairconst key, value类型。哈希函数类用于将元素类型转换为整数类型键值获取类用于从元素类型中提取键值。迭代器需要封装两个指针一个是节点指针用于指向当前遍历的元素另一个是哈希表指针用于在遍历完一个链表后找到下一个不为空的链表。迭代器需要重载一些运算符包括*和-运算符用于访问当前元素的数据域运算符用于移动到下一个元素和!运算符用于比较两个迭代器是否指向同一个元素。迭代器需要提供一些构造函数和析构函数用于创建和销毁迭代器对象。
//前置声明
template class K, class T, class Hash, class KeyOfT
class hashTable;template class K, class T, class Hash, class KeyOfT
struct __HTIterator
{typedef hashNodeT Node;typedef hashTableK, T, Hash, KeyOfT HT;typedef __HTIteratorK, T, Hash, KeyOfT Self;Node* _node;HT* _ht;__HTIterator(Node* node, HT* ht):_node(node),_ht(ht){}Self operator(){if (_node-_next){_node _node-_next;}else{//当前桶走完了要去哈希表里面找下一个桶size_t hashi Hash()(KeyOfT()(_node-_data)) % _ht-_table.size();hashi;while (hashi ! _ht-_table.size() _ht-_table[hashi] nullptr){hashi;}if (hashi _ht-_table.size())_node nullptr;else_node _ht-_table[hashi];}return *this;}T operator-(){return _node-_data;}T* operator*(){return _node-_data;}bool operator!(const Self it)const{return _node ! it._node;}bool operator(const Self it)const{return _node it._node;}
};2.unordered_map的[ ]操作
我们知道unordered_map是一个无序关联容器内部使用哈希表和桶来存储键值对。所以当使用[ ]操作符访问一个键时unordered_map应先计算该键的哈希值然后根据哈希值找到对应的桶。
如果桶中没有任何元素或者没有找到与该键相等的元素unordered_map会在桶中插入一个新的节点键为给定的键值为默认构造的值。如果桶中有一个或多个元素并且找到了与该键相等的元素unordered_map会返回该元素的引用¹。如果桶中有多个元素并且没有找到与该键相等的元素unordered_map会在桶的末尾插入一个新的节点键为给定的键值为默认构造的值。
V operator[](const K key)
{pairiterator, bool ret _ht.Insert(make_pair(key, V()));return ret.first-second;
}pairiterator,bool Insert(const T data)
{KeyOfT kot;iterator it Find(kot(data));if (it ! end())return make_pair(it, false);//如果插入的值已经存在那就不再进行插入返回对应位置迭代器即可。if (_n _table.size()){vectorNode* _newtable;_newtable.resize(__stl_next_prime(_table.size()), nullptr);for (int i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;size_t hashi Hash()(kot(cur-_data)) % _newtable.size();cur-_next _newtable[hashi];_newtable[hashi] cur;cur next;}_table[i] nullptr;}_table.swap(_newtable);}size_t hashi Hash()(kot(data)) % _table.size();Node* newnode new Node(data);newnode-_next _table[hashi];_table[hashi] newnode;_n;return make_pair(iterator(newnode, this), true);
}void test_unordered_map()
{string arr[] { 苹果, 西瓜, 香蕉, 草莓, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 , 蓝莓 ,草莓 };unordered_mapstring, int countMap;for (auto e : arr){countMap[e];}unordered_mapstring, int::iterator it countMap.begin();//1.不用语法糖一点一点遍历也可以while (it ! countMap.end()){cout it-first : it-second endl;it;}//2.我们实现了迭代器直接用语法糖也可以。for (const auto kv : countMap)//将解引用后的迭代器赋值给kv{cout kv.first : kv.second endl;}
}本节完
