hash表

哈希表是一种数据结构,它通过将键映射到存储桶或槽来快速查找数据。它的核心思想是通过一个哈希函数(Hash Function)将输入数据(键)转换为数组中的索引,以便在常数时间内进行查找、插入和删除操作。

哈希表的关键组成部分

  1. 哈希函数 (Hash Function):将输入的键(key)映射为哈希表的索引。理想的哈希函数应该均匀分布键,避免过多冲突。
  2. 存储桶 (Bucket):每个哈希表的槽位。如果两个不同的键通过哈希函数得到了相同的索引(称为哈希冲突),多个键可以通过链表或其他方式存储在同一个槽中。
  3. 哈希冲突 (Hash Collision):当不同的键映射到同一个存储桶时,发生冲突。常见的解决方法有:
    • 链地址法 (Separate Chaining):在每个槽中存储一个链表,冲突的键会被添加到链表中。
    • 开放地址法 (Open Addressing):通过重新计算索引(如线性探测、二次探测等),将冲突的键存储在下一个可用的槽位中。

哈希表的优缺点

优点:

  • 平均情况下,哈希表的查找、插入和删除操作都能在 O(1) 时间复杂度内完成。

缺点:

  • 当发生大量冲突时,查找和插入的性能可能退化到 O(n)
  • 哈希表的空间利用率不如树结构等其他数据结构高。

常见应用场景

哈希表常用于需要快速查找的场景,如数据库索引、缓存、字典等。

接下来我们将分别用开放定址法和哈希桶的方法来实现hash表

开放定址法实现hash表

首先我们在封装hash表之前要了解什么是负载因子。

负载因子 (Load Factor)

负载因子是指哈希表中已存储元素的数量与哈希表大小(存储桶数量)的比值,公式为:

α = n m \alpha = \frac{n}{m} α=mn

  • n:哈希表中已存储的元素数量。
  • m:哈希表的总存储桶(bucket)数量。

例如,如果哈希表有 100 个存储桶,已存储了 60 个元素,那么负载因子为:

α = 60 100 = 0.6 \alpha = \frac{60}{100} = 0.6 α=10060=0.6

负载因子的意义

  1. 负载因子越小:意味着哈希表中空槽越多,冲突(collisions)的概率越低,查找和插入操作的性能更好。
  2. 负载因子越大:意味着哈希表中存储的元素越来越多,冲突的概率增加,查找和插入操作的效率下降。

负载因子的影响

  • 如果负载因子过高(接近 1 或大于 1),冲突会变得频繁,导致性能下降。这时通常会进行再散列 (rehashing),即扩展哈希表的大小,并重新计算所有元素的哈希值。
  • 在一些常见的哈希表实现中,通常当负载因子超过一定的阈值(如 0.75)时,会触发再散列操作,以保证哈希表的操作性能。

再散列 (Rehashing)

当负载因子达到阈值时,哈希表会增大存储桶的数量(通常是倍增),并重新计算所有已存储元素的哈希值,将它们放入新的存储桶中。这一操作虽然代价较高,但可以避免长期的性能退化。

示例

假设一个哈希表的存储桶数量为 10:

  • 当插入 5 个元素时,负载因子为:

α = 5 10 = 0.5 \alpha = \frac{5}{10} = 0.5 α=105=0.5

  • 当插入 9 个元素时,负载因子为:

α = 9 10 = 0.9 \alpha = \frac{9}{10} = 0.9 α=109=0.9 此时可能需要进行再散列操作来扩展哈希表的大小。

整体框架

	//三种状态
	enum State
	{
		EXIST,//存在
		EMPTY,//空
		DELETE//删除
	};
	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		//初始状态是空
		State _state = EMPTY;
	};
	template<class K, class V>
	class HashTable
	{
	public:
	private:
		//用一个Hash表来存储
		vector<HashData<K, V>> _tables;
		//表中插入的数据个数
		size_t _n = 0;
	};

