C++模拟实现哈希表笔记

文章目录

• 🌲C++哈希
• • 🌴哈希冲突
  • 🌴负载因子
  • 🌴哈希函数
  • 🌴闭散列
  • • 🌵处理哈希冲突
    • • 🌵线性探测
      • 🌵二次探测
      • 🌵其它
  • 🌴代码实现
  • • 🌵结点
    • 🌵内置类型以外类型的映射值处理
    • 🌵结构
    • 🌵查找
    • 🌵插入
    • 🌵删除
    • 🌵测试
    • 🌵析构，拷贝构造，构造函数
  • 🌴开散列（哈希桶）
  • • 🌵处理哈希冲突
  • 🌴代码实现
  • • • 🌵结点
      • 🌵结构
      • 🌵查找
      • 🌵插入
      • 🌵删除
      • 🌵析构
      • 🌵拷贝构造和赋值重载
      • 🌵优化
  • 🌴总结

🌲C++哈希

下面把放入哈希表中的值记为key，index是key在哈希表中的位置

🌴哈希冲突

两个key通过同一个映射关系得到了相同的值，即他们需要放在同一个位置（通过key算出的index一样），这就是哈希冲突。

简而言之，不同值映射到了同一个位置.

哈希表的效率与哈希冲突的处理密切相关

举个例子，哈希表大小为10，a[]={1，2，3，4，5，15}，定义class="superseo">哈希算法为 index=key%表长，从前往后构造哈希表。

即数组从前往后算出的index分别为1，2，3，4，5，5，此时key=15的元素算出的index为5，但是5这个位置已经有了key为5的元素，这就是哈希冲突

🌴负载因子

负载因子=哈希表中元素的个数/哈希表的大小

显然负载因子小于1，并且负载因子越大越容易产生哈希冲突（两个数放到一个位置的概率更大，大小为10的容器里放9个数冲突概率肯定比放一个数大）

🌴哈希函数

一般采用除留余数法，即取模的方法，如key对表长进行取模得到index。

此外还有很多种，如平方取中，随机数法等等

🌴闭散列

闭散列也叫开放地址法，发生哈希冲突时只要哈希表没满则说明哈希表中必有一个空位置存放这个值

🌵处理哈希冲突

线性探测和二次探测。

这两个方法都是发生了哈希冲突才用的上的.

🌵线性探测

算出的index往后挨个找，找到一个空位置放入即可。

🌵二次探测

算出的index依次加1，4，9，…这种数，直到找到一个空位置

二次探测放入的数据更散，但是可能死循环（代码测试二次探测时一组数据死循环了）

🌵其它

还有别的办法解决哈希冲突，闭散列主要用的上面两种，

🌴代码实现 🌵结点

template
struct HashData
{
	pair _kv;
	Status _status = EMPTY;
};

结点的三种状态

enum Status//定义一下结点的状态，方便 *** 作
{
	EMPTY,
	EXIST,
	DELETE
};

🌵内置类型以外类型的映射值处理

内置类型以外的类型就是自定义类型和库里的一些类型如pair和string等

我们利用仿函数得到相应的值

template
struct HashFunc
{
	const K& operator()(const K& key)
	{
		return key;
	}
};
template<>//对字符串进行特化，模板进阶的内容
struct HashFunc 
{
	size_t operator()(const string& key)
	{
		size_t value = 0;
		for (auto e : key)
		{
			value = value * 13 + (size_t)e;//乘以131是BKDR发明的字符串哈希算法，*131等数效率更高
		}
		return value;
	}
};

仿函数传入key返回key有啥用？

以一般类型为例，如int，double等传进去直接返回它们本身的值，因为他们本身就是key。如STL中的set和unordered_set。

但是如果要传入pair呢？那就得我们自定义一个仿函数（如同处理string一样），可以写成下面这样

template
struct HashFunc
{
	const K& operator()(const pair& kv)
	{
		return kv.first;
	}
};

仿函数写了如何用？传参时传入这个struct作为模板参数。

🌵结构

	template
	struct HashFunc
	{
		const K& operator()(const K& key) ;
	};
	template<>
	struct HashFunc 
	{
		size_t operator()(const string& key);
	};
	enum Status//定义一下结点的状态，方便查找
	{
		EMPTY,
		EXIST,
		DELETE
	};	
	template
	struct HashData
	{
		pair _kv;
		Status _status = EMPTY;
	};
	template>
	class HashTable
	{
	public:
		HashData* Find(const K& key);
		bool Insert(const pair& kv);
		bool Erase(const K& key);	
	private:
		vector>_tables;
		size_t _n = 0;
	};

