哈希表以及哈希表的底层结构 --- 万字解说【c++11】
目录
哈希概念
哈希冲突
哈希函数
解决哈希冲突的常用方法
闭散列
版本1:闭散列(开放定址法)
开散列
版本2:开散列(开链法/哈希桶)
版本3:设计仿函数支持string
哈希概念
- 插入元素
根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放
- 搜索元素
对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功
- 示例:数据集合{1,7,6,4,5,9};
哈希冲突
哈希函数
哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中
1. 直接定址法--(常用)
- 示例:字符串中的第一个唯一字符
class Solution { public:int firstUniqChar(string s) {int count[27] = {0};for(auto& ch : s){count[ch - 'a']++;} for(size_t i = 0; i < s.size(); ++i){if(count[s[i] - 'a'] == 1)return i;}return -1;} };
2. 除留余数法--(常用)
解决哈希冲突的常用方法
闭散列
1. 线性探测
- 插入
通过哈希函数获取待插入元素在哈希表中的位置如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突, 使用线性探测找到下一个空位置,插入新元素
- 删除
采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素 会影响其他元素的搜索。比如删除元素7,如果直接删除掉,77查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
// 哈希表每个空间给个标记 // EMPTY此位置空, EXIST此位置已经有元素, DELETE元素已经删除 enum State{EMPTY, EXIST, DELETE};
版本1:闭散列(开放定址法)
定义:
#pragma onceenum State {EMPTY,EXIST,DELETE };template<class K> class hash_data { public:K _key; //数据State _state = EMPTY; // 状态 };template<class K> class hash_table { public://闭散列/开放定址法bool insert(const K& key){//映射起始位置size_t hashi = key % _tables.capacity(); //线性探测size_t i = 1;while(_tables[hashi]._state == EXIST){hashi += i;hashi %= _tables.size();i++;}_tables[hashi]._key = key;_tables[hashi]._state = EXIST;_count++;}private:vector<hash_data<K>> _tables;size_t _count = 0; //记录存储的个数 };
- 问题1:这里能使用capacity来确定位置嘛???是选择①还是②?
答案是②,因为熟悉vector的都知道,vector是用 size()来进行边界判断的,如果取模的值比size()要大,会报断言错误,所以这里不能 %capacity()。
- 问题2:这里 %size() 就没有问题了吗?也不尽然,因为存在其他问题,
- 如果capacity()满了怎么办?
- 如果size()为0怎么办?
- 如果size()变了那么映射关系是不是也需要改变???
所以这里需要补充一个相关知识:负载因子
负载因子也被称为载荷因子,表示的是存储量的百分比
散列表的载荷因子定义为: α =填入表中的元素个数 / 散列表的长度
α是散列表装满程度的标志因子。由于表长是定值,α与“填入表中的元素个数”成正比,所以,α越大,表明填入表中的元素越多,产生冲突的可能性就越大;反之,α越小,标明填入表中的元素越少,产生冲突的可能性就越小。实际上,散列表的平均查找长度是载荷因子α的函数,只是不同处理冲突的方法有不同的函数。
对于开放定址法,荷载因子是特别重要因素,应严格限制在0.7-0.8以下。超过0.8,查表时的CPU缓存不命中〈cachemissing)按照指数曲线上升。因此,一些采用开放定址法的hash库,如Java的系统库限制了荷载因子为0.75,超过此值将resize散列表。
所以当我们调用insert就需要扩容:这样可以吗?
//负载因子超过0.7就扩容if (_count * 10 / _tables.size() >= 7){_tables.resize(_tables.capacity() * 2);}
上述代码依旧有问题,因为存在capacity为0的情况,也存在size()没有改变的情况。所以需要优化:
if (_tables.size() == 0 || _count * 10 / _tables.size() >= 7){size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;_tables.resize(newsize);}
这样是否还有问题呢?依然存在,因为size()发生了改变,而未扩容之前插入的数据,%的是未改变的size(), 而接下来插入数据%是已经改变的size(),这样,同一张哈希表,映射的关系居然不同,肯定是错误的,所以,扩容是需要取到之前映射的值重新进行映射。如图:
我们发现,表2是不对的,因为直接扩容之后,再次插入的值%都是20,而之前的值%都是10,直接的问题就是以后进行查找的话,是怎么都找不到的,因为查找要找到映射位置,也要%,那么谁知道%是多少呢?
所以扩容是需要像表3一样,取上面的值重新进行映射,而且我们发现,映射之后的存储位置是有些不同的。所以,哈希表扩容的代价是有些高的。
代码如下:
//负载因子超过0.7就扩容if (_tables.size() == 0 || _count * 10 / _tables.size() >= 7){size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;//方法1.vector<hash_data<K>> newtables(newsize);for (auto& data : _tables){size_t hashi = key % _tables.size();if (data._state == EMPTY){//线性探测size_t i = 1;size_t index = hashi;while (_tables[index]._state == EXIST){index = index + i;index = index % _tables.size();i++;}_tables[index]._key = key;_tables[index]._state = EXIST;_count++;}}_tables.swap(newtables);}
这里的思路是复用,因为需要重新插入,所以重新走了一边线性探测,当然,也可以把线性探测封装成一个函数进行调用,不过这里介绍另一个逻辑,当然也是和复用相关:
hash_table<K> newht;newht._tables.resize(newsize);for (auto& data : _tables){if (data._state == EMPTY){newht.insert(data._key);}}_tables.swap(newht._tables);
我们可以新建一个哈希对象,然后去调用insert,进行内部复用,然后交换指针即可。
现在我们就可以丰富一下这个类,如下:闭散列
hash_table.h
#pragma once #include <vector> namespace dwr {enum State{EMPTY,EXIST,DELETE};template<class K>struct hash_data{K _key; //数据State _state = EMPTY; // 状态};template<class K>class hash_table{public://闭散列/开放定址法bool insert(const K& key){if ( _tables.size() != 0 && find(key)) //去重{return false;}//负载因子超过0.7就扩容if (_tables.size() == 0 || _count * 10 / _tables.size() >= 7){size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;//方法1.//vector<hash_data<K>> newtables(newsize);//for (auto& data : _tables)//{// size_t hashi = key % _tables.size();// if (data._state == EMPTY)// {// //线性探测// size_t i = 1;// size_t index = hashi;// while (_tables[index]._state == EXIST)// {// index = index + i;// index = index % _tables.size();// i++;// }// _tables[index]._key = key;// _tables[index]._state = EXIST;// _count++;// }//}//_tables.swap(newtables);//方法2.hash_table<K> newht;newht._tables.resize(newsize);for (auto& data : _tables){if (data._state == EMPTY){newht.insert(data._key);}}_tables.swap(newht._tables);}//映射起始位置size_t hashi = key % _tables.size();//线性探测size_t i = 1;size_t index = hashi;while (_tables[index]._state == EXIST){index = index + i ;index = index % _tables.size();i++;}_tables[index]._key = key;_tables[index]._state = EXIST;_count++;return true;}hash_data<K>* find(const K& key){//映射起始位置size_t hashi = key % _tables.size();//线性探测size_t i = 1;size_t index = hashi;while (_tables[index]._state != EMPTY){if (_tables[index]._state == EXIST&& _tables[index]._key== key){return& _tables[index];}index = index + i;index = index % _tables.size();++i;}return nullptr; }bool erase(const K& key){hash_data<K>* ret = find(key);if (ret){//伪删除ret->_state = DELETE;_count--;}else{return false;}}private:vector< hash_data<K> > _tables;size_t _count = 0; //记录存储的个数};}void test_hashtable1() {int arr[] = { 3, 33, 2, 13,5, 12, 1002 };dwr::hash_table<int> ht;for (auto& kv : arr){ ht.insert(kv);}if (ht.find(13)){cout << "13在" << endl;}else{cout << "13不再" << endl;}ht.erase(13);if (ht.find(13)){cout << "13在" << endl;}else{cout << "13不再" << endl;} }
但是其实上述代码有两个隐藏的问题,在find内:这里容易引起除0错误,因为_tables.size()可能为0,所以要加一个判断。
size_t hashi = key % _tables.size();
其二,这里:可能会出现死循环,因为假设哈希表内的存储情况只有EXIST和DELETE,那么就会出现,所以也需要优化
while (_tables[index]._state != EMPTY)
优化如下:
hash_data<K>* find(const K& key){//加判断,防止除0错误if (_tables.size() == 0){return nullptr;}//映射起始位置size_t hashi = key % _tables.size();//线性探测size_t i = 1;size_t index = hashi;while (_tables[index]._state != EMPTY){if (_tables[index]._state == EXIST&& _tables[index]._key== key){return& _tables[index];}index = index + i;index = index % _tables.size();++i;//加个判断,防止死循环 - 如果相等,证明寻找一圈也未找到,因为hashi是起始位置if (index == hashi){break;}}return nullptr; }
- 线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为:$H_i$ = ($H_0$ + $i^2$ )% m, 或者:$H_i$ = ($H_0$ - $i^2$ )% m。其中:i =1,2,3…, $H_0$是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置,m是表的大小。
- 研究表明:当表的长度为质数且表装载因子a不超过0.5时,新的表项一定能够插入,而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入时必须确保表的装载因子a不超过0.5,如果超出必须考虑增容。
- 因此:闭散列最大的缺陷就是空间利用率比较低,这也是哈希的缺陷。所以一般情况下,我们更偏向于使用开散列(哈希桶)来解决哈希冲突。
版本2:开散列(开链法/哈希桶)
开散列概念
定义:
template<class K>struct hash_node{hash_node<K>* _next;K _key;hash_node(const K& key):_next(nullptr),_key(key){}};template<class K>class hash_table{typedef hash_node<K> _node;public://代码实现private:vector<_node*> _tables;size_t _count = 0; // 记录个数};
代码实现:如下图
bool insert(const K& key){//计算映射起始位置size_t hashi = key % _tables.size();_node* newnode = new _node(key);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_count;return true;}
开散列增容
如图,这样扩容会导致后面数据的映射关系与扩容之前插入数据的映射关系不同,所以需要重新开辟空间进行扩容
bool insert(const K& key){//负载因子等于1即进行扩容if (_tables.size() == 0 || _count == _tables.size()){size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector<_node*> newtables(newsize, nullptr); // 指针数组for (auto& cur : _tables){while (cur){_node* next = cur->_next;size_t hashi = key % _tables.size(); //重新计算映射位置cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}//计算映射起始位置size_t hashi = key % _tables.size();_node* newnode = new _node(key);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_count;return true;}
for (auto& cur : _tables)
for (size_t i = 0; i < _tables.size(); ++i){_node* cur = _tables[i];//.....}
namespace dwq {template<class K>struct hash_node{hash_node<K>* _next;K _key;hash_node(const K& key):_next(nullptr),_key(key){}};template<class K>class hash_table{typedef hash_node<K> _node;public:bool insert(const K& key){//负载因子等于1即进行扩容if (_tables.size() == 0 || _count == _tables.size()){size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector<_node*> newtables(newsize, nullptr); // 指针数组for (auto& cur : _tables){while (cur){_node* next = cur->_next;size_t hashi = key % _tables.size(); //重新计算映射位置cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}//计算映射起始位置size_t hashi = key % _tables.size();_node* newnode = new _node(key);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_count;return true;}_node* find(const K& key){if (_tables.size() == 0)return nullptr;size_t hashi = key % _tables.size();_node* cur = _tables[hashi];while (cur){if (cur->_key == key){return cur;}cur = cur->_next;}return nullptr;}bool erase(const K& key){size_t hashi = key % _tables.size();_node* cur = _tables[hashi];_node* prev = nullptr;while (cur){if (cur->_key == key){//删除的情况分两种 : a.删除的是头节点 b.删除的是中间节点if (prev == nullptr){//prev为空,代表是是删除的是头节点_tables[hashi] = cur->_next;}else{//反之删除的是中间节点prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}private:vector<_node*> _tables;size_t _count = 0; // 记录个数}; }void test_hashtable2() {int arr[] = { 3, 33, 2, 13, 5, 12, 1002 };dwq::hash_table<int> ht;for (auto& kv : arr){ht.insert(kv);}if (ht.find(13)){cout << "13在" << endl;}else{cout << "13不再" << endl;}ht.erase(13);if (ht.find(13)){cout << "13在" << endl;}else{cout << "13不再" << endl;}}
需要注意的是这里的删除逻辑,因为哈希桶是vector 和forward_list 组成,所以需要注意节点的链接与释放。
并且,删除节点需要分情况讨论,看是为头节点还是中间链接的节点。如图:
开散列与闭散列比较
版本3:设计仿函数支持string
事实上我们会发现,使用哈希表大多数映射的可能不是整型,而是字符串,此时,而上述的哈希桶是不支持字符串的,上述的哈希桶是只支持整型,并且如果是浮点型也是不支持的,如果传整型或浮点型会报错,如下:
所以这里需要设计一些仿函数:
template<class K> struct hash_func {size_t operator()(const K& key){return key;} };
//添加模板参数支持仿函数template<class K, class hash = hash_func<K>>class hash_table
所有需要取模的位置都加上仿函数:
hash ht; size_t hashi = ht(key) % _tables.size();
那这样,这里也就支持了浮点型与整型,那么string类型怎么办?
所有,这里需要新增仿函数:
template<class K>
struct hash_string
{size_t operator()(const string& s){return s[0];}
};
但是这个仿函数有问题,因为如果字符串为空或者这里字符串的首字母相同,就会报错,所有需要进一步优化:
struct hash_str
{size_t operator()(const string& s){size_t hash_count = 0;for (auto& ch : s){hash_count = hash_count + ch;}return hash_count;}
};
这样可以了吗?理论上大致ok,但是如果字符串相同,但是字符串的顺序不同,就会出现问题,如下:
这里库或者是网络给出了经典的一些哈希算法,这里采用BKDR哈希算法。
struct hash_str {size_t operator()(const string& s){size_t hash_count = 0;for (auto& ch : s){//BKDRHashhash_count += ch;hash_count *= 31;}return hash_count;} };
可以看到,这里虽然结果相近,但是却不同。
写到这里是不是以为结束啦?不,还没有,因为这里需要显示去传参,不然是没办法使用的,有没有更好的办法?
hash_table<string, hash_str> ht;
答案是有的,使用模板特化 如下:
template<> struct hash_func<string> {size_t operator()(const string& s){size_t hash_count = 0;for (auto& ch : s){//BKDRHashhash_count += ch;hash_count *= 31;}return hash_count;} };
效果:
附上源码:
hash_table.h
//转换成整型进行比较template<class K> struct hash_func {size_t operator()(const K& key){return key;} };template<> struct hash_func<string> {size_t operator()(const string& s){size_t hash_count = 0;for (auto& ch : s){//BKDRHashhash_count += ch;hash_count *= 31;}return hash_count;} };namespace dwq {template<class K>struct hash_node{hash_node<K>* _next;K _key;hash_node(const K& key):_next(nullptr),_key(key){}};//添加模板参数支持仿函数template<class K, class hash = hash_func<K>>class hash_table{typedef hash_node<K> _node;public:bool insert(const K& key){hash ht;//负载因子等于1即进行扩容if (_tables.size() == 0 || _count == _tables.size()){size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector<_node*> newtables(newsize, nullptr); // 指针数组for (auto& cur : _tables){while (cur){_node* next = cur->_next;size_t hashi = ht(key) % _tables.size(); //重新计算映射位置cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}//计算映射起始位置size_t hashi = ht(key) % _tables.size();_node* newnode = new _node(key);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_count;return true;}_node* find(const K& key){hash ht;if (_tables.size() == 0)return nullptr;size_t hashi = ht(key) % _tables.size();_node* cur = _tables[hashi];while (cur){if (cur->_key == key){return cur;}cur = cur->_next;}return nullptr;}bool erase(const K& key){hash ht;size_t hashi = ht(key) % _tables.size();_node* cur = _tables[hashi];_node* prev = nullptr;while (cur){if (cur->_key == key){//删除的情况分两种 : a.删除的是头节点 b.删除的是中间节点if (prev == nullptr){//prev为空,代表是是删除的是头节点_tables[hashi] = cur->_next;}else{//反之删除的是中间节点prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}private:vector<_node*> _tables;size_t _count = 0; // 记录个数}; }void test_hashtable2() {int arr[] = { 3, 33, 2, 13, 5, 12, 1002 };dwq::hash_table<int> ht;for (auto& kv : arr){ht.insert(kv);}if (ht.find(13)){cout << "13在" << endl;}else{cout << "13不再" << endl;}ht.erase(13);if (ht.find(13)){cout << "13在" << endl;}else{cout << "13不再" << endl;}}void test_hashtable3() {//dwq::hash_table<double> ht;//ht.insert(12.34);//dwq::hash_table<string> ht;//ht.insert("sort");//hash_str hashstr;//cout << hashstr("abcd") << endl;//cout << hashstr("acdb") << endl;//cout << hashstr("cdab") << endl;//cout << hashstr("bcad") << endl;//cout << hashstr("cat") << endl;//cout << hashstr("tca") << endl;dwq::hash_table<string> ht;ht.insert("string");ht.insert("left");ht.insert("right");ht.insert(""); }
关于涉及到的知识:
模板特化
vector
后面会跟一期使用哈希桶封装unordered_set or unordered_map, 底层结构就是上述的哈希桶。
以上仅代表个人观点,仅供参考。