C++ 哈希表实现

2023-12-13 17:12:54

目录

前言

一、什么是哈希表

二、直接定值法

三、开放定值法（闭散列）

1.开放定制法定义

2.开放定制法实现

2.1类的参数

2.2类的构造

2.3查找实现

2.4插入实现

2.5删除实现

2.6string做key

四、哈希桶（开散列）

1.开散列概念

2.开散列实现

2.1类的参数

2.2类的构造函数?

2.3查找实现

2.4插入实现

2.5?删除实现

2.6string做key

五、哈希桶与set和unordered_set的对比?

前言

什么叫做哈希表？

相信大家在很多地方都听过哈希表这三个字。在之前，我看到java之父余胜军装小白面试的时候，对哈希表那是侃侃而谈，非常的羡慕他对哈希表的理解，在学习哈希表过后，我发现他的难度还不一定比得上红黑树，那让我们今天来揭开哈希表的神秘面纱。

一、什么是哈希表

哈希表跟set和map结构类似，库函数如果是unordered_set，那就是Key模型，库函数如果是unordered_map，那就是Key，Value模型。

表我们很容易理解，那么什么是哈希？

关键值与存储位置，建立一个关联关系，通过收到的Key，对Key进行处理，映射成一个不超过数组索引特殊值，存放在数组中。因此，哈希表也被称做散列表

这样一来，会使得我们查找效率近乎O（1）。

二、直接定值法

1.直接定制法，值和位置关系唯一，每个值都存放在唯一位置。

比如我们统计字符串中小写字母的个数，那么我们仅仅需要开辟26个空间的数组即可，对每一个字母都存放在对应位置（如a存放在索引0处，b存放索引1......z存放索引25）。

但这样也会存在一些问题。

比如数据十分分散的情况下，你需要先找出数组中的最大值和最小值，再来开辟空间存放数据。如下数据，就得开辟99999-2+1个空间，会造成空间的极度浪费。

因此，直接定制法在特殊情况下非常好用，但是普遍性不够。不推荐日常使用.

三、开放定值法（闭散列）

1.开放定制法定义

同样是这串数据，我们可以通过哈希函数让key跟位置建立映射关系。

如，函数为? ? hashi = key % len

比如len==10时，2%10 = 2，因此2存放在索引为2的空间，99%10 = 9? ,99存放在索引为9的空间，以此类推。

这样我们就可以在长度为len个范围内，去找到该值的索引，并存放数据了。

但是这又会引发一个问题：哈希冲突（不同的值映射到相同的位置上去）

不管你所给到的函数是什么样子的，都只可能尽量减少哈希冲突，不可完全避免哈希冲突，因此当发生哈希冲突的时候，我们应该如何处理呢？

1.线性探测法（hashi + i (i>=0)）

? ? ? ? 当你想存放的位置存在数据时，就存放在当前位置的下一个，如果下一个位置也有数据，就存放在下一个的下一个，直到没有数据为止。

2.二次探测法 (hashi +?i^{2}(i>=0))

????????当你想存放的位置存在数据时，存放在i^{2}的位置，i为1就是hashi+1，i为2就是hashi+4，因此类推，直到没有数据为止。

后续还有n次探测等等

2.开放定制法实现

2.1类的参数

首先定义一个枚举代表当前位置的状态，状态有? ?空、存在、删除。为什么要有这三个，而不是存在和不存在。主要是为了如下情况

当我们依次插入23,13,33,34。线性探测存值如下所示。

当我们删除13时。 如果只有存在和不存在，那么我们后续就找不到33和34了，因为找到空（不存在）就会停止。

什么？你说不停止继续找？如果不停止，那我搞个哈希表和线性表有什么区别，那时间复杂度还是O（1）吗？

