【C++ —— 哈希】学习笔记 | 模拟实现封装unordered_map和unordered_set

文章目录

  • 前言
  • 一、unordered系列关联式容器
        • 1.1 unordered_map
        • 1.2 unordered_set
  • 二、底层结构
        • 2.1哈希概念（哈希是一种算法思想）
        • 2.2哈希冲突
        • 2.3 解决哈希冲突方法：
          • 1.直接定址法（值和位置关系是唯一关系，每个人都有唯一位置，值很分散，直接定址法会导致空间开很大，资源的浪费）
          • 2.闭散列
          • 2.1 开放地址法/线性探测
          • 3.开散列
            • 1. 哈希桶/拉链法
          • 2.字符串映射问题
  • 三、unordered_map和unordered_set封装哈希表模拟实现
      • 1.UnOrdered_map.h
      • 2.UnOrdered_set.h
      • 3.HashTable.h

前言

本文参考文档：https://legacy.cplusplus.com/reference/unordered_map/

一、unordered系列关联式容器

1.1 unordered_map

1.unordered_map接口说明

函数声明功能介绍
unordered_map构造不同格式的unordered_map对象

在这里插入图片描述
2. unordered_map的容量

函数声明功能介绍
bool empty() const检测unordered_map是否为空
size_t size() const获取unordered_map的有效元素个数

3.unordered_map的迭代器(无序set和map的迭代器都是单向迭代器)

函数功能函数介绍
begin ()返回unordered_map中第一个元素的迭代器
end()返回unordered_map中最后一个元素后一个位置的迭代器
cbegin()返回unordered_map中第一个元素的const迭代器
cend()返回unordered_map中最后一个元素后一个位置的const迭代器

4.unordered_map的元素访问

函数功能函数介绍
operator[]返回key值对应的val值（没有默认值）

注意：该函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶
中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，
将key对应的value返回。

5.unordered_map查询

函数功能函数介绍
find()查询key值是否存在，存在返回key值对应的迭代器的位置，返回key在哈希桶中的位置
count返回哈希桶中关键码为key的键值对的个数

注意：unordered_map中key是不能重复的，因此count函数的返回值最大为1

在这里插入图片描述
6. unordered_map的修改操作

函数功能函数介绍
insert向容器中插入键值对
erase删除容器中的键值对
void clear()清空容器中有效元素个数
void swap()交换两个容器中的元素

7.unordered_map的桶操作

函数功能函数介绍
size_t bucket_count()const返回哈希桶中桶的总个数
size_t bucket_size(size_t n)const返回n号桶中有效元素的总个数
size_t bucket(const K& key)返回元素key所在的桶号
1.2 unordered_set

unordered_set接口根map差不多一样，不过set只存key值且不能修改
这里就不过多赘述了，详情可自行观看文档
set文档资料

二、底层结构

2.1哈希概念（哈希是一种算法思想）

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即
O( l o g 2 N log_2 N log2​N) ，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以 不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立
一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

哈希/散列：映射 一个值和另一个值建立关系。
哈希表/散列表： 映射 关键字和存储位置建立一个关系。

2.2哈希冲突

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突
或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

2.3 解决哈希冲突方法：
1.直接定址法（值和位置关系是唯一关系，每个人都有唯一位置，值很分散，直接定址法会导致空间开很大，资源的浪费）

在这里插入图片描述

2.闭散列
2.1 开放地址法/线性探测

