从C语言到C++_30(哈希)闭散列和开散列(哈希桶)的实现（上）：https://developer.aliyun.com/article/1522312
2.1.2 闭散列二次探测（了解）
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，
因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题。
- 线性探测：start + i，i = 0，1，2，3…
- 二次探测：start + i^2，i = 0，1，2，3…
使用二次探测，查找时也是按照二次探测的方式去查找。
研究表明：
当表的长度为质数且表装载因子不超过0.5时，新的表项一定能够插入，
而且任何一个位置都不会被探查两次。
因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子不超过0.5，如果超出必须考虑增容。
无论是线性探测还是二次探测，闭散列方式的最大缺陷就是空间利用率较低。
所以就引出了下面开散列（哈希桶）的概念。
2.2 开散列(哈希桶)概念和代码
开散列：又叫拉链法(链地址法)，首先对key值集合用哈希函数计算映射下标，
具有相同下标的key值归于同一子集合，每一个子集合称为一个桶，
各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
如上图所示，此时的哈希表中存放的是一个单链表的头指针。
- 不同的数据，根据哈希函数算出的映射位置发生哈希碰撞时，这些碰撞的数据会挂在哈希表对应位置指向的单链表中。这些单链表被形象称为桶。
- 每个桶中放的都是发生哈希冲突的元素。
- 当有新数据插入时，进行头插。
如上图中所示，7，27，57，根据哈希函数都映射到哈希表下标为7的位置，这几个数据按照头插的顺序以单链表的形式挂在哈希表下标为7的位置。
新插入的数据如果尾插的话，在找单链表的尾部时，会有效率损失，由于没有排序要求，所以头插是效率最高的。
开散列的方法，通常被称为哈希桶，使用的也最广泛，能够解决闭散列中空间利用率不高的问题。
哈希桶会不会出现时间复杂度为O（N）的情况？极端情况是会的，但是概率极低，像前面十个空间，扩容了还会把数据分散，开了很多空间的时候，几乎不会出现极端情况，有些库还有一些备案，比如Java库：挂的桶大于8的话（这里也表明挂的桶基本是很少的），就改成挂红黑树。
基于以上原因，哈希桶和快排一样，可以不看最坏时间复杂度，而看平均复杂度：O（1）。
数据类型定义和框架（这里用HashBucket命名空间包起来，把前面的用CloseHash包起来）
namespace HashBucket { template<class K, class V> struct HashNode { pair<K, V> _kv; HashNode* _next; // 不用存状态栏了，存下一个结点指针 }; template<class K> struct HashFunc // 可以把闭散列的HashFunc放在外面直接用，但是这就不放出来了 { size_t operator()(const K& key) { return (size_t)key; // 负数，浮点数，指针等可以直接转，string不行 } }; template<> struct HashFunc<string> // 上面的特化 { size_t operator()(const string& key) { size_t val = 0; for (const auto& ch : key) { val *= 131; val += ch; } return val; } }; template<class K, class V, class Hash = HashFunc<K>> class HashTable { public: typedef HashData<K, V> Node; protected: vector<Node*> _tables; // 指针数组 size_t _size; }; }
采用哈希桶的方式来解决哈希碰撞时，哈希表中存放的数据是单链表的头节点，
链表节点中有键值对，还有下一个节点的指针。仍然使用闭散列中转换整形的仿函数。
插入：
插入首先要去重（用查找），然后检查是否要扩容，最后再插入
先写查找：
Node* Find(const K& key) { if (_tables.size() == 0) { return nullptr; } 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; }
根据哈希函数的映射关系，直接找到key值哈希表中的存放位置。
然后在该位置挂的桶中寻找key值。
哈希桶结构，查找的效率高就高在这里，可以直接根据key值定位哈希表，时间复杂度是O(1)。
现在写插入，哈希桶的方式中也会扩容，否则桶就会越挂越长，违背了哈希桶设计的初衷。
一般情况下，当哈希表的负载因子等于1的时候，发生扩容。
当负载因子等于1时，也就是数据个数和哈希表大小相等的时候进行扩容。
扩容和闭散列类似，将旧的哈希表中的数据插入到新哈希表中，
复用Insert函数，然后旧表被释放，新表留下来。
但是这种方式不是很好，有很大的开销，效率有所损失：
在将旧表中的数据插入新表的时候，每插入一个，新表就需要new一个节点，
旧表中的所有节点都会被new一遍。然后将旧表中的所有节点再释放，
这里做了没必要的工作。相同的一个节点，会先在新表中new一个，再释放旧表的。
新表中完全可以不再new新的节点，直接使用旧表中的节点。
旧表中可以直接复用的节点是：改变了哈希表容量以后，映射关系不变的节点。
比如节点27，哈希表的容量从10变成20，但是映射后的下标仍然是7，这样的节点就可以复用。
那些映射关系变了的节点就不可以直接复用了，需要改变所在桶的位置。
如节点18，哈希表的容量从10变成20，映射后的下标从8变成18，此时就需要改变18所在的桶了。
bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) { return false; } Hash hs; if (_size == _tables.size()) // 负载因子到1就扩容 { size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2; vector<Node*> newTables; newTables.resize(newSize, 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; ++_size; }
写完插入和查找，现在写写删除：
这里的删除就类似链表的删除，哈希表挂的桶是单链表，只指定要删除节点是无法进行删除的，
必须指定前一个节点，否则无法再链接。所以不能直接复用Find删除：
bool Erase(const K& key) { if (_tables.size() == 0) // 防止除零错误 { return false; } Hash hs; size_t hashi = hs(key) % _tables.size(); Node* cur = _tables[hashi]; Node* prev = nullptr; while (cur) { if (cur->_kv.first == key) { if (prev == nullptr) // 头插，先把指针数组存的指针指向cur的下一个 { _tables[hashi] = cur->_next; } else // 中间删 { prev->_next = cur->_next; } delete cur; // 统一在这delete return true; } prev = cur; // 往后走 cur = cur->_next; } return false; // 没找到 }
根据哈希函数的映射关系，定位到对应哈希表中挂的某个桶上。
如果key是单链表的头节点，直接让它的下一个节点当头节点就可以。
如果key不是头节点，则在删除的时候，需要prev指针的辅助来链接单链表。
由于哈希映射的存在，在寻找key时的时间复杂度同样是O(1)，所以删除的效率也很高。
写到这并且想测试，我们应该意识到写个析构函数了，哈希桶必须有析构函数，闭散列的方式，
默认生成的析构函数就能满足要求，但是哈希桶不可以。如果只使用默认生成的析构函数，
在哈希桶销毁的时候，默认的析构函数会调用vector的析构函数。
vector的析构函数只会释放vector的本身，而不会释放vector上挂着的桶。
所以需要显示定义析构函数，在析构函数中将vector挂的桶进行释放。
在释放的时候，需要将单链表的下一个节点记录下来，再释放当前节点，
否则会找不到下一个节点。
~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; } }
测试：
void TestHash3() // 哈希桶测试统计次数的可以用TestHash2改下命名空间 { int arr[] = {1, 11, 4, 15, 26, 7, 44, 55, 99, 78}; HashBucket::HashTable<int, int> ht; for (const auto& e : arr) { ht.Insert(make_pair(e, e)); } ht.Insert(make_pair(22, 22)); // 刚好扩容 }
2.2.1 除留余数法获取素数
有研究表面，哈希表的大小最好是一个素数，这样的话能够提供哈希结构的效率，
那么如何快速获取一个类似两倍关系的素数呢？
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 -1; // 不会走到这，随便返回一个值 }
上面代码是STL库中获取素数的方式。
将素数放在一个数组中，两个素数之间的关系接近二倍，但是又要符合是一个素数。
当需要进行扩容时，就从数组中寻找一个比当前素数大的素数作为新的容量。
上面数组中虽然只有28个素数，但是完全够用了，最大的素数意味着哈希表有4GB个数据，每个数据是一个指针(32位)，也就是4B大小，这样来看已经有16GB的数据量了，再考虑上挂的桶中的数据，数据量是非常大，正常情况下根本没有这么大量的数据。
如果不信讲的复杂度为O（1）的那个，因为这取决于最大桶的长度，
这里可以写几个获取桶个数，最大桶个数，数据个数，表长度来验证验证：
size_t Size() // 存的数据个数 { return _size; } size_t TablesSize() // 表的长度 { return _tables.size(); } size_t BucketNum() // 桶的个数 { size_t num = 0; for (size_t i = 0; i < _tables.size(); ++i) { if (_tables[i]) // 如果不是空就有桶 { ++num; } } return num; } size_t MaxBucketLenth() // 最长桶的长度 { size_t maxLen = 0; for (size_t i = 0; i < _tables.size(); ++i) { size_t len = 0; Node* cur = _tables[i]; while (cur) { ++len; cur = cur->_next; } if (len > maxLen) { maxLen = len; } } return maxLen; }
2.2.2 开散列(哈希桶)完整代码
HashTable.h：（把上面写的闭散列CloseHash命名空间的删了）
#pragma once #include <iostream> #include <vector> using namespace std; namespace HashBucket { template<class K, class V> struct HashNode { pair<K, V> _kv; HashNode* _next; // 不用存状态栏了，存下一个结点指针 HashNode(const pair<K, V>& kv) :_kv(kv) , _next(nullptr) {} }; template<class K> struct HashFunc // 可以把闭散列的HashFunc放在外面直接用，但是这就不放了 { size_t operator()(const K& key) { return (size_t)key; // 负数，浮点数，指针等可以直接转，string不行 } }; template<> struct HashFunc<string> // 上面的特化 { size_t operator()(const string& key) { size_t val = 0; for (const auto& ch : key) { val *= 131; val += ch; } return val; } }; template<class K, class V, class Hash = HashFunc<K>> class HashTable { public: typedef HashNode<K, V> Node; ~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; } } Node* Find(const K& key) { if (_tables.size() == 0) { return nullptr; } 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; } 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 -1; // 不会走到这，随便返回一个值 } bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) { return false; } Hash hs; if (_size == _tables.size()) // 负载因子到1就扩容 { //size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2; vector<Node*> newTables; //newTables.resize(newSize, nullptr); newTables.resize(__stl_next_prime(_tables.size()), 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; ++_size; return true; } bool Erase(const K& key) { if (_tables.size() == 0) // 防止除零错误 { return false; } Hash hs; size_t hashi = hs(key) % _tables.size(); Node* cur = _tables[hashi]; Node* prev = nullptr; while (cur) { if (cur->_kv.first == key) { if (prev == nullptr) // 头插，先把指针数组存的指针指向cur的下一个 { _tables[hashi] = cur->_next; } else // 中间删 { prev->_next = cur->_next; } delete cur; // 统一在这delete return true; } prev = cur; // 往后走 cur = cur->_next; } return false; // 没找到 } size_t Size() // 存的数据个数 { return _size; } size_t TablesSize() // 表的长度 { return _tables.size(); } size_t BucketNum() // 桶的个数 { size_t num = 0; for (size_t i = 0; i < _tables.size(); ++i) { if (_tables[i]) // 如果不是空就有桶 { ++num; } } return num; } size_t MaxBucketLenth() // 最长桶的长度 { size_t maxLen = 0; for (size_t i = 0; i < _tables.size(); ++i) { size_t len = 0; Node* cur = _tables[i]; while (cur) { ++len; cur = cur->_next; } if (len > maxLen) { maxLen = len; } } return maxLen; } protected: vector<Node*> _tables; // 指针数组 size_t _size; }; }
Test.cpp：
#include "HashTable.h" void TestHash1() { int arr[] = { 1, 11, 4, 15, 26, 7, 44 }; // 在加一个数据就会扩容 CloseHash::HashTable<int, int> ht; for (const auto& e : arr) { ht.Insert(make_pair(e, e)); } ht.Print(); ht.Erase(4); cout << ht.Find(44) << endl; // ht.Find(44)->_kv.first就能取出数据 cout << ht.Find(100) << endl; // 不过要先判断是否为空，否则会崩 cout << ht.Find(4) << endl; ht.Print(); ht.Insert(make_pair(-2, -2)); ht.Print(); cout << ht.Find(-2) << endl; } void TestHash2() { string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; //CloseHash::HashTable<string, int> countHT; HashBucket::HashTable<string, int> countHT; for (const auto& str : arr) { auto ptr = countHT.Find(str); if (ptr) { ptr->_kv.second++; } else { countHT.Insert(make_pair(str, 1)); } } } void TestHash3() // 哈希桶测试统计次数的可以用TestHash2改下命名空间 { int arr[] = {1, 11, 4, 15, 26, 7, 44, 55, 99, 78}; HashBucket::HashTable<int, int> ht; for (const auto& e : arr) { ht.Insert(make_pair(e, e)); } ht.Insert(make_pair(22, 22)); } void TestHash4() { int n = 10000; vector<int> v; v.reserve(n); srand(time(0)); for (int i = 0; i < n; ++i) { //v.push_back(i); v.push_back(rand() + i); // 重复少 //v.push_back(rand()); // 重复多 } size_t begin1 = clock(); HashBucket::HashTable<int, int> ht; for (auto e : v) { ht.Insert(make_pair(e, e)); } size_t end1 = clock(); cout << "数据个数:" << ht.Size() << endl; cout << "表的长度:" << ht.TablesSize() << endl; cout << "桶的个数:" << ht.BucketNum() << endl; cout << "平均每个桶的长度:" << (double)ht.Size() / (double)ht.BucketNum() << endl; cout << "最长的桶的长度:" << ht.MaxBucketLenth() << endl; cout << "负载因子:" << (double)ht.Size() / (double)ht.TablesSize() << endl; } int main() { TestHash2(); TestHash3(); TestHash4(); return 0; }
没测TestHash4的：
测TestHash4的：
这是测了几次的结果：（随着负载因子的变大，桶最长也就2或3，因为桶的个数太多了）
多测了几个数量级的n，发现最长的桶的长度也就4：
从C语言到C++_30(哈希)闭散列和开散列(哈希桶)的实现（下）：https://developer.aliyun.com/article/1522315?spm=a2c6h.13148508.setting.17.50c04f0emsc6o6