因此我们需要? ?空、存在、删除三个状态，保证我们遇到删除状态后，能够继续往后寻找。哈希表_tables存放的内容为HashDate，这里使用库里面的vector帮助我们完成哈希表。同时还需要一个长度_n，代表存放了多少个值，如果_n / _tables.size() 的结果达到我们设定的某个值（比如百分之70），这个值我们称做负载因子，达到这个限制值后，如果再插入结点会发生很多的哈希冲突，因此我们需要扩容。

正因为负载因子的存在，就算发生了哈希冲突，我们也能较容易的找到下一个该存放的位置。

enum Status
{
	EMPTY,
	EXIST,
	DELETE,
};

template<class K, class V>
struct HashDate
{
	pair<K, V> _kv;
	Status _s;
};
template<class K,class V>
class HashTable
{
private:
	vector<HashDate<K,V>> _tables;
	size_t _n;
};

2.2类的构造

?构造很简单，我们想让哈希表初始化的时候，帮我们开辟好变量??vector<HashDate<K,V>> _tables??的空间，那么我们调用resize()函数帮助我们开辟空间即可。

HashTable()
{
	_tables.resize(10);
}

2.3查找实现

首先，传入的参数毫无疑问，肯定是key，通过key值判断该值在不在哈希表中。

然后算出key经过哈希函数转化后的值，记为hashi。这个hashi就是我们映射在_tables表里的索引。

我们开始判断是否为空，为空就证明没找到该数据。

不为空，就判断该位置存放的_kv模型的first是否与key值相等，同时判断条件还得加上该位置不能为删除。（为什么要判断是否为删除，因为我们删除函数先找到后，就将他的状态设置为DELETE，并没有重置数据，我们也不知道该将数据重置为什么）

找到了，就范围该位置的地址，不然就线性探测，++hashi往后寻找，代码hashi %= _tables.size();是为了防止越界，发生越界就会回到表的索引0处。直到状态为空结束。

代码部分如下?

HashDate<K,V>* Find(const K& key)
{
	size_t hashi = key % _tables.size();
	while (_tables[hashi]._s != EMPTY)
	{
		if (_tables[hashi]._s != DELETE && _tables[hashi]._kv.first == key)
			return &_tables[hashi];
		hashi++;
		hashi %= _tables.size();
	}
	return nullptr;
}

2.4插入实现

插入的参数是pair模型。

先查看在不在，在就返回false。代表已存在，不能插入了。

依然是先算哈希值，存在就找下一个，为空或者为DELETE我们都选择插入，将状态修改为存在，++_n。

bool Insert(const pair<K,V>& kv)
{
	if (Find(kv.first))
	{
		return false;
	}

	size_t hashi = kv.first % _tables.size();
	while (_tables[hashi]._s == EXIST)
	{
		hashi++;
		hashi %= _tables.size();
	}
	_tables[hashi]._kv = kv;
	_tables[hashi]._s = EXIST;
	++_n;

	return true;
}

我们还差一些东西，比如扩容，当 _n / _tables.size()大于等于负载因子时，需要扩容，代码部分添加到Find函数后面，因为找到该值就会返回，不需要扩容。

????????判断条件就跟负载因子有关，_n / _tables.size()就是我们的负载因子，由于这两个都是整数，因此我们表达式的前后都乘了10。当前的负载因子为0.7。

????????这里我们选择用了更方便的写法，建立了一个新的哈希表newht，将size()开辟为之前的两倍，遍历复用插入，当我们遍历插入完毕后，新哈希表newht的_tables就是我们现在的_tables想要的内容，由于_tables是vector，因此我们调用一下swap就好了。

if (_n*10 / _tables.size() >= 7)
{
	int newcapacity = _tables.size() * 2;
	HashTable<K, V> newHT;
	newHT._tables.resize(newcapacity);
	for (size_t i = 0; i < _tables.size(); i++)
	{
		if(_tables[i]._s == EXIST)
		{
			newHT.Insert(_tables[i]._kv);
		}
	}
	_tables.swap(newHT._tables);
}

