C++STL之unordered_map，unordered_set与哈希表

头发还没掉光光

1033人浏览 · 2025-10-20 18:56:01

头发还没掉光光 · 2025-10-20 18:56:01 发布

1. unordered系列关联式容器

1.1 为什么需要 unordered 容器？

C++98 中的 map 和 set 基于红黑树，查询效率为 (O(log N))
C++11 引入 unordered_map、unordered_set 等，基于哈希表，平均查询效率为 (O(1))

1.2 unordered_map与unordered_set介绍

这两个容器在我们使用方面与map和set完全一致，他们的接口，参数，功能完全一样，详细内容可以参考文章STLmap与set使用详解

不同的是map与set底层使用红黑树，而unordered_map与unordered_set底层使用的是哈希表，那么下文将介绍哈希表以及他们的模拟实现。

2. 哈希表的底层结构

2.1 哈希概念

什么是哈希/散列？

哈希表：使用哈希思想实现的数据结构，哈希思想就是通过建立值和存储位置的映射，从而在查找或者修改的时候能够快速找到该位置。

映射：值和值进行1对1或者1对多的关联

举个例子：

当我们需要使用key的模型统计vector< int > ve = {1,2,5,7,9}这样一个序列时，我们可以使用一个数组

int hash[10];

for(int i = 0;i < ve.size(); i++)

{

hash[ve[i]] = 1;

}

通过这样的方式，当遍历hash数组的时候，某一个下标所在位置存放的数字为1，那么原来的序列中就存在这个值。这就是将序列中的值与数组下标进行直接映射所写的一个哈希表。当然这只是最基础的，在实际中，可能会有{1,567,3648,12,3432}这样数据范围特别大的序列，或者其他类型没法直接映射到下标的类型（string，自定义类型等），那么我们将使用其他映射方法来将值与存储位置相关链接。

常见的整数的映射方法为除留取余法，即数据对哈希表长度取余数，得到的数据为哈希地址，该地址一定是在哈希表范围内的，因此可以存放任意大小的数据。

在这里插入图片描述

2.2 哈希冲突

使用映射规则来映射的时候，不同的key映射出来的存储位置是相同的，被称为哈希冲突。

比如除留余数法，就是将数字对hash表大小取余数，得到的就是哈希地址。

以2.1中的{1,567,3648,12,3432}为例，假设有一个哈希表，大小为10，

vector< int >  ve = {1,567,3648,12,3432}
int hash[10];
for(int i = 0;i < ve.size(); i++)
{
	hashi = ve[i] % 10;
	hash[hashi] = 1; 
}

1%10 = 1,因此1对应hash[1]

567%10 = 7，因此567对应hash[7]

3648%10 = 8, 3648对应hash[8]

12%10 = 2, 12 对应hash[2]

3432%10 = 2, 3432也对应hash[2]

这样虽然解决了数据范围大，空间大小问题，可是带来了新的问题就是12与3432对应同一个位置，就是哈希冲突，在2.1图例中，橙色位置为发生冲突后重新所找的地址，总共两种解决方案，请看下文。

2.3 哈希冲突解决

在哈希表中，哈希冲突是不可避免的，那么我们怎么解决呢？右两种常用方法，闭散列与哈希桶（也叫开散列，链地址法），与此同时，哈希表也是需要扩容的，引入一个荷载因子，来判断扩容的时机。

闭散列（开放定址法）

闭散列就是在遇到哈希冲突的时候，如果哈希表没有满，那么一定还有空位值，继续往下寻找，直到找到空位置即可。

还是以2.1为例，对于序列{1,567,3648,12,3432}，我们在插入3432时会与12冲突，因此向后寻找，3号下标有空位，即存入该位置。若在插入{31,44},也是会发生冲突，则按照规则继续向后寻找。

在这里插入图片描述

可以依次查找（地址每次加1，也叫线性探测），也可以跳跃查找，第一次走1，第二次走4，第三次走9，依次类推，他们在走到hash尾部的时候会类似循环链表一样从头部接着找。

该方法的缺点：