当前位置被占用，在开放空间里按某种规则，找一个没有被占用的位置存储

  1. 线性探测 hashi + i（i >= 0）
  2. 二次探测 hashi + i^2(i >= 0)
    在这里插入图片描述
    多定义一个负载因子，存储有效关键字个数
    当有效关键字个数超过表大小的6~8成就再次扩容，用此种方法可以有效的减少哈希冲突的次数。
    以空间换效率。
    注意：
    负载因子太多：会影响效率。
    负载因子太少：会浪费空间。
    代码实现：
	enum Stutas

	{
		//删除状态的意义：
		//1.再插入，这个位置可以覆盖
		//2.防止后面冲突的值，出现找不到的情况，遇到删除状态还要继续向后寻找
		DELETE,
		EMPTY,
		EXIST

	};
	template<class K,class V>
	struct HashData
	{
		pair<K,V> _kv;
		Stutas _s = EMPTY;
	};


	//开放地址法
	//线性查找，插入
	template<class K>
	struct Hashfunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	//struct HashfuncString
	//{
	//	//BKDR算法
	//	size_t operator()(const string& key)
	//	{
	//		size_t hash = 0;
	//		//把他们的ascll码值加起来
	//		for (auto e : key)
	//		{
	//			hash += e;
	//		}
	//		return hash;
	//	}
	//};
	template<>
	struct Hashfunc<string>
	{

		size_t operator()(const string& key)
		{
			size_t hash = 0;
			//把他们的ascll码值加起来
			for (auto e : key)
			{
				hash += e;
			}
			return hash;
		}
	};

	template<class K,class V, class Hash = Hashfunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);//resize也直接会开初始化size的大小。reserve之会开capecity的大小

		}
		//提供find解决insert能够插入相同key的问题
		
		HashData<K, V>* Find(const K& key)
		{
			Hash ht;
			size_t hashi = ht(key) % _tables.size();
			while (_tables[hashi]._s != EMPTY)
			{
				if (_tables[hashi]._s == EXIST && _tables[hashi]._kv.first == key)
				{
					//找到return找到位置的地址
					//没找到return空
					return &_tables[hashi];
				}
				hashi++;
				//hashi超出table的size大小就给他%回来
				hashi = hashi % _tables.size();
			}

			return nullptr;
		}

		bool Insert(const pair<K, V>& kv)
		{
			Hash ht;
			if (Find(kv.first))
			{
				return false;
			}
			if ((double)_n / _tables.size() >= 0.7)
			{
				//不能直接扩容size的二倍，还要转移数据，重新映射关系（扩容之后值和空间的位置关系已经乱了）
				//释放旧空间
				size_t newsize = _tables.size() * 2;
				HashTable<K,V,Hash> newHT;
				newHT._tables.resize(newsize);
				//遍历旧表，插入新表
				for ( size_t i= 0; i < _tables.size(); i++)
				{
					if (_tables[i]._s == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(newHT._tables);

			}
			//size_t hashi = kv.first % _tables.size();//key不一定是整形，如果是string呢？用仿函数把kv.first的值转化整形值
			//先用字符串映射一个整形
			size_t hashi = ht(kv.first) % _tables.size();

			while (_tables[hashi]._s == EXIST)
			{
				hashi++;
				//hashi超出table的size大小就给他%回来
				hashi = hashi % _tables.size();
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._s = EXIST;
			++_n;

		}
		bool Erase(const K& key)
		{
			HashData<K,V>* ret =  Find(key);
			//find找到会返回找到位置的地址
			if (ret)
			{
				ret->_s = DELETE;
				--_n;
				return true;
			}
			return false;
		}
		void Print()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i]._s == EXIST)
				{
					//cout << i << "->";
					cout <<"["<<i<<"]->"<< _tables[i]._kv.first << ":"<< _tables[i]._kv.second << endl;
					/*printf("[%d]->%d\n", i, _tables[i]._kv.first);
					printf("")*/
				}
				else if (_tables[i]._s == EMPTY)
				{
					printf("[%d]->\n", i);
				}
				else 
				{
					printf("[%d]->DELETE\n", i);
				}

			}
			cout << endl;
		}
	private:
		vector<HashData<K,V>> _tables;
		size_t _n = 0;//存储的关键字个数
	};
3.开散列
1. 哈希桶/拉链法

