[C++][数据结构]哈希1：哈希函数的介绍与线性探测的实现

前言

学完了二叉树，我们要学当前阶段数据结构的最后一个内容了：哈希！！

引入

先来介绍两个用哈希封装的两个容器：unordered_map unordered_set

与map和set的不同：

• map/set是双向迭代器，而另外两个是单向的
• map/set有序，另外两个没有顺序

unordered_map

1. unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
3. 在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
6. 它的迭代器至少是前向迭代器。

哈希

哈希就是散列，
就是这些值key和存储位置之间存在着映射的关联关系

哈希函数

哈希函数的内容也就是一个哈希是如何设计的

哈希函数设计原则：

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

1. 直接定址法–(常用)
   取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

   • 优点：简单、均匀
   • 缺点：需要事先知道关键字的分布情况
   • 使用场景：适合查找比较小且连续的情况

2. 除留余数法–(常用)
   设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
   按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

3. 平方取中法–(了解)
   假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；
   再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
   平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

4. 折叠法–(了解)
   折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
   折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

5. 随机数法–(了解)
   选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。
   通常应用于关键字长度不等时采用此法

6. 数学分析法–(了解)
   设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。

说明

对于第一种方法的弊端很明显：
比如存两个值：1和1000，那我是不是要开1001个空间，空间太浪费了

我们用第二种方法，就能大大的节省空间

哈希碰撞

但还是有问题：
如果取余之后，有了同样的余数怎么办？？

对于两个数据元素的关键字$k_i$和 $k_j$(i != j)，有$k_i$ != $k_j$，但有：Hash($k_i$) == Hash($k_j$)，
即：**不同关键字通过相同哈希哈数计算出相同的哈希地址，**该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
发生哈希冲突该如何处理呢？

解决哈希冲突

补充：
哈希不会填满，到超过自己设定的负载因子的时候，会按照一定倍数扩容
负载因子/载荷因子 = 存进去的数据个数/表的大小
闭散列一般是0.7

闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。
那如何寻找下一个空位置呢？

基本结构

enum State
{
	EMPTY,//空
	EXIST,//存在
	DELETE//删除
};

template<class K, class V>
struct HashData
{
	pair<K, V>_kv;		//键值对
	State _state = EMPTY;	//初始为空
};
1
2
3
4
5
6
7
8
9
10
11
12
13

线性探测

从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

• 插入
  1. 先找到对应的位置
  2. 找到空位置或者遍历完停止查找（要注意循环到尾部的时候，下一个是头部）
     

	bool Insert(const pair<K, V>& kv)				
	//线性探测版本
	{
		if (Find(kv.first) == nullptr)
		{
			return false;
		}

		if (_n*10 / _tables.size() >= 7)
		{
			//方法2:比较神奇的写法
			HashTable<K, V>newHT(_tables.size() * 2);
			for (auto& e : _tables)
			{
				if (e._state == EXIST)
				{
					newHT.Insert(e._kv);
				}
			}
			_tables.swap(newHT._tables);
			//把新的交换给旧的
			//旧的还能自动释放
		}

		size_t hashi = kv.first % _tables.size();
		while (_tables[hashi]._state == EXIST)
		{
			hashi++;
			hashi %= _tables.size();
		}
		_tables[hashi]._kv = kv;
		_tables[hashi]._state = 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
33
34
35

• 查找

	HashData<const k, V>* Find(const K& key)
	{
		size_t hashi = key % _tables.size();
		while (_tables[hashi]._state != EMPTY)
		{
			if (key == _tables[hashi]._kv.first
				&& _tables[hashi]._state == EXIST)
			{
				return &_tables[hashi];
			}
			hashi++;
			hashi %= _tables.size();
		}
		return nullptr;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这里的返回值给指针是为了方便删除

• 删除
  采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影
  响。
  因此线性探测采用标记的伪删除法来删除一个元素。

// 哈希表每个空间给个标记
// EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
enum State{EMPTY, EXIST, DELETE};
1
2
3

	bool Erase(const K& key)
	{
		HashData<K, V>* ret = Find(key);
		if (ret)
		{
			ret->_state = DELETE;
			return true;
		}
		return false;
	}
1
2
3
4
5
6
7
8
9
10

• 扩容
  当超过负载因子的时候，我们就要扩容，
  但是，扩容之后，可能原来不冲突的冲突了。
  所以建议是：开一个新的空间来重新一一映射
  在此提供两种思路：

  开一个新空间，遍历旧表，将值给新表

			//方法1
			size_t newSize = _tables.size() * 2;
			vector<HashData>newTables(newSize);
			_tables.swap(newTables);
1
2
3
4

这种方法比较普通
1

这种方法更巧妙，每次插入新的值都去调用一次Insert，但是，是用扩容后的新表调用，所以不用再扩容，直接找到合适的位置存入即可，
并且交换新表和旧表

			//方法2:比较神奇的写法
			HashTable<K, V>newHT(_tables.size() * 2);
			for (auto& e : _tables)
			{
				if (e._state == EXIST)
				{
					newHT.Insert(e._kv);
				}
			}
			_tables.swap(newHT._tables);
			//把新的交换给旧的
			//旧的还能自动释放
1
2
3
4
5
6
7
8
9
10
11
12

优化1

我们要想一想：如果参数是string这种无法进行%运算的类型怎么办？
所以我们要增加一个模板参数，来讲他们转化成可以运算的整形

那么我们可以将每一位的ASCII码值分别乘以131，来作为关键码去取余，这个131来自BKDRHash函数，我们可以看这篇文章的分析

字符串哈希算法

	struct HashFuncString
	{
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (auto e : s)
			{
				hash += e;
				hash *= 131;
			}
	
			return hash;
		}
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

优化2

因为string经常作为key，所以我们可以进行特化

	// 特化
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (auto e : s)
			{
				hash += e;
				hash *= 131;
			}
			return hash;
		}
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这样就不用再单独去写一个HashFuncString函数了

二次探测

找下一个空位置的方法为：
$H_i$ = ($H_0$ + $i^2$ )% m, 或者：$H_i$ = ($H_0$ - $i^2$ )% m。其中：i = 1,2,3…， $H_0$是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。
也就是说，先对关键码进行加减运算，然后再取余

但是闭散列这种方式还是不够好

总结

闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。
下一篇文章将实现哈希桶。