1.删除的时候，会影响后面数据的查找

查找的首先查找hash位置，如果命中则结束，为命中则要向后继续查找，因为可能存在hash冲突让所要查找数据的值去到了别的位置，在继续查找的过程中找到了则命中结束，遇到空位置则结束，因为如果有空位置那么在插入该值的时候遇到hash冲突了一定会使用。

如果插入数据遇到了hash冲突，那么他不在自己的位置存放，如果他存放的位置与hash地址中间的位置有被删除的数据，那么在查找的时候遇到被删除后的空位置，则会产生误判，因此要使用标记信息来标识被删除的位置是删除，而不是空。

2.导致更多的哈希冲突

在冲突的时候去占用别的值的位置，当被占用位置的数据要插入时，就只能去在找别的数据的地址，会导致一系列更多的冲突。因此在实践中不推荐

那么在插入的时候没有空位置了怎么办？

扩容，哈希表也有满的情况，也需要扩容，而扩容的时机尤为重要。

哈希表越满，哈希冲突的可能性就越大，此时效率越低

哈希表越空，哈希冲突的可能性越小，此时效率高，但是空间利用率低!

因此引入载荷因子来进行扩容时机的判断。

哈希表的载荷因子定义为：载荷因子 = 填入表中的元素个数 / 哈希表长度

开放地址法的载荷因子应控制在0.7-0.8，此时比较平衡，因此在在荷载因子为0.7的时候进行扩容是很好的选择

扩容注意点：

在扩容的时候不能将空间进行拷贝，而是将所有值重新插入，因为哈希表长度变了之后，他的映射规则会发生改变。

开散列（链地址法）

hash表中存放的是链表，当遇到hash冲突时，不会向后去寻找其他位置，而是与该位置已经存在的值“串起来”，可以粗略的理解为链表数组，该方法也叫哈希桶，

将数组中挂的链表形象的形态为桶。

当插入{1,567,3648,12,3432,31,44,2,28}时，遇到哈希冲突，直接进行在该位置所对应的“链表”进行头插，这样插入效率也是O(1).

遇到哈希冲突插入过程如下：
在这里插入图片描述

最终插入后的结果如下：

在这里插入图片描述

哈希桶通常在载荷因子为1的时候进行扩容。

常见哈希函数：

直接定址法：Hash(key) = A*key + B
除留余数法：Hash(key) = key % p（p 为质数）
平方取中法：取平方值的中间几位
折叠法：将 key 分割后叠加
随机数法：Hash(key) = random(key)
数学分析法：选取 key 中分布均匀的几位
BKDR算法：类似于131进制（1313,13131……都可以）

我们在使用unrodered_map的时候，string经常去做key，而库中在实现的时候模板缺省参数hashfun默认给的是整形家族的，对于string，他则是使用特化专门为string实例化出了一个专属版本。其内部使用的就是类似BKDR的算法，将string映射为整形。

对于任意类型，我们都可以考虑将其转为整数在进行除留取余

3. 模拟实现哈希表

3.1 哈希桶结构

哈希桶在实现的时候，我们可以用一个vector容器存放节点的指针，节点设计为单链表的节点，易于维护，头插方便，在实现迭代器的时候也用节点指针，方便快捷。因此哈希桶的结构如下图

template <class T>
	struct hashNode {
		//pair<K, V> _data;
		T _data;
		hashNode* _next;

		hashNode(T data)
			:_data(data), _next(nullptr)
		{
		}

	};
template <class K, class T, class KOfT, class Hash = HashFunc<T>> //模板参数后文介绍
	class hashTable {
		typedef hashNode<T> Node
	public:
	    //……
	private:
		vector<Node*> _table; //节点指针数组来作为哈希表
		size_t _size;   //记录哈希表中的数据个数

	};

3.2 仿函数KOfT，HashFunc介绍

我们实现的是泛型编程，支持各种数据类型的hash表。而用户可能使用int，char，或者string，甚至是其他自定义类型，那么我们在进行hash映射的时候如何控制呢？

通过仿函数HashFunc控制。

