【C++】哈希表 --- 闭散列版本的实现

---

1 C++中的哈希表

哈希表（Hash Table）是一种数据结构，它通过哈希函数将键映射到表中的一个位置来访问记录，支持快速的插入和查找操作。

哈希表的概念最早可以追溯到1953年，由H. P. Luhn提出。他首次描述了使用哈希函数来加速数据检索的过程。随后，这一概念在数据库管理系统和编程语言中得到广泛应用。

在计算机科学中，哈希表的发展与算法和数据处理的需求紧密相关。随着计算机硬件性能的提升和数据量的爆炸性增长，哈希表作为一种高效的数据结构，在软件工程、数据库系统、网络搜索引擎等领域扮演着重要角色。

在C++中unordered系列关联式容器是哈希表

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到$lo{g}_{2}N$，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同

— 使用文档

2 哈希表底层

2.1 功能

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O($lo{g}_{2}N$)，搜索的效率取决于搜索过程中元素的比较次数。

而我们希望的理想搜索方法应该是 ：可以不经过任何比较，一次直接从表中得到要搜索的元素。

如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码key之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

那么当向该结构中：

• 插入元素：只需要根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
• 搜索元素：直接对对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

2.1 哈希冲突

对于两个数据元素的关键字$k_i$和 $k_j$(i != j)，有$k_i$ != $k_j$，但有：Hash($k_i$) ==Hash($k_j$)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

哈希冲突可能是哈希函数引起的：
哈希函数设计原则：

• 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
• 哈希函数计算出来的地址能均匀分布在整个空间中
• 哈希函数应该比较简单

可见哈希函数时有可能造成哈希冲突的

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。发生哈希冲突该如何处理呢？
解决哈希冲突两种常见的方法是：闭散列和开散列

2.3 开散列与闭散列

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

散列表分为闭散列和开散列，这是两种完全不同的方式，但是底层都是数组：

• 闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？
  进行线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
  比如上图中的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。

  • 插入：通过哈希函数获取待插入元素在哈希表中的位置如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素
  • 删除：采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素
  • 线性探测优点：实现非常简单，
  • 线性探测缺点：空间利用率比较低，一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。可以使用二次探测法缓解。

• 开散列：开散列又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链起来，各链表的头结点存储在哈希表中

3 闭散列版本的实现

下面我们来实现闭散列版本的哈希表

3.1 框架搭建

首先我们需要进行一个简单的框架搭建：

1. 我们需要一个HashData类，来储存数据
2. HashTable类底层是vector容器
3. 因为会有不同类型的key，所以我们需要一个仿函数来将不同类型转换为size_t；
4. 因为闭散列的删除不能直接删除节点，否则会导致线性探测失效，所以HashData类里需要记录状态！

pragma once
//----------哈希表模拟实现-----------
//版本一 --- 闭散列
#include<utility>
#include<iostream>
#include<vector>
using namespace std;

//节点状态
enum status
{
	EXIST,
	EMPTY,
	DELETE
};
//设计节点
template<class k , class v>
struct HashData
{
	HashData()
	{
		status = EMPTY;
	}
	//键值对
	pair<k, v> _kv;
	//状态
	status status;
};
// kv键值  ， 仿函数解决不同类型key转换为size_t类型的下标
template<class k , class v , class Hash = HashFunc<k> >
class HashTable
{
public:
	HashTable()
	{
		_table.resize(10);
	}
private:
	//底层是vector容器
	vector<HashData<k , v>> _table;
	size_t _n;//有效数据个数
	Hash hs;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

3.2 仿函数设计

仿函数的作用是将不同数据类型的key转换为可以使用的size_t类型。
对于可以直接显示类型转换的类型直接转换即可。而对于不能直接转换的类型（比如string）就要进行特殊处理了！

//设计仿函数 --- 适配不同数据类型的key
template<class K>
struct HashFunc
{
	//可以进行显示类型转换的直接转换！！！
	size_t operator()(const K& k)
	{
		return (size_t)k;
	}
};
//string不能进行直接转换，需要特化
template<>
struct HashFunc<string>
{
	//可以进行显示类型转换的直接转换！！！
	size_t operator()(const string& k)
	{
		size_t key = 0;
		for (auto s : k)
		{
			key *= 131;
			key += s;
		}
		return key;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

3.3 插入函数

1. 首先插入之前要先检查是否在哈希表中已经有数据了
2. 然后检查该次是否需要进行扩容
3. 通过key值选取合适位置进行插入，有效个数加一

bool insert(pair<k,v> kv)
{
	//插入前先进行一个检查
	if (Find(kv.first)) return false;
	//是否需要扩容
	if (_n == _table.size() * 0.7)
	{
		//进行替换
		HashTable<k, v> newHT;
		newHT._table.resize(_table.size() * 2);
		//进行赋值
		for (auto s : _table)
			newHT.insert(s._kv);
		//进行替换！！！
		_table.swap(newHT._table);
	}
	//进行插入
	//hash地址
	int hashi = hs(kv.first)% _table.size();
	//寻找合适位置进行插入
	// 线性探测
	while (_table[hashi].status == EXIST)
	{
		hashi++;
		hashi %= _table.size();
	}
	//找到合适位置了进行插入
	_table[hashi]._kv = kv;
	_table[hashi].status = EXIST;
	_n++;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

3.4 查找函数

查找的逻辑很简单，通过key值锁定位置进行线性探测即可！

//查找
HashData<k , v>* Find(const k& Key)
{
	int hashi = hs(Key) % _table.size();
	while (_table[hashi].status != EMPTY)
	{
		if (Key == _table[hashi]._kv.first && _table[hashi].status == EXIST)
		{
			return &_table[hashi];
		}
		++hashi;
		hashi %= _table.size();
	}
	return nullptr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.5 删除函数

删除先通过key找到需要删除的数据
然后将状态设置为DELETE , 有效个数减一

//删除
bool Erase(const k& Key)
{
	//int hashi = Key % _table.size();

	//while (_table[hashi].status != EMPTY)
	//{
	//	if (Key == _table[hashi]._kv.first && _table[hashi].status == EXIST)
	//	{
	//		_table[hashi].status = DELETE;
	//		--_n;
	//		return true;
	//	}
	//	++hashi;
	//	hashi %= _table.size();
	//}
	//return false;
	
	//简单版
	HashData<k , v>* ret = Find(Key);
	if (ret == nullptr)
	{
		return false;
	}
	else
	{
		ret->status = DELETE;
		--_n;
		return true;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

这样我们就实现了闭散列的哈希表！！！

Thanks♪(･ω･)ﾉ谢谢阅读！！！

下一篇文章见！！！