文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >链地址法：哈希表高效冲突解决之道

链地址法：哈希表高效冲突解决之道

作者头像
用户11831438
发布于 2025-12-30 13:21:59
发布于 2025-12-30 13:21:59
1480
举报
3.3 链地址法

在上面所学的开放地址法中，是将所有元素都放在哈希表中，但是对于链地址而言并不是这样——

链地址法中所有的元素不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射的这个位置，这个指针为空；有多个数据映射到这个位置时，我们把这些冲突的数据链接成一个链表，挂在哈希表相应映射的位置下面

——链地址法也叫做拉链法或者哈希桶

在开放地址法中，我们的vector就是一个存放一个结构体（数据+该位置的状态），但是在链地址法中，我们vector就是一个存放指针的数组——指针数组，指针是指向链表第一个节点的指针

ok，既然是这样的话，我们就可以快速的写出链地址法的哈希表结构——

3.3.1 链地址法结构解析：指针数组与链表的结合
代码语言：javascript
复制
template<class k, class v>
struct HashNode
{
	pair<k, v> _kv;//存储数据
	HashNode<k, v>* _next;
};
template<class k,class v>
class HashTable
{
	typedef HashNode<k, v> node;
private:
	vector<node*> _table;
	size_t _n;//存入数据个数
};

注意：vector<node*> _table; 也可以复用list，vector<list<k,v>> _table;但是后面会有点麻烦！！！

3.3.2 核心操作：元素的插入
3.3.2.1 空间足够，寻找映射位置，插入到相应链表中

ok，这个还是比较简单的~

代码语言：javascript
复制
//插入
bool insert(const pair<k, v>& kv)
{
	//算出kv要映射的位置
	size_t hashi = kv.first% _table.size();
	node* newnode = new node(kv);
	newnode->_next = _table[hashi];
	_table[hashi] = newnode;
	++_n;
	return true;
}

那当我们不断的插入，插入……总会有满的时候，那这个时候我们就需要进行扩容操作~

3.3.2.2 空间不够，扩容机制

对于链地址法而言，当负载因子=1的时候，也就是说插入数据个数=空间大小，我们就要进行扩容操作。

那这里的扩容还可以按照上面的新创建一个哈希表的方法吗？

ok，这种方法在这里的效果不是很好，当底层的vector交换后，newtable是一个局部对象，局部对象出了作用域就要调用相应的析构函数，vector中有析构函数，可以析构vector，但是vector里面的每个数据类型是内置类型，内置类型没有析构函数的概念，vector释放后，这些节点没有释放

所以交换后，应该先释放节点，再释放vector

这样做好像有点麻烦，需要申请空间，然后再去释放空间，有点浪费

ok，那我们就可以用一种既不new，也不delete的方法，可以直接把旧表的链表中每个节点直接拿下来，重新映射到新的vector中——

当使用除法散列法时，建议M取不太接近2的整数次幂的一个质数（素数）

对于这个问题，我们写出这样一个函数：

代码语言：javascript
复制
//使用下面的函数就可以实现了建议M取不太接近2的整数次幂的一个质数（素数）
//以保证key的每一位2进制都参与运算
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
  53,         97,         193,       389,       769,
  1543,       3079,       6151,      12289,     24593,
  49157,      98317,      196613,    393241,    786433,
  1572869,    3145739,    6291469,   12582917,  25165843,
  50331653,   100663319,  201326611, 402653189, 805306457,
  1610612741, 3221225473, 4294967291
};

inline unsigned long __stl_next_prime(unsigned long n)
{
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	// >= n
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}
  • 插入完整代码：
