哈希表的实现02

很高兴和大家见面，给生活加点impetus！！开启今天的编程之路！！

今天我们来学习另一种实现哈希表的方法，链接地法，这一种方法也是库中实现的底层
作者：٩( ‘ω’ )و260
我的专栏：C++进阶，C++初阶，数据结构初阶，题海探骊，c语言
欢迎点赞，关注！！

哈希表的实现02

链地址法

解决冲突思路

开放定址法中所有的元素都放到哈希表里，当哈希冲突的时候，始终都是去抢占别人的位置，但是链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成⼀个链表，挂在哈希表这个位置下面，链地址法也叫做拉链法或者哈希桶。

来看一个图像理解：

扩容

开放地址法中负载因子必须小于1，在那里我们取得是0.7，但是在链地址法中，对负载因子的大小没有要求，但是，负载因子越大，哈希冲突的概率越高，此时空间利用率越高，相反，负载因子越小，哈希冲突的概率越低，空间利用率越低。

stl库中当负载因子大于1的时候就会扩容，接下来我们使用链地址法的时候也遵循库中的规律。

极端场景

在极端场景下，比如有人恶意攻击我，恶意制造都存储在一个位置的数据组，此时造成某个桶的长度特别长，因为链地址法中可以等价于下面挂了一个链表，此时我们遍历这个链表，效率就会从O（1）到O（n），效率被大打折扣了。

在Java8的HashMap中当桶的长度超过⼀定阀值(8)时就把链表转换成红黑树，反之当阈值小于8时，又会转换成来链表。这里我们不用搞这么复杂，我们来实现以下是简单版本的即可。

代码实现

结构定义

首先，我们哈希表中存储的是结点的指针，因为需要计算负载因子，所以是需要一个成员变量来计算里面插入的数据个数。
后面我们会实现哈希表封装myunordered_set和unordered_map，这里我们先假设数据是pair，即哈希表结点中存储的是pair

来看下面代码：

template<class K.class V>
struct HashNode
{
	pair<K,V> _kv;
	HashNode<K,V>* _next;
	
	HashNode(const pair<K,V>& kv)
		:_kv(kv),_next(nullptr)
	{}
}

template<class K,class V>
class HashTable
{
	typedef HashNodeM<K,V> Node;
public:
	HashTable(size_t n = __stl_next_prime(0))
		:_tables(n),_n(0)
	{}
private:
	vector<Node*> _tables;
	size_t _n;		
}

说明：vector里面不是类似链表吗？为什么我们不用vector<forword-list>来定义这个结构？
首先库中不是这样定义的，而且之后这个迭代器实现起来比较困难。而且这种写法之后要写析构，拷贝，赋值重载，因为里面有资源（我每次的结点都要放入到list中，无lsit需要创建list）。我们这种写法会调用自己的析构函数。
需要注意的是：我们这种写法也需要写析构函数，因为vector的析构会析构掉vector，但是我们其中还有单链表需要析构

析构

析构比较简单，找到不是空的桶，设置指针逐个去删就可
来看代码：

~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;
	}
}

插入

在插入一个数据的时候，实例上等价于在链表中插入一个数据，同时，插入的位置需要我们使用除法散列法。

链表中插入优先选择头插，因为尾插的话还要遍历到最后一个结点。
链表头插的情况分为链表为空时插入和链表不为空时插入。

来看代码实现：

bool Insert(const pair<K,V>& kv)
{
	int hashi=kv.first%_tables.size();
	Node*cur=new Node(kv);
	cur->_next=_tables[hashi];
	_taables[hashi]=cur;
	++_n;
}

这个代码两种情况可以兼得！！
插入毕竟空间是有限的，也不可能在哈希表中一直插入，所以此时我们必须要执行扩容操作，如果我们按照上篇文章的方法来扩容，在循环中复用Insert函数，那么会怎样呢？
来看一下代码：

if(_n==_tables.size())//此时负载因子等于哈希表的大小，此时需要扩容
{
	for(size_t i=0;i<_tables.size();i++)
	{
		HashTable newht(__stl_next_prime(_tables.size() + 1),nullptr);
		Node*cur=_tables[i];
		while(cur)
		{
			newht.Insert(cur->_kv);
			cur=next;
		}
	}
	_tables.swap(newht._tables);
}

