unordered_set,unordered_map模拟实现

前言

unordered_set和unordered_map是c++11中新增的数据结构,底层是一个哈希桶.一般来说认为查找的时间复杂度为o(1)

我们很早就在排序算法中接触过计数排序,简单回顾一下那块的哈希:开一个足够大的整形数组做哈希表,把待排序元素的值作下标,哈希表[下标]++,然后遍历哈希表,即可实现排序.

哈希桶可以理解为把整形数组改为指针数组,以链表的形式存储数据,插入改为头插,对于字符串等不支持直接转下标的类型,需要在调用时提供一些特殊接口

哈希桶

#pragma once
#include <vector>
#include <string>
#include <list>
template<class K>
struct HashFunc {								// 仿函数 可以支持任意类型的key
	size_t operator()(const K& key) {
		return (size_t)key;
	}
};
template<>
struct HashFunc<std::string> {					// 特化
	size_t operator()(const std::string& str) {
		size_t ret = 0;
		for (auto e : str) {	// 字符串哈希算法之一,挂个链接以后用了看
			ret *= 131;		//https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html
			ret += e;
		}
		return ret;
	}
};
//哈希map -----闭散链 ---- 线性探测
namespace HT {
	enum State {
		EMPTY,
		DELETE,
		EXIST
	};
	template<class K, class V>
	struct HashData {
		std::pair<K, V>_kv;	// kv
		State _state;	// 状态
		HashData() {
			_kv.first = K();
			_kv.second = V();
			_state = EMPTY;		//如果不显示写构造函数的话,必须要让EMPTY的值为0!!!
		}
	};

	template<class K, class V ,class Hash = HashFunc<K>>
	class HashTable {
		typedef HashData<K, V> HD;
	public:
		HashTable(int size = 10) {
			_tables.resize(size);
			_n = 0;
		}
		bool Insert(const std::pair<K, V>& kv) {	// 插入
			Hash hash;
			if (Find(kv.first)) {
				return false;
			}
			if (10 * _n / _tables.size() >= 7) {	//size有可能为0,这里我的选择是重写构造函数,使size有一个初始值
				dilatation();	//	负载因子超过0.7进行扩容
			}
			size_t hashi = hash(kv.first) % _tables.size();	// 找到插入下标
			while (_tables[hashi]._state == EXIST) {
				hashi++;
				hashi %= _tables.size();
			}

			_tables[hashi]._kv =kv;				// 找到了,更改哈希表的值
			_tables[hashi]._state = EXIST;
			++_n;
			return true;
		}
		HD* Find(const K key) {
			Hash hash;
			size_t hashi = hash(key) % _tables.size();	// 找到插入下标
			while (_tables[hashi]._state != EMPTY) {
				if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}
				hashi++;
				hashi %= _tables.size();
			}
			return nullptr;
		}
		bool Earse(const K key) {
			HD* tmp = Find(key);
			if (tmp == nullptr)
				return false;
			else {
				tmp->_state = DELETE;
			}
			return true;
		}
	protected:
		void dilatation() {		// 扩容
			size_t new_size = _tables.size() * 2;
			HashTable new_HT;
			new_HT._tables.resize(new_size);
			for (auto e : _tables) {
				if (e._state == EXIST)
					new_HT.Insert(e._kv);
			}
			std::swap(_tables,new_HT._tables);
		}

	private:
		//std::vector<HashData<K, V>> _tables;
		std::vector<HD> _tables;
		size_t _n;
	};
};
namespace hash_buctet {
	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 KeyOfT, class Hash = HashFunc<K>>
	class HashTable {
		typedef HashNode<T> Node;
		typedef HashTable<K, T,KeyOfT, Hash> HT;
	public:
		template<class Ptr, class Ref>
		struct __HTIterator
		{
			typedef HashNode<T> Node;
			typedef __HTIterator Self;

			Node* _node;
			const HashTable* _pht;

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

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

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

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

					if (i == _pht->_tables.size())
					{
						// 所有桶都走完了，最后一个的下一个用nullptr标记
						_node = nullptr;
					}
					else
					{
						_node = _pht->_tables[i];
					}
				}

				return *this;
			}

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

		typedef __HTIterator<T*, T&> iterator;
		typedef __HTIterator<const T*, const T&> const_iterator;