代码语言：javascript
复制
//使用下面的函数就可以实现了建议M取不太接近2的整数次幂的一个质数（素数）
//以保证key的每一位2进制都参与运算
	static const int __stl_num_primes = 28;
	static const unsigned long __stl_prime_list[__stl_num_primes] =
	{
	  53,         97,         193,       389,       769,
	  1543,       3079,       6151,      12289,     24593,
	  49157,      98317,      196613,    393241,    786433,
	  1572869,    3145739,    6291469,   12582917,  25165843,
	  50331653,   100663319,  201326611, 402653189, 805306457,
	  1610612741, 3221225473, 4294967291
	};

	inline unsigned long __stl_next_prime(unsigned long n)
	{
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list + __stl_num_primes;
		// >= n
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}
	template<class k, class v>
	struct HashNode
	{
		pair<k, v> _kv;//存储数据
		HashNode<k, v>* _next;
		HashNode(const pair<k,v>& kv)
			:_kv(kv)
			,_next(nullptr)
		{}
	};
	template<class k,class v>
	class HashTable
	{
		typedef HashNode<k, v> node;
	public:
		HashTable()
			:_table(__stl_next_prime(1))
			,_n(0)
		{}
		//插入
		bool insert(const pair<k, v>& kv)
		{	
			//不允许插入相同的key
			if (find(kv.first))
			{
				return false;
			}
			if (_n == _table.size())
			{
				//扩容
				////新创建一个哈希表
				//HashTable<k, v> newtable;
				//newtable._table.resize(2 * _table.size());
				////遍历旧表，将旧表中的数据插入到新表中
				//for (size_t i = 0; i < _table.size(); i++)
				//{
				//	node* cur = _table[i];
				//	while (cur)
				//	{
				//		newtable.insert(cur->_kv);
				//		cur = cur->_next;
				//	}
				//}
				//_table.swap(newtable._table);

				//创建一个新的vector
				vector<node*> newtable(__stl_next_prime( _table.size()+1));
				for (size_t i = 0; i < _table.size(); i++)
				{
					node* cur = _table[i];
					//将节点一个一个重新映射到新表中
					while (cur)
					{
						//记录旧表链表的下一个节点
						node* next = cur->_next;
						size_t hashi = cur->_kv.first % newtable.size();
						cur->_next = newtable[hashi];
						newtable[hashi] = cur;
						cur = next;
					}
					_table[i] = nullptr;
				}
				_table.swap(newtable);
			}
			//算出kv要映射的位置
			size_t hashi = kv.first% _table.size();
			node* newnode = new node(kv);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			++_n;
			return true;
		}
	private:
		vector<node*> _table;
		size_t _n;//存入数据个数
	};
3.3.3 核心操作：基于键的快速查找

查找步骤

  1. 计算哈希地址：
    • 根据给定的关键字（Key），使用选定的哈希函数 H(Key) 进行计算。
    • 得到结果即为该关键字对应的哈希地址（桶的索引）。假设为 index = H(Key)。
  2. 定位到对应的链表：
    • 根据计算出的 index，找到哈希表中该位置存储的链表头指针。
    • 如果该位置为 NULL 或 nullptr，说明此桶为空链，查找失败，直接进入步骤4。
  3. 遍历链表进行顺序查找：
    • 从链表的第一个节点（头结点）开始，依次将节点的关键字与待查找的关键字 Key 进行比较。
    • 如果相等：查找成功，返回该节点中存储的完整数据（或指向该节点的指针）。
    • 如果不相等：移动到链表中的下一个节点，继续比较。
    • 重复此过程，直到遍历完整个链表。
  4. 得出查找结果：
    • 成功：在链表中找到了匹配的节点，返回相关信息。
    • 失败：遍历完整个链表仍未找到匹配项，返回“未找到”的提示（如 NULL 或特定错误码）。
  • 代码演示：
代码语言：javascript
复制
node* find(const k& key)
{
	//计算出key映射的位置
	size_t hashi = key % _table.size();
	//到相应的映射位置下的链表中查找
	node* cur = _table[hashi];
	while (cur)
	{
		if (cur->_kv.first == key)
		{
			return cur;
		}
		cur = cur->_next;
	}
	return nullptr;
}
3.3.4 核心操作：基于键的快速删除
  • 步骤：

先计算出键的映射位置，找到挂在映射位置下的链表，然后去链表中查找到相应的键，改变删除键的前一个节点（prev）的next指针指向，指向删除键的后一个节点，然后删除要删除的键；如果prev为空，说明要删除的键就在第一个节点中，让删除键的后一个节点成为新的头节点，然后删除

  • 代码演示：
代码语言：javascript
复制
bool erase(const k& key)
{
	//计算出key映射的位置
	size_t hashi = key % _table.size();
	//到相应的映射位置下的链表中查找然后删除
	node* cur = _table[hashi];
	//记录删除节点的前一个节点
	node* prev = nullptr;
	while (cur)
	{
		if (cur->_kv.first == key)
		{
			//删除
			if (prev == nullptr)
			{
				//第一个节点就是删除节点
				_table[hashi] = cur->_next;
			}
			else
			{
				prev->_next = cur->_next;
			}
			delete cur;
			cur = nullptr;
			--_n;
			return true;
		}
		prev = cur;
		cur = cur->_next;
	}
	return false;
}

这……就完了吗？其实还没有

3.3.5 将关键字转为整数

上面所写的是关键字可以取模的（也就是关键字可以转成整型），那关键字不能取模呢（也就是关键字不能转成整型）？我们可以写个函数模板，让这个函数模板作为第三个模板参数，用来将关键字转换成整型，并特化出一个针对于string的函数——

代码语言：javascript
复制
//将不能进行取模的key转换成整型，以便取模
template<class k>
struct hashFunc
{
	size_t operator()(const k& key)
	{
		return size_t(key);
	}
};
//上面的函数模板还是不能将string转换成整型，我们可以特化一下
template<>
struct hashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto& e : s)
		{
			hash += e;
			hash *= 131;
		}
		return hash;
	}
};