哈希桶的平均时间复杂度为O(1)

思路概念：
我们把每个hashi映射的位置，替换成list，链接每次插入的冲突的新key

可以参考下图：如4位置都是冲突的关键字。
在这里插入图片描述

2.字符串映射问题

整形还是可以用除留余数法计算key映射的位置，但是例如string这种字符串呢？
我们可以使用仿函数，实现类型的转换。
例如把字符串的每个字符的ascll码值加起来。
代码实现：

template<class K>
	struct Hashfunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	struct HashfuncString
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			//把他们的ascll码值加起来
			for (auto e : key)
			{
				hash += e;
			}
			return hash;
		}
	};

但是这种转化函数会有一些缺陷，例如abc和acb这两个不同的字符串ascll码值加起来都是相同的，导致了映射位置冲突。
有没有什么办法能解决这类的问题呢？
有大佬专门研究出了很多种算法我们可以参考：
字符串哈希算法
例如：
在这里插入图片描述
这类算法会减少字符串转哈希算法的冲突。但是肯定不能完全避免。
我们也可以模仿大佬算法完善我们的代码：

struct HashfuncString
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		//把他们的ascll码值加起来
		for (auto e : key)
		{
			hash *= 31;//在加ascll码值前*31/131
			hash += e;
		}
		return hash;
	}
};

这种方式也是类似库里面unordered_map的实现方式（要传一个仿函数）
在这里插入图片描述
但是库里面其实比我们实现的更好一些，
库里面不用传第三个模板参数直接取模，
库里面的unordered_map用string做key可以直接转化为整型。

std::unordered_map<string,string> dict;

我们可以用特化模板参数来模拟实现这总功能。

template<class K>
struct Hashfunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
template<>
struct Hashfunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		//把他们的ascll码值加起来
		for (auto e : key)
		{
			hash += e;
		}
		return hash;
	}
};

利用哈希桶实现哈希表代码：

template<class K,class V>
	struct HashNode
	{
		HashNode* _next;
		pair<K, V> _kv;

		HashNode(const pair<K, V>& kv)
			:_kv(kv)
			,_next(nullptr)
		{}
	};
	template<class K>
	struct Hashfunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	
	template<>
	struct Hashfunc<string>
	{
		//BKDR算法
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			//把他们的ascll码值加起来
			for (auto e : key)
			{
				hash *= 31;//在加ascll码值之前*31/131...
				hash += e;
			}
			return hash;
		}
	};
	template<class K,class V ,class Hash = Hashfunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		HashTable()
		{
			_tables.resize(10);
		}
		~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;
			}
		}
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			
			Hash ht;
			//扩容用开放地址法的扩容方法会产生大量的资源浪费
			//可以考虑直接把旧表的数据挪动下来
			if (_n == _tables.size())
			{
				vector<Node*> newtable;
				newtable.resize(_tables.size() * 2, nullptr);
				//遍历旧表
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						//挪动旧表的数据映射到新表
						Node* next = cur->_next;
						size_t hashi = ht(cur->_kv.first) % newtable.size();
						cur->_next = newtable[i];
						newtable[i] = cur;

						//利用cur把节点挪动到新表
						//cur利用next返回到旧表以此循环
						cur = next;

						
					}
					_tables[i] = nullptr;
					//旧表这个桶数据已经被挪动完，记得制空。
					//以防后面析构有问题
				}
				_tables.swap(newtable);

			}
			
			//先算出数据要存入哪个桶
			size_t hashi = ht(kv.first) % _tables.size();
			//头插
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return true;
		}
		Node* Find(const K& key)
		{
			Hash ht;
			size_t hashi = ht(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return NULL;
		}
		bool Erase(const K& key)
		{
			Hash ht;

			size_t hashi = ht(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					return true;
				}
				prev = cur;
				cur = cur->_next;

			}
			return false;
		}
		void Some()
		{
			size_t bucketsize = 0;
			size_t maxbucketlen = 0;
			size_t sumbucketlen = 0;
			double averagebucketlen = 0;
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur == nullptr)
				{
					++bucketsize;
				}
				size_t bucketlen = 0;
				while (cur)
				{
					++bucketlen;
					cur = cur->_next;
				}
				sumbucketlen += bucketlen;
				if (bucketlen > maxbucketlen)
				{
					maxbucketlen = bucketlen;
				}
				

			}
			averagebucketlen = (double)sumbucketlen / (double)bucketsize;
			printf("bucketsize:%d\n", bucketsize);
			printf("maxbucketlen:%d\n", maxbucketlen);
			printf("averagebucketlen:%lf\n", averagebucketlen);
			
		}
		
	private:
		vector<Node*> _tables;
		size_t _n = 0;

	};

