【C++高阶六】哈希与哈希表

1.什么是哈希？
2.unordered系列容器
3.哈希表
- 3.1将key与存储位置建立映射关系
- - 3.1.1直接定址法
  - 3.1.2除留余数法（产生哈希冲突）
- 3.2解决哈希冲突的方法
- - 3.2.1闭散列（开放定址法）
  - 3.3.2开散列（链地址法）（哈希桶）
4.实现哈希表（除留余数法建立映射）
- 4.1闭散列实现
- - 4.1.1状态与结构
  - 4.1.2 Insert
  - 4.1.3负载因子和扩容
  - 4.1.4 Find
  - 4.1.5 Erase
  - 4.1.6 完整代码
- 4.2 开散列实现
- - 4.2.1 状态与结构
  - 4.2.2 Insert
  - 4.2.3 负载因子和扩容
  - 4.2.4 Find
  - 4.2.5 Erase
  - 4.2.6 仿函数
  - 4.2.7 完整代码

1.什么是哈希？

理想中的搜索方法：不经过任何比较和遍历就可以直接从表中搜索想要的元素
如果构造一种存储结构，并通过某种函数能使元素的存储位置与它自身关键码之间建立映射的关系，那么在查找时只要通过函数就可以快速找到该元素

当向该结构中插入元素时，根据待插入元素的关键码，以函数计算出该元素的存储位置并按此位置进行存储
当向该结构中搜索元素时，用函数对元素的关键码进行同样的计算求得元素的存储位置，在结构中按此位置取元素比较，若关键码相等则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

2.unordered系列容器

unordered_map和unordered_set与map和set是什么关系？
在这里插入图片描述
在内部，unordered_map没有对<kye, value>按照任何特定的顺序排序

其实unordered_map和map使用起来没什么区别，那么什么时候应该用unordered系列呢？答案是你只关心键值对的内容而不关心是否有序时就选择unordered系列

3.哈希表

3.1将key与存储位置建立映射关系

3.1.1直接定址法

在这里插入图片描述

每一个值都有一个唯一位置，适用于范围比较集中的数据

3.1.2除留余数法（产生哈希冲突）

在这里插入图片描述

范围不集中，分布分散
key值跟存储位置的关系是取模出来的，不同的值有可能映射到相同的位置，造成哈希冲突，如：5和55取模后都为5

3.2解决哈希冲突的方法

3.2.1闭散列（开放定址法）

当发生哈希冲突时，如果哈希表未被装满，说明哈希表中必然还有空位置，则可以用线性探测把key存放到冲突位置中的下一个位置，若有两个取模相同的值，则将先进来的占住当前取模位置，后进来的向后探测，若有空位置则放入
在这里插入图片描述

key%len，len是表的长度

3.3.2开散列（链地址法）（哈希桶）

对关键码集合用散列函数计算散列地址，具有相同地址码归于同一个子集合，每一个子集称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头节点存储在哈希表中

在这里插入图片描述

4.实现哈希表（除留余数法建立映射）

4.1闭散列实现

4.1.1状态与结构

整体实现全部放入名为开放地址法Open_Address的命名空间中
在这里插入图片描述

假设要删除55，因为55取余后为5，所以先去位置为5的地方去找，没有找到则继续向后寻找，到空才结束
但是把33删除后，再次查找13时，由于提前遇到空，则查找直接结束，不会向后寻找所以找到后不能直接删除，会影响继续查找

设置三种状态： 空、存在、删除

enum Status//状态
{EMPTY,//空EXIST,//存在DELETE//删除
};template<class K,class V>
struct HashData
{pair<K, V> _kv;//kv值Status _status = EMPTY;//状态默认为空
};

state默认设为空，不然有可能造成映射位置没有数据，但状态为存在的情况

4.1.2 Insert

key值跟存储位置的关系是取模出来的（key%len）
len为 _tables.size() 还是 _tables.capacity()？

假设为capacity，若当前位置为空，将值填入并将状态设置为存在，就会造成越界，在vector中operator[]会做越界检查，下标是否小于size

插入：

bool Insert(const pair<K, V>& kv)
{size_t hashi = kv.first % _table.size();_table[hashi]._kv = kv;_table[hashi]._status = EXIST;
}

线性探测：

while (_table[hashi]._status == EXIST)
{hashi++;hashi %= _table.size();//防止越界,可以回到0
}

