哈希：哈希函数 | 哈希概念 | 哈希冲突 | 闭散列 | 开散列

🌈个人主页： 南桥几晴秋
🌈C++专栏： 南桥谈C++
🌈C语言专栏： C语言学习系列
🌈Linux学习专栏： 南桥谈Linux
🌈数据结构学习专栏： 数据结构杂谈
🌈数据库学习专栏： 南桥谈MySQL
🌈菜鸡代码练习： 练习随想记录
🌈git学习： 南桥谈Git
🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈
本科在读菜鸡一枚，指出问题及时改正

unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到$lo{g}_{2}N$，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。

unordered_map

unordered_map介绍

介绍文档

1. unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
3. 在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
6. 它的迭代器至少是前向迭代器。

接口说明

unordered_map 的构造

函数声明	功能介绍
unordered_map	构造不同格式的unordered_map对象

unordered_map的容量

函数声明	功能介绍
bool empty() const	检测unordered_map是否为空
size_t size() const	获取unordered_map的有效元素个数

unordered_map的迭代器

是一个单向迭代器

函数声明	功能介绍
begin	返回unordered_map第一个元素的迭代器
end	返回unordered_map最后一个元素下一个位置的迭代器
cbegin	返回unordered_map第一个元素的const迭代器
cend	返回unordered_map最后一个元素下一个位置的const迭代器

unordered_map的元素访问

函数声明	功能介绍
operator[]	返回与key对应的value，没有一个默认值

unordered_map的查询

函数声明	功能介绍
iterator find(const K& key)	返回key在哈希桶中的位置
size_t count(const K& key)	返回哈希桶中关键码为key的键值对的个数

注意：unordered_map中key是不能重复的，因此count函数的返回值最大为1

unordered_map的修改操作

函数声明	功能介绍
insert	向容器中插入键值对
erase	删除容器中的键值对
void clear()	清空容器中有效元素个数
void swap(unordered_map&)	交换两个容器中的元素

unordered_map的桶操作

函数声明	功能介绍
size_t bucket_count()const	返回哈希桶中桶的总个数
size_t bucket_size(size_t n)const	返回n号桶中有效元素的总个数
size_t bucket(const K& key))	返回元素key所在的桶号

unordered_set文档介绍

set和unordered_set使用方法类似
文档介绍

底层结构

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构

哈希概念

序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O($lo{g}_{2}N$)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

哈希也叫做散列，是一种映射，把值和值进行一对一或者一对多关联。

哈希表：使用哈希思想实现的数据结构。一般都是将值和存储位置建立映射关系。

当向该结构中：

• 插入元素
  根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放搜索元素
• 对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

存在的问题：

• 值很分散时，效率不高
• 有些值不好映射，比如：string、结构体对象

除留余数法解决了数据分散问题，但是会导致哈希冲突，不同的值可能会映射到相同位置。例如下面10001和11就映射到一位置。

哈希冲突

对于两个数据元素的关键字$k_i$和 $k_j$(i != j)，有$k_i$ != $k_j$，但有：Hash($k_i$) ==Hash($k_j$)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

解决哈希冲

闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。也就是说，自己位置被占了，去抢别的位置。冲突次数越高，效率越低。

寻找下一个空位置：

线性探测

从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

插入：
通过哈希函数获取待插入元素在哈希表中的位置
如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。
删除：
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。
扩容：
散列表的载荷因子定义为:α=填入表中的元素个数 / 散列表的长度
负载因子越高，冲突率越高，效率越低；负载因子越小，冲突效率越低，效率就越高，空间利用率就越低。

模拟实现

扩容机制：
首先扩容，然后原有的值不能直接拷贝，需要重新映射。

