二、哈希表/哈希桶
unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构
1、哈希介绍及概念
概念：
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(N)，搜索的效率取决于搜索过程中元素的比较次数
理想的搜索方法是可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素，则复杂度为O(1)非常的高效，而计数排序用的即是这种思想
大体步骤：
插入元素：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)
示例：
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小
示图：
注：该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快，但是这样的搜索存在哈希冲突
2、哈希冲突及解决
概念：
对于不同关键字通过相同哈希哈数可能会计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞，而具有不同关键码而具有相同哈希地址的数据元素称为“同义词”
引起哈希冲突的一个原因可能是：哈希函数设计不够合理，但是好的哈希函数只能是减小冲突的概率，并非能杜绝
哈希函数设计原则：
哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中
常见哈希函数:
直接定制法–(常用)
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀 缺点：需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况
除留余数法–(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m)，将关键码转换成哈希地址
平方取中法–(了解)
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
注意：
哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突
对于像使用计数排序的方式开辟足够大的空间来用下标建立映射关系的方式具有局限性，仅适用于数据集中的正数
解决哈希冲突两种常见的方法是：
闭散列和开散列
3、闭散列/哈希表的实现
概念：
闭散列也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去
寻找下一个空位置方式：
线性探测
从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止，即newindexi=（index+i)%capacity
线性探测实现非常简单，但是一旦发生哈希冲突，所有的冲突连在一起，容易产生数据**“**堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低
二次探测
从发生的冲突的位置开始，不逐个往后找，而是以平方个位置找，即计算位置为newindexi=（index+i^2)%capacity
二次探测可以较为有效的方式减小哈希冲突的概率
闭散列实现步骤：
插入
通过哈希函数获取待插入元素在哈希表中的位置，如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素
示图：线性探测：依次往后找
删除
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索，比如删除元素4，如果直接删除掉，44查找起来可能会受影响
因此线性探测采用标记的伪删除法来删除一个元素，即每个位置都有一个表示当前状态的变量，存在数据为EXIST，不存在为EMPTY，删除为DELETE
示例：
// 哈希表每个空间给个标记 // EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除 enum State { EMPTY, EXIST, DELETE };
查找
对于查找的话先利用哈希函数获取对应的哈希映射位置，再根据具体情况而进行下一步行为
如果探测的位置状态为空，那么不必比较数据且不用再往后查找
如果探测的位置状态为存在，那么则进行比较数据值，相等则查找到了；不相等则往后根据对应的探测方式继续查找
如果探测的位置状态为删除，那么同样需要继续往后查找，直到找到对应存在的数据或者探测到状态为空的位置就不用再查找了
闭散列扩容
哈希表什么时候扩容：
哈希表扩容的实现：
使用除留余数定制法时，对于扩容后的哈希表对应的哈希函数的除数的值会发生相应的改变，导致下一次查找定制的位置可能不同，所以需要对原来的数据进行再次映射到新的位置上
哈希类型取值映射的问题：
由于哈希函数我们旋转的是除留余数法，但是只有整形才能进行取余，所以对于整形，浮点型数据我们可以直接进行强转取值，但是面对字符串类型或者其他自定义的类型的话，我们就需要进行取值特化，实现其对应类型的函数来取其中特定的数据当做取余的值
为了遍历取值，我们选择使用仿函数的方式进行实现，并将该取值类型设置为模板类型，便于特化类型的传入和使用
代码实现：
//比较仿函数-取出类型中的数值 template<class T> struct HashFunc { size_t operator()(const T& key) { return key; } }; //对string类型特化 template<> struct HashFunc<string> { size_t operator()(const string& str) { size_t hash = 0; for (int i = 0; i < str.size(); i++) hash = hash * 131 + str[i];//这种方式的冲突概率小 return hash; } };
- 闭散列代码实现：
enum State { EXIST, DELETE, EMPTY }; //哈希储存的数据类型 template<class K, class V> struct HashData { pair<K, V> _kv; State _state = EMPTY;//缺省值 }; //比较仿函数-取出类型中的数值 template<class T> struct HashFunc { size_t operator()(const T& key) { return key; } }; //对string类型特化 template<> struct HashFunc<string> { size_t operator()(const string& str) { size_t hash = 0; for (int i = 0; i < str.size(); i++) hash = hash * 131 + str[i];//这种方式的冲突概率小 return hash; } }; template<class K, class V, class Hash = HashFunc<K>> class HashTable { public: HashData<K, V>* Find(const K& key) { if (_table.size() == 0)//避免取模0 return nullptr; Hash hf; int i = 0; size_t start = hf(key) % _table.size();//取模size()，使用capacity()可能存到一定位置的空间会使得vector进行自动扩容，不便于控制 size_t index = start; while (_table[index]._state != EMPTY) { if (_table[index]._kv.first == key && _table[index]._state == EXIST)//存在且key相等 return &_table[index]; i++; index = (start + i * i) % _table.size();//二次探测+取模避免越界 } return nullptr; } bool Insert(const pair<K, V>& kv) { if (Find(kv.first))//避免冗余 return false; if (_table.size() == 0 || _size * 1.0 / _table.size() >= 0.7)//空哈希或者哈希因子达到一定程序则扩容 { size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2; HashTable<K, V, Hash> newHT; newHT._table.resize(newsize);//重新开辟足够空间 //重新构建映射 for (size_t i = 0; i < _table.size(); i++) { if (_table[i]._state == EXIST) newHT.Insert(_table[i]._kv); } _table.swap(newHT._table);//交换地址 } Hash hf; int i = 0; size_t start = hf(kv.first) % _table.size();//取模size() size_t index = start; while (_table[index]._state == EXIST) { i++; index = (start + i * i) % _table.size(); } //找到空或者删除则插入 _table[index]._kv = kv; _table[index]._state = EXIST; _size++; return true; } bool Erase(const K& key) { auto ret = Find(key); if (ret == nullptr) return false; else { ret->_state = DELETE;//伪删除 _size--; return true; } } size_t Size() const { return _size; } bool Empty() const { return _size == 0; } private: vector<HashData<K, V>> _table; size_t _size = 0;//记录有效数据个数 };
- 测试代码：
void TestHashTable1() { int a[] = { 5, 3, 100, 9999, 333, 14, 26, 34, 5 }; //int a[] = { 5, 15, 25, 35, 45 }; HashTable<int, int> ht; for (auto e : a) { ht.Insert(make_pair(e, e)); } ht.Erase(3); cout << ht.Find(3) << endl; } void TestHashTable2() { //HashTable<string, string, HashFuncString> dict; HashTable<string, string> dict; dict.Insert(make_pair("sort", "排序")); dict.Insert(make_pair("insert", "插入")); } void TestHashTable3() { HashTable<int, int> ht1; int a[] = { 4, 44, 14, 5, 2, 22, 12, 5, 8, 10, 15 }; for (auto e : a) { ht1.Insert(make_pair(e, e)); } ht1.Insert(make_pair(11, 11)); HashTable<int, int> ht2(ht1); HashTable<int, int> ht; ht = ht2; for (size_t i = 0; i < 53; ++i) { ht.Insert(make_pair(rand(), i)); } ht.Insert(make_pair(rand(), 0)); }
4、开散列/哈希桶的实现
- 概念：
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中
- 示图：
注：开散列中每个桶中放的都是发生哈希冲突的元素
开散列实现步骤：
插入
通过哈希函数进行映射到对应的位置，我们的哈希桶选择存的元素是节点地址，那么直接选择头插就好，并不用担心哈希冲突，但是在插入之前需要进行遍历桶节点查看是否存在与插入的值相同的节点，没有才进行头插
删除/查找
通过哈希函数映射到对应的位置，进行对该位置通的遍历再进行删除或查找
开散列增容
桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容
开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容
科学增容：除留余数法，最好模一个素数
代码实现：
//获取下一个质数（接近二倍开辟）,比较科学减少冲突的取扩容大小的方式 size_t GetNextPrime(size_t prime) { const int PRIMECOUNT = 28; static const size_t primeList[PRIMECOUNT] = { 53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul }; size_t i = 0; for (; i < PRIMECOUNT; ++i) { if (primeList[i] > prime) return primeList[i]; } return primeList[i]; }
- 开散列实现代码：
//哈希储存的数据类型 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 { size_t operator()(const K& key) { return key; } }; template<> struct HashFunc<string> { size_t operator()(const string& str) { size_t hash = 0; for (int i = 0; i < str.size(); i++) { hash = hash * 131 + str[i]; } return hash; } }; //获取下一个质数（接近二倍开辟）,比较科学减少冲突的取扩容大小的方式 size_t GetNextPrime(size_t prime) { const int PRIMECOUNT = 28; static const size_t primeList[PRIMECOUNT] = { 53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul }; size_t i = 0; for (; i < PRIMECOUNT; ++i) { if (primeList[i] > prime) return primeList[i]; } return primeList[i]; } template<class K, class V, class Hash=HashFunc<K>> class HashTable { typedef HashNode<K,V> Node; public: typedef HashTable<K, V, Hash> HT; HashTable() :_n(0) {} HashTable(const HT& ht)//拷贝构造 :_n(ht._n) { if (ht._table.size() == 0)//空栈 return; _table.resize(ht._table.size(), nullptr);//开辟空间并初始化 for (int i = 0; i < ht._table.size(); i++)//遍历深拷贝 { Node* cur = ht._table[i]; while (cur)//遍历桶 { Node* newnode = new Node(cur->_kv); newnode->_next = _table[i];//头插 _table[i] = newnode; cur = cur->_next; } } } HT& operator=(const HT& ht)//赋值重载（现代式） { if (&ht != this) { HT temp(ht);//拷贝构造 _table.swap(temp._table); _n = ht._n; } return *this; } ~HashTable()//析构-释放资源 { for (int i = 0; i < _table.size(); i++) { Node* cur = _table[i]; while (cur) { Node* next = cur->_next; delete cur; cur = next; } _table[i] = nullptr;//置空 } _n = 0; } bool Insert(const pair<K,V>& kv) { Hash hf; //空哈希或者负载因子达到1时进行扩容 if (_table.size() == _n) { //size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2; size_t newsize = GetNextPrime(_table.size());//获取新的扩容大小 vector<Node*> newdata; newdata.resize(newsize, nullptr);//开新的数组并扩容 //将原数组中的节点重新映射插入到新数组 for (size_t i = 0; i < _table.size(); ++i) { Node* cur = _table[i]; while (cur)//挂有节点 { Node* next = cur->_next;//记录下一个节点 size_t index = hf(cur->_kv.first) % newsize;//重新计算下标 cur->_next = newdata[index];//头插 newdata[index] = cur; cur = next;//移动 } _table[i] = nullptr;//原数组置空 } _table.swap(newdata); } size_t index = hf(kv.first) % _table.size(); Node* cur = _table[index];//遍历查看桶数据知否相等 while (cur) { if (cur->_kv.first == kv.first)//相等 return false; else cur = cur->_next; } //头插 Node* newnode = new Node(kv); newnode->_next = _table[index]; _table[index] = newnode; ++_n; return true; } Node* Find(const K& key) { //空哈希 if (_table.size() == 0) return nullptr; Hash hf; size_t index = hf(key) % _table.size(); Node* cur = _table[index]; while (cur) { if (cur->_kv.first == key) return cur; else cur = cur->_next; } return nullptr; } bool Erase(const K& key) { //空哈希 if (_table.size() == 0) return false; Hash hf; size_t index = hf(key) % _table.size(); Node* cur = _table[index]; Node* parent = nullptr; while (cur) { if (cur->_kv.first == key) { if (parent == nullptr)//头结点进行头删 _table[index] = cur->_next; else parent->_next = cur->_next; delete cur; --_n; return true; } else { parent = cur; cur = cur->_next; } } return false; } private: vector<Node*> _table; size_t _n; };