当用户传入数据可以强行转化为整形的时候，我们直接强转为整形，除此之外，string也是一个常用的键类型,我们还可以特化一个string版本，其内部采用BKDR算法将string转为int再返回。也就是说，我们的HashFunc要将用户的数据类型转为整数返回。部分内置类型和string我们来写，用户的自定义类型由用户在示例化哈希表对象的时候自己传入模板参数Hash控制。

template<class T>
struct HashFunc {
	int operator()(const T& key)
	{
		return (size_t)key; //整形家族直接强转
	}
};
template <>
struct HashFunc<std::string> { //特化版本string，使用BKDR转int
	int operator()(const std::string& key)
	{
		int _num = 0;
		for (auto& e : key)
		{
			_num *= 131;
			_num += e;
		}
		return _num;
	}
};

除此之外，我们的哈希表可能被用于实现set，也可能会被用于实现map，那么对于key和key-value的搜索模型，我们在节点中只存放一个数据 T _data,对于单纯的key模型，T对应key，对于key-value模型，T对应的是pair<key, value>键值对。

在哈希表内部，查找，插入，删除等都需要key来做键值，也就是说两种模型， key模型： _data 就是key， key-value模型: _data.first 才是key。我们在内部如何由 _ data 获取到key呢？

通过仿函数KOfT获取

哈希表不知道_data的那种形态是key，但是上层知道，我们在选择实例化map或者set的时候知道，那么在上层传入仿函数KOfT就可以很好的进行控制。

	template<class T>
		struct setKOfT {
			const T& operator()(const T& data)
			{
				return data;
			}
		};


	template<class K， class V>
		struct mapKOfT {
			const K& operator()(const pair<const K, V>& data)
			{
				return data.first;
			}
		};

我们在定义哈希表的时候传入对应的仿函数即可在哈希表内部得到正确的key，这也是泛型编程的典型例子。

3.3 迭代器实现

迭代器我们使用节点指针进行封装，之后重载相应的运算符即可。

模板参数Ptr，Ref用于实例化const迭代器所需参数，如若不理解，请参考文章STL之list，其中对于迭代器有详细介绍

由于Iterator和hashTable中互相都有使用，因此在后方的类中使用前方的类就无法找到（编译器向前检索，而不会向后检索），此时就**需要进行类的前置声明，**类似于函数调用后面定义的函数就需要在该函数前声明一样。

operator++详解

如果在++操作时，当前节点为某一个桶的胃节点，那么就需要跳到下一个桶，但是迭代器中只封装了指针是无法找到下一个桶的，因此还需封装一个哈希表指针，通过哈希表指针就可以找到下一个桶的位置。

封装了哈希表hashTable，需要访问其私有成员_table，则需将迭代器类声明为hashTable类的友元。

因此在++操作时，可以总结为一下几步：

如果当前桶内还有下一个节点，直接移动到下一个节点
如果当前节点时桶的最后一个节点，那么计算该桶在表中的位置，寻找下一个非空桶
找到了非空桶（即哈希表中table[hashi]不为空），返回这个桶的第一个节点
走到了table（哈希表）的结尾，即该节点后无有效节点，返回End()



	template <class K, class T, class KOfT, class Hash>
	class hashTable;  //前置声明


template <class K, class T, class Ptr, class Ref, class KOfT, class Hash>
struct unsetIterator {
    // 类型定义
    typedef unsetIterator<K, T, Ptr, Ref, KOfT, Hash> Self;
    typedef hashNode<T> Node;
    typedef hashTable<K, T, KOfT, Hash> HashTable;

    Node* _it;           // 当前指向的节点
    HashTable* _hashtable; // 所属的哈希表

    // 构造函数：初始化迭代器指向的节点和关联的哈希表
    unsetIterator(Node* it, HashTable* hashtable) 
        :_it(it), _hashtable(hashtable)
    {
    }

    // 解引用操作符：返回当前节点数据的引用
    // 设计思路：提供对迭代器指向元素的直接访问，符合STL迭代器惯例
    Ref operator*() const
    {
        return _it->_data;
    }