三、unordered_map和unordered_set封装哈希表模拟实现

1.UnOrdered_map.h

#include"HashTable.h"

namespace goat
{
	template<class K,class V, class Hash = Hash_Bucket::Hashfunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K,V>& kv)
			{
				return kv.first;
			}

		};
	public:
		typedef typename Hash_Bucket::HashTable<K, pair<const K, V>, MapKeyOfT , Hash>::iterator iterator;


		pair<iterator,bool> insert(const pair<K,V>& kv)
		{
			return _mp.Insert(kv);
		}

		iterator begin()
		{
			return _mp.begin();
		}
		iterator end()
		{
			return _mp.end();
		}
		V& operator[](const K& key)
		{
			pair<iterator, bool>ret = _mp.Insert(make_pair(key,V()));
			return ret.first->second;
		}
		const V& operator[](const K& key)const
		{
			pair<iterator, bool>ret = _mp.Insert(make_pair(key, V()));
			return ret.first->second;
		}

	private:

		Hash_Bucket::HashTable<K, pair<const K,V> ,MapKeyOfT ,Hash> _mp;
	};
}

2.UnOrdered_set.h

#include"HashTable.h"

namespace goat
{
	template<class K ,class Hash = Hash_Bucket::Hashfunc<K>>
	class unordered_set
	{

		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}

		};
	public:
		typedef typename Hash_Bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;
		typedef typename Hash_Bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;

		/*iterator begin() 
		{
			return _st.begin();
		}
		iterator end() 
		{
			return _st.end();
		}*/

		const_iterator begin() const
		{
			return _st.begin();
		}
		const_iterator end() const
		{
			return _st.end();
		}

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

		bool erase(const K& key)
		{
			_st.Erase(key);
		}


		//返回值pair要实现operator[]再去修改
		pair<iterator, bool> insert(const K& key)
		{
			//return _st.Insert(key);//返回普通迭代器，但是这里insert接受的是const迭代器
								   //正常解决方法1:支持const迭代器转化成普通迭代器，方法二：下一层Insert使用节点的指针返回（指针会产生隐式类型转换为迭代器
								   //但是这里unordered迭代器有三个值不能使用方法二
								   //iterator(cur , this ,hashi)
			//这里用另外一种简单的方法
			auto ret = _st.Insert(key);
			return pair<iterator, bool>(iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);


			
		}

	private:
		
		Hash_Bucket::HashTable<K, K , SetKeyOfT, Hash> _st;
	};
	
}

3.HashTable.h

#include<iostream>
#include<vector>
#include<utility>
#include<list>
#include<set>

using namespace std;

namespace Hash_Bucket
{
	template<class T>
	struct HashNode
	{

		HashNode<T>* _next;
		T _data;

		//库里面的unordered是实现插入顺序遍历的
		//要单独维护一个链表
		//HashNode<T>* _linknext;
		//HashNode<T>* _linkprev;
		
		HashNode(const T& data)
			:_data(data)
			,_next(nullptr)
		{}
	};
	template<class K>
	struct Hashfunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	
	template<>
	struct Hashfunc<string>
	{
		