我们运行测试一下，没问题。（打印代码不用管，只是方便我们查看，后面会给出，）

2.5删除实现

使用代码复用，通过Find函数找到该key存放的位置。

找到了就将状态置为DELETE，--_n，返回true，没找到就返回false。

bool Erase(const K& key)
{
	HashDate<K, V>* ret = Find(key);
	if (ret)
	{
		ret._s = DELETE;
		--_n;
		return true;
	}
	return false;
}

测试一下?

2.6string做key

之前我们分析的都是整形来做key，自然而然就可以用除法去找到索引，那么string类型呢？在生活中string类型做key可是非常常见的。

这里我们选择添加一个模板参数，并且是缺省的，这个参数的目的就是利用仿函数将支持强转size_t类型的key转成size_t类型，对于其他类型，我们也可以通过一些方法转成size_t类型。

我们针对string类型使用了模板特化，当发现key为string时就会走该函数，因为特化是现成的代码，而上面那个还需要去推演出来类型。

?至于为什么我们代码的sum要*31，这是防止哈希冲突。

如果不处理，如“abc”和“acb”还有“bbb”就会发生哈希冲突，具体可以看大佬的文章字符串Hash函数

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t sum = 0;
		for (auto& e : s)
		{
			sum *= 31;
			sum += e;
		}
		return sum;
	}
};
template<class K,class V ,class Hash = HashFunc<K>>
class HashTable
{
    //相关代码
};

修改一下，在我们所有要对key变成整数的地方都套上一层，这里只套了一个，明白意思就好。?

测试一下代码，由于我们特化了string，并且HashTable第三个模板参数为缺省参数，因此这里可以不传参，如果你的key是自定义类型，那么你需要自己写哈希函数并传参。

四、哈希桶（开散列）

1.开散列概念

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地 址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链 接起来，各链表的头结点存储在哈希表中

开放定制法如下图所示的图片

同样的数据，放在哈希桶如下，就像拉链一样，一个挂着一个。

那么哈希桶的优势在哪里呢？我们可以发现，当我们去寻找4和14这种数据，似乎区别不大。

但是一旦我们寻找54，差距就大了，开放定制法会一直找到9的后面才结束，而哈希桶只需要将当前挂载的链表找完就可以了。

再比如我们寻找9，开放定制法会一直找到9才结束，而哈希桶一下就找到了。

在Java JDK1.8版本中，如果某个链表长度超过了8，会选择挂载红黑树，增加效率，C++还没有这样做，至于为什么，我们在实现中会测试，大家一起往下看吧。

2.开散列实现

2.1类的参数

我们的_tables里面存放的是结点，为什么不用库里面的list呢？

首先，我们只需要单向链表即可，要用也是用库里面的forward_list(单向链表)，其次，使用库里面的链表会让我们后续封装迭代器更加麻烦，最后，使用自己手写结点也很简单，因此选择自己写一个。

HashNode存放_kv和_next，并且写出了构造函数，方便我们new结点。

template<class K, class V>
struct HashNode
{
	pair<K, V> _kv;
	HashNode<K, V>* _next;
	HashNode(const pair<K,V>& kv)
		:_kv(kv)
		,_next(nullptr)
	{}
};

template<class K, class V>
class HashTable
{
	typedef HashNode<K, V> Node;
public:
    HashTable()
    {
	    _tables.resize(10);
    }
private:
	vector<Node*> _tables;
	size_t _n;
};

2.2类的构造函数?

1.默认构造给_tables开辟十个空间。

2.拷贝构造我们也要自己写，需要深拷贝，选择头插，老生常谈的东西了。

3.operator= 赋值拷贝，传参选择不传&，这样就会发生拷贝构造，同时不传const，因为我们析构后会删除。再调用swap函数即可，将别人的交换一下，出了作用域自动调用析构函数。

4.析构函数遍历加一个个节点删除即可。

