一、线性哈希表的缺陷

• 发生哈希冲突时，需要从当前发生冲突的位置不断地向后去找空闲位置，这个过程会慢慢地将时间复杂度从O(1)变成O(n)，就是存储、删除和查询过程变慢了。发生哈希冲突越严重就越靠近O(n)的复杂度，这个过程可以优化吗？因为它是一个线性表，是数组，需要环形遍历，趋近于O(n)，按一个位置一个位置找，找的越多，时间复杂度就趋近于O(n)。这个过程是没有办法优化的，因为只有这么一个数组结构。当然在链式哈希表中是可以优化的。
• 在多核非常盛行的年代下，多核非常方便使用并发程序，也就是多进程多线程程序。在多线程运行的环境中就存在一个线程安全问题，多个线程能不能在一个数组中进行增加、删除和查询，肯定不可以！像我们C++里所有的容器都不是线程安全的，要在多线程中使用都必须用线程的互斥操作（互斥锁、读写锁或者自旋锁），来对这些容器在多线程环境下的修改查询做一个线程互斥操作，保证这些容器在多线程环境下的操作都是一个原子操作。同样地，vector底层就是数组，数组没办法同时做修改查询，很明显修改和查询都不是一个原子操作，步骤太多了！**线性探测所用到的基于数组实现的哈希表，只能给全局的表用互斥锁来保证哈希表的原子操作，保证线程安全！**因为线性探测只有一个数组，得把整个数组锁起来，也就是说，你是一个线程，我是一个线程，我们都要同时操作这个线程的话，而且我们要放的位置不是同一个位置，那么理论上来说是可以并发执行的，但是实际上我们不能不用锁控制让它执行，因为有可能都发生哈希冲突了，就都需要向后找下一个空闲的位置，如果我们找到同一个空闲的位置，那么不管我们谁先放元素，最终都是后放的把先放的给覆盖了。所以我们给整个哈希表加锁，要么你先操作，要么我先操作。

但是链式哈希表可以采用分段的锁，这样既保证了线程安全，又有一定的并发量，提高了效率。当前我们库里面无序的关联容器并没有实现多线程中的线程安全问题，就是并没有去加锁，但是这并不妨碍当我们真正想要实现一个线程安全，能够直接用在多线程环境下的基于哈希表实现的无序关联容器，我们在代码上可以通过分段锁来实现。

二、链式哈希表的原理

增加

将下面一组数据放入链式哈希表中。

哈希函数用的是除留取余法（为了减少哈希冲突，就是映射以后的结果尽量不冲突，采用数组的个数尽量是一个素数，出了1和自己而不能被其他的数字整除，这样的尽量减少余数产生冲突。），解决哈希冲突的方式是链地址法。

链式哈希表在发生冲突的时候就不像线性探测一样继续往后探测，而是在桶里面生成一个数据结构（链表），我们链式哈希表里面不再需要状态，每个桶都放的是一个链表，把发生哈希冲突的元素都放在一个桶里面，即发生哈希冲突的元素都串在一个链表上。

为什么叫做链式哈希表呢？首先它的一维数组是没有变的，每一个元素代表一个哈希的桶，但是桶里面不再是普通的数据，放的是链表。从代码上去关联：vector<list<int>> table。

搜索

这个0号桶的链表只有一个节点就查的快。但当这个链式哈希表每个桶里面的链表比较长的话，链表搜索花费的时间就多，可能趋近于O(n)。所以不管是链式哈希表还是线性探测都有一个装载因子，如果已占用桶的个数达到总的桶个数的75%，哈希表就要进行扩容了。

删除
删除和搜索的情况非常相似，要先搜索，搜到了再删除。

链式哈希表如果是其中一个桶链表特别长，其他好多桶都是空的，就说明这个哈希函数选的不好，没有办法把原始数据通过哈希函数离散开。我们需要的哈希函数是希望散列结果越均匀越好，就能均匀分散在哈希表里，提高了整体的哈希表的效率。

所以哈希表增删查时间复杂度确实能达到O(1)，但是大部分情况下又没有办法达到O(1)，只能无限趋近于O(1)，因为哈希冲突的存在！

线性哈希表的两个缺陷在链式哈希表里实现的时候会有哪些优化方法？