		size_t operator()(const string& key)
		{
			size_t hash = 0;
		
			for (auto e : key)
			{
				hash *= 31;
				hash += e;
			}
			return hash;
		}
	};
	//解决互相依赖方法一
	//前置声明(不用给缺省参数)
	//因为hashiterator和hashtable是互相依赖的关系

	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;

	template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
	struct __HashIterator
	{
		typedef HashNode<T> Node;
		typedef __HashIterator<K, T,Ref,Ptr, KeyOfT, Hash> Self;

		Node* _node;
		const HashTable<K, T, KeyOfT, Hash>* _pht;
		//解决互相依赖方法二
		//实际上哈希迭代器需要的是：
		//vector<Node*>* _ptb;


		//1.记录当前桶的所在位置
		size_t _hashi;

		__HashIterator(Node* node,const HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
			: _node(node)
			, _pht(pht)
			, _hashi(hashi)
		{}
		
		Self& operator++()
		{
			if (_node->_next)
			{
				//桶还有节点，就走下一个节点
				_node = _node->_next;
			}
			else
			{
				//当前桶已经走完了，需要下一个桶的开始
				//传个哈希表过来
				2.直接算出当前所在桶位置
				//KeyOfT kot;
				//Hash hf;
				//size_t hashi = hf(kot(_node->_data)) % _pht._tables.size();
				++_hashi;


				//_tables是私有成员变量
				//可以考虑友元
				while (_hashi < _pht->_tables.size())
				{
					if (_pht->_tables[_hashi])
					{
						_node = _pht->_tables[_hashi];
						break;
					}
					else
					{
						_hashi++;
					}
				}
				if (_hashi == _pht->_tables.size())
				{
					_node = nullptr;
				}
			}
			return *this;
		}
		Ref operator*()
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &_node->_data;
		}
		bool operator!=(const Self& s)
		{
			return _node != s._node;

		}
	};
	//unordered_set -> HashTable<K,K>
	//unordered_map -> HashTable<K,pair<K,V>>
	template<class K,class T , class KeyOfT,class Hash = Hashfunc<K>>
	class HashTable
	{

		template<class K, class T,class Ref ,class Ptr ,class KeyOfT, class Hash>
		friend struct __HashIterator;


		typedef HashNode<T> Node;
	public:
		typedef __HashIterator<K, T, T&,T* , KeyOfT, Hash> iterator;
		typedef __HashIterator<K, T, const T&,const T* , KeyOfT, Hash> const_iterator;