HashTable()
{
	_tables.resize(10);
}
HashTable(const HashTable<K,V>& ht)
{
	_tables.resize(ht._tables.size(), nullptr);
	for (size_t i = 0; i < ht._tables.size(); i++)
	{
		Node* cur = ht._tables[i];
		while (cur)
		{
			Node* newnode = new Node(cur->_kv);
			if (_tables[i]==nullptr)
			{
				_tables[i] = newnode;
			}
			else
			{
				newnode->_next = _tables[i];
				_tables[i] = newnode;
			}
			cur = cur->_next;
		}
	}
}

HashTable<K, V>& operator=(HashTable<K, V> ht)
{
	_tables.swap(ht._tables);
	swap(_n, ht._n);
	return *this;
}


~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;
	}
}

2.3查找实现

一样先计算哈希值hashi，通过hashi去找到存放在_tables里面的结点，结点不为空，就证明该节点存放了链表，便开始遍历链表，找到就返回结点，没找到就一直找，直到为空。

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

2.4插入实现

开散列的插入大致思路跟开放定制法一样，先查找，在判断负载因子，最后插入。

我们先来看插入部分，先计算映射的哈希值hashi，再new一个新节点，将新节点的_next指向hashi的地址，再将新节点复制给hashi，这样就完成了头插，最后++_n。具体插入如下图所示，newnode为11

对于扩容部分，由于是拉链法，负载因子可以适当大一点，因此我们将负载因子调整到了1，也就是_n==_tables.size()。并且我们并没有像开放定制法那样复用Insert，因为复用insert又会开辟新结点，并且析构函数需要自己写，因为HashNode是自定义类型，并且有指针。这样析构起来速度会很慢，因此我们选择将原来_tables上的结点直接挪动过来，这样也节省了开辟结点和析构结点的时间。

代码部分新创建一个newtables，先开辟原哈希表2倍的大小，遍历原哈希表，将挂载的索引节点重新映射到新表上，依然选择的头插法。当当前链表遍历完毕后，要将_tables[i]置空，因为这是浅拷贝，不置空析构会有问题。最后swap一下即可。

bool Insert(const pair<K, V>& kv)
{
	if (Find(kv.first))
		return false;
	if (_n == _tables.size())
	{
		vector<Node*> newtables;
		newtables.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 = cur->_kv.first % newtables.size();
				cur->_next = newtables[hashi];
				newtables[hashi] = cur;
				cur = next;
			}
			//置空，防止析构出现问题
			_tables[i] = nullptr;
		}
		_tables.swap(newtables);
	}
	size_t hashi = kv.first % _tables.size();
	Node* newnode = new Node(kv);
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;
	return true;
}

运行打印，看看效果，没问题。

2.5?删除实现

?这里我们没有用Find来删除，因为就算我们找到了结点，由于是单链表，我们也无法找到节点的前一个，因此没有用Find函数。

取出哈希值hashi，遍历当前的哈希值的链表，同时记录好前一个。找到Key或者找到空结束，如果找到了，而且前一个为空，证明删除的是第一个，就直接将cur->_next给到_tables[hashi]即可，完成头删。

如果前一个不为空，则不是头删，则prev->_next = cur->_next;? 最后detele 再return true即可。

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

?测试一下

2.6string做key

依然是我们之前写的HashFund，在本文的三、2.6

需要取整数的地方套上一层就可以了。不多赘述。

五、哈希桶与set和unordered_set的对比?

这里我们选取了一百万个随机值进行插入测试，（具体打印函数后续会给出）根据打印内容我们发现，哈希表处理数据的速度是要比红黑树快一点的。

至于之前我们说为什么C++不适用哈希表挂载红黑树的方式，我们可以通过maxBucketLen来知道，一个地方时很难挂载到很多数据的，除非你是人为恶心哈希表才会挂载很多数据。

最后为什么我们的哈希表比库里面的还要快，因为库里面还涉及到了一些东西，我们写的是简单版。

最后附上代码??

