C++之unordered_xxx基于哈希表（链地址法）的自我实现（难）

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

unordered_xxx的自我实现


请添加图片描述

一.哈希表实现（链地址法）

先以图解的形式，看一下数据是如何映射到哈希表当中的：
在这里插入图片描述
可以看到，Key值经过hash函数后，数据一致的并没有分开储存，而是连接到了原来数据之下。因此，让我们来看看链地址法的基础构成部分：

1. 数据结构设计

在我们的实现中，哈希表由一个 vector 容器 _tables 组成，每个元素是一个指向 HashNode 的指针。HashNode 是一个简单的结构体，包含一个键值对 _kv 和一个指向下一个节点的指针 _next。这种结构使得我们可以方便地在链表中插入和删除节点。

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

2. 初始化与销毁

哈希表的构造函数初始化 _tables 为一个大小为质数的空链表数组，并将 _n（存储的有效数据个数）设置为 0。析构函数负责释放所有链表节点的内存，防止内存泄漏。

HashTable(size_t n = __stl_next_prime(0))
			:_tables(n, nullptr)
			, _n(0)
		{
		}

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

3.插入操作

1. 操作流程

插入操作的目标是将一个新的键值对添加到哈希表中。以下是插入操作的详细步骤：

  1. 检查键是否存在：首先，通过调用 Find 函数检查待插入的键是否已经存在于哈希表中。如果键已存在，说明该键值对无需再次插入，直接返回 false。
  2. 计算哈希值：使用哈希函数 Hash 对键进行哈希运算，得到一个哈希值。然后，将该哈希值对哈希表的大小取模，得到该键值对在哈希表中的槽位索引。
  3. 判断是否需要扩容：如果当前哈希表中存储的有效数据个数 _n 等于哈希表的大小，说明哈希表已满，需要进行扩容操作。扩容的具体做法是创建一个新的哈希表，其大小为当前哈希表大小的下一个质数。接着，遍历旧哈希表中的所有链表，将每个链表中的节点重新映射到新哈希表中对应的槽位。
  4. 头插法插入节点：在确定好插入位置后，创建一个新的 HashNode 节点，将待插入的键值对存储在该节点中。然后，采用头插法将新节点插入到对应槽位的链表头部。头插法的好处是操作简单且时间复杂度低，无需遍历整个链表。
  5. 更新数据量计数：插入节点后，将哈希表中存储的有效数据个数 _n 加 1。
  6. 返回插入结果：插入操作成功完成，返回 true。

2. 代码实现

bool Insert(const pair<K, V>& kv)
{
	if (Find(kv.first))
		return false;

	Hash hs;

	// 负载因子到1扩容
	if (_n == _tables.size())
	{
		// 扩容
		vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), 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(cur->_kv.first) % newtables.size();
				cur->_next = newtables[hashi];
				newtables[hashi] = cur;

				cur = next;
			}
			_tables[i] = nullptr;
		}

		_tables.swap(newtables);
	}

	size_t hashi = hs(kv.first) % _tables.size();

	// 头插
	Node* newnode = new Node(kv);
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;

	return true;
}

3. 注意事项

  • 哈希函数的选择：哈希函数的质量直接影响到哈希表的性能。一个好的哈希函数应该能够将键均匀地分布到哈希表的不同槽位中，尽量减少冲突的发生。
  • 扩容时机：在本实现中，当哈希表的负载因子达到 1 时进行扩容。负载因子是指哈希表中存储的有效数据个数与哈希表大小的比值。在实际应用中，可以根据具体需求调整扩容时机，例如将负载因子的阈值设置为 0.7 或 0.8 等，以平衡哈希表的空间利用率和操作性能。

4. 查找操作

1. 操作流程

查找操作的目的是在哈希表中查找一个特定的键，并返回与该键关联的值。以下是查找操作的详细步骤：

  1. 计算哈希值：使用哈希函数 Hash 对待查找的键进行哈希运算，得到一个哈希值。然后，将该哈希值对哈希表的大小取模，得到该键在哈希表中的槽位索引。
  2. 遍历链表：从计算得到的槽位开始，沿着链表逐个节点进行比较，检查每个节点的键是否与待查找的键相等。如果找到匹配的键，则返回对应的节点指针；如果遍历完整个链表仍未找到匹配的键，则返回 nullptr，表示该键不存在于哈希表中。

2. 代码实现

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

		cur = cur->_next;
	}

	return nullptr;
}