		iterator begin()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return iterator(_tables[i] ,this , i);
				}
			}
			return end();
		}
		iterator end()
		{
			return iterator(nullptr, this, -1);
		}
		const_iterator begin() const //const修饰this-> HashTable<K, T, KeyOfT, Hash>* 
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return const_iterator(_tables[i], this, i);
				}
			}
			return end();
		}
		const_iterator end() const
		{
			return const_iterator(nullptr, this, -1);
		}



		HashTable()
		{
			_tables.resize(10);
		}
		~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;
			}
		}
		pair<iterator,bool> Insert(const T& data)
		{
			KeyOfT kot;
			/*if (Find(kot(data)))
			{
				return false;
			}*/
			iterator it = Find(kot(data));
			if(it != end())
			{
				return make_pair(it, false);
			}
			
			Hash ht;
			
			//扩容用开放地址法的扩容方法会产生大量的资源浪费
			//可以考虑直接把旧表的数据挪动下来
			if (_n == _tables.size())
			{
				vector<Node*> newtable;
				newtable.resize(_tables.size() * 2, nullptr);
				//遍历旧表
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						//挪动旧表的数据映射到新表
						Node* next = cur->_next;
						size_t hashi = ht(kot(cur->_data)) % newtable.size();
						cur->_next = newtable[i];
						newtable[i] = cur;

						//利用cur把节点挪动到新表
						//cur利用next返回到旧表以此循环
						cur = next;

						
					}
					_tables[i] = nullptr;
					//旧表这个桶数据已经被挪动完，记得制空。
					//以防后面析构有问题
				}
				_tables.swap(newtable);

			}
			
			//先算出数据要存入哪个桶
			size_t hashi = ht(kot(data)) % _tables.size();
			//头插
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return make_pair(iterator(newnode,this,hashi),true);
		}
		iterator Find(const K& key)
		{
			Hash ht;
			KeyOfT kot;

			size_t hashi = ht(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return iterator(cur , this ,hashi);
				}
				cur = cur->_next;
			}
			return end();
		}
		bool Erase(const K& key)
		{
			Hash ht;
			KeyOfT kot;

			size_t hashi = ht(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					return true;
				}
				prev = cur;
				cur = cur->_next;

			}
			return false;
		}
		void Some()
		{
			size_t bucketsize = 0;
			size_t maxbucketlen = 0;
			size_t sumbucketlen = 0;
			double averagebucketlen = 0;
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur == nullptr)
				{
					++bucketsize;
				}
				size_t bucketlen = 0;
				while (cur)
				{
					++bucketlen;
					cur = cur->_next;
				}
				sumbucketlen += bucketlen;
				if (bucketlen > maxbucketlen)
				{
					maxbucketlen = bucketlen;
				}
				

			}
			averagebucketlen = (double)sumbucketlen / (double)bucketsize;
			printf("bucketsize:%d\n", bucketsize);
			printf("maxbucketlen:%d\n", maxbucketlen);
			printf("averagebucketlen:%lf\n", averagebucketlen);
			
		}
		
	private:
		vector<Node*> _tables;
		size_t _n = 0;

	};
	

	
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/645516.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

python画图：matpolt，设置图片尺寸，字体大小，副坐标轴，保存

python画图：matpolt，设置图片尺寸，字体大小，副坐标轴，保存

文章重心： 写论文的时候，图片的大小，字体的大小，副坐标轴，这些都是很重要的因素，保存一下之前用过的画图代码单图多图（两个子图）堆叠柱状图两个Y轴的图问题： python保存的时候，我选择的是svg，但是这样图片会比较大，查重什么的需要把图片都删了（一般有文件大小限制…
阅读更多...
网页出现为了更好的体验，请将手机竖过来

网页出现为了更好的体验，请将手机竖过来

前言 网站:https://act.xinyue.qq.com/commercial/act/af93dc75d9fc541d4833f05e98a9f54b6pre/index.html 发现必须要手机端才可以,否则显示"为了更好的体验,请将手机竖过来"的提示信息 很好奇怎么做的,UA?发现更改UA后依旧显示,后面看代码就知道了 可以看到是通过…
阅读更多...
单片机原理及技术（二）—— AT89S51单片机（一）（C51编程）

单片机原理及技术（二）—— AT89S51单片机（一）（C51编程）

目录 一、AT89S51单片机的片内硬件结构 二、AT89S51的引脚功能 2.1 电源及时钟引脚 2.2 控制引脚 2.3 并行 I/O口引脚 三、AT89S51的CPU 3.1 运算器 3.1.1 算术逻辑单元&#xff08;ALU&#xff09; 3.1.2 累加器A 3.1.3 程序状态字寄存器&#xff08;PSW&#xff09…
阅读更多...
【狂神说Java】Redis笔记以及拓展

【狂神说Java】Redis笔记以及拓展

一、Redis 入门 Redis为什么单线程还这么快&#xff1f; 误区1&#xff1a;高性能的服务器一定是多线程的&#xff1f; 误区2&#xff1a;多线程&#xff08;CPU上下文会切换&#xff01;&#xff09;一定比单线程效率高&#xff01; 核心&#xff1a;Redis是将所有的数据放在内…
阅读更多...
数据结构 —— 栈 与 队列

