【C++】哈希学习

unordered系列关联式容器

unordered系列关联式容器是从C++11开始，STL提供的。它的查询效率要更优于set/map类型关联式容器。
unordered系列容器的名字是从功能角度来取定的。set/map这类容器，其遍历是有序的，而unordered系列容器的遍历则是无序的。
从底层角度来看，set/map类容器底层采用红黑树实现，而unordered系列容器则是采用的哈希结构。同时，map/set的迭代器是双向的，而unordered系列容器是单向的。
unordered系列容器的使用可以参考set/map的使用【C++】set & map的使用，它们的使用方式大多是类似的。

哈希结构

哈希，也叫散列，是一种值与存储位置之间建立映射关联的结构。
哈希结构通过哈希函数(Hash)使元素的关键码与存储位置之间建立一一映射的关系。当插入元素时，由元素的关键码，根据哈希函数计算出元素的存储位置进行存放；当查找删除元素时，也是同样的计算过程。

除留余数法

哈希函数有很多种，本文中使用的哈希函数为除留余数法。
设哈希表中允许存放的位置个数为n，取一个小于等于n的最大质数p作为除数，按照哈希函数：Hash(key) = key % p，通过计算将关键码转换成哈希表中对应的地址。

哈希冲突

当哈希表中存放的数据越来越多，必然会出现不同的key通过相同哈希函数的计算，出现相同地址的情况，即哈希冲突，或哈希碰撞。
哈希冲突的解决有两种常见方式：闭散列和开散列。

闭散列

闭散列，也叫开放定址法。当发生哈希冲突时，如果哈希表未被填满，也就是还存在空位置，那么可以把关键码key的元素存放到冲突位置的“下一个”空位置去。

线性探测

线性探测：从发生冲突的位置开始，依次向后探测，直到找到一个空位置为止。
线性探测的插入分两种情况：

1. 通过哈希函数计算待插入元素的位置，如果该位置没有元素，即直接插入新元素；
2. 如果该位置有元素，发生哈希冲突，使用线性探测找到空位置，再插入新元素。

线性探测的查找和删除的处理需要额外引入对元素delete的状态标记。

enum State{EMPTY, EXIST, DELETE};

假如哈希表中存在发生哈希冲突的两个元素，这两个元素位置一前一后，状态都为EXIST。如果在前面的元素被删除了，该位置状态直接被置为EMPTY，此时再去找位于后面的元素，就会发生找不到的情况。因为寻找的终止条件就是遇到空EMPTY结束。所以，通过DELETE标记的引入，使得前面元素的删除不会影响到后面的元素。
线性探测实现起来会比较简单。但是一旦发生哈希冲突，可能会相互作用，不断扩大冲突的范围，使得找一个关键码的位置需要比较很多次，从而导致效率的下降。

二次探测

二次探测是对线性探测缺陷的一种改进，但本质上还是没有完全解决哈希冲突问题。
如果说线性探测的“下一个”位置可以用$Hash(key)+i(i>=0)$表示，那么在二次探测中，“下一个”位置的表示就是$Hash(key)+i^2$ 或者 $Hash(key)-i^2$。

负载因子

其实还可以通过扩容来降低哈希冲突发生的概率。
哈希表的负载因子 $\alpha =\frac{填入表中的元素个数}{哈希表的长度(地址个数)}$。
$\alpha$是哈希表填充程度的衡量因子。因为表长是定值，所以$\alpha$与“填入表中的元素个数”成正比。所以，$\alpha$越大，表明填入表中的元素越多，冲突概率也越大；反之，$\alpha$越小，表明填入表中的元素越少，冲突概率也越小。对于闭散列(开放定址法)，应严格限制$\alpha$在0.7 - 0.8。
闭散列最大的缺陷就是空间利用率比较低了，这同时也是哈希的缺陷。

开散列

开散列，也叫拉链法。首先同样是通过哈希函数计算关键码的地址，不同的地方是它将具有相同地址的关键码元素归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表连接起来，哈希表中存储各链表的头节点指针。
所以，开散列中每个桶存放的都是发生哈希冲突的元素。

开散列增容

开散列最好的情况是：每个哈希桶中刚好挂一个节点。然后再继续插入元素时，每一次都会发生哈希冲突。
因此，在元素个数刚好等于桶的个数，再插入时，可以给哈希表增容。

闭散列 VS 开散列

使用开散列处理哈希冲突，需要增设链接指针，似乎增加了存储开销。而闭散列需要预留大量的空闲空间来确保效率，一般表项所占空间有比指针大的多，所以使用开散列反而会比闭散列节省空间。

字符串哈希算法

如果关键码key不为整型，比如为字符串类型，又该如何映射其地址呢？
首先当然是将字符串转为整形再做运算，对于如何转换的问题可以参考BYVoid大佬的这篇关于字符串哈希算法的文章各种字符串Hash函数比较，里面给出了各种哈希算法的源码实现，并对各种算法的性能做了分数排名。

Hash函数	数据1	数据2	数据3	数据4	数据1得分	数据2得分	数据3得分	数据4得分	平均分
BKDRHash	2	0	4774	481	96.55	100	90.95	82.05	92.64
APHash	2	3	4754	493	96.55	88.46	100	51.28	86.28
DJBHash	2	2	4975	474	96.55	92.31	0	100	83.43
JSHash	1	4	4761	506	100	84.62	96.83	17.95	81.94
RSHash	1	0	4861	505	100	100	51.58	20.51	75.96
SDBMHash	3	2	4849	504	93.1	92.31	57.01	23.08	72.41
PJWHash	30	26	4878	513	0	0	43.89	0	21.95
ELFHash	30	26	4878	513	0	0	43.89	0	21.95

线性探测 & 二次探测实现