3. 注意事项

  • 查找效率：在拉链法哈希表中，查找操作的效率主要取决于哈希函数的质量和链表的长度。如果哈希函数能够将键均匀分布，且链表长度较短，则查找操作的效率较高。在最理想的情况下，每个槽位的链表长度为 1，查找操作的时间复杂度为 O(1)。
  • 键的比较：在查找过程中，需要对键进行比较。因此，键的类型应该支持比较操作。如果键是自定义类型，需要确保重载了 == 运算符，以便正确比较键的相等性。

5.删除操作

1. 操作流程

删除操作的目标是从哈希表中移除一个特定的键值对。以下是删除操作的详细步骤：

  1. 计算哈希值：使用哈希函数 Hash 对待删除的键进行哈希运算，得到一个哈希值。然后，将该哈希值对哈希表的大小取模，得到该键在哈希表中的槽位索引。
  2. 遍历链表查找节点：从计算得到的槽位开始，沿着链表逐个节点进行比较，查找与待删除键匹配的节点。同时，需要记录当前节点的前驱节点，以便在删除操作中修改链表的指针。
  3. 删除节点：如果找到了匹配的节点，根据当前节点是否为链表的第一个节点，分别进行不同的处理：
    • 如果当前节点是链表的第一个节点，将该槽位的头指针指向当前节点的下一个节点。
    • 如果当前节点不是链表的第一个节点，将前驱节点的 _next 指针指向当前节点的下一个节点。
  4. 释放内存：删除节点后，使用 delete 释放该节点占用的内存。
  5. 更新数据量计数：将哈希表中存储的有效数据个数 _n 减 1。
  6. 返回删除结果：删除成功返回 true，如果未找到匹配的键，则返回 false。

2. 代码实现

bool Erase(const K& key)
{
	Hash hs;
	size_t hashi = hs(key) % _tables.size();
	Node* prev = nullptr;
	Node* cur = _tables[hashi];
	while (cur)
	{
		if (cur->_kv.first == key)
		{
			if (prev == nullptr)
			{
				_tables[hashi] = cur->_next;
			}
			else
			{
				prev->_next = cur->_next;
			}

			--_n;
			delete cur;
			return true;
		}

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

	return false;
}

3. 注意事项

  • 链表的边界情况：在删除操作中，需要特别注意链表的边界情况，例如当前节点是链表的第一个节点或链表为空的情况。正确处理这些边界情况可以避免程序出现错误。
  • 内存管理：在删除节点后，一定要记得释放该节点占用的内存，以防止内存泄漏。

总代码一览：

namespace hash_bucket
{
	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 Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		HashTable(size_t n = __stl_next_prime(0))
			:_tables(n, nullptr)
			, _n(0)
		{
		}

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

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;

			Hash hs;

			// 负载因子到1扩容
			if (_n == _tables.size())
			{
		

				// 扩容
				vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), 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(cur->_kv.first) % newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}

				_tables.swap(newtables);
			}

			size_t hashi = hs(kv.first) % _tables.size();

			// 头插
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;

			return true;
		}

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

				cur = cur->_next;
			}

			return nullptr;
		}

		bool Erase(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}

					--_n;
					delete cur;
					return true;
				}

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

			return false;
		}
	private:
		vector<Node*> _tables;
		size_t _n;				// 实际存储有效数据个数
	};
}

二.unordered_xxx自我实现部分

2.1unordered_xxx的结构

unordered_xxx底层都是哈希表，通过调用哈希表的接口，进而实现。在这部分，基本与map和set自我实现部分类似，这里直接给出结构。

1.unordered_set结构

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;


	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 K& key)
	{
		return _ht.Insert(key);
	}

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

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

private:
	hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
};

2.unordered_map结构

	template<class K, class V, class Hash = HashFunc<K>>
	class unordered_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;

		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 = insert({ key, V() });
			return ret.first->second;
		}

	private:
		hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
	};

2.2修改自我实现的哈希表

由于上层unordered_xxx向哈希表传来的数据并不同，unordered_set是key而unordered_map是pair类型，所以在底层，哈希表处，我们统一用data来同时处理这两种数据。

1.修改节点

下面是对节点处的修改：

template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;

	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{
	}
};

2.各类操作的修改

针对各类操作，我们需要统一将数据改为data。
在这里还要注意的一点是，在上层unordered_xxx处，我们实现了KeyOfT函数，并传给了模板参数，也就是这里的kot。这是应为，当数据data是pair类型时，我们是不能够直接取出它的key值的，因此，让unordered_set和unordered_map各自实现自己的函数，在底层我们只需统一调用kot函数即可。
下面是对插入，寻找，删除函数的修改：

