哈希表详解及模拟实现（unordered_map）
目录
认识哈希表：
哈希冲突：
除留余数法--(常用)
平方取中法--(了解)
折叠法--(了解)
随机数法--(了解)
泛型编程：
闭散列：
线性探测：
二次探测：
扩容：
查找：
插入：
删除：
开散列：
扩容：
查找：
插入：
删除：
迭代器：
全部代码:
认识哈希表：
哈希表是一种数据结构，也称散列表，主要用于查找，且使用很频繁，可见它的效率相比其他用于查找的数据结构，肯定有优势。之前学习的顺序表和平衡二叉搜索树，查找的时间复杂度为O（n）和O（logn），它们两都需要通过key值一一比较不断缩小查找范围，进而查找到所需数据。而哈希表的优势在于无需比较，只需通过某种函数（哈希函数）计算关键码，通过映射关系可直接找到数据，近似O（1）的时间复杂度。
当向该结构中：
插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置 取元素比较，若关键码相等，则搜索成功
我们将它们放入哈希表key值如何取呢？一般数据是size_t或者能强转成size_t类型的key值直接取该数据，对于无法强转的例如string，则通过哈希函数转换，key值也不是直接当作下标存入哈希表内，不然如果一个数据过大，就要开很大的数组， 一般我们需要将 数据%数组大小来得到对应的下标，这种转换也是哈希函数， 举个例子：数据集合{1，7，6，4，5，9}；
哈希冲突：
还是上面的例子，这时我们有一个数据75要进入哈希表，通过哈希函数计算key值，75 % 10 = 5，但是发现下标为5的位置已经有数据，这就出现了不同的数据对应的相同的下标，这就是所谓的哈希冲突，又称哈希碰撞。
注意哈希冲突是不能完全解决的，只能缓解，鸽巢定理可证，所有的字符串，肯定比size_t的最大值要大，因为不限长度字符串几乎是无限的，所以鸽子比巢多，肯定会有巢有两只以上的鸽子。
缓解哈希冲突主要从两个方面：
1.，第一个方面就是对哈希函数入手，上面这个例子的哈希函数，是用key对数组大小取余，这是直接定址法，这种哈希函数出现哈希冲突的概率还是不小的，先来看看哈希函数的设计原则：
哈希函数的定义域必须包括需要存储的全部关键码，而如果哈希表允许有m个地址时，其值 域必须在0到m-1之间 哈希函数计算出来的地址能均匀分布在整个空间中 哈希函数应该比较简单
再来看看几种常见的哈希函数：
除留余数法--(常用)
假设哈希表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数， 按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
平方取中法--(了解)
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
折叠法--(了解)
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这 几部分叠加求和，并按哈希表表长，取后几位作为散列地址。
随机数法--(了解)
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中 random为随机数函数。
2.第二个方面就是对哈希表的存储结构入手，想必大家见过最多的哈希表结构就是顺序表+链表，其实哈希表也可以单纯用顺序表实现，两种不同的底层结构在于它们如何应对哈希冲突，C++的STL库中使用的是顺序表+链表的方式，没错这种方式的效率是更优的，但是单纯用顺序表的结构也是值得学习的，接下来的内容我会分别介绍并模拟实现这两种哈希表的底层结构。
泛型编程：
在模拟实现中，我的my_unordered_set和my_unordered_map封装了一个哈希表HashTable,但set里面存的是一个数据K，而set里面存的是pair<K,T>,HashTable里面只接受一个data,这就导致了如果是set，data就是K类型，如果是map，data就是pair<K,V>,但我们只有一个哈希表，该怎么解决这种矛盾呢？
仿函数：我们可以分别在set和map里创建一个类，在类里重载运算符（），然后在set中的（）重载中直接返回K，在map中的（）重载中返回pair中的K，也就是pair中的first，然后将这个类传给HashTable，在HashTable中使用data前就调用这个类的括号来取里面的数据：
set：
map：
在HashTable中的使用：（哈希地址的计算中就用到了）
HashFunc和上面讲的一样，主要作用是如果key为其他不是size_t的类型将它们强转成size_t和若为string则通过哈希函数转化成size_t，这种方法就是泛型编程的一种。
闭散列：
闭散列，又称开放定址法，也就是上面提到的单纯使用顺序表的方法来实现哈希表，它应对哈希冲突的方法是如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去，那么如何找到“下一个”空位置呢？
线性探测：
回到最开始的例子，我们需要插入75，通过哈希函数计算下标为5，但下标为5的位置已经被占用。
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
所以最后我们能找到8下标位置为空位置，然后进行插入数据。 注意往后探测过程中不能超过数组长度，所以我们每向后走一次就需要%数组长度，以保证当超过数组长度时，下标能回到数组开头。
如何判断这个位置是否为空，只需将每个位置里面存入一个状态值（枚举类型），总共有三个状态：EMPTY，EXIST，DELETE，分别表示空，存在数据，之前有数据但被删除
这部分代码只需理解线性探测思路就行，其他不理解的地方，需结合全部代码。
二次探测：
虽然线性探测能解决哈希冲突，但可以发现这样冲突的数据大部分都聚在了一起，不离散,如图：
为了避免这种情况，线性探测时hashi每次向后走1步，我们采用二次探测，也就是每次向后走i的平方步，每次i++，也就是依次走1，4，9，16，25......步，实现很简单，这里不演示。
扩容：
闭散列的扩容不是满了才扩容，我们先引入一个概念：负载因子，负载因子 = 存在的元素/数组的容量，简单来说负载因子就是占用率，当负载因子>=0.7的时候我们才进行扩容。
扩容思路：
我们可以直接开一个新的hash表，将新表的大小设为旧表的2倍，再将旧表的元素一个个插入到新表，最后用swap函数交换新旧表。 这样写的好处：不必销毁新表，因为新表是局部对象，函数结束后自动销毁了。
查找：
通过key查找某个节点：
先通过key用哈希函数算出对应哈希地址，再从哈希地址开始往后线性探测，找到后返回节点：
插入：
分析一下插入，当插入一个数时该如何做呢？
1.先用查找函数判断能否找到，若找到了，代表原哈希表里有，直接返回false。 2.用负载因子判断是否需要扩容，需要就进行扩容。 3.通过key和哈希函数，算出哈希地址。 4.哈希地址上有值就往后线性探测。
删除：
因为之前，我们在每个节点上都设置了三种状态：EMPTY，EXIST，DELETE，所以现在删除一个数就非常简单了：
只需先通过哈希函数和线性探测找到该节点，再将该节点的状态改为DELETE即可。
开散列：
开散列也就是C++STL库哈希表实现方法，说明它相比闭散列还是有一定的优越性的，开散列应对哈希冲突的方法就是在冲突数据下面用链表进行连接。
扩容：
开散列的扩容条件就是_n == 数组大小的时候：
相比闭散列的扩容方法，开散列只要扩容条件不同，其他差不多，只有旧表中每个桶的数据要依次头插到新表对应的哈希地址。
查找：
如果对应的哈希地址里面有数据，就沿着该地址的链表遍历，找到即可。
插入：
1.先用查找函数判断能否找到，若找到了，代表原哈希表里有，直接返回false。 2.判断是否需要扩容，需要就进行扩容。 3.通过key和哈希函数，算出哈希地址。 4.在该哈希地址的链表处进行头插。
删除：
1.先通过查找函数找到key对应的哈希地址 2.遍历该哈希地址的链表。 3.找到后连接该节点的上一个和下一个节点。 4.注意如果是头删要特殊处理，因为上一个节点为空。
迭代器：
迭代器功能都比较简单，这里我只讲++的思路，其他功能可以到文章最后看全部代码。
++：
1.到一个哈希地址时要先判断存不存在冲突数据，也就是链表。 2.若有冲突数据，直接走向链表的next即可。 3.链表走到尾部，就需要从这个链表的哈希地址开始往后线性探测，直到找到下一个有有效数据的哈希地址或者哈希表走完。
全部代码:
my_ordered_set.h
#include"HashTable.h"
template<class K,class Hash = HashFunc<K>>
class my_unordered_map
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::iterator iterator;
typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::const_iterator const_iterator;
public:
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
const_iterator begin()const
{
return _ht.begin();
}
const_iterator end()const
{
return _ht.end();
}
pair<iterator,bool> insert(const K& key)
{
return _ht.Insert(key);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
hash_bucket::HashTable<K,const K,SetKeyOfT,Hash> _ht;
};my_unordered_map.h
#include"HashTable.h"
template<class K, class T,class Hash = HashFunc<K>>
class my_unordered_set
{
struct MapKeyOfT
{
const K& operator()(const pair<K,T>& kv)
{
return kv.first;
}
};
typedef typename hash_bucket::HashTable<K, pair<K,T>, MapKeyOfT, Hash>::iterator iterator;
typedef typename hash_bucket::HashTable<K, pair<K,T>, MapKeyOfT, Hash>::const_iterator const_iterator;
public:
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
const_iterator begin()const
{
return _ht.begin();
}
const_iterator end()const
{
return _ht.end();
}
pair<iterator, bool> insert(const K& key)
{
return _ht.Insert(key);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
T& operator[](const K& key)
{
pair<iterator, bool> ret = _ht.Insert(make_pair(key, T()));
return ret->iterator->second;
}
private:
hash_bucket::HashTable<K, pair<K,T>, MapKeyOfT, Hash> _ht;
};HashTable.h
#pragma once
#include<vector>
#include<string>
using namespace std;
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 ch : key)
{
hash *= 131;
hash += ch;
}
return hash;
}
};
namespace open_address
{
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 Hash = HashFunc<K>>
class HashTable
{
public:
HashTable()
{
_tables.resize(10);
}
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
//_n / _table.size() >= 0.7//不采用这种判断方法是因为左右类型不同，所以将左右都*10
if (_n * 10 / _tables.size() >= 7)
{
HashTable<K, V, Hash> newHT;
newHT._tables.resize(_tables.size() * 2);
// 旧表重新计算负载到新表
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();//hs为仿函数，将key转为size_t，因为kv.first 可能为string
// 线性探测
while (_tables[hashi]._state == EXIST)//_tables为顺序表
{
++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; // 有效数据个数
};
}
namespace hash_bucket
{
template<class T>
struct HashNode
{
T _data;
HashNode<T>* next;
HashNode(const T& data)
:_data(data)
,next(nullptr)
{}
};
template<class K,class T,class KeyOfT,class Hash = HashFunc<T>>
class HashTable
{
typedef HashNode<T> Node;
public:
template<class Ptr,class Ref>
struct _HTIterator//迭代器，设置为内部类
{
typedef _HTIterator Self;
typedef HashNode<T> Node;
Node* _node;
const HashTable* _pht;
_HTIterator(Node* node,const HashTable* pht)
:_node(node)
,_pht(pht)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
Self& operator++()
{
if (_node->next)//当前桶没走完，直接找下一个节点
{
return _node->next;
}
else
{
Hash ha;
KeyOfT kot;
size_t i = ha(kot(_node->_data)) % _pht->_table.size();
i++;
for (;i < _pht->_table.size();i++)
{
if (_pht->_table[i])
break;
}//循环结束后要么找到一个有数据的桶，要么整个表走完了
if (i == _table.size())//表走完了
{
_node = nullptr;
}
else//找到了有数据的桶
{
_node = _pht->_table[i];
}
}
return this;
}
};
typedef _HTIterator<T*, T&> iterator;
typedef _HTIterator<const T*, const T&> const_iterator;
iterator end()
{
return iterator(nullptr, this);
}
iterator begin()
{
size_t i = 0;
for (i = 0;i < _table.size();i++)
{
Node* cur = _table[i];
if (cur)
{
return iterator(cur, this);
}
}
}
const_iterator end() const
{
return const_terator(nullptr, this);
}
const_iterator begin() const
{
size_t i = 0;
for (i = 0;i < _table.size();i++)
{
Node* cur = _table[i];
if (cur)
{
return const_iterator(cur, this);
}
}
}
pair<iterator,bool> Insert(const T& data)
{
HashFunc hs;
KeyOfT kot;
iterator it = Find(kot(data));
if (it!=end())//如果表中原来有
{
return make_pair(it, false);
}
if (_n == _table.size())//扩容
{
vector<Node*> newtable(2 * _table.size(), nullptr);
for (int i = 0;i < _table.size();i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->next;
size_t hashi = hs(kot(data)) % newtable._table.size();
//头插
cur->next = newtable[hashi];
newtable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
//新旧表交换
_table.swap(newtable._table);
}
size_t hashi = hs(kot(data)) % _table.size();
Node* newnode = new HashNode(data);
//头插
newnode->next = _table[hashi];
_table[hashi] = newnode;
_n++;
return make_pair(interator(newnode,this),true);
}
iterator Find(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _table.size();
Node* cur = _table[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return iterator(cur,this);
}
cur = cur->next;
}
return end();
}
bool Erase(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _table.size();
Node* prev = nullptr;
Node* cur = _table[hashi];
while (cur)
{
if (kot(cur->data) == key)
{
if (prev == nullptr)//如果删除的是第一个
{
_table[hashi] = cur->next;
}
else//如果删除的是中间的
{
prev->next = cur->next;
}
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->next;
}
}
return false;
}
private:
vector<Node*> _table;
size_t _n;
};
}