🌵查找

思路：先算出key对应的index，如果这个位置存在且key与要查找的key相等就说明找到了，否则往后找，找到空的位置说明表中不存在这个key。

	HashData* Find(const K& key)
	{
		if (_tables.size() == 0)
		{
			return nullptr;
		}
		
		Hash hash;
		size_t start = hash(key) % _tables.size();
		size_t i = 0;
		size_t index = start + i;//算出的index
		while (_tables[index]._status != EMPTY)//这个位置不为空
		{
			if (_tables[index]._kv.first == key
				&& _tables[index]._status == EXIST)//存在且值相等
                //判断是否存在是因为结点有一种可能的状态是删除
			{
				return &_tables[index];
			}
			else
			{
				++i;
				//index = start + i; // 线性探测
				index = start + i * i; // 二次探测
				index %= _tables.size();
			}
		}
		
		return nullptr;
	}

🌵插入

思路：找到一个空位置直接放

具体来说，位置为空直接放，如果找到的位置已经有值了就通过线性探测/二次探测去后面找位置

值得注意的点是负载因子是0.7的时候或者刚开始表长度为0的时候得进行增容

增容拷贝原哈希表数据的方法：开一个新表，调用Insert函数插入数据到新表中，再交换新表和旧表即可。（vector的交换只交换指针，所以开销不大）

增容后表长变化，导致index也要跟着变，直接用新表插入就解决了这个问题

		bool Insert(const pair& kv)
		{
			Hash hash;
			if (Find(kv.first))//原来的表中存在
			{
				return false;
			}
			if (_tables.size()==0||_n*10/_tables.size()>=7)
				//负载因子在0.7的时候扩容 不然可能导致死循环
			{
				size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				
				HashTableNewHT;//搞一个vector出来行吗？可以，但是选用hashtable后面可以直接调用Insert插入数据更方便
				NewHT._tables.resize(newsize);
				for (auto& e : _tables)//这种传引用 不传引用得多拷贝一次
				{
					NewHT.Insert(e._kv);
				}
				_tables.swap(NewHT._tables);//交换之后NewHT就被销毁了
			}
			size_t start = hash(kv.first) % _tables.size();
			size_t i = 0;
			size_t index = start + i;
			//进行线性探测或二次探测
			while (_tables[index]._status==EXIST)//不等于空就一直往后走
			{
				//index++;//由于负载因子在0.7时扩容了所以不会死循环.
				i++;
				//index = start + i 线性探测
				index = start+i*i;
				index %= _tables.size();
			}
			//找到位置了
			
			_tables[index]._status = EXIST;
			_tables[index]._kv = kv;
			_n++;
			return true;
		}

🌵删除

复用Find()即可，这里是一种伪删除，只是更改结点状态而不是删除数据。

bool Erase(const K& key)
		{
			
			/*	Hash hs;
				size_t index = hs(key) % _tables.size();
				while (_tables[index]._status==EXIST)
				{
					if (_tables[index]._kv.first == key)
					{
						_tables[index]._status = DELETE;
						return true;
					}
					index++;//线性探测
					index %= _tables.size();
				}
				return false;*/
			HashData* ret = Find(key);
			if (ret == nullptr)
			{
				return false;
			}
			else
			{
				ret->_status = DELETE;
				return true;
			}
		}

🌵测试

测试整形

	void test1()
	{
		int a[] = { 5, 3, 100, 9999, 333, 14, 26, 34, 5};//这组数据在二次探测时会死循环
		HashTable ht;
		for (auto e : a)
		{
			ht.Insert(make_pair(e, e));
		}

		ht.Erase(3);
		cout << ht.Find(3) << endl;
	}

测试字符串

void test2()
{
	HashTable<string, string, HashFunc<string>>ht;
	ht.Insert(make_pair("sort", "排序"));
	ht.Insert(make_pair("entity", "实体"));
	ht.Insert(make_pair("object", "对象"));
	ht.Insert(make_pair("buffer", "缓冲"));
	ht.Erase("sort");
	cout << ht.Find("sort") << endl;
}

🌵析构，拷贝构造，构造函数

析构，结构选用了vector，vector会帮我们搞定

拷贝构造,没有涉及到深浅拷贝构造，vector会帮我们搞定

构造函数，给了缺省值，也没啥要传参初始化的情况，默认的也够用。

闭散列的哈希表可以理解为对vector进行了一次封装，vector的元素哈希结点也没开辟什么空间，所以也不会出现内存泄漏的问题，但是开散列采用链表的结构（链表是自己写的），所以需要自己去释放链表的空间。

