松山湖网站建设,广西建设网怎么查询证件,移动网站建设查询,wordpress标题字数目录 前言
一、什么是哈希表
二、直接定值法
三、开放定值法#xff08;闭散列#xff09;
1.开放定制法定义
2.开放定制法实现
2.1类的参数
2.2类的构造
2.3查找实现
2.4插入实现
2.5删除实现
2.6string做key
四、哈希桶#xff08;开散列#xff09;
1.开散…目录 前言
一、什么是哈希表
二、直接定值法
三、开放定值法闭散列
1.开放定制法定义
2.开放定制法实现
2.1类的参数
2.2类的构造
2.3查找实现
2.4插入实现
2.5删除实现
2.6string做key
四、哈希桶开散列
1.开散列概念
2.开散列实现
2.1类的参数
2.2类的构造函数
2.3查找实现
2.4插入实现
2.5 删除实现
2.6string做key
五、哈希桶与set和unordered_set的对比 前言
什么叫做哈希表
相信大家在很多地方都听过哈希表这三个字。在之前我看到java之父余胜军装小白面试的时候对哈希表那是侃侃而谈非常的羡慕他对哈希表的理解在学习哈希表过后我发现他的难度还不一定比得上红黑树那让我们今天来揭开哈希表的神秘面纱。
一、什么是哈希表
哈希表跟set和map结构类似库函数如果是unordered_set那就是Key模型库函数如果是unordered_map那就是KeyValue模型。 表我们很容易理解那么什么是哈希 关键值与存储位置建立一个关联关系通过收到的Key对Key进行处理映射成一个不超过数组索引特殊值存放在数组中。因此哈希表也被称做散列表 这样一来会使得我们查找效率近乎O1。
二、直接定值法
1.直接定制法值和位置关系唯一每个值都存放在唯一位置。
比如我们统计字符串中小写字母的个数那么我们仅仅需要开辟26个空间的数组即可对每一个字母都存放在对应位置如a存放在索引0处b存放索引1......z存放索引25。
但这样也会存在一些问题。
比如数据十分分散的情况下你需要先找出数组中的最大值和最小值再来开辟空间存放数据。如下数据就得开辟99999-21个空间会造成空间的极度浪费。 因此直接定制法在特殊情况下非常好用但是普遍性不够。不推荐日常使用.
三、开放定值法闭散列
1.开放定制法定义
同样是这串数据我们可以通过哈希函数让key跟位置建立映射关系。 如函数为 hashi key % len
比如len10时2%10 2因此2存放在索引为2的空间99%10 9 ,99存放在索引为9的空间以此类推。
这样我们就可以在长度为len个范围内去找到该值的索引并存放数据了。
但是这又会引发一个问题哈希冲突不同的值映射到相同的位置上去 不管你所给到的函数是什么样子的都只可能尽量减少哈希冲突不可完全避免哈希冲突因此当发生哈希冲突的时候我们应该如何处理呢 1.线性探测法hashi i (i0) 当你想存放的位置存在数据时就存放在当前位置的下一个如果下一个位置也有数据就存放在下一个的下一个直到没有数据为止。 2.二次探测法 (hashi (i0)) 当你想存放的位置存在数据时存放在的位置i为1就是hashi1i为2就是hashi4因此类推直到没有数据为止。 后续还有n次探测等等 2.开放定制法实现
2.1类的参数
首先定义一个枚举代表当前位置的状态状态有 空、存在、删除。为什么要有这三个而不是存在和不存在。主要是为了如下情况 当我们依次插入23,13,33,34。线性探测存值如下所示。 当我们删除13时。 如果只有存在和不存在那么我们后续就找不到33和34了因为找到空不存在就会停止。 什么你说不停止继续找如果不停止那我搞个哈希表和线性表有什么区别那时间复杂度还是O1吗 因此我们需要 空、存在、删除三个状态保证我们遇到删除状态后能够继续往后寻找。哈希表_tables存放的内容为HashDate这里使用库里面的vector帮助我们完成哈希表。同时还需要一个长度_n代表存放了多少个值如果_n / _tables.size() 的结果达到我们设定的某个值比如百分之70这个值我们称做负载因子达到这个限制值后如果再插入结点会发生很多的哈希冲突因此我们需要扩容。 正因为负载因子的存在就算发生了哈希冲突我们也能较容易的找到下一个该存放的位置。 enum Status
{EMPTY,EXIST,DELETE,
};templateclass K, class V
struct HashDate
{pairK, V _kv;Status _s;
};
templateclass K,class V
class HashTable
{
private:vectorHashDateK,V _tables;size_t _n;
};
2.2类的构造 构造很简单我们想让哈希表初始化的时候帮我们开辟好变量 vectorHashDateK,V _tables 的空间那么我们调用resize()函数帮助我们开辟空间即可。
HashTable()
{_tables.resize(10);
}
2.3查找实现 首先传入的参数毫无疑问肯定是key通过key值判断该值在不在哈希表中。 然后算出key经过哈希函数转化后的值记为hashi。这个hashi就是我们映射在_tables表里的索引。 我们开始判断是否为空为空就证明没找到该数据。 不为空就判断该位置存放的_kv模型的first是否与key值相等同时判断条件还得加上该位置不能为删除。为什么要判断是否为删除因为我们删除函数先找到后就将他的状态设置为DELETE并没有重置数据我们也不知道该将数据重置为什么 找到了就范围该位置的地址不然就线性探测hashi往后寻找代码hashi % _tables.size();是为了防止越界发生越界就会回到表的索引0处。直到状态为空结束。 代码部分如下
HashDateK,V* Find(const K key)
{size_t hashi key % _tables.size();while (_tables[hashi]._s ! EMPTY){if (_tables[hashi]._s ! DELETE _tables[hashi]._kv.first key)return _tables[hashi];hashi;hashi % _tables.size();}return nullptr;
}
2.4插入实现 插入的参数是pair模型。 先查看在不在在就返回false。代表已存在不能插入了。 依然是先算哈希值存在就找下一个为空或者为DELETE我们都选择插入将状态修改为存在_n。 bool Insert(const pairK,V kv)
{if (Find(kv.first)){return false;}size_t hashi kv.first % _tables.size();while (_tables[hashi]._s EXIST){hashi;hashi % _tables.size();}_tables[hashi]._kv kv;_tables[hashi]._s EXIST;_n;return true;
}
我们还差一些东西比如扩容当 _n / _tables.size()大于等于负载因子时需要扩容代码部分添加到Find函数后面因为找到该值就会返回不需要扩容。 判断条件就跟负载因子有关_n / _tables.size()就是我们的负载因子由于这两个都是整数因此我们表达式的前后都乘了10。当前的负载因子为0.7。 这里我们选择用了更方便的写法建立了一个新的哈希表newht将size()开辟为之前的两倍遍历复用插入当我们遍历插入完毕后新哈希表newht的_tables就是我们现在的_tables想要的内容由于_tables是vector因此我们调用一下swap就好了。 if (_n*10 / _tables.size() 7)
{int newcapacity _tables.size() * 2;HashTableK, V newHT;newHT._tables.resize(newcapacity);for (size_t i 0; i _tables.size(); i){if(_tables[i]._s EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);
}
我们运行测试一下没问题。打印代码不用管只是方便我们查看后面会给出 2.5删除实现
使用代码复用通过Find函数找到该key存放的位置。
找到了就将状态置为DELETE--_n返回true没找到就返回false。
bool Erase(const K key)
{HashDateK, V* ret Find(key);if (ret){ret._s DELETE;--_n;return true;}return false;
}
测试一下 2.6string做key
之前我们分析的都是整形来做key自然而然就可以用除法去找到索引那么string类型呢在生活中string类型做key可是非常常见的。 这里我们选择添加一个模板参数并且是缺省的这个参数的目的就是利用仿函数将支持强转size_t类型的key转成size_t类型对于其他类型我们也可以通过一些方法转成size_t类型。 我们针对string类型使用了模板特化当发现key为string时就会走该函数因为特化是现成的代码而上面那个还需要去推演出来类型。 至于为什么我们代码的sum要*31这是防止哈希冲突。
如果不处理如“abc”和“acb”还有“bbb”就会发生哈希冲突具体可以看大佬的文章字符串Hash函数
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};template
struct HashFuncstring
{size_t operator()(const string s){size_t sum 0;for (auto e : s){sum * 31;sum e;}return sum;}
};
templateclass K,class V ,class Hash HashFuncK
class HashTable
{//相关代码
};
修改一下在我们所有要对key变成整数的地方都套上一层这里只套了一个明白意思就好。 测试一下代码由于我们特化了string并且HashTable第三个模板参数为缺省参数因此这里可以不传参如果你的key是自定义类型那么你需要自己写哈希函数并传参。 四、哈希桶开散列
1.开散列概念 开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地 址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链 接起来各链表的头结点存储在哈希表中 开放定制法如下图所示的图片 同样的数据放在哈希桶如下就像拉链一样一个挂着一个。 那么哈希桶的优势在哪里呢我们可以发现当我们去寻找4和14这种数据似乎区别不大。 但是一旦我们寻找54差距就大了开放定制法会一直找到9的后面才结束而哈希桶只需要将当前挂载的链表找完就可以了。 再比如我们寻找9开放定制法会一直找到9才结束而哈希桶一下就找到了。 在Java JDK1.8版本中如果某个链表长度超过了8会选择挂载红黑树增加效率C还没有这样做至于为什么我们在实现中会测试大家一起往下看吧。
2.开散列实现
2.1类的参数
我们的_tables里面存放的是结点为什么不用库里面的list呢
首先我们只需要单向链表即可要用也是用库里面的forward_list(单向链表)其次使用库里面的链表会让我们后续封装迭代器更加麻烦最后使用自己手写结点也很简单因此选择自己写一个。
HashNode存放_kv和_next并且写出了构造函数方便我们new结点。
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 HashTable
{typedef HashNodeK, V Node;
public:HashTable(){_tables.resize(10);}
private:vectorNode* _tables;size_t _n;
};
2.2类的构造函数 1.默认构造给_tables开辟十个空间。 2.拷贝构造我们也要自己写需要深拷贝选择头插老生常谈的东西了。 3.operator 赋值拷贝传参选择不传这样就会发生拷贝构造同时不传const因为我们析构后会删除。再调用swap函数即可将别人的交换一下出了作用域自动调用析构函数。 4.析构函数遍历加一个个节点删除即可。 HashTable()
{_tables.resize(10);
}
HashTable(const HashTableK,V ht)
{_tables.resize(ht._tables.size(), nullptr);for (size_t i 0; i ht._tables.size(); i){Node* cur ht._tables[i];while (cur){Node* newnode new Node(cur-_kv);if (_tables[i]nullptr){_tables[i] newnode;}else{newnode-_next _tables[i];_tables[i] newnode;}cur cur-_next;}}
}HashTableK, V operator(HashTableK, V ht)
{_tables.swap(ht._tables);swap(_n, ht._n);return *this;
}~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;}
}
2.3查找实现
一样先计算哈希值hashi通过hashi去找到存放在_tables里面的结点结点不为空就证明该节点存放了链表便开始遍历链表找到就返回结点没找到就一直找直到为空。
Node* Find(const K key)
{size_t hashi key % _tables.size();Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){return cur;}cur cur-_next;}return nullptr;
}
2.4插入实现
开散列的插入大致思路跟开放定制法一样先查找在判断负载因子最后插入。
我们先来看插入部分先计算映射的哈希值hashi再new一个新节点将新节点的_next指向hashi的地址再将新节点复制给hashi这样就完成了头插最后_n。具体插入如下图所示newnode为11 对于扩容部分由于是拉链法负载因子可以适当大一点因此我们将负载因子调整到了1也就是_n_tables.size()。并且我们并没有像开放定制法那样复用Insert因为复用insert又会开辟新结点并且析构函数需要自己写因为HashNode是自定义类型并且有指针。这样析构起来速度会很慢因此我们选择将原来_tables上的结点直接挪动过来这样也节省了开辟结点和析构结点的时间。 代码部分新创建一个newtables先开辟原哈希表2倍的大小遍历原哈希表将挂载的索引节点重新映射到新表上依然选择的头插法。当当前链表遍历完毕后要将_tables[i]置空因为这是浅拷贝不置空析构会有问题。最后swap一下即可。 bool Insert(const pairK, V kv)
{if (Find(kv.first))return false;if (_n _tables.size()){vectorNode* newtables;newtables.resize(_tables.size() * 2, nullptr);for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;//映射到新表size_t hashi cur-_kv.first % newtables.size();cur-_next newtables[hashi];newtables[hashi] cur;cur next;}//置空防止析构出现问题_tables[i] nullptr;}_tables.swap(newtables);}size_t hashi kv.first % _tables.size();Node* newnode new Node(kv);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;
}
运行打印看看效果没问题。 2.5 删除实现 这里我们没有用Find来删除因为就算我们找到了结点由于是单链表我们也无法找到节点的前一个因此没有用Find函数。 取出哈希值hashi遍历当前的哈希值的链表同时记录好前一个。找到Key或者找到空结束如果找到了而且前一个为空证明删除的是第一个就直接将cur-_next给到_tables[hashi]即可完成头删。 如果前一个不为空则不是头删则prev-_next cur-_next; 最后detele 再return true即可。 bool Erase(const K key)
{size_t hashi key % _tables.size();Node* cur _tables[hashi];Node* prev nullptr;while (cur){if (cur-_kv.first key){if (prev nullptr){_tables[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;return true;}prev cur;cur cur-_next;}return false;
} 测试一下 2.6string做key
依然是我们之前写的HashFund在本文的三、2.6
需要取整数的地方套上一层就可以了。不多赘述。 五、哈希桶与set和unordered_set的对比
这里我们选取了一百万个随机值进行插入测试具体打印函数后续会给出根据打印内容我们发现哈希表处理数据的速度是要比红黑树快一点的。
至于之前我们说为什么C不适用哈希表挂载红黑树的方式我们可以通过maxBucketLen来知道一个地方时很难挂载到很多数据的除非你是人为恶心哈希表才会挂载很多数据。
最后为什么我们的哈希表比库里面的还要快因为库里面还涉及到了一些东西我们写的是简单版。 最后附上代码
HashTable.h
#pragma once
#includevectortemplateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};template
struct HashFuncstring
{size_t operator()(const string s){size_t sum 0;for (auto e : s){sum * 31;sum e;}return sum;}
};
namespace kky_open_address
{enum Status{EMPTY,EXIST,DELETE,};templateclass K, class Vstruct HashDate{pairK, V _kv;Status _s;};templateclass K,class V ,class Hash HashFuncKclass HashTable{public:HashTable(){_tables.resize(10);}Hash hs;HashDateK,V* Find(const K key){size_t hashi hs(key) % _tables.size();while (_tables[hashi]._s ! EMPTY){if (_tables[hashi]._s ! DELETE _tables[hashi]._kv.first key)return _tables[hashi];hashi;hashi % _tables.size();}return nullptr;}bool Erase(const K key){HashDateK, V* ret Find(key);if (ret){ret-_s DELETE;--_n;return true;}return false;}bool Insert(const pairK,V kv){if (Find(kv.first)){return false;}if (_n*10 / _tables.size() 7){int newcapacity _tables.size() * 2;HashTableK, V newHT;newHT._tables.resize(newcapacity);for (size_t i 0; i _tables.size(); i){if(_tables[i]._s EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}size_t hashi hs(kv.first) % _tables.size();while (_tables[hashi]._s EXIST){hashi;hashi % _tables.size();}_tables[hashi]._kv kv;_tables[hashi]._s EXIST;_n;return true;}void Print(){for (size_t i 0; i _tables.size(); i){if (_tables[i]._s EXIST){//printf([%d]-%d:%s\n, i,_tables[i]._kv.first, EXIST);cout [ i ]- _tables[i]._kv.first: _tables[i]._kv.second endl;}else if(_tables[i]._s EMPTY){//printf([%d]-%d:%s\n, i, _tables[i]._kv.first, EMPTY);cout [ i ]- endl;}else{//printf([%d]-%d:%s\n, i, _tables[i]._kv.first, DELETE);cout [ i ]- DELETE endl;}}cout endl;}private:vectorHashDateK,V _tables;size_t _n;};void test01(){HashTableint, int ht;int arr[] { 3,13,23,4,5,14,7,13 };for (auto e : arr){ht.Insert(make_pair(e, e));}ht.Print();ht.Erase(13);ht.Print();ht.Insert(make_pair(33,33));ht.Print();}void test02(){string arr[] { 香蕉,苹果,橘子,香蕉,苹果 ,香蕉,苹果 ,香蕉 };HashTablestring, int ht;for (auto e : arr){HashDatestring, int* ret ht.Find(e);if(ret)ret-_kv.second;elseht.Insert(make_pair(e, 1));}ht.Print();}
}namespace kky_hash_bucket
{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 Hash HashFuncKclass HashTable{typedef HashNodeK, V Node;public:HashTable(){_tables.resize(10);}HashTable(const HashTableK,V ht){_tables.resize(ht._tables.size(), nullptr);for (size_t i 0; i ht._tables.size(); i){Node* cur ht._tables[i];while (cur){Node* newnode new Node(cur-_kv);if (_tables[i]nullptr){_tables[i] newnode;}else{newnode-_next _tables[i];_tables[i] newnode;}cur cur-_next;}}}HashTableK, V operator(HashTableK, V ht){_tables.swap(ht._tables);swap(_n, ht._n);return *this;}~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){Hash hs;if (Find(kv.first))return false;if (_n _tables.size()){vectorNode* newtables;newtables.resize(_tables.size() * 2, nullptr);for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;//映射到新表size_t hashi hs(cur-_kv.first) % newtables.size();cur-_next newtables[hashi];newtables[hashi] cur;cur next;}//置空防止析构出现问题_tables[i] nullptr;}_tables.swap(newtables);}size_t hashi hs(kv.first) % _tables.size();Node* newnode new Node(kv);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;}Node* Find(const K key){Hash hs;size_t hashi hs(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){return cur;}cur cur-_next;}return nullptr;}bool Erase(const K key){Hash hs;size_t hashi hs(key) % _tables.size();Node* cur _tables[hashi];Node* prev nullptr;while (cur){if (cur-_kv.first key){if (prev nullptr){_tables[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;return true;}prev cur;cur cur-_next;}return false;}void Print(){for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];cout [ i ] 挂载-;while (cur){cout cur-_kv.first : cur-_kv.second -;cur cur-_next;}cout endl;}cout endl;}void Some(){size_t bucketSize 0;size_t maxBucketLen 0;double averageBucketLen 0;for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];if (cur){bucketSize;}size_t bucketLen 0;while (cur){bucketLen;cur cur-_next;}if (bucketLen maxBucketLen){maxBucketLen bucketLen;}}averageBucketLen (double)bucketSize / (double)_n;printf(all bucketSize:%d\n,_tables.size());printf(bucketSize:%d\n, bucketSize);printf(maxBucketLen:%d\n, maxBucketLen);printf(averageBucketLen:%lf\n\n, averageBucketLen);}private:vectorNode* _tables;size_t _n;};void test01(){HashTableint, int ht;int arr[] { 3,13,23,4,5,14,33,34,43,44 };for (auto e : arr){ht.Insert(make_pair(e, e));}ht.Print();cout ht.Find(43) endl;ht.Erase(43);ht.Print();cout ht.Find(43) endl;}void test02(){string arr[] { 香蕉,苹果,橘子,香蕉,苹果 ,香蕉,苹果 ,香蕉 };HashTablestring, int ht;for (auto e : arr){HashNodestring, int* ret ht.Find(e);if (ret)ret-_kv.second;elseht.Insert(make_pair(e, 1));}}void test03(){const size_t N 1000000;unordered_setint us;setint s;HashTableint, int ht;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){//v.push_back(rand()); // N比较大时重复值比较多v.push_back(rand() i); // 重复值相对少//v.push_back(i); // 没有重复有序}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 begin10 clock();for (auto e : v){ht.Insert(make_pair(e, e));}size_t end10 clock();cout HashTbale insert: end10 - begin10 endl 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;size_t begin11 clock();for (auto e : v){ht.Find(e);}size_t end11 clock();cout HashTable find: end11 - begin11 endl endl;cout 插入数据个数 us.size() endl endl;ht.Some();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;size_t begin12 clock();for (auto e : v){ht.Erase(e);}size_t end12 clock();cout HashTable Erase: end12 - begin12 endl endl;}
} test.cpp
#includeiostream
#includestring
#includeset
#includeunordered_set
using namespace std;
#includeHashTable.h
#includetest.hint main()
{kky_hash_bucket::test03();
} 感谢大家观看