更详细请看：

  • 完整代码：
代码语言：javascript
复制
namespace hash_bucket
{
//使用下面的函数就可以实现了建议M取不太接近2的整数次幂的一个质数（素数）
//以保证key的每一位2进制都参与运算
	static const int __stl_num_primes = 28;
	static const unsigned long __stl_prime_list[__stl_num_primes] =
	{
	  53,         97,         193,       389,       769,
	  1543,       3079,       6151,      12289,     24593,
	  49157,      98317,      196613,    393241,    786433,
	  1572869,    3145739,    6291469,   12582917,  25165843,
	  50331653,   100663319,  201326611, 402653189, 805306457,
	  1610612741, 3221225473, 4294967291
	};

	inline unsigned long __stl_next_prime(unsigned long n)
	{
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list + __stl_num_primes;
		// >= n
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}
	template<class k, class v>
	struct HashNode
	{
		pair<k, v> _kv;//存储数据
		HashNode<k, v>* _next;
		HashNode(const pair<k,v>& kv)
			:_kv(kv)
			,_next(nullptr)
		{}
	};
	//将不能进行取模的key转换成整型，以便取模
	template<class k>
	struct hashFunc
	{
		size_t operator()(const k& key)
		{
			return size_t(key);
		}
	};
	//上面的函数模板还是不能将string转换成整型，我们可以特化一下
	template<>
	struct hashFunc<string>
	{
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (auto& e : s)
			{
				hash += e;
				hash *= 131;
			}
			return hash;
		}
	};
	template<class k,class v,class hash= hashFunc<k>>
	class HashTable
	{
		typedef HashNode<k, v> node;
	public:
		hash hs;
		HashTable()
			:_table(__stl_next_prime(1))
			,_n(0)
		{}
		//插入
		bool insert(const pair<k, v>& kv)
		{	
			//不允许插入相同的key
			if (find(kv.first))
			{
				return false;
			}
			//负载因子==1就开始扩容
			if (_n == _table.size())
			{
				//扩容
				////新创建一个哈希表
				//HashTable<k, v> newtable;
				//newtable._table.resize(2 * _table.size());
				////遍历旧表，将旧表中的数据插入到新表中
				//for (size_t i = 0; i < _table.size(); i++)
				//{
				//	node* cur = _table[i];
				//	while (cur)
				//	{
				//		newtable.insert(cur->_kv);
				//		cur = cur->_next;
				//	}
				//}
				//_table.swap(newtable._table);

				//创建一个新的vector
				vector<node*> newtable(__stl_next_prime( _table.size()+1));
				for (size_t i = 0; i < _table.size(); i++)
				{
					node* cur = _table[i];
					//将节点一个一个重新映射到新表中
					while (cur)
					{
						//记录旧表链表的下一个节点
						node* next = cur->_next;
						size_t hashi = hs(cur->_kv.first) % newtable.size();
						cur->_next = newtable[hashi];
						newtable[hashi] = cur;
						cur = next;
					}
					_table[i] = nullptr;
				}
				_table.swap(newtable);
			}
			//算出kv要映射的位置
			size_t hashi = hs(kv.first)% _table.size();
			//头插
			node* newnode = new node(kv);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			++_n;
			return true;
		}
		node* find(const k& key)
		{
			//计算出key映射的位置
			size_t hashi = hs(key) % _table.size();
			//到相应的映射位置下的链表中查找
			node* cur = _table[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}
		bool erase(const k& key)
		{
			//计算出key映射的位置
			size_t hashi = hs(key) % _table.size();
			//到相应的映射位置下的链表中查找然后删除
			node* cur = _table[hashi];
			//记录删除节点的前一个节点
			node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					//删除
					if (prev == nullptr)
					{
						//第一个节点就是删除节点
						_table[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					cur = nullptr;
					--_n;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}
	private:
		//链地址法中不需要直接在表中存储数据
		//而是存在挂在表的下面的链表中，
		// 所以我们需要一个指针数组，指针是指向链表中第一个节点的指针
		vector<node*> _table;
		size_t _n;//存入数据个数
	};
}

૮₍ ˶ ˊ ᴥ ˋ˶₎ა

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-12-08，如有侵权请联系 cloudcommunity@tencent.com 删除
链表
数据
指针
存储
函数

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

链表
数据
指针
存储
函数
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 3.3 链地址法
    • 3.3.1 链地址法结构解析：指针数组与链表的结合
    • 3.3.2 核心操作：元素的插入
      • 3.3.2.1 空间足够，寻找映射位置，插入到相应链表中
      • 3.3.2.2 空间不够，扩容机制
    • 3.3.3 核心操作：基于键的快速查找
    • 3.3.4 核心操作：基于键的快速删除
    • 3.3.5 将关键字转为整数
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2026 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论