C++中的unordered_set，unordered_map，哈希表/散列表以及哈希表的模拟实现
一、unordered_set与unordered_map
1.1 unordered_set
1.1.1 模板参数分析
首先观察其模板
template < class Key, /
class Hash = hash<Key>,
class Pred = equal_to<Key>,
class Alloc = allocator<Key>
> class unordered_set;将其与set的模板做对比
template < class T,
class Compare = less<T>,
class Alloc = allocator<T>
> class set;观察可以发现：
①Key所起的作用应当与T一致，都是充当set中存储的类型
②在set的实现过程中，我们可能会遇到要让底层搜索二叉树左子树大于右子树还是右子树大于左子树的问题，所以传入仿函数compare来进行规定
而在哈希表的实现过程中，传入的是一个Hash，它其实是一个哈希函数，具体可以参考文中2.3.1小节
同时为了辅助哈希表的顺利实现，完成映射位置数据是否相等的比较，我们传入一个Pred来规定相等的判定逻辑
③二者的内存池参数与作用完全相同
1.1.2与set的对比
实际上unordered_set与set的功能基本重叠，他们的不同点主要在底层上
①set的底层是红黑树，而unordered_set的底层是哈希表
②对key的要求不同：
set要求本身就可以进行比较大小的key的类型，或者自己实现仿函数来完善比较大小逻辑
unordered_set要求本身可以强制类型转换成size_t类型并且本身自带判断相等逻辑的类型
③set遍历是有序的，但是unordered_set遍历是无序的
④set中是双向迭代器，但是unordered_set中是单项迭代器
⑤在性能上：
插入删除时，unordered_set在重复数多，总数据量不太大时优势明显（set需要先进行二叉搜索树的查找，确认重复跳出逻辑；但是unordered_set只需要找到映射位置后就可以更准确地查找）；
查找的时候，set为O（logN）
unordered_set最优为O（1）
1.1补：
与set对于multiset一样，unordered_set也有其对应的允许重复地unordered_multiset
1.2unordered_map
与unordered_set相对于set完全一样，
unordered_map相对于map地优缺点可以分别对应，且也有自己对应的unordered_multimap
1.3二者的意义
首先明确unordered_set和unordered_map是C++11新支持的
实际上，unordered_set和unordered_map希望实现的功能与set和map是完全相同地，只是底层为哈希表相较于底层是红黑树的时候在查找等方面有机会更为优化，综合所有数据情况来看，哈希表效率的平均水平比红黑树要更高，所以才出现了unordered_set和unordered_map
二、哈希表（散列表）
2.1区分哈希（散列）与哈希表（散列表）
①哈希/散列其实是一种思想，是建立值与值之间的映射关系
例如计数排序中，我们新建一个数组来统计原数组中数字出现的个数，本质上就是利用了哈希的思想，把第一个数组情况映射到统计数组中
②哈希表/散列表是一种数据结构
是建立值与映射位置之间的关系，把值放到映射的存储位置，方便快速查找
2.2哈希表存在的意义
①哈希表是一种牺牲空间换时间的方式，以此来提高运行效率
②作为unordered_set与unordered_map的底层，为其功能的实现提供一种容器
2.3哈希函数与哈希冲突及其处理
2.3.1哈希函数是什么
因为哈希表的本质是进行映射，而进行映射有多种方式，因此我们对这项方式起名为“哈希函数”
2.3.2哈希冲突是什么
在一个表中进行数据的映射，因为表的长度有限，所以无法避免地会出现多个数据映射在同一个位置地情况，即不同值，取模以后映射到同一位置，这种情况我们称之为“哈希冲突”
2.4常见的哈希函数
常见的哈希函数有：
直接定址法、除留余数法，平方取中法，随机数法，数字分析法、叠加法等
而其中常用地有两种
2.4.1直接定址法
即用key的值映射到一个绝对位置或者一个相对位置
优点：速度快，不会出现冲突
缺点：只适合范围相对集中的一组值
2.4.2除留余数法
将key转换为合适的size_t后，用key去模表的大小N，以此映射到一个表中位置
hashi = key % N
例如10，20，15，66，16，10000，N取值为10
映射后：（蓝色线之下）
2.4补：哈希表中冲突不可避免，是否可以在适当时机延长表的长度来减少冲突呢？
是可以的，为了选择合适的时机我们引入了负载因子的概念
α = 填入表中元素个数 / 哈希表长度
即数据占比，不同的哈希冲突处理方法中可以选择不同的负载因子作为扩容哈希表的时机，每次扩大为原来的二倍即可
2.5常见的哈希冲突处理方法
常见的哈希冲突处理方法有闭散列（开放定址法），开散列（链地址法），多次散列等
2.5.1闭散列：开放定址法
即首先找自己的位置，如果自己的位置被占，那么就按规则去其他位置找一个空的位置存储
2.5.1.1规则一：线性探测
即规则设置为：当前位置+1 +2 +3 ...
①此时若要查找16：从16对应的映射位置开始向后找，遇到节点为空就结束
②此时若要删除66：若是直接置为空会影响到查找操作，该怎么办呢？
根据推理可以得出：我们需要有三种节点：存储数据的节点、被删除的节点、为空的节点
因此，我们可以给每个位置一个标记，以此来区分这三种状态
此时若要查找我们就可以跨过66但是不导致查找停止了
③线性探测有一个缺点
观察可以发现：填入的过程可能出现连续占位，即10000本该占0，可是却占到了2的位置
这是我们不愿意看到的，有没有一种办法可以减少连续占位的发生呢？
有，那就是二次探测
2.5.1.2规则二：二次探测
即规则设置为：当前位置+1^2 +2^2 +3^2 ...
若是超过了哈希表的长度，需要进行回调，实现起来即每次加后的和都进行一下取模运算
2.5.1补：闭散列的缺陷
综合来看，闭散列的方法都属于“零和博弈”，一直都属于“我的被占，就去占别人”的情况，并没有通过一些方式防止侵占别人位置的现象
2.5.2开散列：哈希桶/拉链法（也叫链地址法）
本质是存储一个指针数组，其中每个指针分别对应一个映射到当前位置的数组
①查找的时候只要找到模值映射的位置再遍历链表即可
②删除时，只要先进行查找，找到后改变链表指向或者置为nullptr即可
三、哈希表的模拟实现
3.1闭散列：开放定址法的模拟实现
3.1.1首先明确哈希表的结构
哈希表中存储节点，其包括一个键值对_kv和一个枚举类型状态参数_state
3.1.2闭散列的插入
插入过程中需要考虑载荷因子的问题，在闭散列中，α越大，说明插入数据所占比重越大，产生冲突的概率越大，一般在0.7以上我们就需要再开新的空间了（数据分析结果，此处暂不做证明）
载荷因子的计算需要一个参数：当前插入的个数
因此我们需要为哈希表增加一个成员变量size_t _n来获取
接下来进入实现，我们需要考虑两个问题：
①在计算载荷因子的过程当中，size_t / size_t不会出现小数
既然size_t类型相除只能获得整数类型，那么就可以考虑直接把被除数扩大十倍，因为只需要确定负载因子是否大于0.7，所以可以比较
size_t *10 / size_t 是否大于等于 7
就可以轻松解决问题了
②载荷因子不符合要扩容，但扩容可以直接resize吗
很明显是不可以的，因为resize会把原表映射情况复制下来，但是扩容之后映射情况已经改变，所以我们需要考虑循环遍历，把数据重新映射到新表中
1> 为了完成数据的重新映射，首先我们可以考虑创建一个新表
vector< HashData<K,V> > newtables( _tables.size() * 2 );这样以后，我们只需要遍历原表，把原来的数据重新计算并映射到新表中，完成遍历后进行两个表的交换，再走闭散列的逻辑：查找映射位置是否有值，有的话找下一个位置
2> 在实践的过程中我们会发现：“把原来的数据重新计算并映射到新表中”这一过程其实与后来的闭散列插入逻辑是重复的，所以为了减轻代码量，我们可以考虑重用Insert函数
要实现重用，我们需要新建的就不再是一个表了，而是一个新的哈希表，此后直接在遍历原表的时候调用新表的Insert函数即可，再之后的逻辑与1>中完全相同
③如果数据加和到了结尾，如何实现映射位置的回绕
在插入过程中计算映射位置后，如果对应位置hashi已经有值那么就++hashi，之后用新的hashi再次取模，这样即使++hashi操作后超出了表的长度，也会重新回绕回哈希表中
3.1.3闭散列的查找
查找返回的是结点指针HashData<K, V>* ，传入的是一个key的值
按照key的值计算对应的映射位置，再进入一个循环，当节点状态不是EMPTY的时候都可以继续向下查找，当遇到非DELETE并且key的值相等的节点处即可返回结点指针
3.1.4闭散列的删除
首先进行节点的查找，为nullptr就返回false；无需对节点进行详细操作，只要把节点的状态置为DELETE即可，返回true
3.1.5闭散列的析构
没有涉及资源管理，析构无需显示实现
⭐3.1.6对于特殊情况的处理
在之前的实现中，我们针对的都是类型为size_t类型的key，但实际上key的类型并不止size_t一种，
例如此时传入的是一个
HashTable<string, string> hash;此时会出现两个问题：
①无法转化为size_t来与表的大小进行取模
为了解决这一问题，我们采用二层映射（即哈希函数）
为此，给HashTable传入一个模板参数class Hash，使得我们可以在需要的时候通过仿函数来按需求重载()来进行第一层映射，仿函数返回size_t类型值
1>对于可以强制类型转换为size_t类型的，我们选择给一个默认模板参数Hashfunc<K>
2>对于不能强转的单独去实现，例如string
那么问题来了，对于string我们该如何去映射呢？
首先，取地址是可以得到一个可以强转为size_t类型的值的，但这可行吗？
答案是不可以的，因为如果要插入的是s1和s2，而他们存储内容都是“first”，会因为地址不同而映射到不同的位置，但很明显这不是我们想要的，相同的字符串应该映射到同一位置才合理
因此，我们可以考虑第二种方法：把所有字母的ASCII码值相加来获得一个size_t类型的值
这样可以很好地满足相同的字符串应该映射到同一位置这一需求，也方便我们比较key是否相等
这样以后，在使用string的时候就可以
HashTable<string, string, StringHashfunc>但是string比较特殊，它太常见了，可不可以把它归类到默认参数“Hashfunc<K>”中呢？
可以的，我们可以对Hashfunc<K>进行特化处理
template<>
struct Hashfunc<string>处理后，就可以直接使用
HashTable<string, string>而不必担心无法比较的问题了
②无法判断字符串是否相等
可以为哈希表新建一个模板参数 class Pred = equal_to<Key>
再以bool为返回值，重载()来达到判断相等的目的
3.1.6补：string中的冲突减少
假设string中有10位字符，那么它的可能性就有
256^10种
而size_t的可能性只有
2^32种
前者明显大于后者，所以大映射小，冲突不可避免
为此有人研究过如何减少string种冲突的发生，因为好的哈希函数可以最大程度减少冲突
这里给出一种结论方案：在string循环相加的时候，每次把当前加和乘以31，131，1313等值，可以有效的减少冲突（细节暂时跳过）
3.1.7闭散列参考代码
enum STATE
{
EXIST,
EMPTY,
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;
}
};
//对于string进行一次特殊处理
template<>
struct Hashfunc<string>
{
size_t operator()(const string& key)
{
size_t sum = 0;
for (const auto& e : key)
{
sum *= 131;
sum += e;
}
return sum;
}
};
template<class K, class V, class Hash = Hashfunc<K>>
class HashTable
{
public:
HashTable()
{
_tables.resize(10);
}
HashData<K, V>* Find(const K& key)
{
Hash hs;
size_t tmp = hs(key) % _tables.size();
//查找的过程需要看有没有到EMPTY
while (_tables[tmp]._state != EMPTY)
{
if (_tables[tmp]._state != DELETE && _tables[tmp]._kv.first == key)
return &_tables[tmp];
else
{
tmp++;
tmp %= _tables.size();
}
}
return nullptr;
}
bool Insert(const pair<K, V>& kv)
{
Hash hs;
if (Find(kv.first))
{
return false;
}
//控制载荷因子,如果占比大于0.7就要进行扩容
if (_num * 10 / _tables.size() >= 7)
{
//扩容过程不能直接resize，
HashTable newHash;
newHash._tables.resize(_tables.size() * 2);
for (const auto& e : _tables)
{
if (e._state == EXIST)
{
newHash.Insert(e._kv);
}
}
swap(_tables, newHash._tables);
}
//闭散列开放定址法逻辑：先找到映射位置再去看有没有，存入
size_t tmp = hs(kv.first) % _tables.size();
while (_tables[tmp]._state == EXIST)
{
++tmp;
tmp %= _tables.size();
}
_tables[tmp]._kv = kv;
_tables[tmp]._state = EXIST;
_num++;
return true;
}
bool Delete(const K& key)
{
HashData<K, V>* ptr = Find(key);
if (ptr == nullptr)
{
return false;
}
ptr->_state = DELETE;
return true;
}
protected:
vector<HashData<K, V>> _tables;
size_t _num = 0;
};3.2开散列：链地址法的模拟实现
3.2.1首先明确哈希表的结构
每个节点指针都指向一个单链表的头节点，在单链表中存储当前映射位置的所有数据
3.2.2开散列的插入
与闭散列基本同理，都是先查映射位置，只是开散列需要去申请节点来插入
我们选择单链表来存储冲突的数据，进行链表的头插尾插都可以，暂时选用头插来实现，插入后++_n。
插入逻辑理顺后来看负载因子，不同于闭散列，开散列的负载因子要求没有那么严格，当因子为1时进行扩容就可以
再看扩容的过程：
①是否可以像闭散列那样重用Insert呢？
可以但不推荐，因为实现以后会发现有这样的问题：
多次复用Insert，意味着在从原表重新映射到新表的过程中，每个已有节点都需要重新申请，而在交换表后，旧表中的节点又都需要调用析构来释放，这样一来一回会造成极大的资源浪费
②可不可以直接利用旧表的节点，不去申请再释放新节点呢？
答案是可以的，我们只要选择挪动到新的节点位置即可，新建一个指针数组而不是新建哈希表，然后遍历啊旧表所有节点，将其以此头插到新表中
3.2.3开散列的查找
先找到映射的位置，再遍历链表进行查找，暂时只返回是否找到的bool类型
3.2.3开散列的删除
先进行查找，找到后需要记录一下要删除节点的前一个结点（在单链表中的前一个），初始为nullptr
然后分两种情况：
①前一个节点为nullptr：把cur->next赋值给指针数组对应位置，delete当前节点，--_n
②前一个结点不为nullptr：改变前一个结点的指向，再delete当前节点,--_n
3.2.4开散列的改进
①多种类型key的支持
与闭散列中完全相同，增加一个Hash仿函数来让各种类型都可以转为size_t
②一个桶(哈希桶)下挂过多节点的问题
仔细看链地址法会发现：一旦出现许多值都挂在同一个单链表中那么其查找效率会变得和单链表一致，数据量大的话会严重影响效率
有人针对这一种情况，将桶上所挂节点数进行了一个限制，一旦超过这个限制，会自动将单链表中的值拷贝给红黑树，提升查找效率
3.2.5开散列参考代码
template<class K,class V>
struct HashNode
{
pair<K, V> _data;
HashNode* _next;
HashNode(const pair<K, V>& data)
:_data(data)
, _next(nullptr)
{}
};
template<class K>
struct Hashfunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
//对于string进行一次特殊处理
template<>
struct Hashfunc<string>
{
size_t operator()(const string& key)
{
size_t sum = 0;
for (const auto& e : key)
{
sum *= 131;
sum += e;
}
return sum;
}
};
template<class K, class V, class Hash = Hashfunc<K>>
class HashTable
{
typedef HashNode<K,V> Node;
public:
HashTable()
{
//vector进行resize的时候会把第二个参数的值赋给前面开出来的所有空间
_tables.resize(10, nullptr);
}
// 哈希桶的销毁
~HashTable()
{
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
}
}
// 插入值为data的元素，如果data存在则不插入
bool Insert(const pair<K, V>& data)
{
Hash hs;
if (Find(data.first))
{
return false;
}
//负载因子超出1了
if (_n == _tables.size())
{
//这里不适合复用Insert，否则会出现多次new节点再析构的情况
vector<Node*> newtables;
newtables.resize(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
size_t num = hs(_tables[i]->_data.first) % newtables.size();
Node* next = cur->_next;
cur->_next = newtables[num];
newtables[num] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = hs(data.first) % _tables.size();
//申请节点，进行头插
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
_n++;
return true;
}
// 在哈希桶中查找值为key的元素，存在返回true否则返回false
bool Find(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_data.first == key)
{
return true;
}
cur = cur->_next;
}
return false;
}
// 哈希桶中删除key的元素，删除成功返回true，否则返回false
bool Erase(const K& key)
{
if (!Find(key))
{
return false;
}
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
Node* prev = nullptr;
while (cur)
{
if (cur->_data.first == key)
{
//当删除节点是链表最后一个节点
if (prev == nullptr)
{
delete cur;
cur = nullptr;
_tables[i] = nullptr;
return true;
}
prev->_next = cur->_next;
delete cur;
cur = nullptr;
return true;
}
prev = cur;
cur = cur->_next;
}
}
assert(false);
}
private:
vector<Node*> _tables; // 指针数组
size_t _n = 0; // 表中存储数据个数
};3.3一些其他的问题
①在使用链地址法处理冲突的时候，在指针数组各个位置等概率情况下，查找成功的平均查找长度为
所有结点层数 / 元素个数
②因为存在哈希冲突，所以哈希表查找的时间复杂度不是恒定的O（1）
③哈希函数的值域应该尽可能均匀分布，即取每个位置应为等概率的