template<class K>
class Hash
{
public:// 整形直接返回size_t operator()(const K& key){return (size_t)key;}
};template<>
class Hash<string>
{
public:// string类型 -- BKDRHashsize_t operator()(const string& key){size_t hash = 0;for (char c : key){hash *= 131;hash += c;}// 装成整形返回return hash;}
};

// 闭散列
namespace CloseHash
{// 标记哈希表表项的状态enum State{EMPTY,EXIST,DELETE};// 哈希表表项的类型template<class K, class V>class HashNode{public:pair<K, V> _kv; // 要存储的元素State _state = EMPTY;};// 哈希表的实现template<class K, class V, class Hash = Hash<K>>class HashTable{public:// 插入bool Insert(const pair<K, V>& kv){// 找到了，返回false，插入失败if (Find(kv.first))return false;// 先检查扩容 -- 负载因子到0.7就扩容if (_table.size() == 0 || 10 * _size / _table.size() >= 7){size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;HashTable<K, V, Hash> newHT;newHT._table.resize(newSize);// 旧表数据映射到新表for (auto e : _table){if (e._state == EXIST){// 复用Insert()newHT.Insert(e._kv);}}// 交换_table.swap(newHT._table);}// 线性探测Hash hash;// key转整形 -> 除留余数法size_t hashi = hash(kv.first) % _table.size();while (_table[hashi]._state == EXIST){++hashi;hashi %= _table.size();}_table[hashi]._kv = kv;_table[hashi]._state = EXIST;++_size;return true;}// 删除bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){// 将状态标记成DELETE即可ret->_state = DELETE;--_size;return true;}return false;}// 查找HashData<K, V>* Find(const K& key){if (_table.empty()){return nullptr;}Hash hash;size_t start = hash(key) % _table.size();size_t hashi = start;while (_table[hashi]._state != EMPTY){if (_table[hashi]._kv.first == key && _table[hashi]._state != DELETE){return &_table[hashi];}++hashi;hashi %= _table.size();if (hashi == start){break;}}return nullptr;}private:vector<HashNode<K, V>>  _table;size_t _size = 0; // 存储有效数据的个数};
}

// 二次探测
// 只需要将Insert()中的线性探测部分替换成下面的二次探测即可
Hash hash;
size_t start = hash(kv.first) % _table.size();
size_t i = 0;
size_t hashi = start;
while (_table[hashi]._state == EXIST)
{++i;hashi = start + i * i;hashi %= _table.size();
}_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
++_size;

拉链法实现

// 开散列
//namespace OpenHash
namespace HashBucket
{// 哈希节点的类型template<class K, class V>class HashNode{public:HashNode(const pair<K, V>& kv): _kv(kv), _next(nullptr){}pair<K, V> _kv; // 要存储的元素HashNode<K, V>* _next;};template<class K, class V, class Hash = Hash<K>>class HashTable{private:typedef HashNode<K, V> Node;public:// 析构~HashTable(){for (size_t i = 0; i < _table.size(); ++i){Node* cur = _table[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_table[i] = nullptr;}}// 引用STL源码略做修改// 使哈希表每次扩容的大小为素数inline size_t __stl_next_prime(size_t n){static const size_t __stl_num_primes = 28;static const size_t __stl_prime_list[__stl_num_primes] ={53,         97,         193,       389,       769,1543,       3079,       6151,      12289,     24593,49157,      98317,      196613,    393241,    786433,1572869,    3145739,    6291469,   12582917,  25165843,50331653,   100663319,  201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};for (size_t i = 0; i < __stl_num_primes; ++i){if (__stl_prime_list[i] > n){return __stl_prime_list[i];}}return 0; // 表示出错了}bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}Hash hash;// 检查扩容if (_size == _table.size()){vector<Node*> newTable;newTable.resize(__stl_next_prime(_table.size()), nullptr);// 旧表中的节点 移动 映射到新表for (size_t i = 0; i < _table.size(); ++i){Node* cur = _table[i];while (cur){Node* next = cur->_next;// 链接到新表size_t hashi = hash(cur->_kv.first) % newTable.size();cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}_table[i] = nullptr;}// 交换_table.swap(newTable);}size_t hashi = hash(kv.first) % _table.size();// 头插Node* newnode = new Node(kv);newnode->_next = _table[hashi];_table[hashi] = newnode;++_size;return true;}bool Erase(const K& key){if (_table.empty()){return false;}Hash hash;size_t hashi = hash(key) % _table.size();Node* prev = nullptr;Node* cur = _table[hashi];while (cur){if (key == cur->_kv.first){// 头删if (prev == nullptr){_table[hashi] = cur->_next;}else // 其他位置删除{prev->_next = cur->_next;}delete cur;--_size;return true;}prev = cur;cur = cur->_next;}return false;}Node* Find(const K& key){if (_table.empty()){return nullptr;}Hash hash;size_t hashi = hash(key) % _table.size();Node* cur = _table[hashi];// 去桶里面找while (cur){if (key == cur->_kv.first){return cur;}cur = cur->_next;}return nullptr;}// 返回有效数据个数size_t Size(){return _size;}// 表的长度(地址个数)size_t TableSize(){return _table.size();}// 桶的个数size_t BucketNum(){size_t num = 0;for (size_t i = 0; i < _table.size(); ++i){if (_table[i]){++num;}}return num;}// 最大桶的节点个数size_t MaxBucket(){size_t maxLen = 0;for (size_t i = 0; i < _table.size(); ++i){size_t len = 0;Node* cur = _table[i];while (cur){++len;cur = cur->_next;}if (len > maxLen){maxLen = len;}}return maxLen;}private:vector<Node*> _table; // 哈希表存哈希节点的指针size_t _size = 0; // 存储有效数据的个数};
}