初识C++ · 哈希表封装unordered_map/set

但是节点指针只能实现在某个桶里面++，这里顺带提一下，对于unordered_map unordered_set来说，迭代器是单向迭代器，所以我们不用实现--，那么有了节点指针，我们就可以实现某个桶的遍历，const顺序表指针是因为，当我有一个const哈希表的时候，this指针指向的是const对象，这时候我用非const对象指针来接受，就存在了权限放大的问题，所以不行，即调用的情况有两种，一是

XY.散人

1079人浏览 · 2024-08-05 20:02:32

XY.散人 · 2024-08-05 20:02:32 发布

1 正确认识关系

有了哈希表的基础已经红黑树封装map + set的经验，我们现在就可以较为顺畅的捋清楚每个类之间的关系。

第一个：

节点类-> 节点类的同红黑树一样，在unordered_map一层传一个参数用来确定节点类的数据类型，我们实现的是哈希桶来封装，所以成员变量有顺序表，顺序表里面是节点指针，加上数据变量：

template<class T>
struct HashNode
{
	HashNode(const T& data)
		:_next(nullptr)
		, _data(data)
	{}

	HashNode<T>* _next;
	T _data;
};

第二个：
仿函数部分-> 我们在哈希桶部分就知道了如果是自定义类型的话，那么没有办法取模，就需要转为整型，同理，其他自定义类型的话也需要不同的方式转为整型，这样可以映射到每个桶里面去，那么第一个仿函数就是转为整型的，其中有模板特例化语法的出现，第二个仿函数就是老生常谈的了，是KeyOfT，是在unordered_map这一层调用的，和红黑树封装map + set是一样的：

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

template<>
struct SHAlgorithm<string>
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto e : s)
		{
			hash *= 131;
			hash += e;
		}
		return hash;
	}
};

struct MapKeyOfT
{
	const K& operator()(const pair<K, V>& kv)
    {
		return kv.first;
	}
};

第三个：
迭代器，迭代器用来实现的功能依旧是解引用 ++ 判断是否相等，那么迭代器的成员变量有哪些呢？因为要实现遍历，节点指针是肯定的吧？但是节点指针只能实现在某个桶里面++，这里顺带提一下，对于unordered_map unordered_set来说，迭代器是单向迭代器，所以我们不用实现--，那么有了节点指针，我们就可以实现某个桶的遍历，整个顺序表的遍历我们应该如何实现呢？

我们遍历链表，需要节点指针，遍历顺序表自然就是需要顺序表指针了，所以迭代器的成员遍历有两个，那么现在问题又来了：

迭代器如果写在哈希桶的外面，成员变量有哈希表的指针，可是编译器是向上查找的，上面没有，那怎么办？如果写在外面，模板参数该有多少个，哈希桶的模板参数有 K V 两个仿函数，加上迭代器的参数，一共六个模板参数，是不是太冗余了？

解决方法是，如果写在外面，需要一个前置声明，告诉编译器我们有哈希表的节点指针，对于模板参数方面，要解决只能写成内部类：

template< class Ref, class Ptr>
struct HTIterator
{
	typedef HashNode<V> Node;
	typedef HTIterator Self;

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

	Node* _node;
	const HashTable* _pht;


};

typedef HTIterator<V&, V*> iterator;
typedef HTIterator<const V&, const V*> const_iterator;

这是内部的写法，那么有问题了就：

1 为什么typdef 迭代器要写在下面？

2 为什么顺序表指针要写成const？

typedef写在下面是因为编译器同样是向上查找的，如果写在上面了，那么就要加声明。

const顺序表指针是因为，当我有一个const哈希表的时候，this指针指向的是const对象，这时候我用非const对象指针来接受，就存在了权限放大的问题，所以不行，即调用的情况有两种，一是const调用，二是非const调用，因为权限问题所以我们就加上了const。

哈希表本体的话，已经介绍过了，这里就不再多说了。

2 哈希表封装

2.1 查找

查找这里是最简单的，无非就是遍历一下即可，遍历的基本思想是先找下标索引的位置，然后链表++即可：

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

返回的值可能让人有点迷糊，为什么用this指针去构造一个迭代器呢？因为迭代器的成员变量有一个顺序表的对象指针，指向的就是我们要遍历的迭代器，所以这里的用法是很绝的，this指针显式的去使用。