数据结构 —— 栈 与 队列

1.栈 1.1栈的结构和概念 栈&#xff08;Stack&#xff09;是一种特殊的线性数据结构&#xff0c;它遵循后进先出&#xff08;LIFO&#xff0c;Last In First Out&#xff09;的原则。栈只允许在一端插入和删除数据&#xff0c;这一端被称为栈顶&#xff08;top&#xff09;&a…
阅读更多...
第一节：Redis的数据类型和基本操作

第一节：Redis的数据类型和基本操作

最近整理了关于Redis的一些文档&#xff0c;分享给大家&#xff0c;后续会持续更新...... Redis的数据类型 字符串String String&#xff1a;字符串&#xff0c;可以存储String、Integer、Float型的数据&#xff0c;甚至是二进制数据&#xff0c;一个字符串最大容量是512M 列表…
阅读更多...
Linux指令初识

Linux指令初识

ls:显示当前目录底下的指定文件或目录 ls -l更详细的信息 ls -a显示当前目录下的所有文件 命令中的选项可以一次传递多个 ,例如&#xff1a;ls -al 命令和选项有必须一个或多个空格 以.开头的文件&#xff0c;为隐藏文件ls -a可以看到,ls -l看不见 支持命令拼在一起&#…
阅读更多...
【vue2配置】Vue Router

【vue2配置】Vue Router

Vue Router官网 1、npm install vue-router4 2、创建模块&#xff0c;在src目录小创/views/map/MapIndex.vue模块和创router/index.js文件 3、在router/index.js配置路由 import Vue from "vue"; import Router from "vue-router"; // 引入模块 const Ma…
阅读更多...
C++学习/复习5--构造函数与初始化/static成员/友元/内部类/匿名对象/编译器的拷贝构造优化

C++学习/复习5--构造函数与初始化/static成员/友元/内部类/匿名对象/编译器的拷贝构造优化

一、本章概要 二、再谈构造函数 1.构造体赋初值与初始化 2.初始化列表与初始化 2.1定义 2.2注意事项与举例 3.explicit关键字与构造函数 3.1隐式类型转换 也叫做自动类型转换 这种转换通常是从存储范围小的类型到存储范围大的类型&#xff0c;或者是从低精度的数值类型到高…
阅读更多...
【编译原理--- 汇编、编译、解释系统】

【编译原理--- 汇编、编译、解释系统】

汇编、编译、解释系统 1.编译方式和解释方式 程序种类是否生成目标程序是否参与程序的运行过程程序执行速度可移植性编译程序生成不参与快差解释程序不生成参与慢好 编译方式过程&#xff1a;词法分析、语法分析、语义分析、&#xff08;中间代码生成、代码优化、&#xff0…
阅读更多...
【动手学强化学习】第 6 章 Dyna-Q 算法知识点总结

【动手学强化学习】第 6 章 Dyna-Q 算法知识点总结

【动手学强化学习】第 6 章 Dyna-Q 算法知识点总结 本章知识点基于模型的强化学习与无模型的强化学习方法简介无模型的强化学习方法基于模型的强化学习方法 强化学习算法的评价指标Dyna-Q算法Dyna-Q 算法的具体流程Dyna-Q 代码实践 本章知识点 基于模型的强化学习与无模型的强…
阅读更多...
opencv进阶 ——（四）图像处理之去高光

opencv进阶 ——（四）图像处理之去高光

去高光步骤&#xff1a; 1、转换成灰度图 2、二值化图像&#xff0c;得到高光区域 3、进行膨胀操作&#xff0c;放大高光区域&#xff0c;以此得到高光蒙版 4、通过illuminationChange函数对高光区域消除高光
阅读更多...
VMware安装Ubuntu系统(超详细)

VMware安装Ubuntu系统(超详细)

