引子：我们在之前用红黑树来进行封装set与map二大容器，c++11引入了unordered_map，与unordered_set的新容器，这个底层就是哈希表！

告知：布隆过滤器，我只学了原理，下次，我再来代码呈现，我们也要进入c++的学习了，下次，更精彩（抱拳）

话不多说我们直接上代码，请君自行测试

Hash.h底层部分

#pragma once#pragma once#include#include#includeusing namespace std;//key要求有转整形的作用	template	class Hash_to_int	{ 	public:		size_t operator()(const K& key)		{ 			return (size_t)key;		}	};	//对于string类的转换--特化	template<>	class Hash_to_int	{ 	public:		//仿函数		size_t operator()(const string& key)		{ 			size_t numi = 0;			for (auto e : key)			{ 				numi *= 131;				numi += e;			}			return numi;		}	};namespace My_hash{ 	//悬挂的节点	template	struct HashNode	{ 		T _data;		HashNode* _next;		HashNode(const T& data)			:_data(data)			,_next(nullptr)		{ }	};	//前置声明	template>	class HashTable;	//迭代器	template>	class Hash_iterator	{ 	public:		typedef HashNode Node;		typedef Hash_iterator Self;		Node* _node;		const HashTable* _table;		Hash_iterator(Node*node, const HashTable* table)			:_node(node)			,_table(table)		{ }		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 to_int;				size_t numi = to_int(kot(_node->_data)) % _table->_tables.size();				++numi;				while (numi < _table->_tables.size())				{ 					if (_table->_tables[numi])					{ 						break;					}					++numi;				}				if (numi == _table->_tables.size())					 _node = nullptr;				else					 _node = _table->_tables[numi];			}			return *this;		}	};	 	template	class HashTable	{ 	public:		typedef HashNode Node;		template		friend class Hash_iterator;		//普通迭代器		typedef Hash_iterator Iterator;		//const迭代器		typedef Hash_iterator Const_Iterator;	public:		Iterator End()		{ 			return Iterator(nullptr, this);		}		Iterator Begin()		{ 			size_t numi = 0;			for (; numi < _tables.capacity(); ++numi)			{ 				if (_tables[numi])					break;			}			if (numi < _tables.capacity())				return Iterator(_tables[numi], this);			else				return Iterator(nullptr, this);		}		Const_Iterator End() const		{ 			return Const_Iterator(nullptr, this);		}		Const_Iterator Begin() const		{ 			if (_number == 0)				return End();			for (size_t i = 0; i < _tables.size(); i++)			{ 				Node* cur = _tables[i];				if (cur)				{ 					return Const_Iterator(cur, this);				}			}			return End();		}		HashTable()			:_number(0)		{ 			_tables.resize(10, nullptr);		}		~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;			}		}		//查找		Iterator Find(const K& key)		{ 			KeyofT kot;			hash to_int;			size_t hashi = to_int(key) % _tables.size();			Node* cur = _tables[hashi];			while (cur)			{ 				if (kot(cur->_data) == key)				{ 					return Iterator(cur, this);				}				cur = cur->_next;			}			return End();		}		//插入		pair insert(const T&data)		{ 			KeyofT kot;			Iterator it = Find(kot(data));			if (it != End())			{ 				return make_pair(it,false);			}			hash to_int;			size_t numi = to_int(kot(data)) % _tables.size();			//负载因子为1时进行扩容			//即size与数据点相等			if (_number == _tables.size())			{ 				vector newTable(_tables.size() * 2);				//挪动数据				for (size_t i = 0; i < _tables.size(); i++)				{ 					Node* current = _tables[i];					while (current)					{ 						Node* next = current->_next;						size_t numii = to_int(kot(current->_data)) % newTable.size();						// 头插到新表						current->_next = newTable[numii];						newTable[numii] = current;						current = next;					}					_tables[i] = nullptr;				}				_tables.swap(newTable);			}			//进行头插			Node* cmp = new Node(data);			cmp->_next = _tables[numi];			_tables[numi] = cmp;			_number++;			return make_pair(Iterator(cmp,this),true);		}		//删除		bool Erase(const K& key)		{ 			hash to_int;			//找出位置			size_t numi = to_int(key) % _tables.size();			Node* prev = nullptr;			Node* cur = _tables[numi];			while (cur)			{ 				if (cur->_data == key)				{ 					if (prev == nullptr)					{ 						_tables[numi] = cur->_next;					}					else					{ 						prev->_next = cur->_next;					}					delete cur;					_number--;					return true;				}				prev = cur;				cur = cur->_next;			}			return false;		}				// 新增遍历函数		void Traverse()		{ 			for (size_t i = 0; i < _tables.size(); i++)			{ 				KeyofT kot;				Node* current = _tables[i];				while (current)				{ 					cout << kot(current->_data)<< "  "<< endl;					current = current->_next;				}			}		}	private:		vector _tables;		size_t _number;	};}