• 当链表的长度大于一个指定的数，把桶里面的链表转成红黑树，红黑树的增删查是O(logn)，很明显比O(n)线性复杂度要好很多。
• 在链式哈希表，我们只需要在每个桶添加一个锁就可以保证线程安全。所以链式哈希表最先计算出在哪个桶就一定在哪个桶，无非在桶里面新增加一个节点。每个桶里面的链表不能并发操作，但是不同桶里面的链表可以并发操作。
  
  

三、链式哈希表的代码实现

swap交换两个容器的元素，会不会效率很低？swap底层实现是什么？
swap其实效率很高，它只是交换了两个容器的成员变量，并没有交换表里面的数据，没有重新开辟内存、重新拷贝之类的。swap交换图解：

如果两个容器使用的空间配置器不一样，比如一个容器是从内存池里取出的容器进行管理，一个容器是普通的释放内存的free方法，这样就不能简单的成员变量交换了。

#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
using namespace std;

class HashTable
{
private:
	vector<list<int>> _table;
	int _useBucketNum;
	double _loadFactor;
	static const int _primeSize = 10;
	static int _primes[_primeSize];
	int _primeIdx;
	void expand()
	{
		++_primeIdx;
		if (_primeIdx == _primeSize)
			throw "hashtable is too large,can not expand anymore";
		vector<list<int>> oldTable;
		_table.swap(oldTable);
		_table.resize(_primes[_primeIdx]);
		for (auto list : oldTable)
		{
			for (auto key : list)
			{
				int idx = key % _primes[_primeIdx];
				if (_table[idx].empty())
				{
					_useBucketNum++;
				}
				_table[idx].emplace_front(key);
			}
		}

	}
public:
	HashTable(int size = _primes[0], double loadFactor = 0.75)
		:_useBucketNum(0), _loadFactor(loadFactor), _primeIdx(0)
	{
		if (size != _primes[0])
		{
			for (; _primeIdx < _primeSize; ++_primeIdx)
			{
				if (_primes[_primeIdx] > size)
				{
					break;
				}
			}
			if (_primeIdx == _primeSize)
			{
				_primeIdx--;
			}
		}
		_table.resize(_primes[_primeIdx]);
	}
	void insert(int key)
	{
		double factor = _useBucketNum * 1.0 / _table.size();
		cout << factor << endl;
		if (factor > 0.75)
		{
			expand();
		}
		int idx = key % _table.size();
		if (_table[idx].empty())//O(1)
		{
			_useBucketNum++;
			_table[idx].emplace_front(key);
		}
		else
		{
			auto it = ::find(_table[idx].begin(), _table[idx].end(), key);//O(n)
			if (it == _table[idx].end())
			{
				//key不存在
				_table[idx].emplace_front(key);
			}

		}
	}
	void erase(int key)
	{
		int idx = key % _table.size();//O(1)
		//如果链表节点过长，如果散列函数比较集中，（散列函数有问题！）
		//				  如果散列比较离散，链表长度一般不会过长，因为有装载因子
		auto it = ::find(_table[idx].begin(), _table[idx].end(), key);//O(n)
		if (it != _table[idx].end())
		{
			_table[idx].erase(it);
			if (_table[idx].empty())
			{
				_useBucketNum--;
			}
		}
	}
	bool find(int key)
	{
		int idx = key % _table.size();//O（1）
		auto it = ::find(_table[idx].begin(), _table[idx].end(), key);//O(n)
		return it != _table[idx].end();
	}
};
int HashTable::_primes[_primeSize] = { 3,7,23,47,97,251,443,911,1471,42773 };
int main()
{
	HashTable htable;
	htable.insert(12);
	htable.insert(24);
	htable.insert(38);
	htable.insert(15);
	htable.insert(14);
	htable.insert(40);
	htable.insert(93);
	cout << htable.find(12) << endl;
	htable.erase(12);
	cout << htable.find(12) << endl;
}

四、哈希表总结

面试介绍哈希表：一个关键字，经过散列函数进行映射，得到的它在表中的存储位置，符合这样的key及其映射关系后得到在表中的存储位置，这样的表就叫做散列表或者哈希表。然后可以解释哈希冲突的问题，再解释解决哈希冲突的线性探测哈希表和链式哈希表。

优缺点：

散列函数：

散列冲突处理：

二次探测：比如说插入78，发现发生哈希冲突了，就在它的右边找一次，然后左边找一次，然后右边找一次，然后左边找一次…是对线性探测的优化。