一.Ubuntu官网下载镜像 Ubuntu官网&#xff1a;Enterprise Open Source and Linux | Ubuntu 二.安装Ubuntu系统 选择文件->创建虚拟机新建虚拟机&#xff08;ControlN&#xff09;&#xff0c;这里直接选择典型即可 选择稍后安装系统 选择linux Ubuntu 64位 填写虚拟机名称…
阅读更多...
word一按空格就换行怎么办？word文本之间添加空格就换行怎么办？

word一按空格就换行怎么办？word文本之间添加空格就换行怎么办？

如上图&#xff0c;无法在Connection和con之间添加空格&#xff0c;一按空格就会自动换行。 第一步&#xff1a;选中文本&#xff0c;打开段落。 第二步&#xff1a;点击中文版式&#xff0c;勾选允许西文在单词中间换行。 确定之后就解决一按空格就自动换行啦&#xff01;
阅读更多...
基于STM32实现智能水族箱控制系统

基于STM32实现智能水族箱控制系统

目录 引言环境准备智能水族箱控制系统基础代码示例&#xff1a;实现智能水族箱控制系统 水温传感器数据读取水泵与加热器控制水位传感器数据读取用户界面与显示应用场景&#xff1a;水族箱管理与环境控制问题解决方案与优化收尾与总结 1. 引言 本教程将详细介绍如何在STM32嵌…
阅读更多...
steam游戏服务器如何选择

steam游戏服务器如何选择

steam游戏平台现在在国内市场很吃香&#xff0c;当我们自己开发的游戏想要上架steam我们需要准备什么&#xff0c;在选择服务器的时候我们又需要考虑哪些因素呢&#xff0c;该怎样选择一款适合自己游戏的服务器是很关键的 一.Steam服务器的配置选择 Steam专用服务器通常是指由…
阅读更多...
【wiki知识库】01.wiki知识库前后端项目搭建（SpringBoot+Vue3）

【wiki知识库】01.wiki知识库前后端项目搭建（SpringBoot+Vue3）

&#x1f4dd;个人主页&#xff1a;哈__ 期待您的关注 &#x1f33c;环境准备 想要搭建自己的wiki知识库&#xff0c;要提前搭建好自己的开发环境&#xff0c;后端我使用的是SpringBoot&#xff0c;前端使用的是Vue3&#xff0c;采用前后端分离的技术实现。同时使用了Mysql数…
阅读更多...
Spring Boot 3.0：未来企业应用开发的基石

Spring Boot 3.0：未来企业应用开发的基石

文章目录 一、Spring Boot 3.0的核心特性二、Spring Boot 3.0的优势三、如何在项目中应用Spring Boot 3.01.更新项目依赖2.调整代码结构3.测试和部署 《学习Spring Boot 3.0》内容简介作者简介目录内容介绍 随着技术的飞速发展&#xff0c;企业应用开发的需求也在不断演变。Spr…
阅读更多...
创客贴：极简高效的智能平面设计神器测评

创客贴：极简高效的智能平面设计神器测评

给大家推荐一款智能平面设计作图软件——创客贴&#xff0c;简单来说&#xff0c;就是给那些需要频繁进行平面设计的人提供帮助的。它作为一款在线图片编辑器&#xff0c;可以免费使用&#xff0c;让你轻松进行创意设计。创客贴不仅提供了海量正版设计模板和图片素材&#xff0…
阅读更多...
AI 谈“浔川AI翻译机”

AI 谈“浔川AI翻译机”

在天工AI&#xff0c;天工AI在全网搜索“浔川AI翻译机”。 1 创作助手谈“浔川AI翻译机”&#xff1a; “浔川AI翻译机”是一个利用人工智能技术进行语言翻译的设备或应用程序。它可以将一种语言的文字或口语翻译成另一种语言&#xff0c;以实现不同语言之间的沟通和理解。浔…
阅读更多...
最新文章

Copyright @ 2022~2023