【C++进阶篇】哈希表的封装（赋源码）

发布于：2025-06-19 ⋅ 阅读:(21) ⋅ 点赞:(0)

C++哈希表终极封装指南：从线性探测到STL兼容的迭代器魔法


声明：最好在学习了红黑树的封装之后，再来学习哈希表的封装，这里涉及的模版（泛型编程思想）较多，综合较强，两个模块之间相互依赖，需要前置声明。

源码位置：哈希表的封装- Gitee

一. 哈希表的封装

1.1 基本结构

  • 使用哈希桶结构封装出哈希表
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{
	typedef HashNode<T> Node;
public:
private:
	vector<Node*> _tables;  // 指针数组
	size_t _n = 0;			// 表中存储数据个数
};

使用vector容器来存储节点指针，进行线性探测可以挂在后面。
在这里插入图片描述

  • KeyOfT的作用是返回key值，因为对于set而言是key值，而对于map而言是pair类型。
  • Hash作用是将不支持取模类型的数据转换成整数，如string等类型不支持。

1.1.1 插入

查找数据之前，查找该数据是否已经存在，存在则直接返回{该节点已经存在的迭代器，false}，不存在则返回{新插入节点的迭代器，true}，然后计算出该新插入数据节点的哈希值，然后直接头插即可（注：尾插也行，但麻烦，需要找尾），然后返回{当前新插入节点的迭代器，true}即可，将_n++,表示实际存储的数据个数增加了。

  • 伪代码如下：
inline unsigned long __stl_next_prime(unsigned long n)
{
	// Note: assumes long is at least 32 bits.
	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
	};
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}

pair<Iterator, bool> Insert(const T& data)
{
	KeyOfT kot;
	Iterator it = Find(kot(data));

	if (it != End())
		return  { it,false };

	Hash hs;
	// 扩容逻辑

	size_t hashi = hs(kot(data)) % _tables.size();
	Node* newnode = new Node(data);

	// 头插到桶里面
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;
	return { Iterator(newnode,this),true };
}

问题1：如果插入的数据，当前空间已经满了？？？怎么办，需要扩容。

  • 扩容：
    将原哈希表的数据挪动至新表中，然后将旧表与新表交换即可，伪代码：
if (_n == _tables.size())
{
	size_t newSize = __stl_next_prime(_tables.size() + 1);
	vector<Node*> newtables(newSize, nullptr);
	// 遍历旧表，把旧表的节点挪动到新表
	for (size_t i = 0; i < _tables.size(); i++)
	{
		Node* cur = _tables[i];
		while (cur)
		{
			Node* next = cur->_next;

			// cur头插到新表
			size_t hashi = hs(kot(cur->_data)) % newSize;
			cur->_next = newtables[hashi];
			newtables[hashi] = cur;

			cur = next;
		}

		_tables[i] = nullptr;
	}


	_tables.swap(newtables);
}

1.1.2 查找

将要查找的数据转换成哈希值，然后在当前桶中遍历即可。找到返回当前节点的迭代器即可。未找到返回End()。

Iterator Find(const K& key)
{
	Hash hs;
	size_t hashi = hs(key) % _tables.size();
	Node* cur = _tables[hashi];
	KeyOfT kot;
	while (cur)
	{
		if (kot(cur->_data) == key)
		{
			return Iterator(cur,this);
		}

		cur = cur->_next;
	}

	return End();
}

1.1.3 删除

这里直接附上代码即可，在上篇文章已经说过细节：哈希表模拟实现 - CSDN详情看这篇文章。

bool Erase(const K& key)
{
	Hash hs;
	KeyOfT kot;

	size_t hashi = hs(key) % _tables.size();
	Node* prev = nullptr;
	Node* cur = _tables[hashi];
	while (cur)
	{
		if (kot(cur->_data) == key)
		{
			// 删除
			if (prev == nullptr)
			{
				// 头删
				_tables[hashi] = cur->_next;
			}
			else
			{
				prev->_next = cur->_next;
			}

			delete cur;
			return true;
		}

		prev = cur;
		cur = cur->_next;
	}

	return false;
}

1.1.4 Begin()

查找第一个不为空的桶，返回当前节点指针和表指针。都为空则返回nullptr即可。

Iterator Begin()
{
	for (size_t i = 0; i < _tables.size(); i++)
	{
		Node* cur = _tables[i];
		if (cur)
		{
			return Iterator(cur, this);
		}
	}
	return End();
}

1.1.5 End()

返回使用{nullptr，表指针}即可。

Iterator End()
{
	return Iterator(nullptr, this);
}

const迭代器与上述类似。详情看源码即可。

1.1.6 构造函数

将当前容量默认设置为素数表第一个素数即可。

HashTable()
{
	_tables.resize(__stl_next_prime(1), nullptr);
}

1.1.7 析构函数

依次把当前桶桶中的节点指针析构即可，注意：析构当前节点时，需保存下一个节点指针的地址，未提前保存否则会找不到。

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

1.2 迭代器设计（重点）

迭代器里面重要的成员：

  1. 节点指针：用于遍历当前桶的。
  2. 表指针：用于查找下一个不为空的表。
struct __HTIterator
{
	typedef HashNode<T> Node;
	typedef HashTable<K, T, KeyOfT, Hash> HT;
	typedef __HTIterator<K, T, Ref,Ptr,KeyOfT, Hash> Self;

	Node* _node;//节点指针
	const HT* _ht;//表指针

