哈希表的实现（下）
目录
前言
开散列概念
开散列实现
Insert
优化
Find
Erase
前言
上一章节我们用闭散列实现了一下哈希表，但存在一些问题，比如空间浪费比较严重，如果连续一段空间都已经存放值，那么在此位置插入新值的时候就会一直挪动，时间浪费也比较严重，当然可以通过二次探测来解决此问题，但今天我们来讲解一下更优秀的解决方案。
开散列概念
像这样，我们在插入的时候，遇到哈希冲突，不用将它向后移动找到空位置，而是通过链表的形式，将他们一一连接起来，从而达到不影响其他位置的效果。开散列中每个桶中放的都是发生哈希冲突的元素。这样就能有效解决查找和插入的问题。
开散列实现
开散列的实现需要一个指针数组，通过这个数组将插入值进行链接，就像上面的图片。
template<class K, class V>struct HashNode{HashNode* _next;pair<K, V> _kv;HashNode(const pair<K, V>& kv):_kv(kv),_next(nullptr){}};首先先定义一个节点，节点里面包含下一个位置的指针，一个_kv，接下来开始实现。
template<class K, class V>class HashTable{typedef HashNode<K, V> Node;public:HashTable(){_tables.resize(10);}~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;}}private:vector<Node*> _tables;size_t _n = 0;};
在HashTable中定义一个指针数组vector<Node*> _tables，统计插入个数_n，在构造函数中先开10大小的空间，析构函数中一次遍历该数组，如果不为空，依次进行delete，直到为空为止，然后将该数组位置置为nullptr。
Insert
在实现成基本结构后，我们来进行insert的实现。再拿出这个图来鞭尸。
当插入15时，我们找到5的位置，之后在此位置进行头插操作，即可将15链接在这个桶上。
同样和闭散列一样，这种方式也需要考虑扩容的情况，但闭散列的空间利用率较低，负载因子控制在0.7左右，而开散列这种方式可以设置为1。
实现insert的方式有两种，大家可以先自己看一下哪一个更优秀。
1：
bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;// 负载因子最大到1if (_n == _tables.size()){size_t newSize = _tables.size() * 2;HashTable<K, V> newHT;newHT._tables.resize(newSize);// 遍历旧表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while(cur){newHT.Insert(cur->_kv);cur = cur->_next;}}_tables.swap(newHT._tables);}size_t hashi = kv.first % _tables.size();Node* newnode = new Node(kv);// 头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}2：
bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;if (_n == _tables.size()){vector<Node*> newTables;newTables.resize(_tables.size() * 2, nullptr);// 遍历旧表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while(cur){Node* next = cur->_next;// 挪动到映射的新表size_t hashi = cur->_kv.first % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTables);}size_t hashi = kv.first % _tables.size();Node* newnode = new Node(kv);// 头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}第一种方法用了闭散列实现时的方式，直接复用一下insert，这样完成遍历后就可以得到扩容后的哈希表，第二种方法选择直接进行链接，然后将完成链接后的位置置空，同样也可以完成扩容操作。
那么哪种情况会更好呢？答案是第二种，因为我们发现insert会new一个新节点然后再将其链接到哈希表中，而第二种情况是直接将现成的节点插入到扩容后的哈希表中，减少了空间的浪费，所以这种方法更优。
在第二种方法中，我们首先定义一个新的指针数组，然后依次遍历旧表，将旧表中的值重新通过新的哈希函数进行转换，得到的位置就是新插入的位置，然后将它头插到表中即可，再将旧表位置置为空，完成便利后，我们只需要交换新旧表，这样_tables就是扩完容后的哈希表。
优化
通常，我们的K为整形，但K为string时就不能转换为关键字，这时就要用一个仿函数来进行完善。
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};// 11:46继续
//HashFunc<string>
template<>
struct HashFunc<string>
{size_t operator()(const string& key){// BKDRsize_t hash = 0;for (auto e : key){hash *= 31;hash += e;}cout << key << ":" << hash << endl;return hash;}
};我们特化了一个仿函数，当K为string时，直接调用下面的仿函数，里面用到了BKDR算法，它能够将字符串转化为关键字，并且尽可能的避免了哈希冲突的情况，这种方法被广泛应用。这样我们只需要在哈希表中增加一个模板即可完成string这种情况下转为关键字的情况。
template<class K, class V, class Hash = HashFunc<K>>Find
Node* Find(const K& key){Hash hf;size_t hashi = hf(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return NULL;}将要寻找的key转换为关键字，该关键字可以映射哈希表中的一个位置，这时找到该位置，依次遍历该链表，若能找到返回该节点指针，若到空还是不能找到，返回空。
Erase
bool Erase(const K& key){Hash hf;size_t hashi = hf(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;}prev = cur;cur = cur->_next;}return false;}因为我们的节点里面只有next的指针，是一个单项链表，所以我们在删除时要定义一个prev来指向前一个节点的位置。和前面类似，先通过哈希函数进行转换，转换为关键字后找到哈希表中对应的位置，进行查找，则会出现三种情况：
1.找到了该位置，前驱节点prev为空，说明该节点就是头节点，只需要将哈希表中该位置链接到cur的next节点即可。
2.找到了该位置，前驱节点prev不为空，说明前面还有值，那么将prev的next更新为cur的next
即可完成链接。
3.循环结束后还没返回，说明没有此值。
erase还可以先用find查询一下是否存在，若存在继续进行删除操作，不存在直接返回false。