• 哈希-闭散列

    哈希

    哈希的概念

    顺序结构以及平衡树中，元素关键字与其储存位置并没有对应的关系，因此在查找一个元素的时候，即使是平衡树中也需要经过多次比较。顺序查找的时间复杂度为O(N)，平衡树查找一个元素的时间复杂度为O(log2N),N为树的高度。那么有没有更快的方式，甚至让时间复杂度可以达到常数级别的呢？
    因此，理想的搜索方法是可以不进行任何比较，一次直接从表中得到想要搜索的元素。通过某种函数使得元素的存储位置和他的关键字之间能够建立起一一映射的关系，那么在查找时通过该函数可以很快找到该元素。于是便有了哈希这个存储数据的方法。哈希方法中使用的转换函数被称为哈希函数，构造出来的结构被称为哈希表

    哈希函数

    如果把哈希函数设置为：hask(key) = key % capacity。这里的capacity是存储元素空间的总大小，如果用vector来进行存放，那么其实这里的capacity实际上是vector数组的size大小。用这个方法来存放如下数据集合：{1，3，6，4，5，2}
    在这里插入图片描述
    用该方法来存放数据，在搜索数据的时候不需要再顺序遍历或者进行关键字的比较，根据哈希函数便可以快速确定位置，因此搜索速度会比较快。

    常见的哈希函数

    直接定值法

    取关键字的某个线性函数为散列地址：Hash(Key) = A*Key + B，这种哈希函数优点是简单均匀，缺点是需要事先知道关键字的分布情况

    除留余数法

    除留余数法是比较常用的方法。散列中存储的最大空间为m，取一个不大于m，但最接近或者等于m的数作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

    平法取中法

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

    折叠法

    折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。

    哈希冲突

    但是使用哈希来存放数据也不是没有缺点的，哈希函数为hask(key) = key % capacity这种情况下，如果存放数据集合{1，11，21，31，2，12，22}这样的情况，他们通过哈希函数算出来的结果出现很多重复，计算出了相同的哈希地址。这种现象就被称为哈希冲突或者哈希碰撞，那么该如何处理哈希冲突呢？
    解决哈希冲突的两种常见的方法是：闭散列和开散列

    闭散列

    闭散列又叫做开放定址法。他的做法是当发生哈希冲突的时候，如果哈希表未被填满，说明哈希表中还有空位置，那么就可以把数据放到冲突位置的“下一个”空位置去。这个下一个空位置有两种选取方式。

    线性探测

    闭散列寻找下一个空位置，其中一种方法就是使用线性探测，线性探测原理很简单，从冲突位置开始，依次向后找，直到找到下一个空位置为止。
    线性探测插入数据代码如下：这里是简单的线性探测插入代码，主要是体现了线性探测插入时，是从发生冲突位置开始依次向后寻找空位置的情况。但是实际插入的时候需要考虑是否存在重复以及是否需要扩容等问题，这些在后面的代码中会进行实现。

    	bool Insert(const pair<K, V>& _kv)//插入数据
	{
		size_t start = _kv.first % _table.size();//计算起始位置
		size_t i = 0;
		size_t index = start + i;
		while (_table[index]._status == EXIST)
		{
			i++;
			index = start + i;
			index %= _table.size();
		}
		_table[index]._kv = kv;
		_table[index]._status = EXIST;
		_n++;
		return true;

	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    显然这样看起来线性探测存在不足的情况：如果一旦发生哈希冲突，并且所有的冲突连在一起，容易产生数据的堆积，不同的关键字占据了可利用的空位置导致其他原本处于该位置的代码需要经过多次比较重新找位置，效率会比较低。

    二次探测

    为了改善线性探测这个缺点，于是有了二次探测这种解决哈希冲突的方法。二次探测顾名思义就是使用2次方。与线性探测不同，他在寻找下一个空位置的时候，是通过该式子来进行的:Hash= (index +i^2 )% m，这样一来就不会出现连续的冲突的哈希位置，一定程度上避免了堆积的情况。他的代码实现如下：唯一的区别就是在于找哈希地址的时候，寻找的间隔变为了平方。

    	bool Insert(const pair<K, V>& _kv)//插入数据
	{
		size_t start = _kv.first % _table.size();//计算起始位置
		size_t i = 0;
		size_t index = start + i;
		while (_table[index]._status == EXIST)
		{
			i++;
			index = start + (i * i);
			//index = start + i;
			index %= _table.size();
		}
		_table[index]._kv = kv;
		_table[index]._status = EXIST;
		_n++;
		return true;

	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    载荷因子

    但是不管是连续探测还是二次探测，都存在一个问题。如果哈希表内存放的数据过多，那么他在寻找空位置的时候，消耗也就越大，甚至在二次探测的过程中可能出现死循环的情况。那么哈希表中出现了一个新的概念：载荷因子（α）又可以叫做负载因子。他被定义为哈希表中的元素个数/哈希表的总容量。α越大，填入表中的元素越多，产生冲突的可能性越大，α越小，表明填入表中的元素越少，产生冲突的可能性越小，效率越高，空间浪费越多。一般载荷因子需要控制在0.7-0.8以下。如果载荷因子超过了规定为大小，那么就要对哈希表进行扩容，扩容代码如下：

    		if (_n * 10 / _table.size() >= 7)//如果载荷因子大于0.7就要进行扩容
		{
			size_t newCapacity = _table.size() == 0 ? 10 : _table.size() * 2;
			//1、方法1：
			//vector> newTables;
			//newTables.resize(newCapacity);//给新表开辟空间
			//for (size_t i = 0; i < _table.size(); i++)
			//{
			//	//遍历原表，将原表的数据放入新表当中
			//	if (_table[i]._status == EXIST)
			//	{
			//		size_t start = _table[i]._kv.first % newTables.size();
			//		size_t i = 0;
			//		size_t index = start + i;
			//		while (newTables[index]._status == EXIST)
			//		{
			//			i++;
			//			index = start + (i * i);
			//			index %= newTables.size();
			//		}
			//		newTables[index]._kv = _table[i]._kv;
			//		newTables[index]._status = EXIST;
			//	}
			//}
			//_table.swap(newTables);//交换
			//方法2：
			HashTable<K, V> newTables;
			newTables._table.resize(newCapacity);
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i]._status == EXIST)
				{
					newTables.Insert(_table[i]._kv);
				}
			}
			_table.swap(newTables._table);

		}

    • 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

    哈希中的扩容不能直接进行扩容，因为哈希表的长度发生变化的话，会导致映射也会发生变化，因此需要进行处理。这里有两种处理方式

    1. 遍历原表，将原表中的数据，按照newSize映射到新表，然后swap交换
    2. 新建一个哈希表，将新哈希表中的数组设置为新的大小，遍历原表的数组，如果数组中元素状态为存在则将他插入到新表，最后进行交换，具体实现可以参考如上代码。

    去重

    哈希作为unordered_map的底层实现方式，它本身需要具有去重的功能，因此需要实现一个Find函数，在插入前先进行判断哈希表中是否已经存在了该元素。代码实现如下：

    	HashData<K, V>* Find(const K& key)
	{
		if (_table.size() == 0)
		{
			return nullptr;
		}
		size_t start = key % _table.size();
		size_t i = 0;
		size_t index = start + i;
		while (_table[index]._status != EMPTY)
		{
			if (_table[index]._kv.first == key && _table[index]._status != DELETE)
			{
				return &_table[index];
			}
			i++;
			index = start + i;
			index %= _table.size();
		}
		return nullptr;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    删除

    采用闭散列处理哈希冲突的时候，不能随便删除哈希表中已有的元素，直接删除会影响后面元素的插入与查找，因此可以使用状态法来标记哈希表中数据的状态，例如：在每个哈希数据中加上描述状态的枚举类型即可很好解决这个问题

    enum Status//哈希地址状态
{
	EXIST,
	EMPTY,
	DELETE
};



template<class K,class V>
struct HashData
{
	pair<K, V> _kv;
	Status _status = EMPTY;
};


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    删除函数如下：

    	bool Erase(const K& key)
	{
		HashData<K, V>* ret = Find(key);
		if (ret == nullptr)
		{
			return false;
		}
		else
		{
			ret->_status = DELETE;
			_n--;
			return ture;
		}
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    处理其他类型的数据

    目前实现的该哈希算法只能处理正整数，如果遇到字符串或者自定义类型的数据则没办法对其进行处理计算。因此为了支持广泛类型的数据，可以通过给哈希类添加一个仿函数，让他可以处理不同的类型。例如处理字符串仿函数代码如下：这里通过模板的特化来实现哈希处理字符串的情况。

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


template<>
struct Hash<string>
{
	size_t operator()(const string& s)
	{
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    最后，闭散列解决哈希冲突的总体实现以及测试案例代码如下：

    #include
#include


using namespace std;

enum Status//哈希地址状态
{
	EXIST,
	EMPTY,
	DELETE
};



template<class K,class V>
struct HashData
{
	pair<K, V> _kv;
	Status _status = EMPTY;
};

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


template<>
struct Hash<string>
{
	size_t operator()(const string& s)
	{
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}
};

template<class K,class V, class HashFunc = Hash<K>>
class HashTable
{
public:
	bool Erase(const K& key)
	{
		HashData<K, V>* ret = Find(key);
		if (ret == nullptr)
		{
			return false;
		}
		else
		{
			ret->_status = DELETE;
			_n--;
			return true;
		}
	}

	HashData<K, V>* Find(const K& key)
	{
		if (_table.size() == 0)
		{
			return nullptr;
		}
		HashFunc hf;
		size_t start = hf(key) % _table.size();
		size_t i = 0;
		size_t index = start + i;
		while (_table[index]._status != EMPTY)
		{
			if (_table[index]._kv.first == key && _table[index]._status == EXIST)
			{
				return &_table[index];
			}
			i++;
			index = start + i * i;
			index %= _table.size();
		}
		return nullptr;
	}


	bool Insert(const pair<K, V>& kv)//插入数据
	{
		HashData<K, V>* ret = Find(kv.first);
		if (ret)
		{
			return false;
		}
		if (_table.size() == 0 || _n * 10 / _table.size() >= 7)//如果载荷因子大于0.7就要进行扩容
		{
			size_t newCapacity = _table.size() == 0 ? 10 : _table.size() * 2;
			//1、方法1：
			//vector> newTables;
			//newTables.resize(newCapacity);//给新表开辟空间
			//for (size_t i = 0; i < _table.size(); i++)
			//{
			//	//遍历原表，将原表的数据放入新表当中
			//	if (_table[i]._status == EXIST)
			//	{
			//		size_t start = _table[i]._kv.first % newTables.size();
			//		size_t i = 0;
			//		size_t index = start + i;
			//		while (newTables[index]._status == EXIST)
			//		{
			//			i++;
			//			index = start + (i * i);
			//			index %= newTables.size();
			//		}
			//		newTables[index]._kv = _table[i]._kv;
			//		newTables[index]._status = EXIST;
			//	}
			//}
			//_table.swap(newTables);//交换
			//方法2：
			HashTable<K, V> newTables;
			newTables._table.resize(newCapacity);
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i]._status == EXIST)
				{
					newTables.Insert(_table[i]._kv);
				}
			}
			_table.swap(newTables._table);

		}
		HashFunc hf;
		size_t start = hf(kv.first) % _table.size();//计算起始位置
		size_t i = 0;
		size_t index = start + i;
		while (_table[index]._status == EXIST)
		{
			i++;
			index = start + (i * i);
			//index = start + i;
			index %= _table.size();
		}
		_table[index]._kv = kv;
		_table[index]._status = EXIST;
		_n++;
		return true;

	}
private:
	vector<HashData<K,V>> _table;
	int _n;//统计元素个数
};


void TestHash()
{
	HashTable<int, int> test;
	int arr[] = { 2,12,22,32,42,52,62,72 };
	for (auto e : arr)
	{
		test.Insert(make_pair(e, e));
	}
	cout << test.Find(12) << endl;
	cout << test.Find(22) << endl;
	cout << test.Find(72) << endl;
	cout << test.Find(2) << endl;


}


void TestHash1()
{
	HashTable<string, string,Hash<string>> test;
	test.Insert(make_pair("sort", "排序"));
	test.Insert(make_pair("string", "字符串"));
	cout << test.Find("sort") << endl;
}

    • 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
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
  • 相关阅读:
    Python 程序的输出 | 第十套（异常处理）
    kafka----5
    ok-解决qt5发布版本，直接运行exe缺少各种库的问题
    基于slate构建文档编辑器
    vue3+ts+uniapp实现小程序端input获取焦点计算上推页面距离
    Ban or Pick, What‘s the Trick
    C++如何监控键盘输入输出
    Linux下使用lookbusy加载cpu负载
    47、以Orienmask实例分割算法为例子，学习TensorRT的Python和C++开发
    Java CountDownLatch 学习总结
  • 原文地址：https://blog.csdn.net/h1091068389/article/details/126180125