#include<iostream>
#include<vector>
#include<utility>
using namespace std;enum State
{EMPTY,EXIST,DELETE
};template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;
};template<class K, class V>
class HashTable
{
public:HashTable(){_tables.resize(10);}bool Insert(const pair<K, V>& kv){if (Find(kv.first)) return false;//扩容if (_n * 10 / _tables.size() >= 7){//size_t newsize = _tables.size() * 2;//vector<HashData<K, V>> newtables(newsize);//for (size_t i = 0; i < _tables.size(); i++)//{}size_t newsize = _tables.size() * 2;HashTable<K, V> newHT;newHT._tables.resize(newsize);for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}size_t hashi = kv.first % _tables.size();//线性探测while (_tables[hashi]._state == EXIST)  //如果该位置存在继续往后探测{++hashi;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}HashData<K, V>* Find(const K& key){size_t hashi = key % _tables.size();//线性探测while (_tables[hashi]._state != EMPTY)  //如果该位置存在继续往后探测{if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key){return &_tables[hashi];}++hashi;hashi %= _tables.size();}return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret == nullptr) return false;else{ret->_state = DELETE;--_n;return  true;}}private:vector<HashData<K, V>> _tables;size_t _n = 0;  //有效数据个数
};

上述类型是整型，可以直接进行取模运算，但是对于其他类型，例如：string，自定义类型该如何处理？
对于其他类型，可以先转换成整型，然后进行映射。注意这里不是类型转换！key不支持强转整型取模，需要自己提供转换成整型的仿函数。
在书写代码时，需要增加一个仿函数，用于转换类型：

#include<iostream>
#include<vector>
#include<string>
#include<utility>
using namespace std;enum State
{EMPTY,EXIST,DELETE
};template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;
};template<class K>
struct HashFunc  // 用于直接转换成整型
{size_t operator()(const K& key){return (size_t)key;}
};struct StringHashFunc
{size_t operator()(const string& key){return key[0];}
};template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:HashTable(){_tables.resize(10);}bool Insert(const pair<K, V>& kv){if (Find(kv.first)) return false;//扩容if (_n * 10 / _tables.size() >= 7){//size_t newsize = _tables.size() * 2;//vector<HashData<K, V>> newtables(newsize);//for (size_t i = 0; i < _tables.size(); i++)//{}size_t newsize = _tables.size() * 2;HashTable<K, V, Hash> newHT;newHT._tables.resize(newsize);for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}Hash hs;size_t hashi = hs(kv.first) % _tables.size();//线性探测while (_tables[hashi]._state == EXIST)  //如果该位置存在继续往后探测{++hashi;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}HashData<K, V>* Find(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();//线性探测while (_tables[hashi]._state != EMPTY)  //如果该位置存在继续往后探测{if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key){return &_tables[hashi];}++hashi;hashi %= _tables.size();}return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret == nullptr) return false;else{ret->_state = DELETE;--_n;return  true;}}private:vector<HashData<K, V>> _tables;size_t _n = 0;  //有效数据个数
};

对于处理string类型时，会出现冲突，因为英文单词中首字母相同的单词有很多，我们可以对一个单词中所有字母的ASII码值进行相加：

struct StringHashFunc
{size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash += ch;}return hash;}
};

但是这种方法仍然有缺陷 ，例如：abcd，bcad，aadd这几个的ASII码仍然还是有冲突。

字符串哈希算法

二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：$H_i$ = ($H_0$ + $i^2$ )% m, 或者：$H_i$ = ($H_0$ - $i^2$ )% m。其中：i =1,2,3…， $H_0$是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。

开散列

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

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

模拟实现

插入时，需要实现头插：先将待插入的元素插入进去，然后使它变成头结点。

扩容：

• 方案一：将旧表中的数据通过映射的方式拷贝到新表中，然后再释放掉旧表中的内容，就表中虽然vector数组可以通过析构的方式释放掉，但是对应的接点删除效率不高。

if (_n == _tables.size())
{size_t newsize = _tables.size() * 2;HashTable<K, V, Hash> newHT;newHT._tables.resize(newsize);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);
}

• 方案二：将节点从旧表中拿出来，通过映射的方式放在新表中

// 扩容：负载因子为1（平均每个桶下面一个）if (_n == _tables.size()){//方案二：vector<Node*> newTables(_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);}

删除：
再删除的时候需要考虑删除的数据是头结点还是中间的节点，如果是头结点直接删除即可，中间节点之间让前一个节点指向被删除节点的下一个节点。

template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};// 特化
template<>
struct HashFunc<string>
{// abcd// bcad// aadd// BKDRsize_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash *= 131;hash += ch;}return hash;}
};bool Erase(const K& key)
{
size_t hashi = key % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{if (cur->_kv.first == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}return false;
}

完整代码：

namespace gwj_hash_bucket
{template<class K, class V>struct HashNode{pair<K, V> _kv;HashNode<K, V>* _next;HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}};template<class K,class V, class Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:HashTable(){_tables.resize(10, nullptr);_n = 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 pair<K, V>& kv){if (Find(kv.first))return false;Hash hs;// 扩容：负载因子为1（平均每个桶下面一个）if (_n == _tables.size()){//方案一：//	size_t newsize = _tables.size() * 2;//	HashTable<K, V, Hash> newHT;//	newHT._tables.resize(newsize);//	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);//方案二：vector<Node*> newTables(_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* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){if (prev == nullptr){_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 _n;};void TestHT1(){int a[] = { 10001,11,55,24,19,12,31,4,34,44 };HashTable<int, int> ht;for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(32, 32));ht.Insert(make_pair(32, 32));ht.Erase(31);ht.Erase(11);}void TestHT2(){HashTable<string, int> ht;ht.Insert(make_pair("sort", 1));ht.Insert(make_pair("left", 1));ht.Insert(make_pair("insert", 1));}}