【数据结构】哈希——闭散列/开散列模拟实现(C++)

unordered_map/unordered_map和map/set的区别

哈希的实现：

哈希的原理

直接定址法

除留余数法

闭散列：

线性探测

模拟实现：

哈希表的数据

哈希表结构

Insert

Find

Erase

二次探测

开散列：

模拟实现：

哈希表的数据

哈希表结构

Insert

Find

Erase

析构函数

优化

Hash仿函数实现

针对于string的仿函数

针对仿函数进行“模板特化”优化

unordered_map/unordered_set的使用和map/set唯一区别就是前者是无序的，而后者是有序的(unordered直译过来就是无序)，这里就不详细说明了

unordered_map/unordered_map和map/set的区别

1.底层区别

在学过map/set后，我们知道它是由红黑树实现的，而unordered_map/unordered_set的底层是由哈希表实现的

2.效率区别

红黑树的增删查改效率为O(logN)，哈希表的增删查改效率为O(1)，因此unordered_map/unordered_set的效率比map/set要高，这也是它即使在C++11才出现，但得到广泛应用的原因

3.遍历区别

map/set的遍历是有序的，unordered_map/unordered_set的遍历是无序的

4.迭代器区别

map/set的迭代器是双向迭代器，而unordered_map/unordered_set的迭代器是单向迭代器

下面代码用于测试两者效率区别

#include <iostream>
#include <unordered_map>
#include <map>
#include <vector>
using namespace std;int main()
{int n = 1000000;//一百万数据vector<int> v;v.reserve(n);srand(time(0));for (size_t i = 0; i < n; i++){v.push_back(rand());}unordered_map<int, int> um;size_t begin1 = clock();for (auto e : v)um.insert(make_pair(e, e));size_t end1 = clock();map<int, int> m;size_t begin2 = clock();for (auto e : v)m.insert(make_pair(e, e));size_t end2 = clock();cout << "insert:" << endl;cout << "unordered_map: " << end1 - begin1 << "ms" << endl; cout << "map: " << end2 - begin2 << "ms" << endl;size_t begin3 = clock();for (auto e : v)um.find(e);size_t end3 = clock();size_t begin4 = clock();for (auto e : v)m.find(e);size_t end4 = clock();cout << "find:" << endl;cout << "unordered_map: " << end3 - begin3 << "ms" << endl;cout << "map: " << end4 - begin4 << "ms" << endl;size_t begin5 = clock();for (auto e : v)um.erase(e);size_t end5 = clock();size_t begin6 = clock();for (auto e : v)m.erase(e);size_t end6 = clock();cout << "erase" << endl;cout << "unordered_map: " << end5 - begin5 << "ms" << endl;cout << "map: " << end6 - begin6 << "ms" << endl;return 0;
}

VS下Release/Win32环境下三次输出：(仅供参考)

哈希的实现：

哈希的原理

直接定址法

在计数排序中，如果现在需要将4,7,1,8存起来，可以开辟10个int（严格来说是最大数-最小数个空间）的内存，遍历到x时，就将arr[x]++；这就是最普通的哈希函数——直接定址法，映射只跟关键字直接或间接有关系

除留余数法

但如果要将4,7,1,8,500000存起来，再用直接定址法就太浪费空间了，这时可以用除留余数法：我们还是开辟10个int空间的内存，将每个数都%空间大小后再存进去

然而这样有一个很明显的问题——如果此时我再在1,4,7,8中插入一个数据呢？

例如此时我要插入14,14%10==4，还是要插入到4的位置，可这时4的位置已经有数据了，这就叫哈希冲突——不同的值可能会映射到相同的位置上去(直接定址法没有哈希冲突)，哈希最大的问题的问题就是如何解决哈希冲突。解决哈希冲突有两种办法：闭散列和开散列，本篇中详细讲开散列

闭散列：

闭散列又叫作开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有
空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。

开放定址法又分为线性探测和二次探测

线性探测

还是拿上面的例子，此时去4的位置找，发现该位置有值了，因此依次向后探测，直到寻找到下一个空为止即可

查找时也一样，先去对应的位置找，如果该值不是，再依次向后探测，直到为空或找到为止

如果要找24

由此可以发现，影响哈希表效率的是哈希冲突，哈希冲突越多，效率越低

