【c++】哈希桶-链地址法的实现

mosheng

发布于 2026-01-14 18:45:38

1260

文章被收录于专栏：c++c++

hello~ 很高兴见到大家! 这次带来的是C++中关于哈希表这部分的一些知识点,如果对你有所帮助的话,可否留下你宝贵的三连呢? 个人主页: 默|笙

接上回<开放地址法实现博客>

一、链地址法介绍

链地址法是除开放地址法之外的另一种解决哈希冲突的方法，开放地址法的弊端是群集/堆积无法避免，只能通过二次探测、双重散列等办法减少这种现象产生的概率。群集/堆积现象会使哈希表增删查效率变低（每一次插入都会插入在群集元素的末尾，它们会像滚雪球一样越滚越大，最坏的结果是时间复杂度降为O（N））。
相对于开放地址法将所有的元素都存进表里面，链地址法中所有的数据都不再直接存储在哈希表里，而是每个存储位置存入一个指针。
当没有数据映射到表里的位置时，这个存储的指针为空，当有数据映射到这个位置时，会头插在空指针的前面，然后这个位置会存储这个新的头插来的数据的地址。当有冲突的数据映射到这个位置时，也会头插在这一串数据之前。这些冲突的数据会构成一个链表，挂在哈希表这个位置的下面，构成一个“桶”。
比如映射一组数据到M = 11的表中：{ 12, 27, 16, 7, 1, 2, 5 }：

由于不是直接存储数据，所以它的负载因子不像开放地址法<1，它可以大于1，没有限制。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越小，空间利用率越低。stl中unordered_xxx的最大负载因子基本控制在1，大于1就会扩容，接下来我们的实现也采用这个对负载因子的限制条件。
哈希桶它不会因为哈希冲突而抢占别的映射位置，所以它的增删查效率不会因为开放定址法里会出现的群集/堆积现象而降低。只不过它会在扩容（负载因子大于1）的时候效率突然下降，因为扩容也跟开放定址法一样需要将数据重新映射一遍。

二、链地址法实现

它的流程基本和开放地址法的实现差不多： 搭建框架->实现Insert（解决普通插入+扩容+去重）、Find、Erase函数->实现能够将key转化为size_t类型的仿函数。

1. 搭建框架

template<class K, class V>
struct Node
{
	Node(const pair<K, V>& kv)
		:_kv(kv)
		,_next(nullptr)
	{ }
	pair<K, V> _kv;
	Node<K, V>* _next;
};

template<class K, class V, class Hash = HashFunc<K>>
class HashBacket
{
	typedef Node<K, V> Node;
public:
	HashBacket()
		:_tables(53, nullptr)
		,_count(0)
	{ }
	//析构函数，需要释放所有节点
	~HashBacket()
	{
		int i = 0;
		Node* cur = _tables[i];
		while (i < _tables.size())
		{
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}
			i++;
		}
	}
private:
	vector<Node*> _tables;
	size_t _count;
};

用的是vector<Node*>而不是vector<list>是因为list实现了封装，我们之后想实现unordered_map和unordered_set就会变得非常麻烦。
先实现一个节点类：Node有两个成员变量，一个是用来用来储存数据的_kv（这里实现的是map，所以存的是pair类型，自然就要两个模板参数），一个是指向下一个节点的next指针。然后再给一个需要传参使用的构造函数。
接着实现哈希桶结构的搭建：HashBacket两个成员变量一个用来存储节点的vector<Node*>类型的_tables，一个用来记录当前存储的有效数据个数_count。
然后我们需要实现构造函数和析构函数，前者主要是为_tables开辟空间，然后初始化_count。后者是要处理节点（有资源待清理），因为vector类型它会自己析构，但是我们定义的节点类它是不会的。
这里的第三个模板参数先不管，它是实现了下面的Hash仿函数之后再加上去的。

2. 实现Insert函数

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

bool Insert(const pair<K, V>& kv)
	{
		//去重
		if (Find(kv.first))
		{
			return false;
		}
		Hash hs;
		//扩容
		if (_count == _tables.size())
		{
			vector<Node*> newtable;
			newtable.resize(__stl_next_prime(_tables.size() + 1));

			for (int i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;

					size_t hashi = hs(cur->_kv.first) % _tables.size();
					cur->_next = newtable[hashi];
					newtable[hashi] = cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
			_tables.swap(newtable);
		}
		//插入数据
		size_t hashi = hs(kv.first) % _tables.size();
		Node* newnode = new Node(kv);
		newnode->_next = _tables[hashi];
		_tables[hashi] = newnode;
		_count++;
		return true;
	}

它的实现跟开放定址法要处理的点都差不多，一个是需要插入数据，一个是去重，一个是扩容。
对于插入数据：插入一个节点，我们采用头插的方式，因为尾插还需要遍历这个链表去找它的尾节点，而头插直接通过_tables[hashi]就能直接找到头节点。插入方法就是将新节点的_next指针指向头节点，然后这个新节点成为这个位置新的头节点就好。
对于扩容，我们扩容的逻辑是当负载因子等于1的时候就扩容，也就是有效数据个数等于表的大小的时候。这里我们没有像开放地址法那样去复用Insert函数，这是因为插入数据它每次都会创建一个新的节点，不会管原来的那个节点，原来节点需要释放空间，新节点要申请，这会使效率变低，我们希望能够直接将原来的节点拿到新的数组里面去。所以我们直接定义了一个vector<Node*>类型的新表newtable，然后通过遍历原表的每一条链，将节点重新映射到新的表newtable里，最后交换两个表_table和newtable。
去重直接复用Find函数就好。

3. 实现Find和Erase函数

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

通过遍历通过key映射到的链表来找数据，找到了返回这个节点的指针，没有找到则返回空指针。

bool Erase(const K& key)
	{
		Hash hs;
		int hashi = hs(key) % _tables.size();
		Node* it = Find(key);
		if (it)
		{
			Node* next = it->_next;
			if (_tables[hashi] == it)
			{
				delete it;
				_tables[hashi] = next;
			}
			else
			{
				Node* prev = _tables[hashi];
				while (prev->_next != it)
				{
					prev = prev->_next;
				}
				delete it;
				prev->_next = next;
			}
			_count--;
			return true;
		}
		else
		{
			return false;
		}
	}

删除先复用Find函数，如果找到了则执行删除，删除的节点可能会在链表的三个位置：链表头节点，链表尾节点，链表中间节点。其中后面两个位置的删除可以归为一类，定义所要删除节点指针为it，它前面的指针为prev，后面的指针为next，删除it之后所要做的工作就是将prev节点的_next指针指向next；而删除第一类节点，它需要我们删除节点之后将所删节点的下一个节点作为新的头节点。

4. 实现Hash仿函数

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

template<>
struct HashFunc<string>
{
	size_t operator()(const string& str)
	{
		size_t hash = 0;
		for (auto ch : str)
		{
			hash += ch;
			hash *= 131;
		}

		return hash;
	}
};