哈希表

• 1.unorderd系列关联式容器
• • 1.1unordered_map+unordered_set介绍
  • 2.哈希表
  • • 2.1闭散列 -- 开放地址法
    • • 2.1.1线性探测
      • • 插入
        • 查找
        • 删除
        • 针对插入查找做的修改
        • 线性探测完整代码
        • 2.1.2二次探测
        • 2.2开散列 -- 拉链法(哈希桶)
        • • 插入
          • 查找
          • 删除
          • 除留余数法取质数
          • 拷贝构造
          • 赋值重载
          • 哈希桶完整代码

            

            喜欢的点赞，收藏，关注一下把！

            1.unorderd系列关联式容器

            在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 l o g 2 N log_2 N log2​N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对unordered_map和unordered_set进行介绍。

            1.1unordered_map+unordered_set介绍

            unordered_map在线文档说明

            unordered_set在线文档说明

            从功能上来说unordered_map和unordered_set和map和set基本上是一样的，只不过unorder_map和unordered_set底层是哈希表。map和set底层是搜索树，所以迭代器在走的时候map和set是有序的，unordered_map和unordered_set是无序的。

            因为底层不同，所以给它们一个Hash的仿函数，这个是什么我们学了底层就知道了。

            

            并且还是因为底层不同，它们只有单向迭代器。只支持++，不支持- -

            

            哈希表有多种实现方式，库选择桶的实现方式封装unordered_map和unordered_set，因此它们的底层也可以叫做哈希桶。

            下面是对桶操作，不过这些接口我们平常很少用，了解即可。

            

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

            这是有关负载因子的操作，也不用管。

            

            这些东西等我们学过它们的底层之后我们就懂了。

            剩下的接口就和map和set几乎差不多，这样的好处也是减轻我们的学习成本。既然unordered_map，unordered_set和map，set接口这么相似，那封装出它们有什么用呢，我们从各自的效率对比来看一看。

            以unordered_set和set对比为例，注意对比性能走Release

            插入

            int main()
            {
            	size_t N = 1000000;
            	unordered_set us;
            	set s;
            	vector v;
            	v.reserve(N);
            	srand((unsigned int)time(nullptr));
            	for (size_t i = 0; i < N; ++i)
            	{
            		v.push_back(rand());
            	}
            	size_t begin1 = clock();
            	for (auto e : v)
            	{
            		s.insert(e);
            	}
            	size_t end1 = clock();
            	cout << "set insert: " << end1 - begin1 << endl;
            	size_t begin2 = clock();
            	for (auto e : v)
            	{
            		us.insert(e);
            	}
            	size_t end2 = clock();
            	cout << "unordered_set insert: " << end2 - begin2 << endl;
            	return 0;
            }
            

            

            好像unordered快不少，说明它还是有点东西的。

            那在用用有序的数据对比一下看一看

            	for (size_t i = 0; i < N; ++i)
            	{
            		//v.push_back(rand());
            		v.push_back(i);
            	}
            

            

            unordered_set又没有set行了，set一直都是单旋树的高度控制的很低

            

            再换一组数据对比一下，因为rand随机数总共就是三万多个，我们生成一百万个肯定有很多重复的，所以我们让数据更随机一点

            	for (size_t i = 0; i < N; ++i)
            	{
            		v.push_back(rand() + i);
            		//v.push_back(rand());
            		//v.push_back(i);
            	}
            

            

            不同值多一些，set好像更有优势一些。

            先不着急，我们在对比find接口

            int main()
            {
            	size_t N = 1000000;
            	unordered_set us;
            	set s;
            	vector v;
            	v.reserve(N);
            	srand((unsigned int)time(nullptr));
            	for (size_t i = 0; i < N; ++i)
            	{
            		//v.push_back(rand() + i);
            		v.push_back(rand());
            		//v.push_back(i);
            	}
            	size_t begin1 = clock();
            	for (auto e : v)
            	{
            		s.insert(e);
            	}
            	size_t end1 = clock();
            	cout << "set insert: " << end1 - begin1 << endl;
            	size_t begin2 = clock();
            	for (auto e : v)
            	{
            		us.insert(e);
            	}
            	size_t end2 = clock();
            	cout << "unordered_set insert: " << end2 - begin2 << endl;
            	size_t begin3 = clock();
            	for (auto e : v)
            	{
            		s.find(e);
            	}
            	size_t end3 = clock();
            	cout << "set find: " << end3 - begin3 << endl;
            	size_t begin4 = clock();
            	for (auto e : v)
            	{
            		us.find(e);
            	}
            	size_t end4 = clock();
            	cout << "unordered_set find: " << end4 - begin4 << endl;
            	return 0;
            }
            

            这个find在VS2019,release下没测出来，我们在debug下跑的才能看出区别

            

            

            unordered_set底层是哈希，是一种映射关系，就比如书上有一段话，通过映射关系直接找到在那一页，然后再找。而搜索树是比它大往右走比它小往左走。

            

            

            不管是有序set最好的情况下，还是无序，unordered_set的find都比set的要快。

            最后在看一看删除。

            	size_t begin5 = clock();
            	for (auto e : v)
            	{
            		s.erase(e);
            	}
            	size_t end5 = clock();
            	cout << "set erase: " << end5 - begin5 << endl;
            	size_t begin6 = clock();
            	for (auto e : v)
            	{
            		us.erase(e);
            	}
            	size_t end6 = clock();
            	cout << "set erase: " << end6 - begin6 << endl;
            

            

            

            

            对比这些插入，删除，查找就说明一个事情：不同场景不一定unordered_map和unordered_set比map和set好，也不一定就比map和set差，各有优势，但在任何场景下find，unordered_map和unordered_set一定比map和set好。

            2.哈希表

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

            理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。

            如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

            哈希就是一种映射。

            哈希映射：key值跟存储位置建立关联关系

            也就是说知道key值就可以找到存储位置，知道存储位置也可以再去判断在不在，并且K模型，KV模型都可以搞定。

            那如果有一堆整型值来了，哈希映射到表中，会存在什么问题？

            

            是不是值太分散，空间消费太大了。

            如果就像数据结构初阶学过的计数排序那样直接就相对映射了，虽然也可以但是太浪费空间，这种方法也就是我们常用的直接定址法，只适合整型+范围集中。

            1. 直接定址法–(常用)

               取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

               优点：简单、均匀

               缺点：需要事先知道关键字的分布情况

               使用场景：适合查找比较小且连续的情况

            对于这种范围不集中的，我们更喜欢用另一种方法

            2. 除留余数法–(常用)

               设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

            不管你给的我是什么值，假设就是图中的数，我就开10个空间，那一个值来了到底存那呢？我们用这个值去模，模出来余数是几，就存在那个位置。这个时候就和范围不相关了。不管范围是大还是小反正一定能给存到这个表中。

            

            但是这种方法带来了一个新的问题，两个数模之后余数是一样的，3和13都映射到下标3的位置，那这个下标3到底存谁呢？

            

            这就是哈希冲突(碰撞)：不同的值映射到了相同的位置。

            直接定址法是不会有这个问题的。因为直接定址法每个值都有唯一的位置。

            这个问题如何解决呢？

            有两个解决方式:

            1.闭散列 — 开放地址法

            除模取余数是相同的key值，谁先来谁先占据这个位置，后来的往后找下一个空位，要是还被占据就继续往下找。只要这个表没满就找其他空位。

            

            但是这样就影响了其他位置。就如同亮剑里整个晋西北都乱成粥了,那还有其他更好的办法吗?

            2.开散列 — 拉链法(哈希桶)

            每一个数组下标存一个单链表头指针，除模取余数是相同的key值来了之后我就把你挂到同一个链表中。这样就不会影响到其他位置了。

            

            冲突的值用一个这样的单链表挂起来，这也是就一个方向的迭代器的原因。

            如果冲突的值太多了，这挂的链表也太长了，也影响效率。这个我们在写代码的时候解决它。

            2.1闭散列 – 开放地址法

            闭散列 – 开放地址法

            1. 线性探测
            2. 二次探测

            2.1.1线性探测

            我们先把线性探测一说，二次探测也就没有问题了。

            

            插入余数7和余数8你占我的，我占你的。这个我们已经知道了。

            那如何查找呢？比如说查找38，28

            38来了它的映射位置是8，8的位置不是38，继续往下找，最终在2的位置找到38，查找结束

            

            28来了它的映射位置也是8，8的位置不是28，继续往下走，直到遇到空，也就是4的位置，查找结束，不能以值是否为0而结束，万一你找的值就是0呢？这个位置如何为空呢？下面说

            

            删除呢？删除27

            是不是和查找的方式一样啊，要不就找到然后删除，要不就遇到空结束。

            

            这样直接把27删成空对吗？

            那现在在想查找38，28还能找到吗？

            

            是不是最终都在0下标空的位置结束了，结果都没找到，但是38本来是有的。

            如何解决这个问题？

            删除的时候把值置为0，-1？

            这种想法不可行，万一你就是0，-1呢？

            我们可以给每个位置加一个状态！空的位置标记成空，这个位置存了值就标记为存在，删除就标记为删除，但是值我不删还留在这个位置。

            

            这样在查找38、28，38是一定能找到的。

            解决删除影响查找的问题的方法：

            每个位置加一个状态标识

            这样查找就查找到空才能结束，遇到删除并不能停！

            下面我们就实现了

            以前我们没学STL，还需要手搓一个数组，现在我们直接用vector就行了。

            #include
            #include
            using namespace std;
            //枚举 -- 状态
            enum State
            {
            	EMPTY,//空
            	EXIST,//存在
            	DELETE,//删除
            };
            //表中存的数据
            template
            struct HashData
            {
            	pair _kv;//值
            	State _state;//状态标识
            };
            template
            class HashTable
            {
            	typedef HashDate Date;
            public:
            	//...
            private:
            	vector _tables;
            	size_t _n;//哈希表中有效数据个数
            };
            

            插入

            	bool Insert(const pair& kv)
            	{
            		size_t hashi = kv.first % _tables.capacity();
            		size_t hashi = kv.first % _tables.size();
            	}
            

            模的时候是模capacity，还是size呢？

            这里建议模size。因为下面我们要用vector的[ ]接口。

            在vector的时候说过，使用[ ]要小心，可能会报错，在模拟实现的时候我们也模拟了这样的情况其中有一句assert(pos < size())；当前位置要小于size，否则就报错。

            如果你模了capacity

            

            使用[ ]，铁定报错。因此我们要模size。

            并且构造的时候调用resize，调整vector的空间大小。

            template
            struct HashData
            {
            	pair _kv;
            	State _state=EMPTY;
            	//这里我们不用写HashDate构造，默认构造对内置类型不处理，自定义类型调用它的默认构造
            	//所以我们直接给状态一个缺失值就行了
            };
            template
            class HashTable
            {
            	typedef HashData Date;
            public:
            	HashTable()
            		:_n(0)//这里没写vector的构造，系统会自动调用它的默认构造
            	{
            		_tables.resize(10);//先给10后面再说这个空间问题，并且会调用HashDate的默认构造
            	}
            	bool Insert(const pair& kv)
            	{
            		int hashi = kv.first % _tables.size();
            		while (_tables[hashi]._state == EXIST)
            		{
            			//线性探测
            			++hashi;
            			hashi %= _tables.size();//防止出了边界
            		}
            		_tables[hashi]._kv = kv;
            		_tables[hashi]._state = EXIST;
            		++_n;
            		return true;
            	}
            private:
            	vector _tables;
            	size_t _n;//哈希表中有效数据个数
            };
            

            这里只是插入的一部分代码，接下来我们考虑扩容问题。

            哈希表什么情况下进行扩容？如何扩容？

            如果这个表是100，已经插入90了，在插入冲突的概率就极大了。所以闭散列的哈希表绝对不可能让它满的。

            所以提出了这样一个概念：负载因子(载荷因子)

            

            用来衡量表满的程度。

            负载因子越小，冲突概率越小，消耗空间越多

            负载因子越大，冲突概率越大，空间利用率约高

            散列表的载荷因子定义为: α = 填入表中的元素个数/散列表的长度

            α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，表明填入表中的元素越多，产生冲突的可能性就越大﹔反之，α越小，标明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子α的函数，只是不同处理冲突的方法有不同的函数。

            对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中(cachemissing）按照指数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了荷载因子为0.75，超过此值将扩容散列表。

            bool Insert(const pair& kv)
            	{
            		//大于标定负载因子，就需要扩容
            		if (_n / _tables.size() > 0.7)//这样写有没有什么问题
            		{
            		}
            		//。。。
            	}
            

            _n和_tables.size()都是整型，它们俩个相除永远都是0，永远都阔不了容。

            	bool Insert(const pair& kv)
            	{
            		//大于标定负载因子，就需要扩容
            		if (_n*10 / _tables.size() > 7)
            		{
            		}
            		//。。。
            	}
            

            现在问题是如何扩容？

            能不能把数据直接拷贝下来？

            

            不能，表的大小变了，映射关系也就变量，以前是模10，现在应该是模20，所有数据都应该重新映射！

            并且也不建议直接vector.resize()，在当前位置扩容，

            

            这个时候你在映射7，7原本就是下标7位置存着，只能往后走到下标10的位置。但是就不对了。

            所以我们最终是异地扩容，并且在重新映射！

            这里我们也不要重新申请一个vector，而是重新申请一个类，复用insert，最后再把两个vector交换一下就好了。这样就省得在扩容内部在写插入代码造成代码冗余了。

            bool Insert(const pair& kv)
            	{
            		//大于标定负载因子，就需要扩容
            		if (_n*10 / _tables.size() > 7)
            		{
            			//旧表数据,重新计算,映射到新表
            	
            			//vector _newtable;
            			//_newtable.resize(_tables.size() * 2);
            			//for ()
            			//{
            			//这里重写插入的代码
            			//}
            			HashTable newHt;
            			newHt._tables.resize(_tables.size() * 2);//先每个扩容2倍,后面再每个扩容多大的问题
            			for (size_t i = 0; i < _tables.size(); ++i)
            			{
            				if (_tables[i]._state == EXIST)
            				{
            					newHt.Insert(_tables[i]._kv);//复用insert
            				}
            			}
            			_tables.swap(newHt._tables);//交换哈希表
            		}//走到这里调用HashTable的析构,把旧表释放,直接用默认的就行
            		int hashi = kv.first % _tables.size();
            		while (_tables[hashi]._state == EXIST)
            		{
            			//线性探测
            			++hashi;
            			hashi %= _tables.size();//防止出了边界
            		}
            		_tables[hashi]._kv = kv;
            		_tables[hashi]._state = EXIST;
            		++_n;
            		return true;
            	}
            

            插入还差最后一步，不允许插入相同的值，下面我先把查找写了之后，再把插入最后一点代码补充上。

            查找

            	Date* Find(const K& key)
            	{
            		size_t hashi = 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;
            	}
            

            如果是极端场景下，这个代码会不会有问题？假设表大小是10，存在的5个，删除的是5个，是不是查找一个不是插入的数，while这样判断就死循环了？

            所以我们可以让查找一圈了就如果没找到就结束。

            	Date* Find(const K& key)
            	{
            		size_t hashi = key % _tables.size();
            		size_t start = hashi;
            		while (_tables[hashi]._state != EMPTY)
            		{
            			//必须加上存在,不然有可能这个值本来就是删除的,但还是找到了
            			if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
            				return &_tables[hashi];
            			++hashi;
            			hashi%= _tables.size();
            			if (start == hashi) //查找一圈就结束.防止极端条件下死循环
            				break;
            		}
            		return nullptr;
            	}
            

            现在把插入代码补充完

            bool Insert(const pair& kv)
            	{
            		//防止插入相同的值
            		if (Find(kv.first))
            			return false;
            		//大于标定负载因子，就需要扩容
            		if (_n*10 / _tables.size() > 7)
            		{
            			//旧表数据,重新计算,映射到新表
            	
            			//vector _newtable;
            			//_newtable.resize(_tables.size() * 2);
            			//for ()
            			//{
            			//这里重写插入的代码
            			//}
            			HashTable newHt;
            			newHt._tables.resize(_tables.size() * 2);//先每个扩容2倍,后面再每个扩容多大的问题
            			for (size_t i = 0; i < _tables.size(); ++i)
            			{
            				if (_tables[i]._state == EXIST)
            				{
            					newHt.Insert(_tables[i]._kv);//复用insert
            				}
            			}
            			_tables.swap(newHt._tables);//交换哈希表
            		}//走到这里调用HashTable的析构,把旧表释放,直接用默认的就行
            		int hashi = kv.first % _tables.size();
            		while (_tables[hashi]._state == EXIST)
            		{
            			//线性探测
            			++hashi;
            			hashi %= _tables.size();//防止出了边界
            		}
            		_tables[hashi]._kv = kv;
            		_tables[hashi]._state = EXIST;
            		++_n;
            		return true;
            	}
            

            删除

            bool Erase(const K& key)
            	{
            		//找到就删除
            		Date* ret = Find(key);
            		if (ret)
            		{
            			--_n;
            			ret->_state = DELETE;
            			return true;
            		}
            		else
            		{
            			return false;
            		}
            	}
            

            针对插入查找做的修改

            对于整型我们的代码是没有问题的，那字符串呢？

            void TestHT2()
            {
            	string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
            	HashTable countHT;
            	for (auto& e : arr)
            	{
            		HashData* ret = countHT.Find(e);
            		if (ret)
            		{
            			ret->_kv.second++;
            		}
            		else
            		{
            			countHT.Insert(make_pair(e, 1));
            		}
            	}
            }
            

            

            以前是整数可以直接取模，现在是字符串还能取模吗？

            如何解决？

            有可能你会想到取字符串首字母转成整型再取模

            那如果是下面这种汉字字符串还可以取首字母吗？

            

            其实也可以取汉字的首字母了，汉字通常是由多个字母构成的，通过多个字母去查我们的编码表，它底层还是存的一个一个字符，只是说多个字符构成一个汉字，一般是两个字符。

            注意stoi只能把"1234"这样字符数字的字符串转成1234。所以这里也不能用。

            但是如果只取第一个字母（字母底层是char类型的也是整型家族的），那肯定第一个字母相同的串肯定就冲突，有没有更好的办法？

            下面我们先把这个方法实现一下再说其他的。

            这样直接去改可不可以？

            

            答案是不行的，字符串可以这样用，整型不可以。

            

            所以取整型我们写个仿函数。

            template
            struct HashFunc
            {
            	//凡是能转成整型的就转成整型 如负数,如指针,如浮点数
            	//string不能转
            	size_t operator()(const K& key)
            	{
            		return (size_t)key;
            	}
            };
            struct HashFuncString
            {
            	//string取首字母转整型
            	size_t operator()(const string& key)
            	{
            		return key[0];
            	}
            };
            

            把取整数的地方都添上仿函数

            template>
            class HashTable
            {
            	//。。。
            	bool Insert(const pair& kv)
            	{
            		//防止插入相同的值
            		if (Find(kv.first))
            			return false;
            		//大于标定负载因子，就需要扩容
            		if (_n*10 / _tables.size() > 7)
            		{
            			HashTable newHt;
            			newHt._tables.resize(_tables.size() * 2);//先每个扩容2倍,后面再每个扩容多大的问题
            			for (size_t i = 0; i < _tables.size(); ++i)
            			{
            				if (_tables[i]._state == EXIST)
            				{
            					newHt.Insert(_tables[i]._kv);//复用insert
            				}
            			}
            			_tables.swap(newHt._tables);//交换哈希表
            		}//走到这里调用HashTable的析构,把旧表释放,直接用默认的就行
            		
            		//转成整型仿函数
            		Hash hf;
            		int hashi = hf(kv.first) % _tables.size();
            		while (_tables[hashi]._state == EXIST)
            		{
            			//线性探测
            			++hashi;
            			hashi %= _tables.size();//防止出了边界
            		}
            		_tables[hashi]._kv = kv;
            		_tables[hashi]._state = EXIST;
            		++_n;
            		return true;
            	}
            	Date* Find(const K& key)
            	{
            		//转成整型仿函数
            		Hash hf;
            		size_t hashi = hf(key) % _tables.size();
            		size_t start = hashi;
            		while (_tables[hashi]._state != EMPTY)
            		{
            			//必须加上存在,不然有可能这个值本来就是删除的,但还是找到了
            			if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
            				return &_tables[hashi];
            			++hashi;
            			hashi%= _tables.size();
            			if (start == hashi) //查找一圈就结束.防止极端条件下死循环
            				break;
            		}
            		return nullptr;
            	}
            	//。。。
            }
            

            void TestHT2()
            {
            	string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
            	
            	//这里给一个把string转成整型的类，就没问题了
            	HashTable countHT;
            	for (auto& e : arr)
            	{
            		HashData* ret = countHT.Find(e);
            		if (ret)
            		{
            			ret->_kv.second++;
            		}
            		else
            		{
            			countHT.Insert(make_pair(e, 1));
            		}
            	}
            }
            

            那万一我的K不是string，而是vector< string>呢，这个时候怎么办？

            只能针对这个类型写一个仿函数，想办法把这个类型转换成整型。

            总之就是灵活的把你所给的自定义类型转换成整型！

            

            所以unordered_map和unordered_set第二个模板参数给了一个hash< key>，能返回整型就直接返回整型，不能就自己写一个仿函数传过去。

            我们这里把字符串首字母返回，只要首字母相同就冲突。我们换一种写法。把字符串每个字符的ASCLL码加起来。这样会好一点。

            struct HashFuncString
            {
            	//string取全部字母转整型
            	size_t operator()(const string& key)
            	{
            		size_t num = 0;
            		for (auto& ch : key)
            		{
            			num += ch;
            		}
            		return num;
            	}
            };
            

            但是这样还是不太好，再继续说它之前，我们插入一个知识。

            void TestHT2()
            {
            	string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
            	//HashTable countHT;
            	unordered_map countHT;
            	for (auto& e : arr)
            	{
            		//HashData* ret = countHT.find(e);
            		auto it = countHT.find(e);
            		if (it != countHT.end())
            		{
            			it->second++;
            			//ret->_kv.second++;
            		}
            		else
            		{
            			countHT.insert(make_pair(e, 1));
            		}
            	}
            }
            

            为什么这里我们不用传自己写的把字符串转成整型的仿函数，直接用库里的就可以了，它怎么做的呢？

            这里用我们以前学的一个知识模板特化

            通常情况下，使用模板可以实现一些与类型无关的代码，但是对于一些特殊类型可能会得到一些错误的结果。此时，就需要对模板进行特化。即：在原模版类的基础上，针对特殊类型所进行特殊化的实现方式。

            具体知识看这里模板进阶

            template
            struct HashFunc
            {
            	//凡是能转成整型的就转成整型 如负数,如指针,如浮点数
            	//string不能转
            	size_t operator()(const K& key)
            	{
            		return (size_t)key;
            	}
            };
            //模板特化
            template<>
            struct HashFunc
            {
            	size_t operator()(const string& key)
            	{
            		size_t num = 0;
            		for (auto& ch : key)
            		{
            			num += ch;
            		}
            		return num;
            	}
            }
            

            

            这个知识说完，我们再回到上面的问题，不是直接加ASCLL码吗

            

            虽然字符串不同，但是转换成整型都是一样的。

            怎么办？

            直接想加太简单了，给一个复杂的相加规则。

            大佬给了一些办法字符串哈希算法

            

            这里就给了一个常用的办法。

            每次都把上一次的结果乘131在加每个字母的ASCLL码。

            //模板特化
            template<>
            struct HashFunc
            {
            	size_t operator()(const string& key)
            	{
            		size_t num = 0;
            		for (auto& ch : key)
            		{
            			num *= 131;
            			num += ch;
            		}
            		return num;
            	}
            };
            

            

            这样就极大的减少了冲突。

            问：

            map和unordered_map有什么区别？从用的方式对key有没有什么要求？

            答：

            区别可以从底层回答。map底层是一颗搜索树，对key的要求是比较大小，遵守key大的往右比key小的往左的规则，unordered_map底层是哈希表。对key的要求是转成整型，如果不支持直接转成整型要给一个仿函数使它转成整型。

            线性探测完整代码

            template
            struct HashFunc
            {
            	//凡是能转成整型的就转成整型 如负数,如指针,如浮点数
            	//string不能转
            	size_t operator()(const K& key)
            	{
            		return (size_t)key;
            	}
            };
            //模板特化
            template<>
            struct HashFunc
            {
            	//BKDR
            	size_t operator()(const string& key)
            	{
            		size_t num = 0;
            		for (auto& ch : key)
            		{
            			num *= 131;
            			num += ch;
            		}
            		return num;
            	}
            };
            //状态
            enum State
            {
            	EMPTY,
            	EXIST,
            	DELETE,
            };
            template
            struct HashData
            {
            	pair _kv;
            	State _state=EMPTY;
            };
            template>
            class HashTable
            {
            	typedef HashData Date;
            public:
            	HashTable()
            		:_n(0)
            	{
            		_tables.resize(10);//先给10后面再说这个空间问题
            	}
            	bool Insert(const pair& kv)
            	{
            		//防止插入相同的值
            		if (Find(kv.first))
            			return false;
            		//大于标定负载因子，就需要扩容
            		if (_n*10 / _tables.size() > 7)
            		{
            			//旧表数据,重新计算,映射到新表
            			//vector _newtable;
            			//_newtable.resize(_tables.size() * 2);
            			//for ()
            			//{
            			//这里重写插入的代码
            			//}
            			HashTable newHt;
            			newHt._tables.resize(_tables.size() * 2);//先每个扩容2倍,后面再每个扩容多大的问题
            			for (size_t i = 0; i < _tables.size(); ++i)
            			{
            				if (_tables[i]._state == EXIST)
            				{
            					newHt.Insert(_tables[i]._kv);//复用insert
            				}
            			}
            			_tables.swap(newHt._tables);//交换哈希表
            		}//走到这里调用HashTable的析构,把旧表释放,直接用默认的就行
            		Hash hf;
            		int hashi = hf(kv.first) % _tables.size();
            		while (_tables[hashi]._state == EXIST)
            		{
            			//线性探测
            			++hashi;
            			hashi %= _tables.size();//防止出了边界
            		}
            		_tables[hashi]._kv = kv;
            		_tables[hashi]._state = EXIST;
            		++_n;
            		return true;
            	}
            	Date* Find(const K& key)
            	{
            		Hash hf;
            		size_t hashi = hf(key) % _tables.size();
            		size_t start = hashi;
            		while (_tables[hashi]._state != EMPTY)
            		{
            			//必须加上存在,不然有可能这个值本来就是删除的,但还是找到了
            			if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
            				return &_tables[hashi];
            			++hashi;
            			hashi%= _tables.size();
            			if (start == hashi) //查找一圈就结束.防止极端条件下死循环
            				break;
            		}
            		return nullptr;
            	}
            	bool Erase(const K& key)
            	{
            		Date* ret = Find(key);
            		if (ret)
            		{
            			--_n;
            			ret->_state = DELETE;
            			return true;
            		}
            		else
            		{
            			return false;
            		}
            	}
            private:
            	vector _tables;
            	size_t _n;//哈希表中有效数据个数
            };
            

            闭散列不需要自己写析构，拷贝构造，赋值重载。

            自定义类型自己会调，内置类型不管是析构对内置类型不处理，还是拷贝构造、赋值重载对内置类型值拷贝都能满足需求，因此不需要自己写。

            2.1.2二次探测

            二次探测是一个跳跃式的探测，往前一次，往后一次。

            就比如一个取余为7的值，冲突之后再次探测7 + 1^2=8也冲突，再次探测 7 - 1^2=6不冲突直接就可以插入了。当然查找也要按照这种方式去查。

            

            除了插入和查找代码修改一下，其他不用变。

            	bool Insert(const pair& kv)
            	{
            		//防止插入相同的值
            		if (Find(kv.first))
            			return false;
            		//大于标定负载因子，就需要扩容
            		if (_n*10 / _tables.size() > 7)
            		{
            			//旧表数据,重新计算,映射到新表
            	
            			//vector _newtable;
            			//_newtable.resize(_tables.size() * 2);
            			//for ()
            			//{
            			//这里重写插入的代码
            			//}
            			HashTable newHt;
            			newHt._tables.resize(_tables.size() * 2);//先每个扩容2倍,后面再每个扩容多大的问题
            			for (size_t i = 0; i < _tables.size(); ++i)
            			{
            				if (_tables[i]._state == EXIST)
            				{
            					newHt.Insert(_tables[i]._kv);//复用insert
            				}
            			}
            			_tables.swap(newHt._tables);//交换哈希表
            		}//走到这里调用HashTable的析构,把旧表释放,直接用默认的就行
            		Hash hf;
            		int hashi = hf(kv.first) % _tables.size();
            		//闭散列--二次探测 
            		int start = hashi;
            		int odd = 1;
            		int even = 1;
            		int oddeven = 1;//控制start每次加的是正的还是负的
            		while (_tables[hashi]._state == EXIST)
            		{
            			//二次探测 i=1,-1,2,-2,3,-3...
            			if (oddeven % 2 != 0)//奇数start+i^2 (i=1,2,3,4...)
            			{
            				hashi = start + (int)pow(odd++, 2);
            			}
            			else//偶数start-i^2 (i=1,2,3,4...) 
            			{
            				hashi = start + ((int)pow(even++, 2) * -1);
            			}
            			++oddeven;
            			hashi %= _tables.size();
            		}
            		_tables[hashi]._kv = kv;
            		_tables[hashi]._state = EXIST;
            		++_n;
            		return true;
            	}
            	Date* Find(const K& key)
            	{
            		Hash hf;
            		size_t hashi = hf(key) % _tables.size();
            		size_t start = hashi;//防止查找死循环
            		int begin = hashi;//二次探测要用的
            		int odd = 1;
            		int even = 1;
            		int oddeven = 1;
            		while (_tables[hashi]._state != EMPTY)
            		{
            			//必须加上存在,不然有可能这个值本来就是删除的,但还是找到了
            			if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
            				return &_tables[hashi];
            			//二次探测
            			if (oddeven % 2 != 0)
            			{
            				hashi = begin + (int)pow(odd++, 2);
            			}
            			else
            			{
            				hashi = begin + ((int)pow(even++, 2) * -1);
            			}
            			++oddeven;
            			hashi %= _tables.size();
            			if (start == hashi) //查找一圈就结束.防止极端条件下死循环
            				break;
            		}
            		return nullptr;
            	}
            

            2.2开散列 – 拉链法(哈希桶)

            相同余数的值来了再同一个链表中挂起来，原理我们都知道了，下面就来实现它。

            template
            struct HashFunc
            {
            	size_t operator()(const K& key)
            	{
            		return (size_t)key;
            	}
            };
            //模板特化
            template<>
            struct HashFunc
            {
            	//BKDR
            	size_t operator()(const string& key)
            	{
            		size_t num = 0;
            		for (auto& ch : key)
            		{
            			num *= 131;
            			num += ch;
            		}
            		return num;
            	}
            };
            template
            struct HashNode
            {
            	pair _kv;
            	HashNode* _next;//指向链表中下一个节点
            	
            	HashNode(const pair& kv)
            		:_kv(kv)
            		,_next(nullptr)
            	{}
            };
            template>
            class HashTable
            {
            	typedef HashNode Node;
            public:
            	HashTable()
            		:_n(0)
            	{
            		_tables.resize(10);//resize也会调用HashNode的构造
            	}
            private:
            	vector _tables;//数组中位置都存链表的头指针,相当于一个指针数组
            	size_t _n;
            	};
            

            插入

            余数相同的值来了，头插还是尾插？

            建议头插，不然每次都要找链表尾部太麻烦了。同一个桶谁在前谁在后都可以。并且数组里存的是头指针的地址非常方便。

            库里面的单向迭代器就是底层挂的是单链表的原因。当然你也可以改成双向链表那自然就有双向迭代器了。

            

            	bool Insert(const pair& kv)
            	{
            		//Hash匿名对象去调用仿函数,算在第几个桶
            		int hashi = Hash()(kv.first) % _tables.size();
            		//头插
            		Node* newnode = new Node(kv);//调用Node的构造,因此Node写个构造
            		newnode->_next = _tables[hashi];
            		_tables[hashi] = newnode;
            		++_n;
            		return true;
            	
            

            接下来就是扩容，什么时候扩容？

            桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行扩容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表扩容，也就说负载因子是1的时候扩容。

            下面问题是怎么扩容呢？还想闭散列那样重新申请一个类？这样做有没有什么问题？

            bool Insert(const pair& kv)
            {
            	//负载因子控制在1,超过就扩容
            	if (_n == _tables.size())
            	{
            		//重新申请一个类,复用Insert
            		HashTable newHT;
            		newHT._tables.resize(_tables.size() * 2);
            		for (auto cur : _tables)
            		{
            			while (cur)
            			{
            				newHT.Insert(cur->_kv);
            				cur = cur->_next;
            			}
            		}
            		_tables.swap(newHT._tables);//交换，有点像拷贝构造那种现代写法
            	}//走到这里调用HashTable的析构
            	//匿名对象去调用仿函数,算在第几个桶里面
            	int hashi = Hash()(kv.first) % _tables.size();
            	//头插
            	Node* newnode = new Node(kv);//调用Node的构造,因此Node写个构造
            	newnode->_next = _tables[hashi];
            	_tables[hashi] = newnode;
            	++_n;
            	return true;
            } 
            

            哈希桶的析构要不要写？使用默认的析构能不能正确释放空间呢？

            这个需要对vector底层有一点了解，vector的析构不会释放链表，所以造成空间浪费了，因此我们写哈希桶的析构，同样也需要自己写拷贝构造，赋值重载，因为默认生成的拷贝构造，赋值重载调用vector得，但是vector对Node*这个指针也是内置类型只完成了值拷贝(浅拷贝)。这个我们后面再补充。

            先写析构。

            HashTable()
            	:_n(0)//这里虽然没有明确写调用vector构造,但是编译器会按照声明顺序去调用的,所以会自动调用vecto的构造
            {
            	_tables.resize(10);//调用HashNode的构造
            }
            ~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;
            	}
            }//走到这里会自动调用vector的析构
            

            当前扩容还没有优化的空间？

            按照目前写的，首先会调用构造，然后在insert把旧表的数据拿下来在new一个新的数据在插入，最后调用析构把旧表和旧数据释放，

            

            这样效率是不是有点慢了。能不能不释放旧表节点，把旧表节点重新映射到新表。

            因此我们在扩容时只需要申请一个vector就好了，把旧表节点重新映射到新表。

            bool Insert(const pair& kv)
            {
            	//负载因子控制在1,超过就扩容
            	if (_n == _tables.size())
            	{
            		//重新申请一张表，把旧表节点重新映射到新表
            		vector newtable;
            		newtable.resize(_tables.size() * 2);
            		for (size_t i = 0; i < _tables.size(); ++i)
            		{
            			Node* cur = _tables[i];
            			//头插到新表
            			while (cur)
            			{
            				Node* next = cur->_next;
            				size_t hashi = Hash()(cur->_kv.first) % newtable.size();
            				cur->_next = newtable[hashi];
            				newtable[hashi] = cur;
            				cur = next;
            			}
            			_tables[i] = nullptr;
            		}
            		_tables.swap(newtable);//旧表和新表交换一
            	}
            	//匿名对象去调用仿函数,算在第几个桶里面
            	int hashi = Hash()(kv.first) % _tables.size();
            	//头插
            	Node* newnode = new Node(kv);//调用Node的构造,因此Node写个构造
            	newnode->_next = _tables[hashi];
            	_tables[hashi] = newnode;
            	++_n;
            	return true;
            }
            

            接下来就是防止插入相同的值了，也是一样，先把查找写一下，然后再补充插入的。

            查找

            Node* Find(const K& key)
            {
            	size_t hashi = Hash()(key) % _tables.size();
            	Node* cur = _tables[hashi];
            	while (cur)
            	{
            		if (cur->_kv.first == key)
            			return cur;
            		else
            			cur = cur->_next;
            	}
            	return nullptr;
            }
            

            插入完整代码

            bool Insert(const pair& kv)
            {
            	//防止插入相同的值
            	if (Find(kv.first))
            		return false;
            	//负载因子控制在1,超过就扩容
            	if (_n == _tables.size())
            	{
            		vector newtable;
            		newtable.resize(_tables.size() * 2);
            		for (size_t i = 0; i < _tables.size(); ++i)
            		{
            			Node* cur = _tables[i];
            			//头插到新表
            			while (cur)
            			{
            				Node* next = cur->_next;
            				size_t hashi = Hash()(cur->_kv.first) % newtable.size();
            				cur->_next = newtable[hashi];
            				newtable[hashi] = cur;
            				cur = next;
            			}
            			_tables[i] = nullptr;
            		}
            		_tables.swap(newtable);//旧表和新表交换一下
            	}
            	//匿名对象去调用仿函数,算在第几个桶里面
            	int hashi = Hash()(kv.first) % _tables.size();
            	//头插
            	Node* newnode = new Node(kv);//调用Node的构造,因此Node写个构造
            	newnode->_next = _tables[hashi];
            	_tables[hashi] = newnode;
            	++_n;
            	return true;
            }
            

            删除

            删除不能再直接查找了，然后就删除了。因为我们这是单链表，需要知道该节点前一个位置！也不能使用单链表那种O(1)那种覆盖删除法。

            

            所以老老实实的去找，然后再删。

            bool Erase(const K& key)
            {
            	size_t hashi = Hash()(key) % _tables.size();
            	Node* cur = _tables[hashi];
            	Node* prev = nullptr;//记录被删节点前一个位置
            	while (cur)
            	{
            		if (cur->_kv.first == key)
            		{
            			if (cur == _tables[hashi])//被删节点是头一个节点
            			{
            				_tables[hashi] = cur->_next;
            			}
            			else 
            			{
            				prev->_next = cur->_next;
            			}
            			delete cur;
            			return true;
            		}
            		else
            		{
            			prev = cur;
            			cur = cur->_next;
            		}
            	}
            	return false;
            }
            

            除留余数法取质数

            这里我们看看库是怎么取的

            

            库里给我们定义了一个质数表，第一次是53扩容2倍是106肯定不是质数了，因此选了一个靠近106的质数97，也算是接近2倍空间扩容了。

            在我们的代码哈希表也加上这个取质数的函数。

            inline unsigned long __stl_next_prime(unsigned long n)
            {
            	static const int __stl_num_primes = 28;
            	static const unsigned long __stl_prime_list[__stl_num_primes] =
            	{
            	  53,         97,         193,       389,       769,
            	  1543,       3079,       6151,      12289,     24593,
            	  49157,      98317,      196613,    393241,    786433,
            	  1572869,    3145739,    6291469,   12582917,  25165843,
            	  50331653,   100663319,  201326611, 402653189, 805306457,
            	  1610612741, 3221225473, 4294967291
            	};//最大质数取得是靠近整型最大数得质数
            	for (size_t i = 0; i < __stl_num_primes; ++i)
            	{
            		//找比当前空间大的质数
            		if (__stl_prime_list[i] > n)
            			return __stl_prime_list[i];
            	}
            	//不用担心会哈希表会扩到最大质数,因为这时对于整型来说都已经差不多48G了
            	return __stl_prime_list[__stl_num_primes - 1];
            }
            

            构造和插入扩容也都需要改一下

            构造获取比0大的质数

            插入扩容获取比当前空间大的质数

            

            拷贝构造

            HashTable(const HashTable& ht)
            	:_n(ht._n)
            {
            	_tables.resize(ht._tables.size());
            	for (size_t i = 0; i < ht._tables.size(); ++i)
            	{
            		//遍历找头指针
            		Node* cur = ht._tables[i];
            		if (cur)
            		{
            			//找到之后重新申请节点插入新哈希表
            			Node* copy = new Node(cur->_kv);
            			_tables[i] = copy;
            			//如果该链表不止一个节点，把其他节点拿下来重新申请节点尾插
            			while (cur->_next)
            			{
            				cur = cur->_next;
            				//尾插
            				copy->_next = new Node(cur->_kv);
            				copy = copy->_next;
            			}
            		}
            	}
            }
            

            赋值重载

            //赋值重载现代写法 复用拷贝构造
            HashTable& operator=(HashTable ht)
            {
            	_n = ht._n;
            	_tables.swap(ht._tables);
            	return *this;//返回之前会自动调用HashTable的析构，释放对象ht
            }
            

            哈希桶完整代码

            	template
            	struct HashFunc
            	{
            		//凡是能转成整型的就转成整型 如负数,如指针,如浮点数
            		//string不能转
            		size_t operator()(const K& key)
            		{
            			return (size_t)key;
            		}
            	};
            	//模板特化
            	template<>
            	struct HashFunc
            	{
            		//BKDR
            		size_t operator()(const string& key)
            		{
            			size_t num = 0;
            			for (auto& ch : key)
            			{
            				num *= 131;
            				num += ch;
            			}
            			return num;
            		}
            	};
            	template
            	struct HashNode
            	{
            		pair _kv;
            		HashNode* _next;
            		HashNode(const pair& kv)
            			:_kv(kv)
            			,_next(nullptr)
            		{}
            	};
            	template>
            	class HashTable
            	{
            		typedef HashNode Node;
            	public:
            		HashTable()
            			:_n(0)//这里虽然没有明确写调用vector构造,但是编译器会按照声明顺序去调用的,所以会自动调用vecto的构造
            		{
            			//_tables.resize(10);//调用HashNode的构造
            			_tables.resize(__stl_next_prime(0));
            		}
            		~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;
            			}
            		}//走到这里会自动调用vector的析构
            		HashTable(const HashTable& ht)
            			:_n(ht._n)
            		{
            			_tables.resize(ht._tables.size());
            			for (size_t i = 0; i < ht._tables.size(); ++i)
            			{
            				Node* cur = ht._tables[i];
            				if (cur)
            				{
            					Node* copy = new Node(cur->_kv);
            					_tables[i] = copy;
            					while (cur->_next)
            					{
            						cur = cur->_next;
            						//尾插
            						copy->_next = new Node(cur->_kv);
            						copy = copy->_next;
            					}
            				}
            			}
            		}
            		//赋值重载现代写法 复用拷贝构造
            		HashTable& operator=(HashTable ht)
            		{
            			_n = ht._n;
            			_tables.swap(ht._tables);
            			return *this;
            		}
            		bool Insert(const pair& kv)
            		{
            			if (Find(kv.first))
            				return false;
            			//负载因子控制在1,超过就扩容
            			if (_n == _tables.size())
            			{
            				vector newtable;
            				//newtable.resize(_tables.size() * 2);
            				newtable.resize(__stl_next_prime(_tables.size()));
            				for (size_t i = 0; i < _tables.size(); ++i)
            				{
            					Node* cur = _tables[i];
            					//头插到新表
            					while (cur)
            					{
            						Node* next = cur->_next;
            						size_t hashi = Hash()(cur->_kv.first) % newtable.size();
            						cur->_next = newtable[hashi];
            						newtable[hashi] = cur;
            						cur = next;
            					}
            					_tables[i] = nullptr;
            				}
            				_tables.swap(newtable);//旧表和新表交换一下
            			}
            			//匿名对象去调用仿函数,算在第几个桶里面
            			int hashi = Hash()(kv.first) % _tables.size();
            			//头插
            			Node* newnode = new Node(kv);//调用Node的构造,因此Node写个构造
            			newnode->_next = _tables[hashi];
            			_tables[hashi] = newnode;
            			++_n;
            			return true;
            		}
            		Node* Find(const K& key)
            		{
            			size_t hashi = Hash()(key) % _tables.size();
            			Node* cur = _tables[hashi];
            			while (cur)
            			{
            				if (cur->_kv.first == key)
            					return cur;
            				else
            					cur = cur->_next;
            			}
            			return nullptr;
            		}
            		bool Erase(const K& key)
            		{
            			size_t hashi = Hash()(key) % _tables.size();
            			Node* cur = _tables[hashi];
            			Node* prev = nullptr;//记录被删节点前一个位置
            			while (cur)
            			{
            				if (cur->_kv.first == key)
            				{
            					if (cur == _tables[hashi])//被删节点是头一个节点
            					{
            						_tables[hashi] = cur->_next;
            					}
            					else 
            					{
            						prev->_next = cur->_next;
            					}
            					delete cur;
            					return true;
            				}
            				else
            				{
            					prev = cur;
            					cur = cur->_next;
            				}
            			}
            			return false;
            		}
            		inline unsigned long __stl_next_prime(unsigned long n)
            		{
            			static const int __stl_num_primes = 28;
            			static const unsigned long __stl_prime_list[__stl_num_primes] =
            			{
            			  53,         97,         193,       389,       769,
            			  1543,       3079,       6151,      12289,     24593,
            			  49157,      98317,      196613,    393241,    786433,
            			  1572869,    3145739,    6291469,   12582917,  25165843,
            			  50331653,   100663319,  201326611, 402653189, 805306457,
            			  1610612741, 3221225473, 4294967291
            			};//最大质数取得是靠近整型最大数得质数
            			for (size_t i = 0; i < __stl_num_primes; ++i)
            			{
            				if (__stl_prime_list[i] > n)
            					return __stl_prime_list[i];
            			}
            			//不用担心会哈希表会扩到最大质数,因为这时对于整型来说都已经差不多48G了
            			return __stl_prime_list[__stl_num_primes - 1];
            		}
            	private:
            		vector _tables;
            		size_t _n;
            	};
            

             
             免费建网站软件  手机上怎么做网站  产品设计方案范本  阿里企业邮箱  真正免费logo设计  推广网站免费