• 数据结构篇【4】——哈希（散列）线性探测实现

    哈希

    构造一种存储结构，通过某种函数（hashFunc）使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。最理想的情况是可以不经过任何比较，一次直接从表中得到要搜索的元素。

    • 插入元素 根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
    • 搜索元素 对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
      这样的方式即为哈希（散列）方法，哈希方法中使用的转换函数称为哈希（散列）函数，构造出来的结构称为哈希（散列）表（Hash Table）

    哈希冲突

    对于两个数据元素的关键字ki和kj(i != j),有ki != kj,但有Hash(ki) == Hash(kj)，即：不同关键字通过相同哈希函数计算出相同的哈希地址，这种现象称为哈希冲突或哈希碰撞。
    把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

    哈希函数

    引起哈希冲突的一个原因可能是：哈希函数设计不够合理。哈希函数设计原则：

    • 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有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）作为哈希地址，平方取中法比较适合不知道关键字的分布，而位数又不是很大的情况

    哈希冲突的解决方法

    解决哈希冲突有两种常见的方法：闭散列和开散列

    闭散列

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

    1. 线性探测
      在这里插入图片描述
      如上图所示，现在我们想在哈希表中插入44，那么通过求余数我们发现44应该在下标为4的位置上，但这个位置已经被4占据，因此44应该不断向后查找一个空余的位置，在这里一直到8号下标才找到空余位置
    2. 二次探测
      线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：Hi = (H0 + i2) % m，计算得到的位置，m是表的大小。照这样的思路，上面的例子中要插入的44的位置就应该这样去找，先找下标为(4 + 12) % 10的位置，此位置被占，继续找4后第(4 + 22) % 10个位置，此位置没被占，下标为8。
      研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不用考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。
      接下来我们先用代码来实现一个线性探测的哈希，首先我们来创建哈希表中存储元素的类,
    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

    哈希表中存储的元素包含两部分，分别是KeyValue对和该位置此时的状态，首先将_status赋默认值EMPTY，这样可以在HashTable在建立时自动初始化。
    下一步我们要考虑如何把key值转化为可以取模的整型，key值可以有多种类型，比如int，string等，当我们得到的数据是int时可以直接进行取模，但是如果传入的key值是string类型，那么我们就需要对这些类型进行特殊的转换，因此我们还需要设计对应的哈希函数来处理这些key值

    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

    这段代码中我们给传入的key值创建的默认哈希函数是直接返回key值，对应于整形，而对于string类型我们进行了特化处理，将它也转化为一个整型。
    接着我们来看看HashTable的基本框架，

    template<class K, class V, class HashFunc = Hash<K>>
	class HashTable
	{
	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;
	};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    我们不需要给HashTable类设计构造函数，因为我们在创建成员变量_n时已经给它赋初始值0，因此在初始化列表会自动给他初始化，而对于_tables，他会自动调用HashData的构造函数，而和_n相同的的原理，_status也会在初始化列表中被自动赋初值。
    接下来就要开始实现接口了，首先我们来看看Find如何实现，

    		HashData<K, V>* Find(const K& key)
		{
			// 必须检查表的大小是否为0，否则在
			// 之后的代码会出现除数为0的错误
			if (_tables.size() == 0)
			{
				return nullptr;
			}

			HashFunc hf;
			size_t start = hf(key) % _tables.size();
			size_t i = 0;
			size_t index = start;
			// 当元素为空时还未找到目标值就说明表中无目标值
			// 若元素的状态为DELETE时应该继续向后查找
			while (_tables[index]._status != EMPTY)
			{
				if (_tables[index]._kv.first == key && _tables[index]._status == EXIST)
				{
					return &_tables[index];
				}
				++i;
				index = start + i;
				index %= _tables.size();
			}
			return nullptr;
		}

    • 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

    接下来我们先实现Erase接口，

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

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

    当我们删除元素时不应该直接将元素删除，而是用一个特殊标记(DELETE)来表明该元素已被删除，因为我们查找元素失败的判断标志就是是否碰到空位置，因此直接删除元素会导致在之后查找元素时碰到问题。
    最后我们来看看如何实现Insert接口，

    		bool Insert(const pair<K, V>& kv)
		{
			// 如果已有该元素则插入失败
			HashData<K, V>* ret = Find(kv.first);
			if (ret)
			{
				return false;
			}
			// 负载因子到0.7，就扩容
			if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
			{
				// 扩容
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				HashTable<K, V, HashFunc> newHT;
				newHT._tables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._status == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(newHT._tables);
			}
			HashFunc hf;
			size_t start = hf(kv.first) % _tables.size();
			size_t i = 0;
			size_t index = start;
			while (_tables[index]._status == EXIST)
			{
				++i;
				index = start + i;
				index %= _tables.size();
			}
			_tables[index]._kv = kv;
			_tables[index]._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
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    这样我们就完成了线性探测的哈希表，下面是完整的代码

    HashTable

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

namespace ssj
{
	enum Status
	{
		EXIST,
		EMPTY,
		DELETE
	};

	template <class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		Status _status = EMPTY;
	};
	
	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
			{
				--_n;
				ret->_status = DELETE;
				return true;
			}
		}

		HashData<K, V>* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}

			HashFunc hf;
			size_t start = hf(key) % _tables.size();
			size_t i = 0;
			size_t index = start;
			while (_tables[index]._status != EMPTY)
			{
				if (_tables[index]._kv.first == key && _tables[index]._status == EXIST)
				{
					return &_tables[index];
				}
				++i;
				index = start + i;
				index %= _tables.size();
			}
			return nullptr;
		}

		bool Insert(const pair<K, V>& kv)
		{
			HashData<K, V>* ret = Find(kv.first);
			if (ret)
			{
				return false;
			}
			// 负载因子到0.7，就扩容
			if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
			{
				// 扩容
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				HashTable<K, V, HashFunc> newHT;
				newHT._tables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._status == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(newHT._tables);
			}
			HashFunc hf;
			size_t start = hf(kv.first) % _tables.size();
			size_t i = 0;
			size_t index = start;
			while (_tables[index]._status == EXIST)
			{
				++i;
				index = start + i;
				index %= _tables.size();
			}
			_tables[index]._kv = kv;
			_tables[index]._status = EXIST;
			++_n;
			return true;
		}

	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;
	};
}

    • 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
  • 相关阅读:
    制作OpenCV相机标定板棋盘格图像
    SpringCloud微服务---Nacos配置中心
    【tio-websocket】12、应用层包—Packet
    HICO-DET：适合踏入 HOI detection 领域的初学者阅读的论文......
    Future和CompletableFuture
    [UE虚幻引擎插件介绍] DTSQLite 插件说明 ：蓝图操作SQLite3文件，执行SQL语句。
    SNMP协议架构与操作类型
    sys文件系统
    解决：给 VSCode 手动添加(解压压缩包)相关插件的问题
    【无标题】
  • 原文地址：https://blog.csdn.net/JayceSun/article/details/125434261