unordered系列的封装

• 1 unordered_map 和 unordered_set
• 2 改造哈希桶
• • 2.1 模版参数
  • 2.2 加入迭代器
• 3 上层封装
• • 3.1 unordered_set
  • 3.2 unordered_map
• 4 面试题分析
• Thanks♪(･ω･)ﾉ谢谢阅读！！！
• 下一篇文章见！！！

1 unordered_map 和 unordered_set

unordered系列的库是以哈希桶为底层的容器，其是用来快速寻找指定数据。这里主要介绍unordered_map和unordered_set。

1. unordered_map是用来储存 键值对的容器，可以通过Key快速寻找到其对应的value,注意Key和value的类型可以不一样。并且key不可更改，value可以更改！
2. unordered_map内部并不是按照特定顺序储存的，而是按照key转换得到的数组下标来进行存储，因此内部是无序的！
3. unordered_map通过key查找元素比map快非常多！！！但对应迭代的速度比较慢。
4. unordered_map允许[ ]下标访问！
5. unordered_map只有正向迭代器！没有反向迭代器！

1. unordered_set是只储存key值的容器！和set相似，用来去重或者判断是否存在！
2. unordered_set内部并不是按照特定顺序储存的，而是按照key转换得到的数组下标来进行存储，因此内部是无序的！
3. 3. unordered_set通过key查找元素比set快非常多！！！但对应迭代的速度比较慢。
4. unordered_set不提供[ ]下标访问！
5. unordered_set只有正向迭代器！没有反向迭代器！

他们都提供以下接口：

接下来我们就来实现这些功能！

2 改造哈希桶

2.1 模版参数

unordered_map 和 unordered_set的底层是开散列版本的哈希表（哈希桶），但是他们两个储存的数据却不一样：一个是键值对pair , 一个是键值key。所以为了可以让哈希桶适配，就要进行泛型编程的改造，增加模版参数。由上层的unordered_map 和 unordered_set控制底层的哈希桶存储什么数据，因此我们需要添加一个class T模版参数，供上层决定储存什么数据。与之对应的，从数据中获取key的仿函数。
这样加上将转换key为size_t的仿函数，共用四个模版参数：

1. class k : 表明键值key的类型，这是最基本的。
2. class T: 储存的数据类型：pair 或 key。
3. class KeyOfT: 如何从T中获取key，这是很关键的，是我感觉最巧妙的一环，通过仿函数来适配不同类型，太妙了！
4. class HashFunc:将key值转换为size_t的数组下标。

通过这四个模版参数，就可以通过传入对应的参数来保证适配！（迭代器我们后续来实现）

