前面我们对于哈希表的实现使用的是开放定址法的方式。不过这种方式也不是当前的主流方式。

一、链地址法

链地址法的数据不是直接存储到哈希表中的，哈希表中每个位置存储的是一个哈希元素指针，当没有数据映射到这个位置的时候，那么这个位置的指针就为空，然后多个数据映射到这个位置的时候，这个位置的数据就会串联成一个链表，我们又称为哈希桶。

下面我们插入一堆数据看看其是咋样的：

我们插入{19，30，5，36，13，20，21，12，24，96}这一组值到M=11的哈希表中：

那么其最终效果如下：

开放定址法负载因子必须小于1，然而链式定址法对于负载因子就没有限制了，其可以大于1，负载因子越大，哈希冲突的概率越大，空间的利用率越大，负载因子越小，哈希冲突的概率越小，空间利用率越小。不过我们将负载因子基本控制在1左右，在其到1的时候就进行扩容。

但是使用这个方式存在一种极端情况：

极端情况下，会存在某个桶特别的长，那么对于这种情况，我们就会会采用全域散列法随机去使用一个哈希函数。

二、哈希桶的实现

1、哈希桶的基本结构

首先就是一个指针数组，然后数组存储的是一个一个链表，链表存储的数据的kv结构的：

不过，我们使用哈希桶是要对unordered_set和unordered_map进行封装，所以我们将数组存储的结点和哈希表的结构封装进行分离：

然后对于扩容的机制和前面的开放定址法的类似，使用一个函数，将28个素数放一个数组中，然后传入一个n，在这个数组中找大于等于n的数进行扩容。

2、哈希桶的查找实现

哈希桶的查找，就是使用哈希函数，找到它映射的位置，然后就在这个位置指向的指针开始找，找的方式和链表一样。

3、哈希桶的插入实现

哈希桶的插入前面的逻辑和前面的开放定址法的方式一样，也是使用哈希函数，找到其映射的位置，然后进行插入。然后就是到我们数组中的插入了，我们数组中存储的是一个一个链表，那么我们要考虑在链表中是头插还是尾插了。如果是尾插，那么我们就要先找到链表的尾结点，然后再进行插入，而且还要先判断当前链表是否为空。所以我们就使用头插。

        

上面就是哈希桶的插入的实现了，然后就是到扩容了。

4、扩容

扩容也有好几种方式，最简单的方式就是开辟一个新表，然后将旧表的数据插入到新表中，然后交换两个表。

但是上面这种扩容方式并不是很好，其时间复杂度达到了O(n)。

我们本质上可以直接移动哈希表中的每一个结点，不需要重新开辟新节点，我们上面调用新表的插入函数，其会再重新开辟结点然后进行插入。

我们还可以将旧表中的每个结点拿下来，然后再映射到新哈希桶中。

然后对于插入的key数据不为整型的情况下，和我们前面的哈希表一样，使用仿函数，将其转化为整型。

5、哈希桶的删除

删除也很简单：

三、完整代码

#pragma once
#include<iostream>
#include<list>
#include<vector>

using namespace std;

//template<class K,class V>
//class HashTable 
//{
//private:
//	vector<list<pair<K, V>>>_table;
//	size_t n = 0;
//};
template<class K,class V >
class HashNode 
{
	pair<K, V>_kv;
	HashNode<K, V>* _next;

	HashNode(const pair<K,V>&kv)
		:_kv(kv)
		,_next(nullptr)
	{

	}
};

template<class K>
struct HashFunc
{
	size_t operotar()(const K& key)
	{
		return (size_t)key;
    }
};

template<class K,class V,class Hash=HashFunc<K>>
class HashTable 
{
	typedef HashNode<K, V> Node;

	inline unsigned long __stl_next_prime(unsigned long n)
	{
		static 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
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list +
			__stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}

public:

	Node* Find(const K&key)
	{
		Hash hs;
		size_t hash0 = hs(key) % _table.size();
		Node* cur = _table[hash0];
		while (cur) 
		{
			if (cur->_kv.first == key)
			{
				return cur;
			}
			cur = cur->_next;
		}
		return nullptr;
	}

	bool Insert(const pair<K,V>&kv)
	{
		//已存在，不能插入
		if (Find(kv.first))
		{
			return false;
		}

		//扩容1
		//if (_n==_table.size())
		//{
		//	//创建新表
		//	HashTable<K, V>newHT(__stl_next_prime(_table.size() + 1);

		//	for (size_t i = 0; i < _table.size(); i++)
		//	{
		//		Node* cur = _table[i];
		//		while ()
		//		{
		//			newHT.Insert(cur->_kv);
		//			cur->_next;
		//		}
		//	}
		//	_table.swap(newHT._table);
		//}

		//扩容2
		if (_n==_table.size())
		{
			HashTable<K, V>newHT(__stl_next_prime(_table.size() + 1), nullptr);

			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					//将旧表中的数据映射到新表
					size_t hashi = next._kv.first % newHT._table.size();

					newHT._table[hashi] = cur;
					cur = next;
				}
				newHT._table[i] = nullptr;
			}
			_table.swap(newHT._table);
		}


		//先使用哈希函数找其映射的位置
		size_t hash0 = kv.first % _table.size();
		
		Node* newnode = new Node(kv);

		newnode->_next = _table[hash0];

		_table[hash0] = newnode;

		_n++:

		return true;
	}

	bool Erase(const K& key)
	{
		Hash hs;
		size_t hashi = hs(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;
				--_n;
				return true;
			}
			prev = cur;
			cur = cur->_next;
		}
		return false;
	}


   private:

	   vector<Node>_table;
	   size_t n = 0;

};