但这样就会有一个问题：如果此时我将4删掉，再去找14呢？

因此，对于哈希表的每个数据来说，都有一个状态(state)，来定义该数据状态是空(empty)，存在(exist)，删除(DELETE)

前面说过，发生哈希冲突时，在哈希表没满的情况下，一定有另外一个空位置可以插入，那哈希表要是满了呢？

哈希表是永远不会满的，因为它的扩容不是在满时才扩容，这里需要引出一个概念——负载因子

负载因子是表中有效数据个数 / 表的容量，若负载因子大于某个值，就需要扩容

在闭散列中，一般负载因子为0.7(即表中有70%数据)时就需要扩容

怎么扩容呢？

扩容后，表的大小发生了变化，因为映射关系是表数据个数 / 表大小得来的，所以映射关系也会发生变化，如果只是将原表中的数据拷贝到新表，再找数据时会映射关系会对不上

因此，开辟新表后，需要将旧表的数据再重新映射(插入)到新表

并且重新映射后，原来的哈希冲突也会消失一部分(例如上图的14和37)

模拟实现：

哈希表的数据

哈希表每个数据除了存对于类型的值(K或KV)之外，还需要存当前数据的状态(空，存在，删除)

这里的状态编主是用的枚举实现

enum State//哈希表中数据的状态
{EMPTY,//空EXIST,//存在DELETE//删除
};template<class T>
struct HashData
{T _data;State _state;
};

哈希表结构

模板参数和模拟实现map/set时一样，K为key，T为key或pair，KOfT是用来在T中取出key的仿函数

哈希表的存储结构这里用的是vector，vector中的每个数据都有一个值和一个状态

除此之外还需要一个_num来表示当前有效数据个数，因为表的每个数据在插入之前就必须有一个空状态，所以在插入数据之前，就已经_table.resize(n)了，此时_table._state的值会被默认为0，即EMPTY(空)

template<class K, class T, class KOfT>//KOfT是用来提取出T类型中Key的仿函数
class HashTable//哈希表
{typedef HashData<T> HashData;
private:vector<HashData> _table;size_t _num = 0;//哈希表中有效数据的个数
};

Insert