🌴开散列（哈希桶）

STL里的unordered_set和unordered_map底层的哈希就选用了开散列结构

🌵处理哈希冲突

采用链表的形式

• 那开散列的结构是不是不需要扩容？

需要的。以上图为例，表长就为10，我要放10000个数据，平均下来就算每个链表放1000个，那查找和删除指定元素的效率依旧不高。

• 那需要增容的话什么时候增容？

负载因子为1时增容

STL库里默认是1

🌴代码实现 🌵结点

哈希表采用vector存储，vector的每个元素都是一个链表，链表的每个元素即是哈希结点

那么这个结点肯定需要有next指针指向下一个，又要存储类型的值，这里的类型采用pair,所以就有了pair

链表也可以用双向循环链表，单链表简单点，根据泛型编程的思想可以把pair改成模板。

struct HashNode
{
	pair _kv;
	HashNode* _next;
	HashNode(const pair& kv)
		:_kv(kv)
		:next(nullptr)
	{}
};

🌵结构

namespace open_hash也行 开散列 ，但是命名空间取为哈希桶更加形象，每个桶都是一个链表

namespace HashBucket//防止与库里的一些名字相同导致命名冲突
{
	template>
	struct HashNode
	{
		pair _kv;
		HashNode* _next;
		HashNode(const pair& kv)
			:_kv(kv)
			: next(nullptr)
		{}
	};
	template
	class HashTable
	{
		typedef HashNode Node;
	public:

		Node* Find(const K& key)//Find函数返回值一般都是指针，通过指针访问这个自定义类型的成员
		{

		}
		bool Insert(const pair& kv)
		{

		}
		bool Erase(const K& key)
		{

		}
		~HashTable()//哈希桶采用的链表结构 需要释放每个链表
		{

		}
	private:
		vector_tables;//存的是链表首元素的指针
		size_t n;//有效数据
	};

}

拷贝构造和赋值单重载后面独实现

🌵查找

思想：先计算出桶号（对应的index），遍历桶号对应的这根链表，看是否能找到这个值

Node* Find(const K& key)//Find函数返回值一般都是指针，通过指针访问这个自定义类型的成员
{
	Hash hash;//把string之类的类型映射成整数，即处理内置类型以外的类型
	if (_tables.size() == 0)//表的大小为0，防止取余0
	{
		return nullptr;
	}
	size_t index = hash(key) % _tables.size();//找到桶号
	Node* cur = _tables[index];
	while (cur)
	{
		if (cur->_kv.first == key)
		{
			return cur;
		}
		else
		{
			cur = cur->_next;
		}
	}
	return nullptr;
}

🌵插入

思路：先去桶里找，去看看有没有这个值，如果有直接返回false。没有的话算出应该放入的桶，再将这个结点进行头插，插入前需要检查是否需要扩容。

为什么进行头插不进行尾插？因为尾插要找尾，由于采用的是单链表找尾得遍历这个链表更麻烦

怎么进行扩容？取出原来表的每个结点插入新表，再交换新旧两个表

注意扩容后表长变化导致index变化，比如原来表长是10，模10就行了，现在表长扩容成了20，就必须去模20了。同时一些本来在同一个桶的结点也可能不在同一个桶了。

bool Insert(const pair& kv)
{
	if (Find(kv.first))//有相同的key直接返回false
	{
		return false;
	}
	//if(_n==0||_n==_tables.size())
	Hash hash;
	if (_n == _tables.size())//最开始_n为0，而_tables.size()也为0所以可以简化为一行代码
        //负载因子为1是增容
	{
		//增容
		size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
		vectornewTables;
		newTables.resize(newSize, nullptr);
		for (int i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;//记录下一个位置
				size_t index = hash(cur->_kv.first) % newTables.size();
				cur->_next = newTables[index];//cur当头
				newTables[index] = cur;//更新vector里的头
				cur = next;
			}
		}
		_tables.swap(newTables);//把新表的数据放入旧表中
        //思考newTable存在内存泄漏吗？
        //newTable生命周期结束后调用自己的析构函数，又因为newTable交换后每条链表最多一个结点，所以默认的结点的析构就够用。注意：交换后两个table都存了链表的头结点（通过调试可以清楚看到）
        //原因：这里把旧表数据拷贝到新表其实就是单链表的拷贝，但是拷贝后旧表依然记住了一个结点（拷贝过程中没有 *** 作旧表的vector，所以旧表vector存的Node*没变,不过头结点指针指向的Node里面的_next被置为空了，因为旧表每个桶的头结点拷贝过去都会是新表的最后一个结点（头插）），所以旧表拷贝前后都是记住了每个链表的头结点的，因此旧表每个桶最多只有一个头结点
	}
			
	size_t index = hash(kv.first) % _tables.size();//算出桶号
	//头插
	Node* newNode = new Node(kv);
	newNode->_next = _tables[index];
	_tables[index]=newNode;
	++_n;//别忘记更新有效数据的个数
	return true;
}