    // 成员访问操作符：返回当前节点数据的指针
    // 设计思路：支持通过箭头操作符直接访问数据成员，提供语法糖便利性
    Ptr operator->() const
    {
        return &(_it->_data);
    }

    // 前置递增操作符：移动到下一个元素
    // 设计思路：实现迭代器的前进功能，处理桶内移动和跨桶跳转的复杂逻辑
    Self& operator++()
    {
        // 如果当前桶内还有下一个节点，直接移动到下一个节点
        if (_it->_next == nullptr)
        {
            // 当前桶已遍历完，需要找到下一个非空桶
            KOfT kot;
            Hash hs;
            // 计算当前节点在哈希表中的位置
            int hashi = hs(kot(_it->_data)) % _hashtable->_table.size();
            hashi++; // 从下一个桶开始查找
            
            // 跳过所有空桶，找到下一个非空桶
            while (hashi < _hashtable->_table.size() && 
                   _hashtable->_table[hashi] == nullptr)
            {
                hashi++;
            }
            
            // 如果找到有效桶，指向该桶的第一个节点；否则设为nullptr表示结束
            if (hashi == _hashtable->_table.size())
            {
                _it = nullptr;
            }
            else
            {
                _it = _hashtable->_table[hashi];
            }
        }
        else
        {
            // 当前桶内还有节点，移动到链表中的下一个节点
            _it = _it->_next;
        }
        return *this;
    }

    // 相等比较操作符：判断两个迭代器是否指向同一元素
    // 设计思路：通过比较节点指针来实现迭代器的等价性判断
    bool operator==(const Self& it)
    {
        return _it == it._it;
    }

    // 不等比较操作符：判断两个迭代器是否指向不同元素
    // 设计思路：提供与相等操作符相反的判断逻辑
    bool operator!=(const Self& it)
    {
        return _it != it._it;
    }
};

template <class K, class T, class KOfT, class Hash = HashFunc<T>> 
	class hashTable {
		typedef hashNode<T> Node
	public:
        typedef unsetIterator<K, T, T*, T&, KOfT, Hash> Iterator;
		typedef unsetIterator<K, T, const T*, const T&, KOfT, Hash> constIterator
        
		friend struct Iterator;  //声明为友元类
		friend struct constIterator; 
        
	    //……
	private:
		vector<Node*> _table; //节点指针数组来作为哈希表
		size_t _size;   //记录哈希表中的数据个数

	};

3.4成员函数具体实现

构造函数 hashTable():_size(0)

hashTable():_size(0)
{
    _table.resize(10, nullptr);
}

在构造函数中直接初始化哈希表大小10，所有位置初始化为空指针

查找函数 Find(const K& key)

	Iterator Find(const K& key)
		{
			Hash hs;
			KOfT kot;
			int 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();

		}
		constIterator Find(const K& key) const
		{
			Hash hs;
			KOfT kot;
			int hashi = hs(key) % _table.size();
			Node* cur = _table[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return constIterator(cur);
				}
				cur = cur->_next;
			}
			return cEnd();

		}

通过哈希函数计算数据对应的哈希地址，在对应桶的链表中线性搜索目标数据，使用仿函数提取数据的键值进行比较，未找到返回End()迭代器，找到了则返回该位置迭代器。同时兼具const版本，返回const迭代器

插入函数 Insert(const T& data)

pair<Iterator, bool> Insert(const T& data)
		{

			Hash hs;
			KOfT kot;
			Iterator ret = Find(kot(data));
			if (ret != End())
			{
				return make_pair(ret, false);
			}
			if (_size == _table.size())
			{

				vector<Node*> _newtable(_table.size() * 2, nullptr);
				for (auto& e : _table)
				{
					if (e != nullptr)
					{
						Node* cur = e;
						while (cur)
						{
							Node* next = cur->_next;

							int hashi = hs(kot(cur->_data)) % _newtable.size();

							if (_newtable[hashi] == nullptr)
							{
								_newtable[hashi] = cur;
								cur->_next = nullptr;
							}
							else
							{
								cur->_next = _newtable[hashi];
								_newtable[hashi] = cur;
							}
							cur = next;
						}
						e = nullptr;
					}
				}

				_table.swap(_newtable);
			}
			Node* newnode = new Node(data);
			int hashi = hs(kot(data)) % _table.size();

			if (_table[hashi] == nullptr)
			{
				_table[hashi] = newnode;
			}
			else
			{
				newnode->_next = _table[hashi];
				_table[hashi] = newnode;
			}
			_size++;
			return make_pair(Iterator(newnode, this), true);

		}

