企业整站网站模板下载佛山市企业网站seo点击软件

当前位置： 首页 > news >正文

企业整站网站模板下载,佛山市企业网站seo点击软件,吧台 东莞网站建设,网站建站东莞一、哈希的概念及其性质 1.哈希概念 在顺序结构以及平衡树中#xff0c;元素关键码与其存储位置之间没有对应的关系#xff0c;因此在查找一个元素时#xff0c;必须要经过关键码的多次比较。比如顺序表需要从第一个元素依次向后进行查找#xff0c;顺序查找时间复杂度为…一、哈希的概念及其性质 1.哈希概念 在顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。比如顺序表需要从第一个元素依次向后进行查找顺序查找时间复杂度为O(N)平衡树中需要从第一层开始逐层往下进行比较查找的次数为树的高度即O(logN)搜索的效率取决于搜索过程中元素的比较次数 尽管红黑树或者AVL树的查找效率已经很高了但是还是不够极致理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。 如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素当向该结构中 插入元素时 : 根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放 搜索元素时 : 对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功 该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表(Hash Table)(或者称散列表) 我们需要注意的是不管是顺序查找平衡树查找还是哈希查找其key值都是唯一的也就是说搜索树和哈希表中都不允许出现相同的key 值 2.哈希函数 哈希函数设计原则 1.哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间 2.哈希函数计算出来的地址能均匀分布在整个空间中 3.哈希函数应该比较简单 常见哈希函数 1.直接定址法–(常用) 直接定址法取关键字的某个线性函数为散列地址HashKe A*Key B 它的优点是简单且不会引起哈希冲突–哈希冲突是指多个不同的key值映射到同一个存储位置由于直接定址法的key值经过哈希函数转换后得到的值一定是唯一的所以不存在哈希冲突 直接定址法适用于数据范围比较集中的情况这样key值映射到哈希表之后哈希表的空间利用率高浪费非空间较少不适用与数据分散的情况因为这样会导致空间的利用率很低从而造成空间浪费 下面是一道哈希定址法的典型例子 387.字符串中第一个唯一字符[LeetCode] class Solution { public:int firstUniqChar(string s) {int arr[26]{0};for(size_t i0;is.size();i){// 题目中说明只有小写字母我们减去字符得到的数作为下标arr[s[i]-a];}// 遍历查找第一个为1的下标for(size_t i0;is.size();i){if(arr[s[i]-a]1){return i;}}return -1;} };2.除留余数法–(常用) 除留余数法思想 : 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址 我们使用key值对哈希表的大小进行取模得到的树作为哈希映射的地址将key保存到该地址中除留余数法的优点是可以处理数据范围分散的数据缺点是会引发哈希冲突比如对于数据集合 数据集合{176459} 哈希函数设置为hash(key) key % capacity; capacity为存储元素底层空间总的大小。 此时如果我们继续插入数据11那么通过哈希函数计算出应该存储在下标为1的位置但是下标为 1的位置引进存放了数据1此时就会发生哈希冲突 3.平方取中法–(了解) 假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址再比如关键字为4321对它平方就是18671041抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合不知道关键字的分布而位数又不是很大的情况 4.折叠法–(了解) 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)然后将这几部分叠加求和并按散列表表长取后几位作为散列地址。 折叠法适合事先不需要知道关键字的分布适合关键字位数比较多的情况 5.随机数法–(了解) 选择一个随机函数取关键字的随机函数值为它的哈希地址即H(key) random(key),其中random为随机数函数。 通常应用于关键字长度不等时采用此法 6.数学分析法–(了解) 设有n个d位数每一位可能有r种不同的符号这r种不同的符号在各位上出现的频率不一定相同可能在某些位上分布比较均匀每种符号出现的机会均等在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小选择其中各种符号分布均匀的若干位作为散列地址。 假设要存储某家公司员工登记表如果用手机号作为关键字那么极有可能前7位都是 相同的那么我们可以选择后面的四位作为散列地址如果这样的抽取工作还容易出现 冲突还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成123446)等方法 数字分析法通常适合处理关键字位数比较大的情况如果事先知道关键字的分布且关键字的若干位分布较均匀的情况 注意哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突 3.哈希冲突 对于两个数据元素的关键字字 k i k_i ki​和 K_j(i ! j)有 k i k_i ki​ ! k j k_j kj​但有Hash( k i k_i ki​) Hash( k j k_j kj​)即不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞 解决哈希冲突两种常见的方法是闭散列和开散列 1.闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个”空位置中去 2.开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中,即发生哈希冲突之后把key直接链接在该位置的下面 二、闭散列 闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个”空位置中去。那如何寻找下一个空位置呢这里有两种方法–线性探测法和二次探测法 1.线性探测 线性探测法是指从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止比如下面的场景中现在需要插入元素44先通过哈希函数计算哈希地址hashAddr为4因此44理论上应该插在该位置但是该位置已经放了值为4的元素即发生哈希冲突则我们可以向后寻找一个空的位置即下标为8 的位置进插入 下面我们来模拟实现哈希函数的除留余数法并使用闭散列的线性探测法来解决哈希冲突的问题 2.哈希表的基本框架 哈希表节点结构的定义如下 #pragma once #include vectornamespace closeHash {// 定义一个位置的状态enum state{EMPTY, // 空EXIST, // 存在数据DELETE, //该位置数据被删除};// 哈希表每个节点下标位置存储的数据的结果templateclass K,class Vstruct HashData{pairK, V _kv;state _state EMPTY; // 默认为空};templateclass K,class V, class Hash HashFuncKclass HashTable{typedef HashDataK, V Data;private:vectorData _tables;size_t _n 0; // 表中存储的有效数据的个数}; }为了方便在哈希表中我们使用vector来存储数据并增加了一个变量n来记录表中有效数据的个数同时哈希表的每一个下标位置存储的数据都是一个KV模型的键值对此外我们还需要使用一个state变量来记录每一个位置的状态。 原因是因为我们可能是删除哈希表中的数据但是我们在插入的时候当key映射的下标位置被占用时key会向后寻找下一个空的位置进行插入但是如果key走到数据尾部还没有找到就会从数组的起始位置开始寻找。 假如我们删除了其中的一个节点此时我们需要查找一个节点由于被占用的原因该节点在被删除节点的位置的后面我们一步一步向后找的时候在走到被删除节点的位置发现该位置没有数据之后就会返回false但事实上这个数据是存在的即使我们说删除之后我们将该位置的数据修改为一个数字但是选择哪一个呢0-1/1都不合适因为插入的数据是可能的任何数据但是当我们使用一个state来标识一个位置的状态的时候我们查找走到已经被删除位置的时候发现该位置的数据被删除了但是查找会继续向后进行查找。 所以在哈希表中每个位置的数据增加了一个state变量类似标记该位置的状态。 3.哈希表的操作 1.哈希表的插入 插入一个分为两步 1.通过哈希函数获取待插入元素在哈希表中的位置 2.如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素 我们插入的时候需要考虑扩容的问题这个我们在哈希表扩容的时候再进行详细的讲解。 插入代码如下 templateclass K struct HashFunc {size_t operator()(const K key){return (size_t)key;} }; // 插入 bool Insert(const pairK, V kv) {// 已经存在该值返回falseif (Find(kv.first))return false;// 大于标定负载因子就需要扩容if (_n * 10 / _tables.size() 7){// 使用一个新的哈希表进行插入然后进行交换两个哈希表的_tablesHashTableK, V newHT;newHT._tables.resize(_tables.size() * 2);for (auto e : _tables){if (e._state EXIST){newHT.Insert(e._kv);}}_tables.swap(newHT._tables);}Hash hf;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; }2.哈希表的查找 通过哈希函数得到余数即数组下标取出下标位置的key与目标key进行比较相等就返回该位置的地址如果查找到状态为空的下标位置就返回nullptr但是这样有几个需要注意的地方 1.当遇到状态为空的下标位置才返回nullptr而不是遇到状态为删除的位置就返回nullptr因为我们要查找的数据可能在删除数据的后面 2.将查找函数的返回值定义为Data而不是bool这样可以方便我们进行删除和修改(修改key对应的value)查找到之后直接通过指针的解引用修改value与state 3.哈希表经过不断的插入和删除最终可能会出现一种极端的情况–哈希表中元素的状态全为EXIST和DELETE此时如果我们找空就会造成死循环所以我们需要对这种情况进行单独的处理 // 查找 // 查找返回那个位置的地址 Data Find(const K key) {Hash hf;// 仿函数对象size_t hashi hf(key) % _tables.size();// 记录hashi的起始位置避免哈希表中元素全为EXISR和DELETE造成死循环size_t starti hashi;while (_tables[hashi]._state ! EMPTY){// key相等且state为EXIST才表示找到if (_tables[hashi]._state EXIST _tables[hashi]._kv.first key){return _tables[hashi];}hashi;hashi % _tables.size();// 如果找了一圈都没有找到则跳出循环if(starti hashi)break;}return nullptr; }3.哈希表的删除 哈希表的删除我们复用查找函数查到到就通过查找函数的返回值将下标位置数据的状态置为DELETE即可没有找到就返回false 代码如下 // 删除 bool Erase(const K key) {Data* ret Find(key);if (ret){// 删除之后将该位置的状态改为删除ret-_state DELETE;–_n;return true;}else{return false;} }4.哈希表的扩容 哈希表的扩容和普通顺序表容器的扩容不同它不是容器满了才进行扩容而是会有一个负载因子当负载因子 超过一定大小时才会进行扩容书上对负载因子的表述如下 哈希的扩容并不是简单的扩大空间而是需要将已经插入到哈希表中的元素取出全部重新进行插入因为扩容后会导致哈希表的长度改变那么key通过哈希函数映射到的位置也会发生改变所以需要重新进行插入 我们这里使用一个HashTable对象进行插入然后交换二者的数组 // 插入 bool Insert(const pairK, V kv) {// 已经存在该值返回falseif (Find(kv.first))return false;// 大于标定负载因子就需要扩容if (_n * 10 / _tables.size() 7){// 使用一个新的哈希表进行插入然后进行交换两个哈希表的_tablesHashTableK, V newHT;newHT._tables.resize(_tables.size() * 2);for (auto e : _tables){if (e._state EXIST){newHT.Insert(e._kv);}}_tables.swap(newHT._tables);}Hash hf;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; }5.哈希表的仿函数 我们插入的key值不是整数的时候但是我们要让key与哈希表的长度取模得到映射位置此时我们就需要进行两次转换先将其他类型的数据转换成整数再将该整数作为key转换为下标比如我们统计水果数量的时候就需要先将字符串转换为整数作为key值然后再进行映射。 由于key值可以是不同类型的数据我们不能只考虑字符串字符串我们可以选择使用[]的方式获得第一个字符但是对于其他类型就不再适用了所以我们需要使用仿函数来帮我们解决这个问题。 我们可以为哈希表增加一个模板参数给模板参数是一个仿函数仿函数分为设计者提供的默认的仿函数和用户提供的仿函数系统默认提供的仿函数可以将一些常见的key的类型全部转换为整形比如字符串指针整数。而用户提供的仿函数则可以根据用户自己的需求将对应的key值转换为整形。 代码如下 templateclass K struct HashFunc {size_t operator()(const K key){return (size_t)key;} };// 特化 –针对string类型写一个仿函数–转成整形 template struct HashFuncstring {size_t operator()(const string key){size_t hash 0;for (auto ch : key){hash * 131;hash ch;}return hash;} };有了仿函数之后我们只需要在key与TableSize取模的地方使用仿函数对象将key转换为整形即可。这样对于常见的key类型哈希表可以通过内置的默认仿函数来完成下标的映射对于用户自定义的key类型需要我们自己提供对应的仿函数类来完成下标的映射 6.字符串的哈希算法 哈希表中key值的类型在我们日常生活中运用十分的广泛我们可以取第一个字符来进行映射但是这样很容易发生哈希冲突–只要字符串的首字母相同就会发生冲突我们也可以考虑将字符串的所有字符的ASCII值加起来作为key值进行映射但是对于这样的字符串–“abc “acb” “bca” aad等等这样的字符串的ASCII值相等也会发生哈希冲突 所有就有人专门研究看字符串哈希算法即如何将字符串转换为整形可以使得将哈希冲突率变得很低下面的一篇博客介绍了许多优秀非字符串哈希算法我们可以借鉴学习学习各种字符串Hash-clq-博客园(cnblogs.com) 其中BKDR哈希字符串算法是最出名也是平均分最高的上面我们的代码中字符串算法就是使用的该算法 7.完整代码 这里我们需要注意的是哈希表的拷贝构造析构赋值重载使用我们编译器默认生成的即可–对于自定义类型编译器会调用自定义类型的拷贝构造析构和赋值重载由于table是vector类型的成员变量而vector中实现了深拷贝与析构所以不需要我们自己来实现 HashTable.h #pragma once#include vectortemplateclass K struct HashFunc {size_t operator()(const K key){return (size_t)key;} };// 特化 –针对string类型写一个仿函数–转成整形 template struct HashFuncstring {size_t operator()(const string key){size_t hash 0;for (auto ch : key){hash * 131;hash 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 Hash HashFuncKclass HashTable{typedef HashDataK, V Data;public:// 默认构造HashTable():_n(0){_tables.resize(10);}// 插入bool Insert(const pairK, V kv){// 已经存在该值返回falseif (Find(kv.first))return false;// 大于标定负载因子就需要扩容if (_n * 10 / _tables.size() 7){// 使用一个新的哈希表进行插入然后进行交换两个哈希表的_tablesHashTableK, V newHT;newHT._tables.resize(_tables.size() * 2);for (auto e : _tables){if (e._state EXIST){newHT.Insert(e._kv);}}_tables.swap(newHT._tables);}Hash hf;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();// 记录hashi的起始位置避免哈希表中元素全为EXISR和DELETE造成死循环size_t starti hashi;while (_tables[hashi]._state ! EMPTY){// key相等且state为EXIST才表示找到if (_tables[hashi]._state EXIST _tables[hashi]._kv.first key){return _tables[hashi];}hashi;hashi % _tables.size();// 如果找了一圈都没有找到则跳出循环if (starti hashi)break;}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; // 表中存储的有效数据的个数}; }Test.cpp #define _CRT_SECURE_NO_WARNINGS 1#include iostream using namespace std;#include HashTable.hvoid TestHT1() {closeHash::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;closeHash::HashTablestring, int countHT;for (auto e : arr){closeHash::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; } int main() {//TestHT1();TestHT2();return 0; }8.二次探测 线性探测优点实现非常简单 线性探测缺点一旦发生哈希冲突所有的冲突连在一起容易产生数据堆积”即不同关键码占据了可利用的空位置使得寻找某关键码的位置需要许多次比较导致搜索效率降低。如何缓解呢 线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位置的方式就是挨着往后逐个去找因此二次探测为了避免该问题找下一个空位置的方法为 H i H_i Hi​ ( H 0 H_0 H0​ i 2 i^2 i2 )% m,或者 H i H_i Hi​ ( H 0 H_0 H0​ - i 2 i^2 i2 )% m。其中i 1,2,3… H 0 H_0 H0​是通过散列函数Hash(x)对元素的关键码key进行计算得到的位置m是表的大小。即根据余数找到下标位置如果位置被占用不是去挨着的下一个位置找而是去余数i的平方的位置找插入位置其中i是寻找的次数 研究表明当表的长度为质数且表装载因子a不超过0.5时新的表项一定能够插入而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置就不会存在表满的问题。在搜索时可以不考虑表装满的情况但在插入时必须确保表的装载因子a不超过0.5如果超出必须考虑增容 比散列最大的缺陷就是空间利用率比较低这也是哈希的缺陷.最后二次探测法在一定程度上减轻了哈希冲突的概率但也没有从根源上解决问题。 三、开散列 1.开散列概念 开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。 即在发生哈希冲突的时候把key作为一个节点直接链接在对应下面位置的哈希桶 从上图可以看出开散列中每个桶中放的都是发生哈希冲突的元素。 2.开散列的节点结构 由于开散列的不同冲突的元素之间不会相互影响所以开散列不再需要status变量来记录每一个下面位置的状态此外开散列的每个下标位置链接的都是一个哈希桶所以vector中的每一个元素都是一个节点的指针指向单链表中的第一个元素所以_tables是一个指针数组这样就不会去占用别人的位置所以不管在插入还是查找方面开散列都要比闭散列要更加的高效所以CSTL中的unordered_set和unordered_map以及Java中的HashSet和HashMap的底层都是使用哈希表的开散列方式实现的。最后为了使得不同类型的key都能够计算出其映射的下标位置所以我们需要传递一个仿函数 // 仿函数 templateclass K struct HashFunc {size_t operator()(const K key){return (size_t)key;} };// 特化 –针对string类型写一个仿函数–转成整形 template struct HashFuncstring {size_t operator()(const string key){size_t hash 0;for (auto ch : key){hash * 131;hash ch;}return hash;} }; // 哈希表达节点结构–单链表 templateclass K, class V struct HashNode {pairK, V _kv;HashNodeK, V* _next;HashNode(const pairK, V kv):_kv(kv), _next(nullptr){} };// 哈希表 templateclass K, class V, class HashHashFuncK class HashTable {typedef HashNodeK, V Node; private:vectorNode* _tables; //指针数组size_t _n;// 表中有效数据的个数 };3.开散列的操作 1.开散列的插入 开散列插入和闭散列一样首先需要根据key值与哈希表的大小得到映射的下标的位置此外由于哈希表中每个下标位置都是一个哈希桶即一个单链表那么我们插入的时候只需要将冲突的元素链接到哈希桶中即可。这里链接有两种方式 1.将发生哈希冲突的元素链接到单链表的末尾即尾插 2.将发生哈希冲突的元素链接到单链表的头部即头插 但是由于单链表尾插需要从头结点开始遍历进行找尾这样插入的效率就比较低所以我们选择头插的方式 插入部分代码如下 bool Insert(const pairK, V kv) {if (Find(kv.first))return false;//调用仿函数的匿名对象将key转换为整数size_t hashi Hash()(kv.first) % _tables.size();// 头插Node* newnode new Node(kv);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true; }2.开散列的查找 开散列的查找只需要根据取模得到下标由于下标位置存储的是单链表首元素的地址我们进行遍历即可 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; }3.开散列的删除 和闭散列不同的是开散列的删除不能直接通过查找函数的返回值进行删除因为单链表在删除节点时还需要改变父节点的指向让其指向下一个节点和单链表的删除相同所以我们需要遍历单链表找到删除的节点进行删除 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 (prev nullptr)if(cur _tables[hashi]){//_tables[hashi] nullptr;_tables[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;–_n;return true;}else{cur cur-_next;prev cur;}}return false; }4.开散列的扩容 桶的个数是一定的随着元素的不断插入每个桶中元素的个数不断增多极端情况下可能会导致一个桶中链表节点非常多会影响的哈希表的性能因此在一定条件下需要对哈希表进行增容那该条件怎么确认呢开散列最好的情况是每个哈希桶中刚好挂一个节点再继续插入元素时每一次都会发生哈希冲突因此在元素个数刚好等于桶的个数时可以给哈希表增容。 开散列最好的情况是每一个哈希桶中都只有一个元素再继续插入元素的时候每一次就会发生哈希冲突因此我们可以在元素的个数等于桶的个数的时候进行扩容即负载因子为1 这样我们可以采用两种扩容的方式: 1.采用闭散列扩容的思路-通过复用insert函数来进行扩容但是开散列每个插入的时候都需要新开辟节点在插入完毕之后我们还需要释放表中原来的节点这样就会使得效率很低 2.我们可以创建一个vector取出旧表中的每一个节点链接到新的表中然后再交换旧表和新表这样就没有开辟节点和释放节点的消耗了从而大大提高了扩容的效率。注我们不能直接将原表中的整个哈希桶链接到新表中因为新表的大小改变后原表中的元素可能会映射到表的其他位置 所以开散列的析构函数需要我们自己实现因为默认生成的析构函数不会释放掉哈希桶 我们每次扩容不一定都在扩容2倍有人提出了表的大小为质数 的时候哈希冲突的概率会低一些当使用质数作为除数时能够更加均匀地散列key值就会较少哈希冲突的发生。库中可以这样实现的但是也不是必须的所以我们这里使用一个数组保存一组质数大概是2倍的关系但是在42亿之后就不会再进行扩容了其实我们也不用担心因为我们整数的数据一共才42亿是可以存储得下的。 但是在某一些极端场景下或者面对某些碰撞攻击时(对方知道我们好像表的长度以及取模的逻辑这个时候就专门设计一些冲突的数据使得效率就不变得很低)那么机会导致单链表的长度过长从而降低哈希的查找与删除的效率。 为了应对这种情况Java 8中使用的HashMap在使用红黑树来优化哈希冲突的情况因为红黑树可以保证查找插入和删除的时间复杂度为O(logN)效率就会比链表快很多此外C11也引入了一个新的数据结构–开发定址哈希表(open addressing table)用于存储哈希冲突时的元素开放定址哈希表是一种不使用链表来解决哈希冲突的实现方式。这种实现方式中如果一个槽(slot)已经被占用了就会尝试找到下一个可用的槽直达找到一个空槽因为开发地址哈希表可以更好的利用缓冲从而提高查找性能。C11之后的版本中unordered_map的哈希桶使用了两种不同的数据结构包括单链表和开放定址哈希表–当桶中元素较少时使用链表当桶的元素较多的时候会自动转换为开放定址哈希表 STL源码中的实现 // 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 };inline unsigned long __stl_next_prime(unsigned long n) {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);return pos last ? *(last - 1) : *pos; } 扩容代码如下 // 负载因子控制在1超过就扩容 if (_tables.size() _n) { 创建一个哈希表对象然后进行插入之后交换双方的vector//HashTableK, V newHT;//newHT._tables.resize(_tables.size() * 2);//for (size_t i 0; i _tables.size(); i)//{// Node* cur _tables[i];// while (cur)// {// newHT.Insert(cur-_kv);// cur cur-_next;// }//}//_tables.swap(newHT._tables);vectorNode* newTables;//newTables.resize(_tables.size() * 2, nullptr);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[i];newTables[i] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTables); }5.开散列完整代码实现 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;// 负载因子控制在1超过就扩容if (_tables.size() _n){ 创建一个哈希表对象然后进行插入之后交换双方的vector//HashTableK, V newHT;//newHT._tables.resize(_tables.size() * 2);//for (size_t i 0; i _tables.size(); i)//{// Node* cur _tables[i];// while (cur)// {// newHT.Insert(cur-_kv);// cur cur-_next;// }//}//_tables.swap(newHT._tables);vectorNode* newTables;//newTables.resize(_tables.size() * 2, nullptr);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[i];newTables[i] 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 (prev nullptr)if(cur _tables[hashi]){//_tables[hashi] nullptr;_tables[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;–_n;return true;}else{cur cur-_next;prev cur;}}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;}; }6.开散列与闭散列比较 应用链地址法处理溢出需要增设链接指针似乎增加了存储开销。事实上由于开地址法必须保持大量的空闲空间以确保搜索效率如二次探查法要求装载因子a 0.7而表项所占空间又比指针大的多所以使用链地址法反而比开地址法节省存储空间。