unordered_Map部分

#pragma once
#include"Hash.h"
//#include
namespace My_Map
{

    template>
    class unordered_Map
    {
    public:
        class M_KeyofT
        {
        public:
            const K& operator()(const pair& kv)
            {
                return kv.first;
            }

        };

        typedef typename My_hash::HashTable, M_KeyofT, hash>::Iterator iterator;
        typedef typename My_hash::HashTable, M_KeyofT, hash>::Const_Iterator const_iterator;

        iterator begin()
        {
            return _cmp.Begin();
        }

        iterator end()
        {
            return _cmp.End();
        }

        const_iterator begin() const
        {
            return  _cmp.Begin();
        }

        const_iterator end() const
        {
            return  _cmp.End();
        }

        pair insert(const pair& kv)
        {
            return _cmp.insert(kv);
        }

        //如果找到就是有重复值，find功能
        //没有则为insert功能
        V& operator[](const K& key)
        {
            pair ret = _cmp.insert(make_pair(key, V()));

            return ret.first->second;
        }

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

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

    private:
        My_hash::HashTable, M_KeyofT, hash>_cmp;
    };
    
    void test_map()
    {
        unordered_Map dict;
        dict.insert(make_pair("sort", "排序"));
        dict.insert({ "left", "左边" });
        dict.insert({ "right", "右边" });

        dict["left"] = "左边，剩余";
        dict["insert"] = "插入";
        dict["string"];

        for (auto e : dict)
        {
            cout << e.first << ":" << e.second << endl;
        }
    }
}

unordered_Set部分

#pragma once
#include"Hash.h"

namespace My_Set
{
    template>
    class unordered_Set
    {
    public:
        class S_keyofT
        {
        public:
            const K& operator()(const K& key)
            {
                return key;
            }
        };

        typedef typename My_hash::HashTable::Iterator iterator;
        typedef typename My_hash::HashTable::Const_Iterator const_iterator;
        iterator begin()
        {
            return _cmp.Begin();
        }

        iterator end()
        {
            return _cmp.End();
        }

        const_iterator begin() const
        {
            return  _cmp.Begin();
        }

        const_iterator end() const
        {
            return  _cmp.End();
        }

        pair insert(const K& key)
        {
            return _cmp.insert(key);
        }

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

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

    private:
        My_hash::HashTable_cmp;
    };
    
    void Print(const unordered_Set& s)
    {
        unordered_Set::const_iterator it = s.begin();
        while (it != s.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    }

    struct Date
    {
        int _year;
        int _month;
        int _day;

        bool operator==(const Date& d) const
        {
            return _year == d._year
                && _month == d._month
                && _day == d._day;
        }
    };

    struct HashDate
    {
        size_t operator()(const Date& key)
        {
            // 112
            // 121
            return (key._year * 31 + key._month) * 31 + key._day;
        }
    };

    void test_set()
    {
        unordered_Set s;
        int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 3,3,15 };
        for (auto e : a)
        {
            s.insert(e);
        }

        for (auto e : s)
        {
            cout << e << " ";
        }
        cout << endl;

        unordered_Set us;
        us.insert({ 2024, 7, 25 });
        us.insert({ 2024, 7, 26 });
        for (auto e : us)
        {
            cout << e._year << " " << e._month << " " << e._day << endl;
        }
    }
}

测试结果：

大家有疑问，直接在评论区问我，我们一起进步！