2.2 插入

pair<iterator, bool> Insert(const V& data)
{
	KeyOfT kot;
	Hash hs;
	//去重

	iterator it = Find(kot(data));
	// -> 注意这里是!=
	if (it != End())
	{
		return make_pair(it, false);
	}

	//扩容 -> load_factor达到1时进行扩容
	if (_n == _table.size())
	{
		vector<Node*> newTables(_table.size() * 2, nullptr);
		for (size_t i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[i];
			while (cur)
			{
				Node* next = cur->_next;
				size_t hashi = hs(kot(cur->_data)) % newTables.size();
				cur->_next = newTables[hashi];
				newTables[hashi] = cur;

				cur = next;
			}

			_table[i] = nullptr;
		}

		_table.swap(newTables);
	}
	//插入方式使用头插
	size_t hashi = hs(kot(data)) % _table.size();
	Node* newnode = new Node(data);
	newnode->_next = _table[hashi];
	_table[hashi] = newnode;
	_n++;

	return make_pair(iterator(newnode,this),true);
}

这里返回值保持和红黑树那里一样，返回值是pair<K,V>类型的，也就去重，扩容，插入即可，这是链表的插入，也没有什么要特别注意的。

2.3 删除

删除就是跳跃节点连接即可：

bool Erase(const K& key)
{
	Hash hs;
	KeyOfT kot;
	size_t hashi = hs(key) % _table.size();
	Node* cur = _table[hashi];
	Node* prev = nullptr;
	while (cur)
	{
		if (kot(cur->_kv) == key)
		{
			//头结点
			if (prev == nullptr)
			{
				_table[hashi] = cur->_next;
			}
			else
			{
				prev->_next = cur->_next;
				delete cur;
				return true;
			}
		}
		else
		{
			prev = cur;
			cur = cur->_next;
		}
		delete cur;
		return true;
	}
	return false;
}

这里的三个函数都是和红黑树那边一样的，那么现在就差迭代器了，迭代器的* -> != 都是和之前的一样的，++的基本思路就是Begin找到第一个不为空的桶，返回第一个节点姐可以，那么++ 就是从该桶遍历，该桶遍历完了就顺序表指针++，直到找到一个新的桶，如果没有找到新的桶，那么将节点指针置为空即可：

template< class Ref, class Ptr>
struct HTIterator
{
	typedef HashNode<V> Node;
	typedef HTIterator Self;
	//typedef HTIterator<Ref, Ptr> Self;

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

	Node* _node;
	const HashTable* _pht;

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

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

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

	Self& operator++()
	{
		if (_node->_next)
		{
			_node = _node->_next;
		}
		//当前桶空了 走到下一个不为空的桶里面遍历
		else
		{
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(kot(_node->_data)) % _pht->_table.size();
			hashi++;
			for (; hashi < _pht->_table.size(); hashi++)
			{
				if (_pht->_table[hashi])
					break;
			}
			if (hashi == _pht->_table.size())
			{
				_node = nullptr;
				//cout << "遍历结束了已经" << endl;
			}
			else
			{
				_node = _pht->_table[hashi];
			}
		}
		return *this;
	}
};

2.4 析构函数

析构每个节点，这里可不能调用默认的析构函数，虽然vector可以调用自己的析构，但是我们new出来的节点是没有办法析构的，就需要我们自己手动的析构，和析构链表的节点是一样的：

~HashTable()
{
	for (int i = 0; i < _table.size(); i++)
	{
		Node* cur = _table[i];
		while (cur)
		{
			Node* next = cur->_next;
			delete cur;
			cur = next;
		}
		_table[i] = nullptr;
	}
}

2.5 Begin部分

iterator Begin()
{
	for (int i = 0; i < _table.size(); i++)
	{
		Node* cur = _table[i];
		if (cur)
			return iterator(cur, this);
	}
	return End();
}
iterator End()
{
	return iterator(nullptr, this);
}
const_iterator Begin() const
{
	for (int i = 0; i < _table.size(); i++)
	{
		Node* cur = _table[i];
		if (cur)
			return iterator(cur, this);
	}
	return End();
}
const_iterator End() const
{
	return iterator(nullptr, this);
}

在unordered_map一层的代码几乎和map + set那里的一模一样，就不多介绍了。

感谢阅读！