template class HashTable { public: 	typedef HashNode Node; 	iterator begin() 	{} 	iterator end() 	{} 	const_iterator begin() const  	{} 	const_iterator end() const  	{} 	 	HashTable() 		:hs(), 		kot() 	{ 		_table.resize(10, nullptr); 		_n = 0; 	} 	//插入数据 	pair insert(const T kv) 	{} 	//删除 	bool erase(const K& key) 	{} 	//查找 	iterator find(const K& key) 	{} private: 	//底层是一个指针数组 	vector _table; 	//有效数量 	size_t _n; 	//仿函数 	Hash hs; 	KeyOfT kot; }; 

我们的模版参数修改之后，我们的函数体也要进行改造，不能直接写死，要符合泛型编程：

函数基本都是修改了原本的cur->_kv。first 变为 kot(cur->_kv)，通过仿函数来获取key值，并且返回值设置为迭代器。这样无论我们传入的是pair 或 key，都可以通过仿函数获取对应的key值！下面给出插入函数的代码，其余函数的改造类似！

//插入数据 pair insert(const T kv) { 	iterator it = find(kot(kv)); 	if (it != end()) 		return make_pair(it, false);  	//扩容 	if (_n == _table.size() * 0.7) 	{ 		//直接把原本的节点移动到新的table中即可 		vector newtable(2 * _table.size()); 		//遍历整个数组 		for (int i = 0; i < _table.size(); i++) 		{ 			if (_table[i]) 			{ 				Node* cur = _table[i]; 				while (cur) 				{ 					//获取数据 					Node* next = cur->_next; 					//计算新的映射 					//kot(cur->_kv) 来获取 T 中的key 					size_t hashi = hs(kot(cur->_kv)) % newtable.size(); 					//进行头插 					cur->_next = newtable[hashi]; 					newtable[hashi] = cur;  					cur = next; 				}  			} 		} 		_table.swap(newtable); 	} 	//首先寻找到合适下标 	size_t hashi = hs(kot(kv)) % _table.size(); 	//进行头插 	Node* newnode = new Node(kv);  	newnode->_next = _table[hashi]; 	_table[hashi] = newnode; 	++_n;  	return make_pair(iterator(newnode , this), true); } 

2.2 加入迭代器

实现封装一定少不了迭代器!!!迭代器可是强大的武器，有了迭代器就可以使用基于范围的for循环，还可以通过迭代器来访问修改数据。

那么我们就要来写一个迭代器，来供我们使用。

哈希表的迭代器和之前写过的迭代器有所不同，我们来看奥：我们搭建一个基本框架:

1. 首先我们需要一个节点指针，这是迭代器中的关键元素，用来访问数据
2. 然后我们的迭代器其要支持++运算，可以移动到下一个节点。移动规则：当前桶没走完就移动到下一个元素， 当前桶走完了就移动到下一个桶的第一个元素，而移动到下一个桶需要哈希表表,所以内部需要有一个哈希表
3. 还要提供基本的!= == * ->运算。
4. 注意构造函数要使用const HashTable* ht低权限，因为我们不会对其修改，还要避免上层传入``const HashTable* `,所以要做好预防！

template struct _HTIterator { 	typedef _HTIterator Self; 	//成员 	Node* _node; 	//哈希表 	const HashTable* _pht; 	//构造函数 	_HTIterator(Node* node, const HashTable* ht) 		:_node(node), 		_pht(ht) 	{} 	//++ 	Self& operator++() 	{ 	} 	//判断很好写 	bool operator!=(const Self& s) 	{ 		return _node != s._node; 	} 	bool operator==(const Self& s) 	{ 		return _node == s._node; 	} 	Ref operator*() const 	{ 		return _node->_kv; 	} 	Ptr operator->() const 	{ 		return &_node->_kv; 	} }; 

如果我们将迭代器正常放在哈希表的外面，会发现报错：编译器不认识 HashTable,很正常，因为HashTable在其后面才进行定义，所以我们可以在迭代器之前加一个HashTable前置声明！或者使用内部类，把迭代器放HashTable内部就好了！

然后我们就来解决这个++的问题：

1. 如果当前桶还没有走到最后，就要移动到下一个节点，使用cur = cur ->next即可！
2. 如果走完当前桶了（next指针是nullptr时），就要向后寻找下一个桶了。
3. 如果找到了就继续进行，没有找到，说明走完了

//++ Self& operator++() { 	Hash hs; 	KeyOfT kot; 	//++ 	//当前桶没走完就移动到下一个 桶走完了就移动到下一个桶  	if (_node->_next) _node = _node->_next; 	else 	{ 		//桶走完了就移动到下一个桶 		size_t i = hs(kot(_node->_kv)) % _pht->_table.size(); 		i++;  		for (; i < _pht->_table.size(); i++) 		{ 			if (_pht->_table[i]) 				break; 		} 		//走完循环有两种可能，要进行判断 		if (i == _pht->_table.size()) 			_node = nullptr; 		else 		{ 			_node = _pht->_table[i]; 		} 	}  	return *this; } 

这样我们的迭代器就完成了，再在hashtable中实例化普通迭代器和const迭代器：

//迭代器 typedef _HTIterator iterator; //const 迭代器 typedef _HTIterator const_iterator; 

然后加入我们begin()和end(）函数

1. begin()：从哈希表的第一个桶开始寻找，找到桶中的第一个元素
2. end() : 设置为空就可以

 iterator begin() { 	for (size_t i = 0; i < _table.size(); i++) 	{ 		if (_table[i]) 			return iterator(_table[i], this); 	} 	return iterator(nullptr, this); }  iterator end() { 	return iterator(nullptr, this); }  const_iterator begin() const  { 	for (size_t i = 0; i < _table.size(); i++) 	{ 		if (_table[i]) 			return const_iterator(_table[i], this); 	} 	return const_iterator(nullptr, this); }  const_iterator end() const  { 	return const_iterator(nullptr, this); } 

这样底层就实现好了，接下来我们开始在上层做动作！

3 上层封装

底层的哈希桶我们已经改造完毕了，接下来就是在上层来调用：

3.1 unordered_set

先来看unordered_set，其底层要注意：

1. unordered_set储存是key值，注意不可修改！要设置为const变量
2. 使用仿函数SetKeyOfT来从T中获取Key值
3. 上层要通过给对应的哈希函数
4. 大部分函数直接调用底层Hashtable中的函数就可以！
5. 在实例化迭代器时，需要使用typename关键字来明确指出iterator是一个类型，而不是一个变量或者别的什么。

这样我们可以搭建起一个框架

//仿函数 template struct SetKeyOfT { 	const K operator()(const K& k) 	{ 		return k; 	} };  template> class my_unoerder_set { public: 	//迭代器 	typedef typename HashTable, Hash >::iterator iterator; 	typedef typename HashTable, Hash >::const_iterator const_iterator;  	pair insert(const K& k) 	{ 		return _table.insert(k); 	} 	iterator find(const K& k) 	{ 		return _table.find(k); 	} 	bool erase(const K& k) 	{ 		return _table.erase(k); 	} 	iterator begin() 	{ 		return _table.begin(); 	} 	iterator end() 	{ 		return _table.end(); 	} 	const_iterator begin() const 	{ 		return _table.begin(); 	} 	const_iterator end() const  	{ 		return _table.end(); 	} private: 	HashTable , Hash > _table; };  

这样就设置好了，我们来测试一下：

void test_set1() { 	my_unoerder_set S; 	vector arr = { "sort" , "hello" , "JLX" , "Hi" }; 	for (auto e : arr) 	{ 		S.insert(e); 	} 	my_unoerder_set::iterator it = S.begin(); 	cout << "-------while循环遍历--------" << endl; 	while (it != S.end()) 	{ 		//(*it)++; 		std::cout << *it << endl; 		++it; 	} 	cout << "-------基于范围的for循环--------" << endl; 	for (auto e : S) 	{ 		//e++; 		cout << e << endl; 	} 	cout << "-------查找\"hello\"--------" << endl; 	cout << *(S.find("hello")) << endl; } 

测试结果：

完美，这样unordered_set就完成了，当然还可以继续完善功能函数，其他的函数比较简单就不加赘述。

3.2 unordered_map

继续来看unordered_map：

1. 与unordered_set不同，unordered_map里面储存的是pair，而且注意k值不能修改所以要传入pair!
2. 使用仿函数MapKeyOfT来从T中获取Key值
3. 上层要通过给对应的哈希函数
4. 大部分函数直接调用底层Hashtable中的函数就可以！
5. 在实例化迭代器时，需要使用typename关键字来明确指出iterator是一个类型，而不是一个变量或者别的什么。
6. 另外要额外实现[ ]操作：非常简单，[ ]的运算规则是：如果对应key已经存在，就返回其value值。不存在就进行插入，value设置为初始值，所以直接调用Insert函数就可以，因为Insert函数不会插入重复的数据并且会返回对应的迭代器！

//仿函数 template struct MapKeyOfT { 	const K& operator()(const pair& kv) 	{ 		return kv.first; 	} };  template> class my_unoerder_map { public: 	//迭代器 	typedef typename HashTable< K, pair, MapKeyOfT , Hash>::iterator iterator; 	typedef typename HashTable< K, pair, MapKeyOfT , Hash>::const_iterator const_iterator;  	pair insert(pair kv) 	{ 		return _table.insert(kv); 	} 	iterator find(const K& k) 	{ 		return _table.find(k); 	} 	bool erase(const K& k) 	{ 		return _table.erase(k); 	} 	iterator begin() 	{ 		return _table.begin(); 	} 	iterator end() 	{ 		return _table.end(); 	} 	//[]操作 	V& operator[](const K& k) 	{ 		pair it = insert(make_pair( k , V() )); 		return it.first->second; 	}  private: 	HashTable, MapKeyOfT , Hash> _table; };  

我们来进行一下测试奥：

void test_unordered_map() { 	my_unoerder_map countMap; 	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", 	"苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };  	for (auto& e : arr) 	{ 		countMap[e]++; 	} 	my_unoerder_map::iterator it = countMap.begin(); 	while (it != countMap.end()) 	{ 		//(*it).first += 2; 		cout << (*it).first << ':' << (*it).second << endl; 		++it; 	} } 

运行结果：

完美！！！

4 面试题分析

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？

错误回答：通过哈希表，遍历一遍该文件，获取到每个IP地址出现的次数，再遍历一遍哈希表，得到出现次数的IP地址。
…
这样的回答是对哈希理解的不够深导致的，我们看题目条件：超过100G大小的log file！哈希中负载因子一般为0.5 ~ 0.7，所以会有很多空间是浪费的，文件本身已经100G了，可想而知这个哈希表会有多大了！
我们可以使用

1. 分治法：将大文件分割成多个小文件，每个文件分别统计IP出现次数，然后再合并结果。
2. 哈希分区：根据IP地址的哈希值将日志分布到多个小文件中，每个小文件分别处理，最后合并结果。
3. 外部排序：如果内存有限，可以使用外部排序算法来处理大量数据。布隆过滤器：如果内存非常有限，可以使
4. 用布隆过滤器来估算IP地址的出现频率，但可能会有误报。
   …

正确回答(分治 + 哈希)：

1. 预处理：如果日志文件格式允许，可以使用命令行工具（如awk，grep，sort等）对日志进行预处理，提取IP地址并排序。
2. 分治：将大文件分割成多个小文件，每个文件大小可以基于内存限制来决定。
3. 计数：对于每个小文件，使用哈希表统计IP出现次数。合并：将所有小文件的统计结果合并起来。这里可以使
4. 用外部排序或者分布式系统来进行合并。
5. 找到最频繁的IP：在合并结果中找到出现次数最多的IP。

与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？

正确答案：

1. 提取IP地址：使用awk或grep等工具从日志文件中提取IP地址。
2. 排序：使用sort命令对提取出的IP地址进行排序(文件过大可以分成若干个文件进行排序)。
3. 计数：使用uniq -c命令来计数每个IP地址出现的次数。
4. 排序并获取Top K：再次使用sort命令，这次是根据计数进行排序，并使用head -n K来获取前K个结果。
5. 对应指令：awk '{print $1}' log_file | sort | uniq -c | sort -nr | head -n K

给定100亿个整数，设计算法找到只出现一次的整数？

正确回答：可以使用位图（Bitmap）数据结构来有效地解决问题。位图是一种数据结构，用于存储与处理布尔值，其中每个值只占用一个位（bit）的空间。位图中是一个整型数组，每个整型可以储存32个比特位

1. 初始化位图：创建一个位图，其大小足以表示所有可能出现的整数。需要一个大小为10亿位的位图。
2. 标记出现次数：遍历所有的整数，对于每个整数，将其在位图中对应的位设置为1。如果整数再次出现，则将其在位图中对应的位设置为-1,在出现就不进行处理。这样，最终位图中为1的位对应的整数就是只出现一次的整数。
3. 收集结果：遍历位图，找到所有为1的位，这些位对应的整数就是只出现一次的整数。

给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

正确回答：

• 方法一：分治法 + 哈希分桶
  1. 分治法：将每个文件分割成多个小文件，每个小文件的大小可以基于内存限制来决定。
  2. 哈希分桶：使用哈希函数将文件中的整数分布到多个桶中。对于每个桶，可以在内存中处理两个文件中的整数，找到交集。
  3. 合并结果：将所有小文件的交集结果合并起来，得到最终的交集
• 方法二：外部排序
  1. 排序：分别对两个文件进行外部排序。由于内存限制，每次只处理一部分数据。
  2. 合并：使用外部归并排序的思想，逐步合并两个文件中的数据（取整数出现次数少的那部分），找到交集。

位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

正确回答：

• 方法一：分治法 + 哈希表
  1. 分治法：将大文件分割成多个小文件，每个小文件的大小可以基于内存限制来决定。
  2. 计数：对于每个小文件，使用哈希表（如std::unordered_map）来计数每个整数出现的次数。
  3. 过滤：遍历哈希表，将出现次数不超过2次的整数输出到结果文件中。
  4. 合并结果：将所有小文件的结果合并起来，得到最终的输出。
• 方法二：哈希分桶
  1. 哈希分桶：使用哈希函数将文件中的整数分布到多个桶中。
  2. 计数：对于每个桶，可以在内存中使用哈希表来计数每个整数出现的次数。
  3. 过滤：遍历哈希表，将出现次数不超过2次的整数输出到结果文件中。
  4. 合并结果：将所有桶的结果合并起来，得到最终的输出

Thanks♪(･ω･)ﾉ谢谢阅读！！！

下一篇文章见！！！