首先需要一个KOfT的对象，来返回T(可能是K也可能是pair)对象中的Key，取出要插入的值的映射，并开始寻找

	bool Insert(const T& data){KOfT koft;//用来提取出T类型中Key的仿函数size_t index = koft(data) % _table.size();//将原值除留余数法while (_table[index]._state == EXIST)//如果该位置已经满员了，就继续向后胎侧{if (koft(_table[index]._data) == koft(data))//如果值相同，则插入失败return false;index++;if (index == _table.size())//如果遍历到最后了，就回到0继续遍历index = 0;}_table[index]._data = data;_table[index]._state = EXIST;_num++;//这里用的是线性探测return true;}

但这样还不行，还需要判断扩容的情况，由于哈希表刚开始时size为0，因此负载因子>=0.7和容量为0都是扩容的条件

bool Insert(const T& data)
{//负载因子 = 表中数据 / 表的大小 衡量哈希表满的程度//表越接近满，插入数据越容易冲突，冲突越多，效率越低//哈希表并不是满了才增容，开放定址法中，一般负载因子到了0.7左右就开始增容if (_table.size() == 0 || _num * 10 / _table.size() >= 7)//等同于num / table.size() >= 0.7{//扩容HashTable<K,T,KOfT> newht;//直接定义一个新哈希表，这样可以直接复用Insertsize_t newsize = _table.size() ? _table.size() * 2 : 10;//若表容量为0就扩容到10，否则是原表的二倍newht._table.resize(newsize);//这样是为了初始化状态为空(EMPTY为0)for (const auto& e : _table)//将旧表数据映射到新表if (e._state == EXIST)newht.Insert(e._data);_table.swap(newht._table);//交换旧表与新表，旧表将会在出作用域时自动销毁}KOfT koft;//用来提取出T类型中Key的仿函数size_t index = koft(data) % _table.size();//将原值除留余数法while (_table[index]._state == EXIST)//如果该位置已经满员了，就继续向后胎侧{if (koft(_table[index]._data) == koft(data))//如果值相同，则插入失败return false;index++;if (index == _table.size())//如果遍历到最后了，就回到0继续遍历index = 0;}_table[index]._data = data;_table[index]._state = EXIST;_num++;return true;
}

这里是用的现代写法，即新建一个哈希表来当做新表，这样可以服用哈希表的insert来映射旧表数据(此时的新表大小已经被resize过了，因此不会再扩容而死循环)，最后与新表与旧表交换，交换后，newht._table是旧表，就会在出作用域后自动销毁(调用析构函数)

Find

取出要找的数据的映射后，依次向后探测寻找，直到状态为空

HashData* Find(const K& key)
{KOfT koft;//用来取出T类型的Keysize_t index = key % _table.size();//将key除留余数法while (_table[index]._state != EMPTY)//只要状态不为空就继续向后探测{if (koft(_table[index]._data) == key)//找到该keyif (_table[index]._state == EXIST)//如果状态还是存在，就返回该值地址return &_table[index];else//如果状态是删除，后面也不可能再有了，返回空return nullptr;index++;//线性探测if (index == _table.size())//如果走到最后了，就继续从头开始找index = 0;}return nullptr;
}

Erase

删除时不需要动表中的_data，只需要将状态置DELETE即可

bool Erase(const K& key)
{HashData* hd = Find(key);//复用Find函数，找到该keyif (hd)//找到{hd->_state = DELETE;_num--;return true;}else//没找到{return false;}
}

二次探测

线性探测的思路是“我的位置被占了，我就挨着往后去占别人的位置”，这样可能会导致一片一片的冲突，所有冲突都挤到一块，引发洪水效应

二次探测就是为了优化这个问题而出现的

线性探测中，每次往后移i位，而二次探测是每次往后移i^2位，即第一次往后移1位，第二次往后移4位(2^2)，第三次往后移9位(3^2)

这样插入的数据，即使有哈希冲突，也会更分散一点

将线性探测改为二次探测也很简单

#pragma once
#include <vector>enum State//哈希表中数据的状态
{EMPTY,//空EXIST,//存在DELETE//删除
};template<class T>
struct HashData
{T _data;State _state;
};//unordered_set<K>    ->HashTable<K,K>
//unordered_map<K,V>  ->HashTable<K,pair<K,V>>
template<class K, class T, class KOfT>//KOfT是用来提取出T类型中Key的仿函数
class HashTable//哈希表
{typedef HashData<T> HashData;
public:bool Insert(const T& data){//负载因子 = 表中数据 / 表的大小 衡量哈希表满的程度//表越接近满，插入数据越容易冲突，冲突越多，效率越低//哈希表并不是满了才增容，开放定址法中，一般负载因子到了0.7左右就开始增容if (_table.size() == 0 || _num * 10 / _table.size() >= 7)//等同于num / table.size() >= 0.7{//扩容HashTable<K,T,KOfT> newht;//直接定义一个新哈希表，这样可以直接复用Insertsize_t newsize = _table.size() ? _table.size() * 2 : 10;//若表容量为0就扩容到10，否则是原表的二倍newht._table.resize(newsize);//这样是为了初始化状态为空(EMPTY为0)for (const auto& e : _table)//将旧表数据映射到新表if (e._state == EXIST)newht.Insert(e._data);_table.swap(newht._table);//交换旧表与新表，旧表将会在出作用域时自动销毁}KOfT koft;//用来提取出T类型中Key的仿函数//线性探测//size_t index = koft(data) % _table.size();//将原值除留余数法//while (_table[index]._state == EXIST)//如果该位置已经满员了，就继续向后胎侧//{//	if (koft(_table[index]._data) == koft(data))//如果值相同，则插入失败//		return false;//	index++;//线性探测//	if (index == _table.size())//如果遍历到最后了，就回到0继续遍历//		index = 0;//}//二次探测size_t start = koft(data) % _table.size();//将原值除留余数法size_t index = start;int i = 1;while (_table[index]._state == EXIST)//如果该位置已经满员了，就继续向后胎侧{if (koft(_table[index]._data) == koft(data))//如果值相同，则插入失败return false;index = start + i * i;//二次探测i++;index %= _table.size();if (index == _table.size())//如果遍历到最后了，就回到0继续遍历index = 0;}_table[index]._data = data;_table[index]._state = EXIST;_num++;return true;}HashData* Find(const K& key){KOfT koft;//用来取出T类型的Key//线性探测//size_t index = key % _table.size();//将key除留余数法//while (_table[index]._state != EMPTY)//只要状态不为空就继续向后探测//{//	if (koft(_table[index]._data) == key)//找到该key//		if (_table[index]._state == EXIST)//如果状态还是存在，就返回该值地址//			return &_table[index];//		else//如果状态是删除，后面也不可能再有了，返回空//			return nullptr;//	index++;//	if (index == _table.size())//如果走到最后了，就继续从头开始找//		index = 0;//}//二次探测size_t start = key % _table.size();//将key除留余数法size_t index = start;int i = 1;while (_table[index]._state != EMPTY)//只要状态不为空就继续向后探测{if (koft(_table[index]._data) == key)//找到该keyif (_table[index]._state == EXIST)//如果状态还是存在，就返回该值地址return &_table[index];else//如果状态是删除，后面也不可能再有了，返回空return nullptr;index = start + i * i;//二次探测i++;if (index == _table.size())//如果走到最后了，就继续从头开始找index = 0;}return nullptr;}bool Erase(const K& key){HashData* hd = Find(key);//复用Find函数，找到该keyif (hd)//找到{hd->_state = DELETE;_num--;return true;}else//没找到{return false;}}private:vector<HashData> _table;size_t _num++;//当前有效数据个数
};template<class K>
struct KeyOfSet
{const K& operator()(const K& key){return key;}
};

开散列：

经过了解闭散列，我们可以看到闭散列不是一种好的解决方式，因为他是一种“我的位置被占了，我就去抢别人位置”的思路，也就是说他它的哈希冲突会互相影响，整体效率都会偏低，即使是二次探测也只是基于这个思路优化出来的，解决不了本质问题

因此就诞生出了开散列，又叫哈希桶

如下图所示，这就是哈希桶在插入arr数组中元素的过程

可以看到，在发生哈希冲突时，它会把元素继续挂在已有元素的下面，由于这样每个数组中的元素都可以被视作一个桶，故得名哈希桶

哈希桶在解决哈希冲突时，不会去占用别的位置，而是自力更生解决，因此效率也会比闭散列高

模拟实现：

哈希表的数据

哈希桶中的数据就不需要存状态了，取而代之的是一个单链表指针，为了可以将发生哈希冲突的数据挂在该桶中

template<class T>
struct HashNode
{T _data;//K或KVHashNode* _next;//单链表HashNode(const T& data)//默认构造，为下面的new HashNode而准备:_data(data), _next(nullptr){ }
};

哈希表结构

数组中每个元素都是一个单链表，这就是哈希桶的结构

	template<class K,class T,class KOfT>//T可能是K或pair，KOfT是为了从T中取出key的仿函数class HashTable{typedef HashNode<T> Node;private:vector<Node*> _table;//哈希表(指针数组)size_t _num = 0;//表中有效数据个数};
}

Insert

即使是哈希桶也需要增容，否则当一个桶中挂的元素过多时，效率也会变低。哈希桶一般负载因子到1时扩容

扩容时和闭散列一样，将旧表中的数据重新映射到新表，不过因为编主写的扩容没有再开辟节点，直接用的旧表的节点，所以每映射完一个桶，都要将旧表对应位置的桶置空，这是为了防止交换后旧表在出作用域时调用析构函数将节点都析构掉

bool Insert(const T& data)
{KOfT koft;//用于取出T类型的Keyif (_table.size() == _num)//负载因子到1时扩容{//1.开2倍大小空间(不一定是2倍)//2.遍历旧表数据，重新计算在新表中位置//3.释放旧表vector<Node*> newtable;size_t newsize = _table.size() ? _table.size() * 2 : 10;newtable.resize(newsize);for (auto& cur : _table){//将旧表中的节点取下来重新计算在新表中的位置，并插入进去Node* head = cur;while (head){Node* next = head->_next;size_t index = HashFunc(koft(head->_data)) % newtable.size();//头插进桶中head->_next = newtable[index];newtable[index] = head;head = next;}cur = nullptr;//将旧表该位置置空，否则最后析构旧表时就将节点都析构了}_table.swap(newtable);//旧表在出作用域后自动销毁}size_t index = koft(data) % _table.size();//除留余数法取出映射//先查找值是否重复Node* cur = _table[index];while (cur){if (koft(cur->_data) == koft(data))//如果是重复值，插入失败return false;elsecur = cur->_next;}Node* newnode = new Node(data);//开辟新空间//头插到对应桶中(尾插也可以)newnode->_next = _table[index];_table[index] = newnode;_num++;return true;
}

可以看到这里编主使用的是头插来解决哈希冲突，其实头插尾插都差不多，但由于尾插还要找到最后一个元素，所以头插效率相对更高(这是单链表，如果是双向链表尾插头插效率都一样)

Find

只需要在找到对应的桶后，到该桶去遍历寻找数据即可

Node* Find(const K& key)
{KOFT koft;//用于取出T类型的keysize_t index = key % _table.size();//算出映射//去该映射桶中找Node* cur = _table[index];while (cur){if (koft(cur->_data) == key)return cur;elsecur = cur->_next;}return nullptr;//找不到返回空
}

Erase

和给单链表删除数据一样，设要删除的节点为cur，cur的上一个为prev，那就是prev->_next = cur->next，即将删除节点的下一个赋值给上一个的下一个

但如果删的是头结点，即prev为空时，要将该桶的头结点指向cur->_next

bool Erase(const K& key)
{KOfT koft;//用于取出T类型的keysize_t index = key % _table.size();//算出映射Node* prev = nullptr;Node* cur = _table[index];while (cur){if (koft(cur->_data) == key)//如果找到{if (prev == nullptr)//此时要删除的就是该桶的头结点_table[index] = cur->_next;elseprev->_next = cur->_next;delete cur;_num--;return true;}else//继续向下找{prev = cur;cur = cur->_next;}}return false;
}

析构函数

无非就是把数据都释放掉，这里不再多讲

~HashTable()
{clear();
}void clear()
{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;}
}