1：上述我们创建了一个素数表，呈现二倍增长，并不断取其中的数据（使用upper_bound函数，取得是>=的），与Java中M的增长趋势相同
2：vector，list等底层是数组的结构调用自己的swap函数开销不大，本质上也就是交换一个指针而已。
3：上面我们调用了vetor的构造函数，将哈希表中的所有空间初始化为nullptr

如果我们按照这种思路来写的话，会发现复用的时候有创建了结点，就等价于是我创建了结点，交换的之后，又把创建的结点给删了（局部变量出了作用域之后自动调用析构函数)，为什么我们不换一种思路？我们直接把挂在上面的结点给拿到新的指针上去呢？这样就可以省略掉new的开销。
我们来实现一下这种新的思路：

if(_n==_table.size())
{
	vector<Node*> newtables(__stl_next_prime(_tables.size() + 1),nullptr);
	for(size_t i=0;i<_tables.size();i++)
	{
		Node*cur=_tables[i];
		while(cur)
		{
			Node*next=cur->_next;
			int hashi=cur->_kv.first%newtables.size()；
			cur->_next=newtables[hashi];
			newtables[hashi]=cur;
			
			cur=next;
		}
		_tables[i]=nullptr;//旧表用完之后我们将这个位置置为空
	}
	_tables.swap(newtables);
}

我们发现，其实就是相当于我们将复用Insert的逻辑再来实现一遍，只不过原先new的结点在旧表中已经存在。

第一种方法是创建一个哈希表，第二中方法是创建一个哈希数组。
第一种是直接实现Insert复用，第二种是将复用的逻辑写下来
两者都是直接交换数组。

仿函数

在上一篇文章中我们也已经提到过了，有可能存在某些不能够取模的类型
此时我们就必须使用仿函数，这里同上篇文章一样，主要还是涉及字符串转换成整形，因为字符串十分常见：
来看代码：

template<class K>
struct HashFunc
{
	size_t operator()(K& key)const
	{
		return (size_t)key;
	}
}
//对模版进行特化处理
template<>
struct StringFunc<string>
{
	size_t operator()(string& s) const
	{
		int hashi=0;
		for(auto& e:s)
		{
			hashi+=e;
		}
		return hashi;
	}
}

查找

查找的思路其实与插入一致，即先寻找需要查找的位置，即key的映射位置，随后再这个位置中来查找
来看代码：

Node* Find(const K&key)
{
	size_t hashi=key%_tables.size();
	Node*cur=_tables[hashi];
	while(cur)
	{
		if(key == _tables[hashi]._kv.first)
		{
			return cur;
		}
		cur=cur->_next;
	}
	return nullptr;//没找到，返回空指针
}

重点：
从上面我们可以发现特点：
问：红黑树和哈希表分别对key有什么要求？
红黑树：至少需要满足一个大小比较，库中默认的是小于，不支持的话写仿函数
哈希表：至少需要满足能够取模并且支持相等，不支持就写仿函数
而且，这两点在库中也有详细的展示，来看库中的数据：

删除

接下来我们来看删除的逻辑，删除还是需要计算key的映射位置，在这个位置上我们看能不能找到需要删除的数据。

细节：删除的时候分为头删和尾删，即需要注意删除的结点是头结点或者是中间结点。
注意：与开放地址法不同的是，我们不能复用Find函数，因为我们删除如果有前一个结点，会让前一个结点指向删除结点的下一个结点。单单复用Find函数的话是找不到前一个结点的。

来看代码：

bool Erase(const K& key)
{
	int hasi=key%_tables.size();
	Node*cur=_tables[hashi];
	Node*prev=nullptr;
	while(cur)
	{
		if(cur->_kv.first == key)
		{
			if(prev==nullptr)//没有前一个结点
			{
				_tables[hashi]=cur->_next;
			}else{
				prev->_next=cur->_next;	
			}
			--_n;
			delete cur;
			return true
		}
		prev=cur;
		cur=cur->_next;
	}
	return false;
}

细节：
1:这里的删除和查找都是使用的的key，不管底层是k还是kv的结构，所以封装Unordered系列的时候肯定是再需要传递一个key过去的。
2:删除和查找中也要考虑key能不能取模的情况，即需要仿函数来转换一下

结语

感谢大家阅读我的博客，不足之处欢迎指正，感谢大家的支持
逆水行舟，楫摧而志愈坚；破茧成蝶，翼湿而心更炽！！加油！！