HashTable.h

#pragma once
#include<vector>

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t sum = 0;
		for (auto& e : s)
		{
			sum *= 31;
			sum += e;
		}
		return sum;
	}
};
namespace kky_open_address
{
	enum Status
	{
		EMPTY,
		EXIST,
		DELETE,
	};
	
	template<class K, class V>
	struct HashDate
	{
		pair<K, V> _kv;
		Status _s;
	};

	template<class K,class V ,class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}
		Hash hs;

		HashDate<K,V>* Find(const K& key)
		{
			size_t hashi = hs(key) % _tables.size();
			while (_tables[hashi]._s != EMPTY)
			{
				if (_tables[hashi]._s != DELETE && _tables[hashi]._kv.first == key)
					return &_tables[hashi];
				hashi++;
				hashi %= _tables.size();
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			HashDate<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_s = DELETE;
				--_n;
				return true;
			}
			return false;
		}

		bool Insert(const pair<K,V>& kv)
		{
			if (Find(kv.first))
			{
				return false;
			}
			if (_n*10 / _tables.size() >= 7)
			{
				int newcapacity = _tables.size() * 2;
				HashTable<K, V> newHT;
				newHT._tables.resize(newcapacity);
				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 = hs(kv.first) % _tables.size();
			while (_tables[hashi]._s == EXIST)
			{
				hashi++;
				hashi %= _tables.size();
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._s = EXIST;
			++_n;

			return true;
		}
		
		void Print()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i]._s == EXIST)
				{
					//printf("[%d]->%d:%s\n", i,_tables[i]._kv.first, "EXIST");
					cout << "[" << i << "]->" << _tables[i]._kv.first<<":" << _tables[i]._kv.second << endl;
				}
				else if(_tables[i]._s == EMPTY)
				{
					//printf("[%d]->%d:%s\n", i, _tables[i]._kv.first, "EMPTY");
					cout << "[" << i << "]->" <<endl;
				}
				else
				{
					//printf("[%d]->%d:%s\n", i, _tables[i]._kv.first, "DELETE");
					cout << "[" << i << "]->" <<"DELETE" << endl;
				}
			}
			cout << endl;
		}

	private:
		vector<HashDate<K,V>> _tables;
		size_t _n;
	};

	void test01()
	{
		HashTable<int, int> ht;
		int arr[] = { 3,13,23,4,5,14,7,13 };
		for (auto e : arr)
		{
			ht.Insert(make_pair(e, e));
		}
		ht.Print();
		ht.Erase(13);
		ht.Print();
		ht.Insert(make_pair(33,33));
		ht.Print();
	}
	void test02()
	{
		string arr[] = { "香蕉","苹果","橘子","香蕉","苹果" ,"香蕉","苹果" ,"香蕉" };
		HashTable<string, int> ht;
		for (auto e : arr)
		{
			HashDate<string, int>* ret = ht.Find(e);
			if(ret)
				ret->_kv.second++;
			else
				ht.Insert(make_pair(e, 1));
		}
		ht.Print();
	}
}

namespace kky_hash_bucket
{
	template<class K, class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K, V>* _next;
		HashNode(const pair<K,V>& kv)
			:_kv(kv)
			,_next(nullptr)
		{}
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		HashTable()
		{
			_tables.resize(10);
		}
		HashTable(const HashTable<K,V>& ht)
		{
			_tables.resize(ht._tables.size(), nullptr);
			for (size_t i = 0; i < ht._tables.size(); i++)
			{
				Node* cur = ht._tables[i];
				while (cur)
				{
					Node* newnode = new Node(cur->_kv);
					if (_tables[i]==nullptr)
					{
						_tables[i] = newnode;
					}
					else
					{
						newnode->_next = _tables[i];
						_tables[i] = newnode;
					}
					cur = cur->_next;
				}
			}
		}

		HashTable<K, V>& operator=(HashTable<K, V> ht)
		{
			_tables.swap(ht._tables);
			swap(_n, ht._n);
			return *this;
		}