在开放定址法中,我们需要用一个状态来表示hash表中每个位置的状态,由于每个位置的状态不止两种,所以我们不能使用布尔值来表示每个位置的状态,应该使用enum来定义多种状态,我们定义三种状态(EMPTY,EXIST,DELETE)分别表示空,存在,删除。
在HashTables中_n表示hash表中插入了多少个数。
接下来我们来封装insert

insert

bool Insert(const pair<K, V>& kv)
{
	//去冗余
	if (Find(kv.first))
	{
		return false;
	}
	//扩容,通过负载因子来进行扩容
	if (_n * 10 / _tables.size() == 7)//负载因子为0.7的时候进行扩容
	{
		//不能直接进行resize,因为扩容之后空间变化了,映射也要跟着变化
		//创建一个新表是以前表的二倍
		HashTable<K, V>  newHT;
		newHT._tables.resize(_tables.size() * 2);
		for (size_t i = 0;i < _tables.size();i++)
		{
			if (_tables[i]._state == EXIST)
			{
				//直接复用insert
				//这里不是自己调用自己,因为这里是两个对象
				newHT.Insert(_tables[i]._kv);
			}
		}
		_tables.swap(newHT._tables);
	}
	Hash hs;
	//算起始位置
	size_t hashi = hs(kv.first) % _tables.size();
	//状态存在则继续
	while (_tables[hashi]._state == EXIST)
	{
		hashi++;
		//防止hashi越界
		hashi %= _tables.size();
	}
	//添加值并且状态改为存在
	_tables[hashi]._kv = kv;
	_tables[hashi]._state = EXIST;
	_n++;
	return true;
}

【C++进阶】hash表的封装-LMLPHP
要进行插入我们首先需要找到插入位置,假如当我们找到位置的时候,当前位置已经被占据了,所以我们只能向后移动。
【C++进阶】hash表的封装-LMLPHP
插入的及基本逻辑经济就是如此,既然有插入那肯定有插入位置满的时候,所以插入逻辑中应该涉及到扩容,但是我们不能直接进行扩容,因为当我们扩容的时候,每个data的映射的位置也会随之而变化,这就涉及到我们应该找到新的映射位置,但是对于开放定址法来说,我们不是在插入位置满的时候扩容,而是在负载因子到达0.7的时候进行扩容。
【C++进阶】hash表的封装-LMLPHP
在扩容的时候,我们可以直接创建一个新表,然后在新表中重新映射数据,这里我们可以直接复用insert。(注意:这里调用的不是同一个insert,因为是两个不同的对象)

Find

HashData<K, V>* Find(const K& key)
{
	Hash hs;
	//算起始位置
	size_t hashi = hs(key) % _tables.size();
	//状态存在则继续
	while (_tables[hashi]._state != EMPTY)
	{
		//这个状态不是DELETE才能进行查找
		if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
		{
			return &_tables[hashi];
		}
		hashi++;
		//防止hashi越界
		hashi %= _tables.size();
	}
	return nullptr;
}

对于查找来说我们只需要找到当前需要查找的数据的所在的位置,然后从查找的位置对这个表进行遍历,如果遇到和当前值相等的则直接返回当前位置的地址,需要注意的是:我们还要考虑状态,当状态是DELETE的时候,但是当前值又等于查找的值,这个值是不能返回的,因为当前值已经删除了,所以这种情况需要排除,所以前面需要添加一个判断条件。

erase

bool Erase(const K& key)
{
	//找到删除位置
	HashData<K, V>* ret = Find(key);
	if (ret)
	{
		ret->_state = DELETE;
		return true;
	}
	return false;
}

对于删除某个值,我们首先需要查找,所以这里我们可以复用查找,用HashData<K,V>接收一下,如果当前指针是空指针就直接返回false,说明需要删除的值没在表中,如果当前指针不是空指针,则将状态设置为DELETE状态。

hash桶封装

框架

template<class K,class V>
struct HashNode
{
	pair<K,V> _kv;
	HashNode<T>* _next;
	HashNode(const pair<K,V>& kv)
		:_kv(kv)
		,_next(nullptr)
	{}
};
template<class K, class V>
class HashTable
{
public:
	typedef HashNode<K,V> Node;
private:
	//hash桶
	//hash桶当中的Node节点是new出来的,需要写析构函数
	vector<Node*> _tables;
	//表中存储的数据个数
	size_t _n = 0;
};