pair<Iterator, bool> Insert(const T& data)
{
	KeyOfT kot;
	Iterator it = Find(kot(data));
	if (it != End())
		return { it, false };

	Hash hs;

	// 负载因子到1扩容
	if (_n == _tables.size())
	{
		vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), 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)) % newtables.size();
				cur->_next = newtables[hashi];
				newtables[hashi] = cur;

				cur = next;
			}
			_tables[i] = nullptr;
		}

		_tables.swap(newtables);
	}

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

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

		cur = cur->_next;
	}

	return End();
}

bool Erase(const K& key)
{
	Hash hs;
	size_t hashi = hs(key) % _tables.size();
	KeyOfT kot;
	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;
			}

			--_n;
			delete cur;
			return true;
		}

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

	return false;
}

注意：
map⽀持[]

  • unordered_map要⽀持[]主要需要修改insert返回值⽀持，修改HashTable中的insert返回值为 pair<Iterator, bool> Insert(const T& data)
  • 请添加图片描述
    可以看到insert的返回值是一个pair类型的结构。first指向的是一个迭代器，就是所插入值的迭代器，第二个second是bool类型，用来判断是否插入成功。

3.实现迭代器功能(实现了const和非const版本)

迭代器的实现，主要有++， * ， -> ， != ， == 操作。在这里我们主要说明++操作。其余只将实现列出。

operator++代码解析
Self& operator++()
{
    if (_node->_next)
    {
        // 当前桶还没走完
        _node = _node->_next;
    }
    else 
    {
        // 当前桶走完了，需要找下一个不为空的桶里面的第一个节点
        KeyOfT kot;
        Hash hs;
        size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
        hashi++;
        while (hashi < _pht->_tables.size())
        {
            if (_pht->_tables[hashi])
            {
                _node = _pht->_tables[hashi];
                break;
            }

            ++hashi;
        }

        if (hashi == _pht->_tables.size())
        {
            // 所有桶都走完了，置为end()
            _node = nullptr;
        }
    }

    return *this;
}
  1. 当前桶未走完

如果当前节点 _node 的 _next 指针不为空，说明当前链表还有后续节点，直接将 _node 指向下一个节点：

if (_node->_next)
{
    _node = _node->_next;
}
  1. 当前桶已走完

如果当前节点 _node 的 _next 指针为空，说明当前链表已经遍历完毕，需要找到下一个非空的链表头节点。以下是实现步骤：

  • 获取当前节点的哈希值：通过 KeyOfT 和 Hash 获取当前节点数据的哈希值，并计算其在哈希表中的位置：

    KeyOfT kot;
Hash hs;
size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();

    这里，kot 是一个 KeyOfT 类型的对象，用于从数据中提取键值；hs 是一个 Hash 类型的对象，用于计算键值的哈希值。

  • 寻找下一个非空链表：从当前哈希值的下一个位置开始，逐个检查哈希表中的槽位，直到找到一个非空的链表：

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

    ++hashi;
}

    如果找到非空链表，将 _node 指向该链表的头节点。

  • 处理所有桶都已遍历完的情况：如果遍历完所有槽位都没有找到非空链表，说明已经到达哈希表的末尾，将 _node 置为 nullptr，表示迭代器到达 end()：

    if (hashi == _pht->_tables.size())
{
    _node = nullptr;
}
  1. 返回当前迭代器

最后，返回当前迭代器对象的引用，以便支持链式操作：

return *this;
迭代器其余操作
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
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* _pht;

	HTIterator(Node* node, const HT* pht)
		:_node(node)
		, _pht(pht)
	{
	}

	Self& operator++()
	{
		if (_node->_next)
		{
			// 当前桶还没走完
			_node = _node->_next;
		}
		else 
		{
			// 当前桶走完了，需要找下一个不为空的桶里面的第一个节点
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
			hashi++;
			while (hashi < _pht->_tables.size())
			{
				if (_pht->_tables[hashi])
				{
					_node = _pht->_tables[hashi];
					break;
				}

				++hashi;
			}

			if (hashi == _pht->_tables.size())
			{
				// 所有桶都走完了，置为end()
				_node = nullptr;
			}
		}

		return *this;
	}

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

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

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

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

4.哈希表对迭代器的复用

typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;


Iterator Begin()
{
	if (_n == 0)
		return End();

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

	return End();
}

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

ConstIterator Begin() const
{
	if (_n == 0)
		return End();

	for (size_t i = 0; i < _tables.size(); i++)
	{
		if (_tables[i])
		{
			return ConstIterator(_tables[i], this);
		}
	}

	return End();
}

ConstIterator End() const
{
	return ConstIterator(nullptr, this);
}
代码解析