优化

如果用目前的开散列去插入数据，若key为int或char还好说，但如果为string等非数字类型(自定义类型)

void Test_Hash()
{HashTable<string,string, KeyOfSet<string>> ht;ht.Insert("APEX");ht.Insert("Zelda");ht.Insert("Link");
}

会有如下报错：

这是因为此时的Key是string类型，除留余数法时，会将string当被除数，而string无法被除

因此我们需要给哈希表再加一个模板参数——用来将非数字类型转换成整型的仿函数

template<class K,class T,class KOfT,class Hash>//T可能是K或pair，KOfT是为了从T中取出key的仿函数
class HashTable
{}

此事在STL中也有记载

那么之前所用到模除取余的地方都需要修改，不如专门写一个函数(接口)，来完成将非数字类型转换成整型的任务

size_t HashFunc(const K& key)//将K类型的数据转换成整型
{Hash hash;return hash(key);//调用仿函数的()重载，将K类型的数据转换成整型
}

限于篇幅问题，下面就只放Insert改后的代码了

bool Insert(const T& data)
{KOfT koft;//用于取出T类型的Keyif (_table.size() == _num)//负载因子到1时扩容{//1.开2倍大小空间(不一定是2倍)//2.遍历旧表数据，重新计算在新表中位置//3.释放旧表vector<Node*> newtable;size_t newsize = _table.size() ? _table.size() * 2 : 10;newtable.resize(newsize);for (auto& cur : _table){//将旧表中的节点取下来重新计算在新表中的位置，并插入进去Node* oldcur = cur;while (cur){Node* next = cur->_next;size_t index = HashFunc(koft(cur->_data)) % newtable.size();//头插进桶中cur->_next = newtable[index];newtable[index] = cur;cur = next;}oldcur = nullptr;//将旧表该位置置空，否则最后析构旧表时就将节点都析构了}_table.swap(newtable);//旧表在出作用域后自动销毁}size_t index = HashFunc(koft(data)) % _table.size();//除留余数法取出映射//先查找值是否重复Node* cur = _table[index];while (cur){if (koft(cur->_data) == koft(data))//如果是重复值，插入失败return false;elsecur = cur->_next;}Node* newnode = new Node(data);//开辟新空间//头插到对应桶中(尾插也可以)newnode->_next = _table[index];_table[index] = newnode;_num++;return true;
}