思考newTable存在内存泄漏吗？

newTable生命周期结束后调用自己的析构函数，newTable交换后每条链表最多一个结点，所以默认的结点的析构就够用。注意：交换后两个table都存了链表的头结点（通过调试可以清楚看到）

为啥newTable交换后每条链表最多一个结点？或者说拷贝后、交换前的旧表每条链表最多一个结点

原因：这里把旧表数据拷贝到新表其实就是单链表的拷贝，但是拷贝后旧表依然记住了一个结点（拷贝过程中没有 *** 作旧表的vector，所以旧表vector存的Node*没变,不过头结点指针指向的Node里面的_next被置为空了，因为旧表每个桶的头结点拷贝过去都会是新表的最后一个结点（头插）），所以旧表拷贝前后都是记住了每个链表的头结点的，因此旧表每个桶最多只有一个头结点

插入时的效率变化

🌵删除

思路：先看这个元素存不存在，不存在直接返回false。存在的话算出桶号转为单链表的删除。

单链表的删除分为是否是头结点，先找到这个元素再看是不是头结点

为什么不直接Find()找到这个结点直接删除？单链表删除需要借助删除结点的前一个结点，Find只能找到当前结点。所以删除没有复用Find().

bool Erase(const K& key)
{ 
	//if (!Find(key))//找不到这个元素 
	// 这么写也可以，但是后面删除的过程中会顺带遍历整个桶
	//{
	//	return false;
	//}
	if (_tables.size() == 0)//哈希表为空
	{
		return false;
	}
	Hash hash;
	size_t index = hash(key) % _tables.size();
	Node* cur = _tables[index];
	Node* prev = nullptr;//记录前一个位置
	while (cur)
	{
		if (cur->_kv.first == key)//找到这个元素了
		{
			if(cur==_tables[index])//元素是头结点
			{
				_tables[index] = cur->_next;
						
			}
			else//不是头结点
			{
				prev->_next = cur->_next;
			}
			delete cur;
			cur = nullptr;
			_n--;
			return true;
		}
		else
		{
			prev = cur;
			cur = cur->_next;
		}
	}
	return false;
}

🌵析构

判断桶的头结点是否为空，为空说明没有结点直接下一个，有的话从第二个开始遍历链表删除

为什么不从第一个删除

第一个的删除交给vector，如果从第一个开始会造成同一个元素析构两次，程序会崩…

~HashTable()//哈希桶采用的链表结构 需要释放每个链表
{
	for (int i=0;i<_tables.size();i++)
	{
		Node* cur = _tables[i];
		if (cur == nullptr)
		{
			continue;
		}
		else
		{
			cur = cur->_next;//不为空从第二个开始
		}
		while (cur)
		{
			Node* next = cur->_next;
			delete cur;
			cur = next;
		}
		_tables[i] = nullptr;
	}
	_n = 0;
}

🌵拷贝构造和赋值重载

拷贝构造和赋值重载都要拷贝出完全相同的一份，所以需要尾插，由于单链表尾插需要找尾，效率不高。所以没有实现，网上找的资源也没找到答案。阅读STL源码的能力还不够，所以打算以后看源码怎么实现拷贝构造的。

🌵优化

哈希表的大小建议是素数，网上有大佬可以探讨过了，这里直接贴一下网上的代码。

素数的话除留余数法时哈希冲突的可能性更小

		size_t GetNextPrime(size_t prime)
		{
			const int PRIMECOUNT = 28;
			static const size_t primeList[PRIMECOUNT] =
			{
				53ul, 97ul, 193ul, 389ul, 769ul,
				1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
				49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
				1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
				50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
				1610612741ul, 3221225473ul, 4294967291ul
			};
			//ul表示unsigned long
			size_t i = 0;
			for (; i < PRIMECOUNT; ++i)
			{
				if (primeList[i] > prime)
					return primeList[i];
			}

			return primeList[i];
		}

🌴总结

哈希表的结构掌握后，处理哈希冲突即可。处理哈希冲突的方式不同会导致哈希表的效率不同。