这段代码实现了哈希表的 Begin 和 End 方法，分别用于获取指向哈希表第一个元素的迭代器和指向哈希表末尾的迭代器。这些方法对于遍历哈希表中的所有元素非常重要。下面是对这段代码的详细解析：

1. 类型定义

首先，定义了两种迭代器类型：

typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;
  • Iterator：用于非常量哈希表的迭代器，允许修改元素。
  • ConstIterator：用于常量哈希表的迭代器，不允许修改元素。
2. Begin 方法

Begin 方法返回一个指向哈希表第一个元素的迭代器。如果哈希表为空，则返回 End。

Iterator Begin()
{
    if (_n == 0)
        return End();

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

    return End();
}
逻辑解析：

  1. 检查哈希表是否为空：

    • 如果 _n（实际存储的有效数据个数）为 0，说明哈希表为空，直接返回 End。

  2. 遍历哈希表的槽位：

    • 从第一个槽位开始，逐个检查 _tables[i] 是否非空。
    • 如果找到一个非空的链表，返回该链表的第一个节点的迭代器。

  3. 返回 End：

    • 如果所有槽位都为空（理论上不会发生，已经因为检查了 _n），返回 End。
3. End 方法

End 方法返回一个指向哈希表末尾的迭代器。这个迭代器通常用于表示迭代的结束。

Iterator End()
{
    return Iterator(nullptr, this);
}
逻辑解析：
  • 返回一个迭代器，其 _node 指针为 nullptr，表示迭代结束。
  • _pht 指向当前哈希表对象，用于在迭代器的递增操作中访问哈希表的内部结构。
4. 常量版本的 Begin 和 End

为了支持常量哈希表的遍历，还提供了常量版本的 Begin 和 End 方法：

ConstIterator Begin() const
{
    if (_n == 0)
        return End();

    for (size_t i = 0; i < _tables.size(); i++)
    {
        if (_tables[i])
        {
            return ConstIterator(_tables[i], this);
        }
    }

    return End();
}

ConstIterator End() const
{
    return ConstIterator(nullptr, this);
}
逻辑解析：
  • 这些方法的逻辑与非常量版本相同，但返回的是 ConstIterator。
  • ConstIterator 保证了对哈希表中元素的只读访问，符合常量方法的要求。

2.3哈希表结构总览

namespace hash_bucket
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;

		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{
		}
	};

	// 前置声明
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;

	template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
	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* _pht;

		HTIterator(Node* node, const HT* pht)
			:_node(node)
			, _pht(pht)
		{
		}

		Self& operator++()
		{
			if (_node->_next)
			{
				// 当前桶还没走完
				_node = _node->_next;
			}
			else 
			{
				// 当前桶走完了，需要找下一个不为空的桶里面的第一个节点
				KeyOfT kot;
				Hash hs;
				size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
				hashi++;
				while (hashi < _pht->_tables.size())
				{
					if (_pht->_tables[hashi])
					{
						_node = _pht->_tables[hashi];
						break;
					}

					++hashi;
				}

				if (hashi == _pht->_tables.size())
				{
					// 所有桶都走完了，置为end()
					_node = nullptr;
				}
			}

			return *this;
		}

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

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

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

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

	template<class K, class T, class KeyOfT, class Hash>
	class HashTable
	{
		// 友元声明
		template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
		friend struct HTIterator;

		typedef HashNode<T> Node;
	public:
		typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
		typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;


		Iterator Begin()
		{
			if (_n == 0)
				return End();

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

			return End();
		}

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

		ConstIterator Begin() const
		{
			if (_n == 0)
				return End();

			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return ConstIterator(_tables[i], this);
				}
			}

			return End();
		}

		ConstIterator End() const
		{
			return ConstIterator(nullptr, this);
		}

		HashTable(size_t n = __stl_next_prime(0))
			:_tables(n, nullptr)
			, _n(0)
		{
		}

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

		pair<Iterator, bool> Insert(const T& data)
		{
			KeyOfT kot;
			Iterator it = Find(kot(data));
			if (it != End())
				return { it, false };

			Hash hs;

			// 负载因子到1扩容
			if (_n == _tables.size())
			{
				vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), 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)) % newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}

				_tables.swap(newtables);
			}

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

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

				cur = cur->_next;
			}

			return End();
		}

		bool Erase(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			KeyOfT kot;
			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;
					}

					--_n;
					delete cur;
					return true;
				}

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

			return false;
		}
	private:
		vector<Node*> _tables;
		size_t _n;				// 实际存储有效数据个数
	};
}

在这里插入图片描述

网站公告

今日签到

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

热门文章

最新发布