-
【C++从0到王者】第三十六站：哈希
一、unordered系列容器
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到logN，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到。在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。
unordered_xxx系列与map和set容器的用法上几乎没有任何区别
他们的区别就是
- unordered_xxx系列都是哈希表作为底层的，而map和set是用红黑树作为底层的
- unordered_xxx系列不排序，只去重
- unordered_xxx系列是单项迭代器
二、unordered_set
如下就是unordered_set的文档
unordered_set是一种容器，它以无特定顺序的方式存储唯一的元素，并允许根据元素的值快速检索各个元素。
在unordered_set中，元素的值同时也是它的键，唯一标识该元素。键是不可变的，因此，unordered_set中的元素一旦放入容器后就不能被修改，不过可以插入和删除。
在内部，unordered_set中的元素不按任何特定顺序排序，而是根据它们的哈希值组织成桶，以便通过它们的值（平均具有恒定的平均时间复杂度）直接快速访问各个元素。
对于通过键访问单个元素，unordered_set容器比set容器更快，尽管对于通过子集范围迭代它们通常效率较低。
容器中的迭代器是单向迭代器。
由于接口其实大差不差，所以我们可以直接使用去感受一下
void test1() { unordered_set<int> us; us.insert(1); us.insert(5); us.insert(2); us.insert(6); us.insert(4); us.insert(3); unordered_set<int>::iterator usit = us.begin(); while (usit != us.end()) { cout << *usit << endl; usit++; } cout << endl; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
三、unordered_map
如下是unordered_map的文档
无序映射是关联容器，存储由键值和映射值组合形成的元素，并允许根据它们的键快速检索各个元素。
在unordered_map中，键值通常用于唯一标识元素，而映射值是与该键关联的对象的内容。键和映射值的类型可以不同。
在内部，unordered_map中的元素不根据它们的键或映射值按任何特定顺序排序，而是根据它们的哈希值组织成桶，以便通过它们的键值直接快速访问各个元素（平均具有恒定的平均时间复杂度）。
对于通过键访问单个元素，unordered_map容器比map容器更快，尽管对于通过子集范围迭代它们通常效率较低。
无序映射实现了直接访问运算符（operator[]），允许使用键值作为参数直接访问映射值。
容器中的迭代器是单向迭代器。
void test2() { unordered_map<string, string> dict; dict["insert"] = "插入"; dict["sort"] = "排序"; dict["delete"] = "删除"; dict["string"] = "字符串"; dict["insert"] = "xxxxx"; dict.insert(make_pair("iterator", "迭代器")); unordered_map<string, string>::iterator umit = dict.begin(); while (umit != dict.end()) { cout << umit->first << ":" << umit->second << endl; umit++; } cout << endl; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
四、unordered_set与set的比较
如下所示，我们采用如下代码进行比较
void test3() { const size_t N = 100000; unordered_set<int> us; set<int> s; vector<int> v; v.reserve(N); srand(time(0)); for (size_t i = 0; i < N; ++i) { v.push_back(rand()); //v.push_back(rand()+rand()); //减少重复数据 //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 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 << endl; cout <<"插入数据个数："<< s.size() << endl; cout <<"插入数据个数：" << us.size() << endl << 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 << endl; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
可以看到，在无序的数据的时候，unordered_set更占优势一些。
但是我们会发现有很多的重复数据，于是我们可以对随机值+随机值以此减少重复数据
可以看到，还是unordered_set占据优势
然后我们可以尝试一下有序的数据
此时set占据优势
可见，如果数据是无序的，unordered_set更优，如果是有序的，使用set更好
五、各种查找的比较
- 暴力查找
首先就是我们最常见的暴力查找，他的时间复杂度是O(N)
- 二分
不过我们可以对其进行一定程度的优化，即先排序，这样的画他的时间复杂度就变为了logN，但是增删还是不方便
- 平衡树
再后来就是使用红黑树，他的效率都是很优秀的，增删查改都是logN
- 哈希
除此之外还有一种方式就是哈希，即存储的值和存储位置建立出一个对应关系，这样的话时间复杂度直接变为了O(1)，哈希我们也称作散列
哈希的方式有点类似于计数排序
这种方式在现实生活中就应用于图书馆中的分区
但是上面这种哈希仅仅只是比较适合于数据比较集中的，像字母只有26个，就很集中比较适合上面这种方式
这种方式也被称为直接定址法
但是如果数据很分散的话，就不适合了。因为会试想一下，在一个数组中，大部分的元素位于0~20之间，但是突然一个数据是9999，那么我们难道就要开这么大的空间，去直接定址吗？显然是不可能的！
于是我们就有了下面一种哈希，除留余数法，即对所有数据对一个数据取模后，在根据这个值进行放入。
不过这种方法会导致一种问题，就是哈希冲突：不同的值，可能会映射到一个位置，值和位置是多对一的关系
为了解决这种方法，我们可以使用很多种方法去解决。
一种方法是线性探测、或者二次探测，即使用某种规则去占用下一个位置，不过这种方式不是很好，因为会影响其他位置
不过还有一种方式是拉链法，即哈希桶的方式去解决。这种方式比较好，不会影响其他位置
六、哈希函数
1.哈希函数概念与哈希冲突
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(logN)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素当向该结构中：
- 插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放 - 搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置
取元素比较，若关键码相等，则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)
例如在如下的哈希函数中
例如：数据集合{1，7，6，4，5，9}；
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
不过有时候我们也会遇到一种情况，当我们继续插入44的时候，我们发现原本的4的位置已经被占领了
**不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞 **
**把具有不同关键码而具有相同哈希地址的数据元素称为“同义词” **
2.常见哈希函数
- 直接定址法
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
比如统计字符串中的字符出现的个数，因为字符的范围比较集中
- 除留余数法
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址。
不过上述的方法可能会产生哈希冲突
七、解决哈希冲突
**解决哈希冲突两种常见的方法是：闭散列和开散列 **
1.闭散列—开放定址法
所谓的开放定址法：其实就是当前位置被占用了，通过某种规则去找下一个位置（占用别人的位置）
常见的方案有：线性探测，二次探测等…
我们下面主要探讨线性探测
下面是线性探测的插入策略：
如下所示，我们使用这个哈希函数，当我们依次插入1，111，4，5，6，7，44，9的时候，44由于下标为四的状态已经被占用了，所以要向后寻找空位置，进行放入。111也由于1的下标被占用了，也冲突了，所以向后寻找。这就是线性探测，如果我们继续插入一个19，那么他应该放入9下标的位置，但是9已经被占用了，所以会放入0的位置
如下就是已经有9了，继续放入19
下面是线性探测的查找：
在如下所示的表中，如果我们想继续查找44的话，那么就会根据哈希函数计算出下标，从4的位置开始找起来，如果不是直接匹配，那么就继续向后寻找，直到找到。如下就可以在8的位置找到44
如果想要找到54的话，那么也是根据哈希函数，从4开始找起来，一值找到0位置，发现0位置是一个空位置，那么结束查找，因为没有找到。
在这里也侧面反映出一个问题，哈希表不可以太满了，太满了会导致效率极其低下
线性探测的删除：
试想一下，我们删除一个数据是可以直接删除的吗？如果遇到如下的情况，先删除了6，然后查找44。似乎出现了卡bug的行为，因为删除6以后，6的位置已经为空了，而查找是一旦发现为空就停止查找了
所以删除会影响查找
所以为了解决上面的办法，我们删除不应该是将一个位置变为空，而是使用标记。
我们可以对每个数据使用三种状态进行标记：EXIST、EMPTY、DELETE，分别表示存在，空，删除三种状态
这样的话，当我们删除一个数据的时候，直接修改他的状态即可。
而对于查找的时候，遇到DELETE的时候不要停止，遇到空才停止
闭散列的代码实现
首先是闭散列的结构，如下所示。 在哈希表中，虽然vector已经有size函数了，但是这里计算出来的并非有效数据，所以我们还需要一个n来记录哈希表中的有效数据
enum STATE { EXIST, EMPTY, DELETE }; template<class K,class V> struct HashDate { pair<K, V> _kv; STATE _state = EMPTY; }; template<class K, class V > class HashTable { public: private: vector<HashDate<K, V>> _table; size_t _n = 0; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 闭散列的插入实现
考虑到，闭散列是根据线性探测查找的，所以我们可以简单的写出以下代码，因为我是是使用vector作为底层的，所以我们使用size作为模的对象，切记不可以使用capacity，因为capacity虽然开出来了容量，但是这个容量是不可以使用的。size才是可访问的范围。
上面的代码其实还存在一定问题:
那就是哈希表的扩容问题，何时进行扩容，是需要我们去考虑的。而且我们不能让哈希表满了，因为哈希表一旦满了，就会死循环了
对于这个负载因子
负载因子越大，冲突概率越大，空间利用率越高
负载因子越小，冲突概率越小，空间利用率越低
哈希表不能满了在扩容，控制负载因子到一定值就必须扩容
所以我们可能会写出以下代码，但是下面代码还是错的
为什么错了呢？其实是因为，resize以后，导致哈希函数改变了，从而导致映射关系乱了，需要重新映射
我们重新映射的办法就是，在创建一个哈希表，然后依次往新的哈希表中插入数据，最后交换两个哈希表的vector，这样的写法有点类似于赋值运算符重载的现代写法
bool Insert(const pair<K, V>& kv) { if (10 * _n / _table.size() >= 7) { size_t newSize = _table.size() * 2; //遍历旧表，重新映射到新表 HashTable<K, V> newHT; newHT._table.resize(newSize); for (int i = 0; i < _table.size(); i++) { if (_table[i]._state == EXIST) { newHT.Insert(_table[i]._kv); } } _table.swap(newHT._table); } size_t hashi = kv.first % _table.size(); while (_table[hashi]._state == EXIST) { hashi++; hashi %= _table.size(); } _table[hashi]._kv = kv; _table[hashi]._state = EXIST; ++_n; return true; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
我们可以使用如下的测试用力进行测试：
void test4() { Sim::HashTable<int, int> ht; int a[] = { 1,111,4,15,25,7,44,9 }; for (auto e : a) { ht.Insert(make_pair(e, e)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
如下图是扩容之前的
如下是扩容之后的
- 闭散列查找
闭散列的查找还是比较容易的，这里我们特别注意的是，我们的返回值是一个HashDate
*类型的，因为我们要避免哈希表中的第一个元素被修改了，一旦第一个元素被修改了，那么就麻烦了，映射关系乱了，而我们返回的时候，由于我们的底层的第一个参数并不是const类型的，这里也不是权限的缩小，而是两种完全不同的类型，所以我们需要强制类型转换来处理 HashDate<const K, V>* Find(const K& key) { size_t hashi = key % _table.size(); while (_table[hashi]._state != EMPTY) { if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key) { return (HashDate<const K, V>*) & _table[hashi]; } hashi++; hashi %= _table.size(); } return nullptr; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 闭散列删除
如下所示，哈希表的删除是少数删除比插入还简单的容器，因为只需要改一个状态即可。
bool Erase(const K& key) { HashDate<const K, V>* ret = Find(key); if (ret) { ret->_state = DELETE; --_n; return true; } return false; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 特殊类型的量化
上面的代码其实还是不够完善的，因为当我们的哈希表中的元素是字符串类型的时候，就麻烦了，字符串类型无法进行取模运算，所以我们需要有一个办法对字符串进行量化，让他转化为整型，有了整型以后，才能去建立映射关系。甚至于这个key都一定是字符串，如果不是字符串，那么又该如何进行量化，这才是插入中最麻烦的地方。
为了解决这个问题，我们可以使用仿函数。利用仿函数去量化，那么仿函数该如何去写呢？首先就是默认的，可以直接转为size_t类型的
template<class K> struct DefaultHashFunc { size_t operator()(const K& key) { return (size_t)key; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
如果遇到特殊类型的，我们可以自己写一个仿函数去量化，比如string类型
struct StringHashFunc { size_t operator()(const string& key) { return (size_t)key[0]; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
这样我们只需要传参的时候使用这个仿函数即可
但是对于string其实使用是很高频的，所以我们不妨使用模板的特化
template<> struct DefaultHashFunc<string> { size_t operator()(const string& key) { return (size_t)key[0]; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
接下来，我们可以使用如下测试用例进行测试
void test5() { //Sim::HashTable* ret = dict.Find("sort"); Sim::HashDate<const string, string>* ret = dict.Find("sort"); ret->_kv.second = "xxxx"; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
虽然解决了特殊类型的问题，但是对于string类型而言，上面的处理其实并不是很好，因为太单一了，随便两个首字母相同的就冲突了，所以我们可以考虑所有字母相加
template<> struct DefaultHashFunc<string> { size_t operator()(const string& key) { size_t hash = 0; for (auto ch : key) { hash += ch; } return hash; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
但是上面还是无法规避一些特殊情况，比如两个字符串里面的字母都相同，仅仅只是交换了某些字母的顺序
其实对于字符串转整型有很多种方法
如旁边所示，是字符串转整型的一些方法：字符串转整型
我们可以使用第一种方法
template<> struct DefaultHashFunc<string> { size_t operator()(const string& key) { size_t hash = 0; for (auto ch : key) { hash = hash * 131 + ch; } return hash; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
这样的话，确实不是那么容易冲突了
上面就是线性探测的方法了。
线性探测所存在的问题就是，容易发生拥堵踩踏事件
线性探测的基本思路就是
hashi = key % n; hashi = hashi + i; i>=0;- 1
- 2
- 3
为了防止过于频繁的拥堵踩踏事件，我们可以使用二次探测。
二次探测与线性探测的唯一不同就是，二次探测每次是探测平方的，这样就会导致每个数据都会间隔开。使得数据不是那么集中拥堵，可以一定程度缓解拥堵踩踏
hashi = key % n; hashi = hashi + pow(i,2); i>=0;- 1
- 2
- 3
但是无论如何，无论是线性探测也好，二次探测也好，他们都会导致拥堵踩踏，产生冲突，冲突的值会相互影响，这是开放定址法自身的缺陷
如下是闭散列/开放地址法的完整代码
namespace open_address { enum STATE { EXIST, EMPTY, DELETE }; template<class K,class V> struct HashDate { pair<K, V> _kv; STATE _state = EMPTY; }; template<class K> struct DefaultHashFunc { size_t operator()(const K& key) { return (size_t)key; } }; template<> struct DefaultHashFunc<string> { size_t operator()(const string& key) { size_t hash = 0; for (auto ch : key) { hash = hash * 131 + ch; } return hash; } }; //template<> //struct DefaultHashFunc//{ // size_t operator()(const string& key) // { // size_t hash = 0; // for (auto ch : key) // { // hash += ch; // } // return hash; // } //}; //template<> //struct DefaultHashFunc //{ // size_t operator()(const string& key) // { // return (size_t)key[0]; // } //}; //struct StringHashFunc //{ // size_t operator()(const string& key) // { // return (size_t)key[0]; // } //}; template<class K, class V, class HashFunc = DefaultHashFunc<K>> class HashTable { public: HashTable() { _table.resize(10); } bool Insert(const pair<K, V>& kv) { //去重 if(Find(kv.first)) { return false; } if (10 * _n / _table.size() >= 7) { size_t newSize = _table.size() * 2; //遍历旧表，重新映射到新表 HashTable<K, V, HashFunc> newHT; newHT._table.resize(newSize); for (int i = 0; i < _table.size(); i++) { if (_table[i]._state == EXIST) { newHT.Insert(_table[i]._kv); } } _table.swap(newHT._table); } HashFunc hf; size_t hashi = hf(kv.first) % _table.size(); while (_table[hashi]._state == EXIST) { hashi++; hashi %= _table.size(); } _table[hashi]._kv = kv; _table[hashi]._state = EXIST; ++_n; return true; } HashDate<const K, V>* Find(const K& key) { HashFunc hf; size_t hashi = hf(key) % _table.size(); while (_table[hashi]._state != EMPTY) { if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key) { return (HashDate<const K, V>*) & _table[hashi]; } hashi++; hashi %= _table.size(); } return nullptr; } bool Erase(const K& key) { HashDate<const K, V>* ret = Find(key); if (ret) { ret->_state = DELETE; --_n; return true; } return false; } private: vector<HashDate<K, V>> _table; size_t _n = 0; }; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
2.开散列—拉链法/哈希桶
- 开散列概念：
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中
所以开散列其实就是一个指针数组，关键码对应的值直接挂在对应的下标下面
开散列的基本思路
如下所示，是开散列的基本思路，我们使用一个指针数组来将每个结点给链接上去
namespace hash_bucket { template<class K,class V> struct HashNode { pair<K, V> _kv; HashNode<K, V>* _next = nullptr; HashNode(const pair<K, V>& kv) :_kv(kv) {} }; template<class K, class V> class HashTable { typedef HashNode<K,V> Node; public: HashTable() :_n(0) { _table.resize(10, nullptr); } private: vector<Node*> _table; size_t _n; }; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 开散列的插入
如下所示，是我们一开始的基本思路，我们先不考虑特殊类型无法取模的问题，我们直接使用头插法，便可以很轻松的完成插入
bool Insert(const pair<K, V>& kv) { size_t hashi = kv.first % _table.size(); Node* newnode = new Node(kv); newnode->_next = _table[hashi]; _table[hashi] = newnode; ++_n; return true; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
但是这段代码还存在的问题就是扩容问题。因为我们不可能让这个桶上一直挂数据。
也就是说，不扩容，不断插入，某些桶越来越长，效率得不到保障，但是这里的负载因子可以适当放大一些，一般负载因子在1，平均下俩每个桶一个数据
如果按照我们上面闭散列的逻辑的话，那么就是这样扩容的
一个一个的将值给放进去，但是这样的话，存在一个问题，那就是我们还需要new一些新结点，而原来的结点还需要再释放一下
这样做其实是不太好的，效率比较低。而前面闭散列敢这样做的原因，就是因为不需要new新节点，所以可以这样玩。而这里不能这样做就是需要开新节点了
所以我们最好的策略就是直接把原来的结点给挪用即可
如下就是最终代码，这里我们已经添加了仿函数进行处理特殊类型了。
bool Insert(const pair<K, V>& kv) { //去重 if (Find(kv.first)) { return false; } HashFunc hf; if (_n == _table.size()) { size_t newSize = _table.size() * 2; vector<Node*> newTable(newSize, nullptr); for (int i = 0; i < _table.size(); i++) { Node* cur = _table[i]; while (cur) { Node* next = cur->_next; size_t hashi = hf(cur->_kv.first) % newTable.size(); cur->_next = newTable[hashi]; newTable[hashi] = cur; cur = next; } _table[i] = nullptr; } _table.swap(newTable); } size_t hashi = hf(kv.first) % _table.size(); Node* newnode = new Node(kv); newnode->_next = _table[hashi]; _table[hashi] = newnode; ++_n; return true; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
我们使用如下测试用例
void test6() { hash_bucket::HashTable<int, int> ht; int a[] = { 1,111,4,15,25,7,44,9 }; for (auto e : a) { ht.Insert(make_pair(e, e)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
监视窗口如下所示
我们也可以写一个print用来展示
void Print() { for (int i = 0; i < _table.size(); i++) { Node* cur = _table[i]; printf("[%d]->", i); while (cur) { cout << cur->_kv.first << "->"; cur = cur->_next; } cout << "NULL" << endl; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
然后我们的测用例改为如下，可以更加直观的感受扩容
void test6() { hash_bucket::HashTable<int, int> ht; int a[] = { 1,111,4,15,25,7,44,9 }; for (auto e : a) { ht.Insert(make_pair(e, e)); } ht.Print(); cout << endl; ht.Insert(make_pair(24, 24)); ht.Insert(make_pair(34, 34)); ht.Insert(make_pair(54, 54)); ht.Print(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
运行结果如下：
- 开散列的查找
Node* Find(const K& key) { HashFunc hf; size_t hashi = hf(key) % _table.size(); Node* cur = _table[hashi]; while (cur) { if (cur->_kv.first == key) { return cur; } cur = cur->_next; } return nullptr; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 开散列的删除
bool Erase(const K& key) { HashFunc hf; size_t hashi = hf(key) % _table.size(); Node* cur = _table[hashi]; Node* prev = nullptr; while (cur) { if (cur->_kv.first == key) { if (prev) { prev->_next = cur->_next; } else { _table[hashi] = cur->_next; } delete cur; cur = nullptr; _n--; return true; } else { prev = cur; cur = cur->_next; } } return false; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
接下来我们来测试一下
void test6() { hash_bucket::HashTable<int, int> ht; int a[] = { 1,111,4,15,25,7,44,9 }; for (auto e : a) { ht.Insert(make_pair(e, e)); } ht.Print(); cout << endl; ht.Insert(make_pair(24, 24)); ht.Insert(make_pair(34, 34)); ht.Insert(make_pair(54, 54)); ht.Print(); cout << endl; ht.Erase(44); ht.Erase(4); ht.Erase(24); ht.Print(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
运行结果为
- 开散列的析构
开散列与闭散列的不同之处在于，他需要写一个析构函数，因为闭散列的数组上都是自定义类型，所以可以不用写析构函数，而开散列的数组上都是一些指针，这些指针都是内置类型，他们指向一段空间， 就需要写上析构函数了
~HashTable() { for (int i = 0; i < _table.size(); i++) { Node* cur = _table[i]; while (cur) { Node* next = cur->_next; delete cur; cur = next; } _table[i] = nullptr; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
我们可以用如下代码来进行测试
void test7() { hash_bucket::HashTable<string, string> dict; dict.Insert(make_pair("sort", "排序")); dict.Insert(make_pair("insert", "插入")); dict.Insert(make_pair("delete", "删除")); dict.Insert(make_pair("process", "进程")); dict.Insert(make_pair("right", "xxxx")); hash_bucket::HashNode<string, string>* ret = dict.Find("right"); ret->_kv.second = "右边"; dict.Print(); cout << endl; dict.Erase("sort"); dict.Print(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
运行结果为
下面是哈希桶的完整代码：
namespace hash_bucket { template<class K,class V> struct HashNode { pair<K, V> _kv; HashNode<K, V>* _next = nullptr; HashNode(const pair<K, V>& kv) :_kv(kv) {} }; template<class K> struct DefaultHashFunc { size_t operator()(const K& key) { return (size_t)key; } }; template<> struct DefaultHashFunc<string> { size_t operator()(const string& str) { size_t hashi = 0; for (auto ch : str) { hashi = hashi * 131 + ch; } return hashi; } }; template<class K, class V, class HashFunc = DefaultHashFunc<K>> class HashTable { typedef HashNode<K,V> Node; public: HashTable() :_n(0) { _table.resize(10, nullptr); } bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) { return false; } HashFunc hf; if (_n == _table.size()) { size_t newSize = _table.size() * 2; vector<Node*> newTable(newSize, nullptr); for (int i = 0; i < _table.size(); i++) { Node* cur = _table[i]; while (cur) { Node* next = cur->_next; size_t hashi = hf(cur->_kv.first) % newTable.size(); cur->_next = newTable[hashi]; newTable[hashi] = cur; cur = next; } _table[i] = nullptr; } _table.swap(newTable); } size_t hashi = hf(kv.first) % _table.size(); Node* newnode = new Node(kv); newnode->_next = _table[hashi]; _table[hashi] = newnode; ++_n; return true; } void Print() { for (int i = 0; i < _table.size(); i++) { Node* cur = _table[i]; printf("[%d]->", i); while (cur) { cout << cur->_kv.first << ":" << cur->_kv.second << "->"; cur = cur->_next; } cout << "NULL" << endl; } } Node* Find(const K& key) { HashFunc hf; size_t hashi = hf(key) % _table.size(); Node* cur = _table[hashi]; while (cur) { if (cur->_kv.first == key) { return cur; } cur = cur->_next; } return nullptr; } bool Erase(const K& key) { HashFunc hf; size_t hashi = hf(key) % _table.size(); Node* cur = _table[hashi]; Node* prev = nullptr; while (cur) { if (cur->_kv.first == key) { if (prev) { prev->_next = cur->_next; } else { _table[hashi] = cur->_next; } delete cur; cur = nullptr; _n--; return true; } else { prev = cur; cur = cur->_next; } } return false; } ~HashTable() { for (int i = 0; i < _table.size(); i++) { Node* cur = _table[i]; while (cur) { Node* next = cur->_next; delete cur; cur = next; } _table[i] = nullptr; } } private: vector<Node*> _table; size_t _n; }; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
-
相关阅读:
流量分析三—远程登陆
【WLAN】如何从显示角度调试WFD问题
常用工具链和虚拟环境-Cygwin
隆云通吸顶多参数传感器
ReqAndRespAndZuul的一些自己的见解，和超时异常的解方案
MyBatis--获取参数和各种查询
扫雷游戏优化详解——c语言实现
C++ 定义一个地图类和地点类，开发一个小游戏。
数据预处理之数据缩放
top命令应用(查看进程实时动态信息)
- 原文地址：https://blog.csdn.net/jhdhdhehej/article/details/133709892