先检查元素是否已存在避免重复插入，当负载因子达到1时进行2倍扩容并重新哈希所有现有元素。

使用头插将新节点插入到对应桶中，同时维护元素数量，确保哈希表性能稳定。

删除函数 Erase(const T& data)

bool Erase(const K& key)
		{
			Hash hs;
			KOfT kot;
			int hashi = hs(key) % _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						_table[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					_size--;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}

定位到数据所在的桶后遍历链表查找目标节点，同时维护前驱指针以正确处理头节点和中间节点的删除操作，删除成功后释放节点内存并更新元素数量。

如果是双向链表，那就可以服用FInd函数，用该函数找到要删除元素的位置，进行删除。单链表没有前驱指针，使用FInd找到后删除了，无法链接其前和后的指针，因此需要手动寻找，并且维护prev指针来找他的前驱节点

大小函数 Size()

int Size()
{
    return _size;
}

时间复杂度O(1)，因为维护了_size成员变量

析构函数 ~hashTable()

~hashTable()
{
    for (auto& e : _table)
    {
        if(e != nullptr)
        {
            Node* cur = e;
            Node* next;
            while (cur)
            {
                next = cur->_next;
                delete cur;
                cur = next;
            }
        }
        e = nullptr;
    }
}

由于默认生成的析构函数，内置类型不做处理，自定义类型会调用他的析构，vecotr中存放的是指针类型，也是内置类型，他在释放的时候只会释放自身一个节点，作为头指针，链表后面的节点都没有得到释放，会造成内存泄露，因此需要我们写析构函数来释放。

析构函数遍历所有哈希桶，对每个非空桶遍历其链表并释放所有节点内存，确保资源正确释放，防止内存泄漏

迭代器

迭代器在构造的时候，第一个参数穿节点指针，第二个参数穿哈希表指针，我们在调用Begin这类函数的时候，会有this指针传入函数，this指针就是调用函数对象的指针，我们直接将其作为第二个参数传入即可。


		Iterator Begin() //用第一个有效节点构造迭代器返回
		{
			int i = 0;
			for (; i < _table.size(); i++)
			{
				if (_table[i] != nullptr)
				{
					return Iterator(_table[i], this);
				}
			}
			return End();
		}
		Iterator End()//用nullptr构造迭代器返回
		{
			return Iterator(nullptr, this);
		}

		constIterator cBegin()
		{
			int i = 0;
			for (; i < _table.size(); i++)
			{
				if (_table[i] != nullptr)
				{
					return constIterator(_table[i], this);
				}
			}
			return cEnd();
		}
		constIterator cEnd()
		{
			return constIterator(nullptr, this);
		}

3.5 unordered_map 与 unordered_set 封装

unordered_map与unordered_set底层使用哈希桶，其接口与哈希桶基本一致，只需"套壳"即可。

完整封装代码如下：

#pragma once
#include<iostream>
#include<vector>
#include<string>

template<class T>
struct HashFunc {
	int operator()(const T& key)
	{
		return (size_t)key;
	}
};
template <>
struct HashFunc<std::string> {
	int operator()(const std::string& key)
	{
		int _num = 0;
		for (auto& e : key)
		{
			_num *= 131;
			_num += e;
		}
		return _num;
	}
};

namespace MyHashBucket {  //哈希桶版本的哈希表
	template <class T>
	struct hashNode {

		//pair<K, V> _data;
		T _data;
		hashNode* _next;

		hashNode(T data)
			:_data(data), _next(nullptr)
		{
		}

	};

	using namespace std;

	template <class K, class T, class KOfT, class Hash>
	class hashTable;

	template <class K, class T, class Ptr, class Ref, class KOfT, class Hash>
	struct unsetIterator {

		typedef unsetIterator<K, T, Ptr, Ref, KOfT, Hash> Self;
		typedef hashNode<T> Node;
		typedef hashTable<K, T, KOfT, Hash> HashTable;

		Node* _it;
		HashTable* _hashtable;

		unsetIterator(Node* it, HashTable* hashtable) :_it(it), _hashtable(hashtable)
		{
		}
		Ref operator*() const
		{
			return _it->_data;
		}

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

		Self& operator++()
		{
			if (_it->_next == nullptr)
			{
				KOfT kot;
				Hash hs;
				int hashi = hs(kot(_it->_data)) % _hashtable->_table.size();
				hashi++;
				while (hashi < _hashtable->_table.size() && _hashtable->_table[hashi] == nullptr)
				{
					hashi++;
				}
				if (hashi == _hashtable->_table.size())
				{
					_it = nullptr;
				}
				else
				{
					_it = _hashtable->_table[hashi];
				}
			}
			else
			{
				_it = _it->_next;
			}
			return *this;
		}

		bool operator==(const Self& it)
		{
			return _it == it._it;
		}

		bool operator!=(const Self& it)
		{
			return _it != it._it;
		}
	};


	template <class K, class T, class KOfT, class Hash = HashFunc<T>>
	class hashTable {
		typedef hashNode<T> Node;


	public:
		typedef unsetIterator<K, T, T*, T&, KOfT, Hash> Iterator;
		typedef unsetIterator<K, T, const T*, const T&, KOfT, Hash> constIterator;



		friend struct Iterator;
		friend struct constIterator;


		hashTable() :_size(0)
		{
			_table.resize(10, nullptr);
		}

		Iterator Begin()
		{
			int i = 0;
			for (; i < _table.size(); i++)
			{
				if (_table[i] != nullptr)
				{
					return Iterator(_table[i], this);
				}
			}
			return End();
		}
		Iterator End()
		{
			return Iterator(nullptr, this);
		}

		constIterator cBegin()
		{
			int i = 0;
			for (; i < _table.size(); i++)
			{
				if (_table[i] != nullptr)
				{
					return constIterator(_table[i], this);
				}
			}
			return cEnd();
		}
		constIterator cEnd()
		{
			return constIterator(nullptr, this);
		}
		Iterator Find(const K& key)
		{
			Hash hs;
			KOfT kot;
			int 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();

		}
		constIterator Find(const K& key) const
		{
			Hash hs;
			KOfT kot;
			int hashi = hs(key) % _table.size();
			Node* cur = _table[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return constIterator(cur);
				}
				cur = cur->_next;
			}
			return cEnd();

		}
		pair<Iterator, bool> Insert(const T& data)
		{

			Hash hs;
			KOfT kot;
			Iterator ret = Find(kot(data));
			if (ret != End())
			{
				return make_pair(ret, false);
			}
			if (_size == _table.size())
			{

				vector<Node*> _newtable(_table.size() * 2, nullptr);
				for (auto& e : _table)
				{
					if (e != nullptr)
					{
						Node* cur = e;
						while (cur)
						{
							Node* next = cur->_next;

							int hashi = hs(kot(cur->_data)) % _newtable.size();

							if (_newtable[hashi] == nullptr)
							{
								_newtable[hashi] = cur;
								cur->_next = nullptr;
							}
							else
							{
								cur->_next = _newtable[hashi];
								_newtable[hashi] = cur;
							}
							cur = next;
						}
						e = nullptr;
					}
				}

				_table.swap(_newtable);
			}
			Node* newnode = new Node(data);
			int hashi = hs(kot(data)) % _table.size();

			if (_table[hashi] == nullptr)
			{
				_table[hashi] = newnode;
			}
			else
			{
				newnode->_next = _table[hashi];
				_table[hashi] = newnode;
			}
			_size++;
			return make_pair(Iterator(newnode, this), true);

		}

		bool Erase(const K& key)
		{
			Hash hs;
			KOfT kot;
			int hashi = hs(key) % _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						_table[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					_size--;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}
		void Print()
		{
			for (auto& e : _table)
			{
				if (e != nullptr)
				{
					Node* cur = e;
					while (cur)
					{
						cout << (cur->_data).first << ":" << (cur->_data).second << endl;
						cur = cur->_next;
					}
				}
			}
			cout << endl;
		}

		int Size()
		{
			return _size;
		}
		~hashTable()
		{
			for (auto& e : _table)
			{
				if (e != nullptr)
				{
					Node* cur = e;
					Node* next;

					while (cur)
					{
						next = cur->_next;
						delete cur;
						cur = next;
					}
				}
				e = nullptr;
			}
		}
	private:
		vector<Node*> _table;
		size_t _size;

	};



	//void test1()
	//{
	//	hashTable<pair<string,int>, KOfT<string,int>, HashFunc<string>> t;
	//	
	//	vector<string> ve = { "aaa","bbb","cc","aaa","aaa"};
	//	for (auto& e : ve)
	//	{
	//		t.Insert({ e,0 });
	//	}
	//	t.Print();

	//}
}


namespace MyHashOpenAddr  //开放地址法版本的哈希表
{
	enum state {
		EXIT,
		OCCUPY,
		NIL
	};
	template <class T>
	struct hashNode {

		//pair<K, V> _data;
		T _data;
		state _st;
		hashNode(T data = T())
			:_data(data), _st(NIL)
		{
		}

	};

	using namespace std;

	template <class T, class KOfT, class Hash = HashFunc<T>>
	class hashTable {
		typedef hashNode<T> Node;
	public:

		hashTable() :_size(0)
		{
			_table.resize(10);
		}
		Node* Find(const T& data)
		{
			Hash hs;
			KOfT kot;
			int hashi = hs(kot(data)) % _table.size();
			while (_table[hashi]._st != NIL)
			{
				if (kot(_table[hashi]._data) == kot(data))
				{
					return &_table[hashi];
				}
				hashi++;
				hashi %= _table.size();
			}
			return nullptr;
		}
		bool Insert(const T& data)
		{
			if (Find(data) != nullptr)
			{
				return false;
			}
			Hash hs;
			KOfT kot;
			if ((_size * 10) / _table.size() >= 7)
			{

				vector<Node> _newtable(_table.size() * 2);
				for (auto& e : _table)
				{
					if (e._st != NIL)
					{
						int hashi = hs(kot(data)) % _table.size();

						while (_table[hashi]._st == OCCUPY)
						{
							hashi++;
							hashi %= _table.size();
						}

						_table[hashi] = e;
					}
				}

				_table.swap(_newtable);
			}
			Node* newnode = new Node(data);
			newnode->_st = OCCUPY;
			int hashi = hs(kot(data)) % _table.size();

			while (_table[hashi]._st == OCCUPY)
			{
				hashi++;
				hashi %= _table.size();
			}

			_table[hashi] = *newnode;
			_size++;
			return true;

		}

		bool Erase(const T& data)
		{
			Node* ptr = Find(data);
			if (ptr == nullptr)
				return false;

			ptr->_st = EXIT;
			return true;
		}
		void Print()
		{
			for (auto& e : _table)
			{
				if (e._st == OCCUPY)
				{
					cout << e._data.first << " " << e._data.second << endl;
				}
			}
			cout << endl;
		}

		int Size()
		{
			return _size;
		}


	private:
		vector<Node> _table;
		size_t _size;

	};

	template<class K, class V>
	struct KOfT {
		const K& operator()(const pair<K, V>& data)
		{
			return data.first;
		}
	};


}

Myunordered_map.h

#pragma once
#include"HashTable.h"


namespace MyUDmap {



	using namespace MyHashBucket;
	template<class K, class V>
	class unordered_map {

		typedef pair<const K, V> T;

		template<class T>
		struct KOfT {
			const K& operator()(const T& data)
			{
				return data.first;
			}
		};

	public:

		typedef typename hashTable< K,  T, KOfT<T>, HashFunc<K>>::Iterator iterator;
		typedef typename hashTable< K,  T, KOfT<T>, HashFunc<K>>::constIterator const_iterator;


		pair<iterator, bool> insert(const T& data)
		{
			return _hash.Insert(data);
		}
		V& operator[](const K& key)
		{
			return (insert(make_pair(key, V())).first)->second;
		}
		void print()
		{
			_hash.Print();
		}
		int size()
		{
			return _hash.Size();
		}
		iterator find(const T& key)
		{
			return _hash.Find(key);
		}
		const_iterator find(const T& key) const
		{
			return _hash.Find(key);
		}
		bool erase(const K& key)
		{
			return _hash.Erase(key);
		}

		iterator begin()
		{
			return _hash.Begin();
		}
		iterator end()
		{
			return _hash.End();
		}
		const_iterator cbegin()
		{
			return _hash.cBegin();
		}
		const_iterator cend()
		{
			return _hash.cEnd();
		}
	private:

		hashTable< K, T, KOfT<T>, HashFunc<K> > _hash;
	};

	


}

Myunordered_set.h

#pragma once
#include"HashTable.h"


namespace MyUDset {



	using namespace MyHashBucket;
	template<class T>
	class unordered_set {

		template<class T>
		struct KOfT {
			const T& operator()(const T& data)
			{
				return data;
			}
		};

	public:

		typedef typename hashTable< T, const T, KOfT<T> >::Iterator iterator;
		typedef typename hashTable< T, const T, KOfT<T> >::constIterator const_iterator;


		pair<iterator,bool> insert(const T& data)
		{
			return _hash.Insert(data);
		}
		void print()
		{
			_hash.Print();
		}
		int size()
		{
			return _hash.Size();
		}
		iterator find(const T& key)
		{
			return _hash.Find(key);
		}
		const_iterator find(const T& key) const
		{
			return _hash.Find(key);
		}
		bool erase(const T& key)
		{
			return _hash.Erase(key);
		}

		iterator begin()
		{
			return _hash.Begin();
		}
		iterator end()
		{
			return _hash.End();
		}
		const_iterator cbegin()
		{
			return _hash.cBegin();
		}
		const_iterator cend()
		{
			return _hash.cEnd();
		}
	private:

		hashTable< T, const T, KOfT<T>,HashFunc<T>> _hash;
	};

	
}

AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

SeedVR2终极指南：如何用单步扩散模型实现专业级视频修复

还在为老旧视频的模糊画质而烦恼吗？面对抖动严重的监控录像或褪色的家庭影像，你是否曾希望有一种简单高效的修复方案？SeedVR2正是为解决这些痛点而生的一站式视频修复工具。作为字节跳动推出的先进视频修复模型，它能够在单步推理中实现专业级的视频质量提升，彻底改变了传统视频修复的工作流程。## 核心价值：为什么选择SeedVR2进行视频修复？**传统视频修复的三大瓶颈**：1. **计算成本高

AI Agent技术社区

深度解析Amlogic S9xxx电视盒子Armbian系统：从闲置设备到Linux服务器的终极实战指南

你是否拥有一台闲置的Amlogic S9xxx系列电视盒子？想让它摆脱单一的视频播放功能，变身为功能强大的Linux服务器、开发平台或家庭媒体中心？本指南将为你详细解析如何通过Armbian系统实现这一转变，让你的电视盒子重获新生，成为高性能的Linux设备。Armbian系统基于Debian/Ubuntu构建，专为ARM芯片优化，提供了完整的Linux生态支持。## 🎯 核心价值与独特优势

AI Agent技术社区

CANN/runtime Event管理API

本章节描述 CANN Runtime 的 Event 管理接口，用于事件的创建、记录、同步、计时及 IPC 跨进程共享。- [`aclError aclrtCreateEvent(aclrtEvent *event)`](#aclrtCreateEvent)：创建Event，创建出来的Event可用于统计两个Event之间的耗时、多Stream之间的任务同步等场景。- [`aclError