Hash仿函数实现

既然想让全部情况都用Hash仿函数，那么需要先给最基本的是数字的情况写一个仿函数

template<class K>
struct _Hash
{const K& operator()(const K& key){return key;}
};

它没有任何作用，只是返回key本身

针对于string的仿函数

将string转换成整型有很多种方案，例如取字符串的第一个字符作为key，但这样的话只要第一个字符相同，就会发生哈希冲突。

因此，为了减少哈希冲突，我们采取不容易重复的方案——将字符串中所有字符相加作为key

struct HashString//将string转换为整型
{size_t operator()(const string& s){size_t hash = 0;for (const auto& c : s)hash += c;//将字符串所有字符都加起来return hash;}
};

但这样还是太容易出现重复值，例如"abcd"和"aadd"，虽然字符串不一样，但相加起来的结果是一样的

因此就有了专门针对字符串的"字符串Hash函数"

各种字符串Hash函数 - clq - 博客园https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html这篇文章总结了很多字符串Hash函数，而这其中最为出名的是BKDR算法(也就是上面文章中的第一个)

简单点来说就是在原来(将字符都加起来)的基础上，每次相加都*131

为什么是131？

答：选择 131 作为 BKDRHash 的乘数，本质上是利用质数的数学特性（均匀分布、减少冲突），结合计算机系统的溢出机制，以及实际应用中的经验验证。它并非唯一的选择，但经过长期实践证明是一个高效且可靠的方案。如果需要更高的安全性，也可以尝试其他质数（如13331）或双哈希（Double Hashing）策略。

struct HashString//将string转换为整型
{size_t operator()(const string& s){size_t hash = 0;//这里采用BKDR算法for (const auto& ch : s)hash = hash * 131 + ch;//将字符串所有字符都加起来（每次加前*131）return hash;}
};

针对仿函数进行“模板特化”优化

现在想要实例化一个哈希对象，必须4个模板参数都写上

HashTable<string,string, KeyOfSet<string>,HashString> ht1;
HashTable<int, int, KeyOfSet<int>, _Hash<int>> ht2;

但实例化unordered_map/set时也不需要传第4个参数啊？

这时就要用到模板的特化了

由于针对string的仿函数和普通类型的仿函数内部代码结构不一样，因此不能用普通的模板，这时只要将针对string的仿函数单独拎出来作为参数为string时的仿函数就可以了

template<>//针对string类型的模板特化
struct _Hash<string>//将string转换为整型
{size_t operator()(const string& s){size_t hash = 0;//这里采用BKDR算法for (const auto& ch : s)hash = hash * 131 + ch;//将字符串所有字符都加起来（每次加前*131）return hash;}
};

如果还想用别的自定义类型作key，可以再自己写仿函数

最后将哈希表的Hash模板参数设上默认值

template<class K,class T,class KOfT,class Hash = _Hash<K>>//T可能是K或pair，KOfT是为了从T中取出key的仿函数，Hash是将不同类型的K转换为整型的仿函数
class HashTable
{}

此时即使不写这个参数也可以了

HashTable<string, string, KeyOfSet<string>> ht1;
HashTable<int, int, KeyOfSet<int>> ht2;

哈希表扩容优化

当前的哈希表扩容机制是按二倍增容，但有研究指出，如果哈希表的大小是质数个，哈希冲突的概率会降低，因此这里就将扩容改成质数扩容

我们使用STL实现哈希表中给出的质数表：

STL中就是将该表作为扩容的数据量，这里就不用构建一个结构体了，直接用函数实现

size_t GetNextPrime(size_t num)
{const size_t PrimeCount = 28;const 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};for (size_t i = 0; i < PrimeCount; i++){if (PrimeList[i] > num)//找到下一个比当前容量大的值return PrimeList[i];}return PrimeList[PrimeCount - 1];//如果到最大值
}

理论来说是不会出现扩容失败的情况的，因为最大值是42亿，这也是int类型的最大值...有这个数据量....嗯...

最后再将Insert中的扩容改一下

pair<iterator,bool> Insert(const T& data)
{KOfT koft;//用于取出T类型的Keyif (_table.size() == _num)//负载因子到1时扩容{//1.开2倍大小空间(不一定是2倍)//2.遍历旧表数据，重新计算在新表中位置//3.释放旧表vector<Node*> newtable;size_t newsize = GetNextPrime(_table.size());//取到比当前容量大的那一个质数//...............	
}