	__HTIterator(Node* node,const HT* ht)
		: _node(node)
		,_ht(ht)
	{}
}

问题1：这里表指针为啥要const修饰？？？
为了配合const的迭代器，const的迭代器修饰表指针，不用设计权限放大，这是不允许的。

1.2.1 重载operator*()

typedef __HTIterator<K, T, T&,T*,KeyOfT, Hash> Iterator;
typedef __HTIterator<K, T, const T&,const T*,KeyOfT, Hash> ConstIterator;
template<class K, class T,class Ref,class Ptr, class KeyOfT, class Hash>
struct __HTIterator ；

直接取节点中的数据即可。

Ref operator*()
{
	return _node->_data;
}

1.2.2 重载operator->()

返回节点中数据的地址即可。

Ptr operator->()
{
	return &_node->_data;
}

1.2.3 重载operator++()

  1. 当前桶中节点未走完，则需要继续往当前桶中继续往后走。
  2. 当前桶中的节点已经为空，表示已经遍历完了，则需要找下一个不为空的桶。
    问题1：如何找下一个不为空的桶？？？
  3. 将当前节点的数据转换成哈希值，然后将该哈希值++，继续判断，如果当前桶中的节点不为空，则将该节点赋值给_node，如果为空，继续将哈希值++，继续往后查找。
Self operator++()
{
	if (_node->_next)
	{
		_node = _node->_next;
	}
	else
	{
		//当前桶中的链表数据已经遍历完，寻找下一个有数据的桶
		KeyOfT kot;
		Hash hs;
		size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();
		++hashi;//当前的下一个位置

		while (hashi < _ht->_tables.size())
		{
			if (_ht->_tables[hashi])
			{
				_node = _ht->_tables[hashi];
				break;
			}
			else
			{
				++hashi;
			}
		}

		if (hashi == _ht->_tables.size())
		{
			_node = nullptr;
		}
	}

	return *this;
}

1.2.4 重载operator==()

直接判断节点相等即可。

bool operator==(const Self& s)
{
	return _node == s._node;
}

1.2.5 重载operator==()

直接判断节点是否相等即可。

bool operator!=(const Self& s)
{
	return _node != s._node;
}

1.3 封装 unordered_set

1.3.1 基本结构

template<class K, class Hash = HashFunc<K>>
class unordered_set
{
	//仿函数
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
public:
	typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
	typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;
private:
	hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
};
  • 基本都是调用哈希桶中哈希表中的接口。
iterator begin()
{
	return _ht.Begin();
}
iterator end()
{
	return _ht.End();
}

const_iterator begin()const
{
	return _ht.Begin();
}
const_iterator end()const
{
	return _ht.End();
}

iterator Find(const K& key)
{
	return _ht.Find(key);
}
bool Erase(const K& key)
{
	return _ht.Erase(key);
}

pair<iterator, bool> insert(const K& key)
{
	return _ht.Insert(key);
}

该代码实现了一个STL风格容器适配器，封装底层哈希表的核心功能：1) 提供const/non-const迭代器接口，支持范围遍历；2) insert方法返回插入状态对(迭代器+成功标识)，兼容关联容器规范；3) Find/Erase实现键值查询与删除操作；4) 通过组合模式复用底层实现，提供类型安全的键值存储接口。整体设计遵循STL容器规范，支持迭代器遍历和标准操作接口，实现高效的键值对管理。

1.4 封装unordered_map

1.4.1 基本结构

template<class K, class V, class Hash>
class unoredred_map
{
	//仿函数
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv)
		{
			return kv.first;
		}
	};
public:
	typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
	typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;
private:
	hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
  • 基本都是调用哈希桶中哈希表中的接口。
iterator begin()
{
	return _ht.Begin();
}
iterator end()
{
	return _ht.End();
}

const_iterator begin()const
{
	return _ht.Begin();
}
const_iterator end()const
{
	return _ht.End();
}

pair<iterator,bool> insert(const pair<K, V>& kv)
{
	return _ht.Insert(kv);
}

iterator Find(const K& key)
{
	return _ht.Find(key);
}
bool Erase(const K& key)
{
	return _ht.Erase(key);
}

V& operator[](const K& key)
{
	pair<iterator,bool> ret = _ht.Insert(make_pair(key, V()));
	return ret.first->second;
}

该代码实现了一个容器适配器，封装了底层哈希表_ht的核心接口：1) 提供迭代器支持(begin/end)，支持范围遍历；2) insert方法返回插入状态对(迭代器+成功标识)；3) Find/Erase实现键值查找与删除；4) 重载operator[]实现类似map的便捷访问——若键不存在则自动插入默认值。整体设计遵循STL容器风格，通过组合模式复用底层哈希表功能，提供类型安全的键值存储与高效操作接口。

二. 最后

本文详细阐述了C++哈希表容器的封装实现，采用vector存储指针数组处理冲突，通过线性探测法解决哈希碰撞，并设计素数表实现动态扩容。核心模块包括：1) 哈希表基类：实现插入(含自动扩容)、查找、删除等操作，提供迭代器接口；2) 迭代器设计：支持跨桶遍历，通过哈希值跳跃实现高效遍历；3) 无序容器适配：通过组合模式封装哈希表，实现unordered_set/unordered_map容器，提供STL标准接口(begin/end/insert/find/erase)，其中unordered_map重载operator[]实现自动值初始化。整体设计遵循RAII原则，内存管理安全，完美兼容STL生态体系。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布