		~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)
		{
			Hash hs;
			if (Find(kv.first))
				return false;
			if (_n == _tables.size())
			{
				vector<Node*> newtables;
				newtables.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 = hs(cur->_kv.first) % newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;
						cur = next;
					}
					//置空，防止析构出现问题
					_tables[i] = nullptr;
				}
				_tables.swap(newtables);
			}
			size_t hashi = hs(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 hs;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			Hash hs;
			size_t hashi = hs(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 Print()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				cout << "[" << i << "]" << "挂载"<<"->";
				while (cur)
				{
					cout << cur->_kv.first << ":" << cur->_kv.second << "->";
					cur = cur->_next;
				}
				cout << endl;
			}
			cout << endl;
		}

		void Some()
		{
			size_t bucketSize = 0;
			size_t maxBucketLen = 0;
			double averageBucketLen = 0;

 			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					++bucketSize;
				}

				size_t bucketLen = 0;
				while (cur)
				{
					++bucketLen;
					cur = cur->_next;
				}


				if (bucketLen > maxBucketLen)
				{
					maxBucketLen = bucketLen;
				}
			}

			averageBucketLen = (double)bucketSize / (double)_n;

			printf("all bucketSize:%d\n",_tables.size());
			printf("bucketSize:%d\n", bucketSize);
			printf("maxBucketLen:%d\n", maxBucketLen);
			printf("averageBucketLen:%lf\n\n", averageBucketLen);
		}

	private:
		vector<Node*> _tables;
		size_t _n;
	};
	void test01()
	{
		HashTable<int, int> ht;
		int arr[] = { 3,13,23,4,5,14,33,34,43,44 };
		for (auto e : arr)
		{
			ht.Insert(make_pair(e, e));
		}
		ht.Print();
		cout << ht.Find(43) << endl;
		ht.Erase(43);
		ht.Print();
		cout << ht.Find(43) << endl;
	}
	void test02()
	{
		string arr[] = { "香蕉","苹果","橘子","香蕉","苹果" ,"香蕉","苹果" ,"香蕉" };
		HashTable<string, int> ht;
		for (auto e : arr)
		{
			HashNode<string, int>* ret = ht.Find(e);
			if (ret)
				ret->_kv.second++;
			else
				ht.Insert(make_pair(e, 1));
		}
	}
	void test03()
	{
		const size_t N = 1000000;

		unordered_set<int> us;
		set<int> s;
		HashTable<int, int> ht;

		vector<int> v;
		v.reserve(N);
		srand(time(0));
		for (size_t i = 0; i < N; ++i)
		{
			//v.push_back(rand()); // N比较大时，重复值比较多
			v.push_back(rand() + i); // 重复值相对少
			//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 begin10 = clock();
		for (auto e : v)
		{
			ht.Insert(make_pair(e, e));
		}
		size_t end10 = clock();
		cout << "HashTbale insert:" << end10 - begin10 << endl << 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;

		size_t begin11 = clock();
		for (auto e : v)
		{
			ht.Find(e);
		}
		size_t end11 = clock();
		cout << "HashTable find:" << end11 - begin11 << endl << endl;

		cout << "插入数据个数：" << us.size() << endl << endl;
		ht.Some();

		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 << "unordered_set erase:" << end6 - begin6 << endl;

		size_t begin12 = clock();
		for (auto e : v)
		{
			ht.Erase(e);
		}
		size_t end12 = clock();
		cout << "HashTable Erase:" << end12 - begin12 << endl << endl;
	}
}

?test.cpp

#include<iostream>
#include<string>
#include<set>
#include<unordered_set>
using namespace std;
#include"HashTable.h"
#include"test.h"

int main()
{
	kky_hash_bucket::test03();
}

?感谢大家观看！！！

文章来源:https://blog.csdn.net/kkbca/article/details/134888563
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。