完整代码：

bool Insert(const pair<K, V>& kv)
{size_t hashi = kv.first % _table.size();while (_table[hashi]._status == EXIST){hashi++;hashi %= _table.size();//防止越界,可以回到0}_table[hashi]._kv = kv;_table[hashi]._status = EXIST;
}

4.1.3负载因子和扩容

哈希表冲突越多效率就越低，若表中位置都满了就需要扩容，所以提出负载因子的概念
负载因子 = 填入表的元素个数 / 表的长度，用于表示表储存数量的百分比
填入表的元素个数越大，表示冲突的可能性越大，所以在开放定址法时，应该控制在0.7-0.8以下，超过就会扩容

if (_num * 10 / _table.size() == 7)
{size_t new_num = _table.size() * 2;HashTable<K, V> new_HT;for (size_t i = 0; i < _table.size();i++)//遍历旧表{if (_table[i]._status == EXIST){new_HT.Insert(_table[i]._kv);}}_table.swap(new_HT._table);
}

创建new_HT，将其中的_tables的size进行扩容，通过复用insert的方式，完成对新表的映射，最后交换旧表的_tables与new_HT的_tables ，以达到更新数据的目的

4.1.4 Find

若当前位置的状态为存在或者删除，则继续找，遇见空就结束
若在循环中找到了，则返回对应位置的地址，若没找到则返回nullptr
删除只是把要删除的数据的状态改为DELETE，但是数据本身还是在的，所以Find还是可以找到的

HashData<K, V>* Find(const K& key）
{size_t hashi = key % _table.size();while (_table[hashi]._status != EMPTY){if (_table[hashi]._status == EXIST && _table[hashi]._kv.first == key){return &_table[hashi];}hashi++;hashi %= _table.size();}return nullptr;
}

4.1.5 Erase

bool Erase(const k& key)
{HashData<K, V>* temp = Find(key);if (temp){temp->_status = DELETE;_num--;return true;}else{return false;}
}

4.1.6 完整代码

using namespace std;
namespace Open_Address//闭散列（开放定址法）
{enum Status//状态{EMPTY,//空EXIST,//存在DELETE//删除};template<class K,class V>struct HashData{pair<K, V> _kv;//kv值Status _status = EMPTY;//状态默认为空};template<class K,class V>class HashTable{public:HashTable(){_table.resize(10);}bool Insert(const pair<K, V>& kv){//负载因子等于0.7时扩容if (_num * 10 / _table.size() == 7){size_t new_num = _table.size() * 2;HashTable<K, V> new_HT;for (size_t i = 0; i < _table.size();i++)//遍历旧表{if (_table[i]._status == EXIST){new_HT.Insert(_table[i]._kv);}}_table.swap(new_HT._table);}//线性探测size_t hashi = kv.first % _table.size();while (_table[hashi]._status == EXIST){hashi++;hashi %= _table.size();//防止越界,可以回到0}_table[hashi]._kv = kv;_table[hashi]._status = EXIST;}HashData<K, V>* Find(const K& key）{size_t hashi = key % _table.size();while (_table[hashi]._status != EMPTY){if (_table[hashi]._status == EXIST && _table[hashi]._kv.first == key){return &_table[hashi];}hashi++;hashi %= _table.size();}return nullptr;}bool Erase(const k& key){HashData<K, V>* temp = Find(key);if (temp){temp->_status = DELETE;_num--;return true;}else{return false;}}private:vector<HashData<K, V>> _table;//指针数组size_t _num;//存储的数据个数};
}

4.2 开散列实现

4.2.1 状态与结构

整体实现全部放入名为哈希桶Hash_Bucket的命名空间中

template<class K,class V>
struct HashNode
{HashNode(const pair<K,V>& kv):_kv(kv),_next(nullptr){}HashNode<K, V>* _next;//指向下一个节点pair<K, V> _kv;//记录数据
};

4.2.2 Insert

在同一个桶中数据不分先后
在这里插入图片描述
创建一个新节点newnode，使newnode的next连接到当前映射位置，再让newnode成为桶的头节点

size_t hashi = kv.first % _table.size();
Node* newnode = new Node(kv);
newnode->_next = _table[hashi];
_table[hashi] = newnode;

4.2.3 负载因子和扩容

负载因子越大，冲突的概率越高，查找效率越低，空间利用率越高
负载因子越小，冲突的概率越低，查找效率越高，空间利用率越低

在这里插入图片描述

在这里插入图片描述
原表的节点重新计算位置后移动到新表中
由于新表的size大小为20，所以12可以找到对应位置的桶，而102没有对应大小的桶，所以取模来到对应2位置处，与2形成链式结构
遍历旧表中的数据，若数据为空，就往后遍历
若数据不为空，则将其移动到新表中，进行头插

if (_num == _table.size())
{size_t newsize = _table.size() == 0 ? 10 : _table.size()*2;vector<Node*> new_table;new_table.resize(newsize, nullptr);for (size_t i = 0; i < _table.size(); i++){Node* temp = _table[i];while (temp){Node* next = temp->_next;//挪动到新表size_t hashi = _table[i] % new_table.size();temp->_next = new_table[i];new_table[hashi] = temp;temp = next; }_table[i] = nullptr;}_table.swap(new_table);
}

4.2.4 Find

使用temp记录当前映射位置，遍历当前位置的单链表，查询是否有key值的存在，若有则返回temp，若没有则返回空

Node* Find(const K& key)
{if (_table.size() == 0){return nullptr;}size_t i = key % _table.size();Node* temp = _table[i];while (temp){if (temp->_kv.first == key){return temp;}temp = temp->_next;}return nullptr;
}

4.2.5 Erase

在这里插入图片描述
假设要删除3，则需让表的位置指向要删除节点的下一个

假设要删除13，则需找到删除节点的前一个节点，使其指向要删除节点达到后一个节点

bool Erase(const K& key)
{size_t i = key % _table.size();Node* prev = nullptr;//记录前一个结点Node* temp = _table[i];while (temp){if (temp->_kv.first == key){if(prev == nullptr)//删除头节点{_table[i] = temp->_next;}else{prev->_next = temp->_next;}delete temp;return true;}prev = temp;temp = temp->_next;}return false;
}

4.2.6 仿函数

在这里插入图片描述

若为string类型，使用insert无法计算对应的hashi值，所以需要加入仿函数
在这里插入图片描述
加入全局仿函数：

template<class K>
struct HashFunc//仿函数
{size_t operator()(const K& key){return (size_t)key;}
};template<>
struct HashFunc<string>//仿函数特化
{size_t operator()(const string& key){size_t hash = 0;for (auto e : key){hash *= 31;//乘31或者131都行，为了避免数字重复hash += e;}return hash;}
};

再次使用 HashTable时不用传入仿函数也能调用string 类型

4.2.7 完整代码

namespace Hash_Bucket//开散列（哈希桶）
{template<class K,class V>struct HashNode{HashNode(const pair<K,V>& kv):_kv(kv),_next(nullptr){}HashNode<K, V>* _next;//指向下一个节点pair<K, V> _kv;//记录数据};template<class K,class V,class Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:bool Insert(const pair<K,V>& kv){//负载因子等于1时扩容Hash hash;if (_num == _table.size()){size_t newsize = _table.size() == 0 ? 10 : _table.size()*2;vector<Node*> new_table;new_table.resize(newsize, nullptr);for (size_t i = 0; i < _table.size(); i++){Node* temp = _table[i];while (temp){Node* next = temp->_next;//挪动到新表size_t hashi = hash(temp->_kv.first) % new_table.size();temp->_next = new_table[i];new_table[hashi] = temp;temp = next; }_table[i] = nullptr;}_table.swap(new_table);}size_t hashi = hash(kv.first) % _table.size();Node* newnode = new Node(kv);//头插newnode->_next = _table[hashi];_table[hashi] = newnode;_num++;return true;}Node* Find(const K& key){if (_table.size() == 0){return nullptr;}size_t i = hash(key) % _table.size();Node* temp = _table[i];while (temp){if (temp->_kv.first == key){return temp;}temp = temp->_next;}return nullptr;}bool Erase(const K& key){size_t i = key % _table.size();Node* prev = nullptr;//记录前一个结点Node* temp = _table[i];while (temp){if (temp->_kv.first == key){if(prev == nullptr)//删除头节点{_table[i] = temp->_next;}else{prev->_next = temp->_next;}delete temp;return true;}prev = temp;temp = temp->_next;}return false;}private:vector<Node*> _table;//指针数组size_t _num = 0;//存储的数据个数};
}