		iterator begin() {
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i] != nullptr)
					return iterator(_tables[i], this);
			}
			return end();
		}
		iterator end() {
			return iterator(nullptr, this);
		}
		const_iterator cbegin() const {
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i] != nullptr)
					return const_iterator(_tables[i], this);
			}
			return cend();
		}
		const_iterator cend() const {
			return const_iterator(nullptr, this);
		}
		HashTable(size_t size = 10){
			_tables.resize(size);
			_n = 0;
		}
		~HashTable() {
			for (size_t i = 0; i < _tables.size(); i++) {
				Node* cur = _tables[i];
				Node* next;
				while (cur != nullptr){
					next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
			_tables.~vector();
			_n = 0;
		}
		HashTable(HT& ht) {
			*this = ht;
		}
		HT& operator=(HT& ht) {
			this->~HashTable();
			this->_tables.resize(ht._tables.size());
			for (size_t i = 0; i < ht._tables.size(); i++) {
				Node* cur = ht._tables[i];
				Node* next;
				while (cur != nullptr) {
					next = cur->_next;
					Insert(cur->_kv);
					cur = next;
				}
			}
			return *this;
		}
		std::pair<iterator,bool> Insert(const T& data)  {
			iterator ret= Find(KeyOfT()(data));
			/*ret._node = nullptr;
			ret._pht = this;*/
			if (ret._node != nullptr)
				return std::make_pair(ret, false);

			if (_n == _tables.size()) {
				dilatation();
			}

			size_t hashi = Hash()( KeyOfT()(data) ) % _tables.size();
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			_n++;
			return std::make_pair (iterator(newnode, this), true ) ;
		}
		iterator Find(const K key) {
			size_t hashi = Hash()(key) % _tables.size();
			Node* node = _tables[hashi];
			while (node != nullptr) {
				if (KeyOfT()(node->_data) == key) {
					return iterator(node,this);
				}
				node = node->_next;
			}
			return iterator(nullptr,this);
		}
		bool Earse(const K& key) {
			size_t hashi = Hash()(key) % _tables.size();
			Node* node = _tables[hashi];
			Node* parent = node;
			while (node != nullptr) {
				if (KeyOfT()(node->_data) == key) {
					if (parent != node) {
						parent->_next = node->_next;
					}
					else {
						_tables[hashi] = node->_next;
					}
					_n--;
					delete node;
					return true;
				}
				else {
					parent = node;
					node = node->_next;
				}
			}
			return false;
		}
	protected:
		void dilatation() {		// 扩容
			size_t newsize = _tables.size() * 2;
			HashTable newHT(newsize);				// 我这里没有去改newHT的_n,因为函数末尾直接调析构,后面不会用
			for (auto& e : _tables) {
				Node* q = e;
				Node* next;
				while (q != nullptr) {
					next = q->_next;
					newHT.protected_Insert(q);
					q =  next;
				}
				e = nullptr;
			}
			std::swap(_tables,newHT._tables);
			newHT.~HashTable();
		}
		void protected_Insert(Node* node) {					//	将整个node节点进行插入
			size_t hashi = Hash()(KeyOfT()(node->_data)) % _tables.size();
			node->_next = _tables[hashi];
			_tables[hashi] = node;
		}
	private:
		std::vector<Node*> _tables;
		size_t _n;
	};
}

封装哈希桶

unordered_set

#pragma once
#include "HsahTable.h"
namespace mystl {
	template<class K>
	struct SetKeyOfT {
		K operator()(K data)
		{
			return data;
		}
	};

	template<class K,class Hash = HashFunc<K>>
	class unordered_set {
	public:
		typedef typename hash_buctet::HashTable<K, const K, SetKeyOfT<K>, Hash>::iterator iterator;
		typedef typename hash_buctet::HashTable<K, const K, SetKeyOfT<K>, Hash>::const_iterator const_iterator;
		iterator begin() {
			return _ht.begin();
		}
		iterator end() {
			return _ht.end();
		}
		std::pair<iterator, bool> inset(const K& key) {
			return _ht.Insert(key);
		}
		bool earse(const K& key) {
			return _ht.Earse(key);
		}
		iterator find(const K& key) {
			return _ht.Find(key);
		}
		const_iterator cbegin() const{
			return _ht.cbegin();
		}
		const_iterator cend() const {
			return _ht.cend();
		}

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

unordered_map

#pragma once
#include "HsahTable.h"
namespace mystl {
	template<class K, class V>
	struct MapKeyOfT {
		K operator()(const std::pair<K, V>& data)
		{
			return data.first;
		}
	};
	template<class K,class V, class Hash = HashFunc<K>>
	class unordered_map {
	public:
		typedef typename hash_buctet::HashTable<K, std::pair<const K, V>, MapKeyOfT<K,V>, Hash>::iterator iterator;
		typedef typename hash_buctet::HashTable<K, std::pair<const K, V>, MapKeyOfT<K,V>, Hash>::const_iterator const_iterator;

		iterator begin() {
			return _ht.begin();
		}
		iterator end() {
			return _ht.end();
		}
		const_iterator cbegin() const {
			return _ht.cbegin();
		}
		const_iterator cend() const {
			return _ht.cend();
		}
		std::pair<iterator, bool> inset(const std::pair<K,V>& data) {
			return _ht.Insert(data);
		}
		bool earse(const K& key) {
			return _ht.Earse(key);
		}
		iterator find(const K& key) {
			return _ht.Find(key);
		}
		V& operator[](K& key) {
			std::pair<iterator, bool> tmp = inset({ key,V() });
			return tmp.first->second;
		}
	private:
		hash_buctet::HashTable<K, std::pair<const K,V>,MapKeyOfT<K,V> > _ht;

	};
}