在之前的文章中我们学习了以二叉搜索树为基础的AVL树与红黑树，在本文中我们将来继续介绍另外一种存储结构哈希表。
哈希概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素
时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即
O(log_2 N)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立
一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中插入元素的时候，根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放；搜索元素的过程也是同样的，将求得的函数值当做元素存储的位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。
这种方式被称为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)
例如：数据集合{1，7，6，4，5，9}；
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
哈希函数
哈希函数的设计原则：
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
- 哈希函数计算出来的地址能均匀分布在整个空间中
- 哈希函数应该比较简单
常见的哈希函数有：
直接定址法
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
除留余数法
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
还有折叠法、平方取中法、随机数法、数学分析法等等
哈希冲突
对于两个不同的数据元素的通过哈希函数的计算可能会得到相同的哈希地址，这种现象被称为哈希冲突或者哈希碰撞。哈希函数设计的不够合理就会引起哈希碰撞。
哈希碰撞的解决的常见方法有闭散列与开散列。
闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有
空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。我们使用线性探测的方法来进行处理：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
哈希表节点与状态定义
首先需要定义一个标识的状态，给每个数据结构体进行设计。
enum State
{EMPTY,EXIST,DELETE
};template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;
};
然后我们进行哈希表的设计：在这里使用vector作为记录数据的容器。并且需要又一个用于记录存储数据个数的变量。
插入
- 通过哈希函数获取待插入元素在哈希表中的位置；
- 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。
这里使用线性探测的方式进行插入操作，这里使用的是pair构成的键值对来进行数据的处理。首先使用哈希函数记录每个数据映射的哈希地址，从vector的哈希地址处进行线性探测，寻找状态值为空的位置放入数据，将记录数据个数的变量++，然后将地址的状态设为存在。
size_t hashi = kv.first % _tables.size();// 线性探测
size_t i = 0;
size_t index = hashi;
while (_tables[index]._state != EMPTY)
{index = hashi + i;//index = hashi + i*i; // 二次探测index %= _tables.size(); // 防止一直加出现越界的问题出现++i;
}
_tables[index]._kv = kv;
_tables[index]._state = EXIST;
++_n;
线性探测是从哈希地址处开始，每次往后探测一位。所谓的二次探测就是每次探测的位置距离起始哈希地址为i*i。此外，为了防止容器出现越界的问题，我们需要将线性探测的距离每次都与容器的size相与。还有一个需要注意的点就是在求解哈希地址的时候，在这里使用pair的first模上的是容器的size而不是capacity，因为如果我们模上的是capacity那么在vector的size比capacity小时，我们无法访问比size大比capacity小的位置，那么就可能会发生越界报错的问题。
在插入操作还有需要完善的地方，最开始vector的size是0，需要在插入开始的时候进行判断容量的大小，这里还需要说的一点就是当哈希表也需要扩容，提及到扩容，就需要说到载荷因子.
载荷因子
散列表的载荷因子α = 填入表中的数据个数 / 散列表的长度
α是散列表装满程度的标志因子.由于表长是定值，与“填入表中的元素个数”成正比，所以，α越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之，α越小，标明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子α的函数，只是不同处理冲突的方法有不同的函数.
对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7~0.8以下.超过0.8，查表时的cpu缓存不命中(缓存)失踪)按照指数曲线上升。因此，一些采用开放定址法的散列库，如JAVA的系统库限制了荷载因子为0.75，超过此值将调整大小散列表。
因此在这里我们设计载荷因子大于0.7时进行表的扩容。
// 负载因此超过0.7就进行扩容
// 这里还需注意要把size == 0考虑进判断中
if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7) // 负载因子/载荷因子 反应表存储数据量的百分比 // 整数进行相处是没有小数的，需要转换成double或者将被除数*10
{//_tables.reserve(_tables.capacity()) 未处理表为空的情况 光扩容量无法访问//size_t newsize = _tables.size() == 0 ? 10 : tables.size() * 2;//_tables.resize(newsize);// 代码重复的写法//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;//vector<HashData<K, V>> newtable;//newtable.resize(newsize);遍历旧表，重新映射到新表//for (size_t i = 0; i < _tables.size(); ++i)//{// if (_tables[i]._state == EXIST)// {// size_t hashi = _tables[i]._kv.first % newtable.size();// size_t j = 0;// size_t index = hashi;// while (newtable[index]._state == EXIST)// {// index = hashi + j;// index %= newtable.size();// ++j;// }// newtable[index]._kv = _tables[i]._kv;// newtable[index]._state = EXIST;// }//}//_tables.swap(newtable);// 构建新的HashTable来接收旧表size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;HashTable<K, V> newht;newht._tables.resize(newsize);for (auto& data : _tables){if (data._state == EXIST){newht.Insert(data._kv);}}_tables.swap(newht._tables);
}
在进行处理的时候有这么几点需要注意，首先就是因为记录数据的个数和容器的size都是整形数据相除只能得到整形，这里可以将这两个数据都变为double类型，或者将记录数据个数的变量数据量*10这样就可得到正确的结果。
在扩容的时候因为旧表与新表的size大小是不一样的，那么经过哈希函数得到的哈希地址，就有可能会发生变化，因此不能够在原来的表中进行处理，需要构建新表。在这里同样也有着多样的处理方法，首先可以构建新的vector，遍历旧表重新将数据映射到新表中，再将新的vector与旧表中的vector会进行交换。或者我们可以直接构建一个新的哈希表，遍历旧表，将旧表中的数据依次重新映射到新表中，这样的写法更加减少了代码的重复。
Find
在哈希表中不可或缺的就是查找，在插入时我们也可以先进行查找的操作，如果已经查找到数据，就可以直接进行返回。查找的过程同样是线性探测的过程，但是需要注意的就是当表中的数据状态为DELETE时也需要继续探测，直到表中的数据状态为EMPTY。这里还需要防止一种情况就是当哈希表里面的状态全是DELETE与EXIST时，这是就需要我们记录当前的哈希地址，当哈希地址和线性探测的下标再次相等的时候，就表示已经查找过一轮，说明全是存在与删除就跳出返回空。
HashData<K, V>* Find(const K& key)
{if (_tables.size() == 0){return nullptr;}size_t hashi = key % _tables.size();// 线性探测size_t i = 1;size_t index = hashi;while (_tables[index]._state != EMPTY){if (_tables[index]._state != DELETE&& key == _tables[index]._kv.first){return &_tables[index];}index = hashi + i;index %= _tables.size();++i;// 已经查找了一圈说明全是存在与删除if (hashi == index){break;}}return nullptr;
}
删除
在删除的时候我们不能随意地进行删除操作，线性探测的过程中，可能在删除的位置后面还会有相同哈希地址的关键字，这样就会影响其他元素的搜索。因此在这里需要使用一种伪删除的方式，我们设计一个标志位来对要删除的数据进行标识。
开散列
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地
址的关键码归于同一子集合，每一个子集合称为一
size_t hashi = hash(kv.first) % _tables.size();// 插入
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
个桶，各个桶中的元素通过一个单链表链
接起来，各链表的头结点存储在哈希表中。
哈希表节点
在开散列中就不需要定义状态，只需要有_next指针来作为记录下一个冲突数据位置。
template<class K, class V>
struct HashNode
{HashNode<K, V>* _next;pair<K, V> _kv;HashNode(const pair<K, V> kv):_next(nullptr),_kv(kv){}
};
插入
此时的插入操作也非常的简单就是寻找到插入的哈希地址，然后使用链表的头插的方法进行插入
size_t hashi = hash(kv.first) % _tables.size();// 插入
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
将原先表中的数据地址赋给新节点的next，并将新节点的地址存放在表中哈希地址处。同样拉链法也有着载荷因子，这里的载荷因子可以设置的比较大，比如我们将载荷因子设置为1，就表示这平均每个桶的里面都放着一个节点，如果存在着哈希冲突，只有三分之一的桶有着数据的存储，那么，载荷因子为1就表示着平均每个桶的下面都挂着所有数据中三分之一的数据量。假如有10个数据，那么就是有三个桶平均每个桶挂三个数据。
if (_n == _tables.size())
{//size_t newsize = _tables.size() == 0 ? 10 : _tables.size()*2;//HashTable<K, V> newht;//newht.resize(newsize);//for (auto cur : _tables)//{// while (cur)// {// newht.Insert(cur->_kv);// cur = cur->_next;// }//}//_tables.swap(newht._tables);size_t newsize = GetNextPrime(_tables.size());//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector<Node*> newtable(newsize, nullptr);//for (Node*& cur : _tables)//for (size_t i = 0; i < _tables.size(); ++i)//{// Node* cur = _tables[i];for (auto& cur : _tables) {while (cur){Node* next = cur->_next; // 记录下一个结点size_t hashi = hash(cur->_kv.first) % newtable.size();// 插入cur->_next = newtable[hashi]; // 桶的第一个节点是存储在桶中的newtable[hashi] = cur;cur = next;}}_tables.swap(newtable);
}
这里进行扩容也有着不同的写法，首先就是，可以与我们在闭散列中的写法一致，构建一个新的哈希表，然后遍历旧表将数据重新链接到新表中。还有一种更加优化的方法，如果采用上述的写法，桶的空间需要释放，每个桶中的链表的空间也需要释放，新表中又要重新的建立这样会浪费资源，因为每个桶中的节点，都是可以被复用的，我们就可以将旧表中的结点直接链接到新表中。先记录下一个结点的位置，然后将当前的结点链接到新表中，如果下一个结点为空，就到下一个桶中进行继续操作，最后将新表与旧表进行交换。
删除
拉链法的删除就会有一些复杂，这里需要有一个前置指针来记录上一个的位置，在进行删除之后将若是桶中还是剩余的数据就进行链接。首先需要找到数据存储在哪一个桶中，其次需要进行判断这个数据的结点位置是在头结点上，还是在桶的链表上，然后进行不同的处理。
bool Erase(const K& key)
{Hash hash;size_t hashi = hash(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;
}
字符串的哈希算法
这里还有一个很重要的问题就是，之前我们编写代码是都是假设的整形的数据，这些数据是可以进行取模操作的，但当我们要存储字符串甚至是自定义类型的数据结构的时候就会产生错误。因此我我们要想办法让字符串或者其余的数据结构能够进行取模，这样才能够进行哈希表的映射。
我们很容易就可以想到字符串要取模，就可以取字符串的首元素的整数数据的大小，然后我们就可以编写仿函数进行尝试：
struct HashStr
{size_t operator()(const string& s){return s[0];}
};
将其放入哈希表中，确实能够解决字符串不能存储的问题，下面紧接着又会出现下一个问题就是字符串abcd和aadd这两个字符串明显是不同的，但使用我们的方法进行哈希函数的映射，这两个数据就会产生冲突，明显是存在着问题的。因此这里就需要引入字符串的哈希算法，这里使用BKDRHash算法，同时字符串使用的频率会会比较高，我们可以直接使用模板的特化将字符串的仿函数编写在哈希表中，这样就可以大概率的不会引起冲突。
template<class K>
struct HashFunc
{size_t operator()(const K& key){return key;}
};// 模板的特化
template<>
struct HashFunc<string>
{size_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;hash *= 31;}return hash;}
};
具体的一些算法可以参考这篇博客https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html
除留余数法，最好模一个素数
在进行扩容的时候我们可以将空间的大小设置为素数，这样如果给我们随机的数列放到哈希表中，如何保障它能尽量减少冲突呢，就需要模的因子最少，而因子最少的就是素数了，这就是为什么哈希表取模为素数的原因了。
size_t GetNextPrime(size_t prime)
{// SGIstatic const int __stl_num_primes = 28;static const unsigned long __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};size_t i = 0;for (; i < __stl_num_primes; ++i){if (__stl_prime_list[i] > prime)return __stl_prime_list[i];}return __stl_prime_list[i];
}
每次需要扩容的时候就可以将新的空间大小通过这个函数进行获取。
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