用hash桶来封装hash表我们需要一个结构体,结构体中包含指向下一个结构体的指针,还有一个存放数据的kv。
在HashTable中我们需要一个vector,这个vector的类型是Node*,相当于存放的是指针。
【C++进阶】hash表的封装-LMLPHP
上述代码描述的结构就是上面这种结构。

insert

bool Insert(const pair<K,V>& kv)
{
	if (Find()) {
		return false;
	}
	//找到插入的位置

	size_t hashi = kv.first % _tables.size();
	//需要控制负载因子,hash桶的负载因子需要控制在1
	if (_n == _tables.size())
	{

		vector<Node*> newtables(_tables.size() * 2, nullptr);
		for (size_t i = 0;i < _tables.size();i++)
		{
			//将旧表中的节点进行复用,头插
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;
				//重新计算插入位置
				size_t hashi = cur->_kv.first % newtables.size();
				cur->_next = newtables[hashi];//先指向第一个
				newtables[hashi] = cur;//然后再成为第一个
				cur = next;
			}
			_tables[i] = nullptr;
		}
		_tables.swap(newtables);
	}
	//头插,尾插也可以,但是尾插需要找到尾,所以这里我们选择头插不用找尾
	Node* newnode = new Node(kv);
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	_n++;
	return true;
}

对于插入来说,我们可以直接算出插入位置,然后在当前桶中进行头插,为什么进行头插而不进行尾插呢?
因为头插可以直接插,而尾插则需要找到尾之后才能插入,大大影响了我们的插入效率,所以我们进行头插。
插入的逻辑说完之后,,我们也要扩容,对于hash桶实现hash表来说,我们的扩容的前提是当每个_n== 1的时候,意思就是每个桶都有一个节点的时候,_n==1的时候最好的情况是每个桶有一个节点,,这个情况的前提就是保证每个桶都有节点。

如果我们直接扩容的话也不是不行,但是会很浪费我们的空间,所以我们可以不释放当前节点,直接把旧表的节点插入到新表映射的位置上去,就不用浪费空间了。

find

Node* Find(const K& key)
{
	size_t hashi = key % _tables.size();
	Node* cur = _tables[hashi];
	while (cur)
	{
		if (cur->_data == key)
		{
			return cur
		}
		cur = cur->_next;
	}
	return nullptr;
}

对于查找来说直接找到映射位置遍历hash桶即可。

erase

bool Erase(const K& key)
{
	size_t hashi = key % _tables.size();
	Node* cur = _tables[hashi];
	Node* prev = nullptr;
	while (cur)
	{
		if (cur->_data == key)
		{
			if (prev == nullptr)
			{
				_tables[hashi] = cur->_next;
			}
			else
			{
				prev->_next = cur->_next;
			}
			delete cur;
			_n--;
			return true;
		}
		prev = cur;
		cur = cur->_next;
	}
	return false;
}

对于删除的逻辑我们先找到映射位置,然后先定义一个prev标记前一个指针,然后遍历当前桶,如果当前位置的值和需要删除的值相同,则可以分出两种情况,第一种情况是头删,头删就说明prev是nullptr,则可以直接令头指针等于下一个节点,如果是删除中间的,则可以令prev指向cur的下一个节点,然后释放当前节点,注意:释放当前节点的时候需要_n—。

~HashTable()

因为每个节点都是我们new出来的,所以需要我们手动释放,所以写一个析构函数,释放每个节点,遍历每个桶逐个释放

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

总结

通过对哈希表的封装,我们不仅提升了代码的可读性和复用性,还通过合理设计哈希函数和处理冲突机制,优化了哈希表的性能。封装让我们可以将底层的细节隐藏起来,提供一个简洁高效的接口,便于后续在项目中的使用。在实际开发中,理解负载因子、再散列等概念,并针对具体场景合理调整这些参数,能够确保哈希表在性能和内存占用上的平衡。掌握了这些知识后,相信你能够更加自信地在复杂应用中使用哈希表。

09-09 03:33