哈希算法（开散列）- 支持string（this指针指向的理解）

一.开散列的定义

闭散列（开放地址法）的缺点是线性探测和二次探测都会存在哈希冲突的问题，数据越多冲突就会越明显，导致查询数据的时间复杂度大幅度提升

个人思路：创建一个指针数组，当某个位置要插入一个数据，就再创建一个数组，指针数组对应位置的指针指向此数组的首元素（数组地址），再在相同位置插入数据时就是对数组进行扩容 / 删除

开散列的定义大致相同，但是考虑数组显然我忘记分析了数组Erase的时间复杂度，所以开散列将数组换成了链表，数组的填写元素位置是链表的头节点head的地址，此引出了开散列的定义（当插入数据就进行头插）

具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中

二.开散列的实现

1.自构建一个单链表

桶实现的底层逻辑其实是挂载一个单链表，所以要先定义一个单链表的结构体struct HashNode

重点：当在某个函数中声明使用此链表HashNode<K, V>* newnode = new HashNode<K, V>(kv)，因为是自定义类型struct HashNode，当在函数中要new一个节点，就会调用构造函数，所以结构体中要声明构造函数

小Tips：自定义结构体中直接在结构体中声明构造函数

// 自构建一个链表
	template<class K, class V>
	// 当使用HashNode时，因为是自定义类型，会调用默认构造，所以结构体要声明构造函数
	struct HashNode
	{
		struct HashNode* _next;
		pair<K, V> _kv;

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

2.class的类中成员变量

为了简便代码，将创建节点时HashNode<K, V>* newnode = new HashNode<K, V>(kv);转变为typedef HashNode<K, V> Node;

自此在原闭散列的情况下进行更改vector<Node*> _tables;，由原本的直接插入数据改变为向链表中出入数据，size_t _n = 0;负载因子决定是否扩容

不同点：开散列中是否扩容主要是由数据个数决定的，数据过多且关键值多重复就会导致某个桶过满，所以为避免此情况，当数据个数 == _tables.size()就要进行扩容

3.类HashTable的初定义

此包括类HashTable的构造 / 析构函数，关于链表的初始定义 - 链表的指针类型是struct HashNode<K, V>* -> Node* - 结构体为HashNode - new Node就相当于声明了一个结构体的空间 - 参数包括_next / _kv

template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
	// 链表的指针类型是struct HashNode<K, V>* -> Node*
	// 结构体为HashNode - new Node就相当于声明了一个结构体的空间 - 参数包括_next / _kv
	typedef HashNode<K, V> Node;
public:
	HashTable()
	{
		_tables.resize(10);
		// _n未声明按缺省值初始化（private）
	}

	~HashTable()
	{
		for (size_t hashi = 0; hashi < _tables.size(); ++hashi)
		{
			Node* cur = _tables[hashi];
			while (cur)
			{
				Node* curNext = cur->_next;
				// delete和new配对使用
				delete cur;
				cur = curNext;
			}
				
			_tables[hashi] = nullptr;
		}

		cout << "~HashTable()" << endl;
	}

4.this指针的理解（重点）

在闭散列Insert的扩容操作有一个重要步骤就是swap，开散列也同样有此操作，在函数中重新定义了一个临时变量HashTable<K, V> newHt;，那么编译器是如何知道我们目前在对哪一个HashTable<K, V>定义的变量进行修改的呢？

答案是：this指针，在函数中this指针指向哪个以类名HashTable<K, V>定义的临时变量，就能修改这个临时变量中的成员函数的数据，所以当我们定义多个，newHt1 / newHt2，调用其newHt1._tables，newHt2._tables，this指针就会分别指向newHt1 / newHt2，编译器以此来区分指向哪个临时变量

深层次问题：如果初始未定义相关类变量，this指向什么？ - this指针此时会指向类中的成员变量（即private中的成员变量），this->_tables / this->_n

误区解读：当我们新创建newHt时，this指针指向newHt，不再指向类中原本的成员变量，那么如何调取类中原本的成员变量 - 重点:newHt出了作用域后会调用析构函数销毁，而类中原本的成员变量则是一直存在的，同理，类中的原本的成员变量始终可以直接且能始终访问，当把类中原本变量插入新的newHt._tables时，this指针时指向newHt的（因为他在修改），_tables（类中原本的成员变量）是可以直接访问的

总结：this指针指向的变量内的成员变量可以修改，类中原有的成员变量始终存在且可以直接访问

5.Insert函数的实现（相关优化）

重点：this指针的指向和作用
疑惑点：创建newHt后，this指向newHt（原指向_tables），是否会导致无法访问_tables（_tables中的数据丢失）
解答：1.不会，_tables始终存在在类中，开始没有声明HashTable<K, V>，默认用this访问，但_tables也可以直接访问，始终在类中，数据也始终存在，可以直接访问
2.class类中的成员变量不受this指针的影响，始终存在在类中（数据不会丢失），可以直接访问，临时创建的变量需要指明调用的对象（newHt.），这时this会改变指向
3.this指针指向哪个变量，就修改哪个变量中指定的值 - 开始this指向_tables（初始修改_tables），后临行变量newHt，就会修改newHt的_tables，_n
4. 所以for循环一进入，修改的就是newHt中的_tables和_n - （易错点1）
5.swap后this指针重新指向_tables，newHt作为临时变量调用自己的析构函数，_tables再修改内部数据

易错点1：为什么_n不用交换：因为_table的数据个数是n，经过for循环后newHt的_n数量也是n，不交换二者数量也相同

易错点2：_tables是始终存在的变量，newHt是临时变量，所以_tables在函数中始终可以访问（一直存在），不需要管this指针的指向,在这个类中_tables始终可以访问，存入数据后即使this指针指向newHt，仍然可以访问_tables，_tables可始终访问

1.依照闭散列模拟实现Insert

bool Insert(const pair<K, V>& kv)
{
	if (Find(kv.first))
		return false;
			
	// 扩容逻辑 - 复用逻辑
	if (_n == _tables.size())
	{
		HashTable<K, V> newHt;
		size_t newSize = _tables.size() * 2;
		newHt._tables.resize(newSize);

		for (size_t i = 0; i < _tables.size(); ++i)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				newHt.Insert(cur->_kv);
				cur = cur->_next;
			}
		}
		newHt._tables.swap(_tables);	
	}
	// 不需要扩容
	Hash _hf;
	size_t hashi = _hf(kv.first) % _tables.size();
	Node* newnode = new Node(kv);

	// 头插
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;

	return true;
}

2.开散列Insert函数优化

优化：上面这种方式，复用的是下面Insert的逻辑，所以当旧表中的节点再插入新表时会再开一个新Node，浪费空间（数据过多可能会导致空间不足）

所以已有的节点不再新开，直接移动，转换扩容逻辑

bool Insert(const pair<K, V>& kv)
{
	if (Find(kv.first))
		return false;
			
	// 扩容逻辑 - 复用逻辑
	//if (_n == _tables.size())
	//{
	//	HashTable<K, V> newHt;
	//	size_t newSize = _tables.size() * 2;
	//	newHt._tables.resize(newSize);

	//	for (size_t i = 0; i < _tables.size(); ++i)
	//	{
	//		Node* cur = _tables[i];
	//		while (cur)
	//		{
	//			newHt.Insert(cur->_kv);
	//			cur = cur->_next;
	//		}
	//	}
	//	newHt._tables.swap(_tables);
			
	// 优化：上面这种方式，复用的是下面Insert的逻辑，所以当旧表中的节点再插入新表时会再开一个新Node，浪费空间
	// 所以已有的节点不再新开，直接移动，转换扩容逻辑
	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* curNext = cur->_next;
				cur->_next = _newTables[i];
				_newTables[i] = cur;
				cur = curNext;
			}
		}

		_newTables.swap(_tables);
	}

	// 不需要扩容
	Hash _hf;
	size_t hashi = _hf(kv.first) % _tables.size();
	Node* newnode = new Node(kv);

	// 头插
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;

	return true;
}

6.Find函数的实现

Node* Find(const K& k)
{
	Hash _hf;
	size_t hashi = _hf(k) % _tables.size(); // _tables始终都能访问
			
	Node* cur = _tables[hashi];
	while (cur)
	{
		if (cur->_kv.first == k)
		{
			return cur;
		}
		cur = cur->_next;
	}

	return nullptr;
}

7.Erase函数的实现

重点：开散列的Erase不能用Find函数来查询，因为用Find函数会返回目标数的地址，这样会导致找不到此地址的上一个节点，无法进行删除

两种情况：1.删除头节点 / 2.删除重点节点（包括尾节点） - 因为HashNode的声明，所以尾节点的_next的是nullptr,最后若指向尾节点的_next则是指向nullptr

思路提升：Erase的思路是将找到所要删除值时进行处理（一个if），没有找到时进行处理（else） / 判断curPrev == nullptr为依据判断是否当前处于头节点

bool Erase(const K& k)
{
	Hash _hf;
	size_t hashi = _hf(k) % _tables.size();

	Node* cur = _tables[hashi];
	Node* curPrev = nullptr;
			
	while (cur)
	{
		// 处理当找到值与对应值相同的情况
		// 1.所处位置为头部位置（head） - cur若是尾部数据，则_next是nullptr
		// 2.所处位置在中心或底部位置
		if (cur->_kv.first == k)
		{
			if (curPrev == nullptr)
			{
				_tables[hashi] = cur->_next;
			}
			else
			{
				// 若cur的_next无数据，则是nullptr
				curPrev->_next = cur->_next;
			}
		}
				
		curPrev = cur;
		cur = cur->_next;
	}
	return false;
}

8.统计函数的实现 - 观测桶的状态

all bucketSize - 当前数组大小
bucketSize - 占用数组元素的个数
maxbucketLen - 最大桶的长度
averagebucketlen - 平均桶的长度

void Count()
{
	// all bucketSize
	// bucketSize
	// maxbucketLen
	// averagebucketlen

	size_t bucketSize = 0, maxbucketLen = 0, bucketLen = 0, sumbucketLen = 0;
	double averagebucketLen;
			
	for (size_t hashi = 0; hashi < _tables.size(); ++hashi)
	{
		Node* cur = _tables[hashi];
		if (cur)
		{
			++bucketSize;
			bucketLen = 0;
			while (cur)
			{
				++bucketLen;
				cur = cur->_next;
			}
			sumbucketLen += bucketLen;
			maxbucketLen = max(bucketLen, maxbucketLen);
		}
	}
	// 重点：强转：size_t转成double类型
	averagebucketLen = (double)sumbucketLen / (double)bucketSize;

	cout << "all bucketSize" << ": " << _tables.size() << endl;
	cout << "bucketSize" << ": " << bucketSize << endl;
	cout << "maxbucketLen" << ": " << maxbucketLen << endl;
	printf("averagebucketlen:%lf\n", averagebucketLen);
}

9.Print函数的实现

反映各个桶的具体情况

void Print()
{
	for (size_t hashi = 0; hashi < _tables.size(); ++hashi)
	{
		Node* cur = _tables[hashi];

		if (cur)
		{
			cout << "[" << hashi << "]" << " -> ";
			while (cur)
			{
				//cout << cur->_kv.first << " -> ";
				// String类型支持
				cout << "[" << cur->_kv.first << ": " << cur->_kv.second << "]" << " -> ";
				cur = cur->_next;
			}
			cout << "nullptr" << endl;
		}

		else
		{
			cout << "[" << hashi << "]" << " -> " << "nulluptr" << endl;
		}
	}

			cout << endl;
}

三.支持String类型插入

同样，现在的类仅能支持int类型，想要支持string类型依旧需要进行模板 + 结构体 + 运算符重载 + 模板偏特化（详情可见闭散列实现支持string）

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

template<>
struct HashFunc<string>
{	
	size_t operator()(const string& k)
	{
		size_t hashi = 0;
		for (auto& e : k)
		{
			hashi *= 31;
			hashi += e;
		}

		return hashi;
	}
};

四.测试代码

void TestHT1()
{
	HashTable<int, int> ht;
	int a[] = { 4, 14, 24, 34, 5, 7, 1, 15, 25, 3 };
	for (auto e : a)
	{
		ht.Insert(make_pair(e, e));
	}

	//ht.Print();
	// 扩容测试
	ht.Insert(make_pair(13, 13));
	ht.Print();
	//ht.Erase(24);
	//ht.Print();

	ht.Count();
}

// String类型测试
void TestString()
{
	HashTable<string, string> ht;
		
	ht.Insert(make_pair("left", "左边"));
	ht.Insert(make_pair("sort", "排序"));
	ht.Insert(make_pair("right", "右边"));
	ht.Insert(make_pair("middle", "中间"));

	//ht.Print();
	// 扩容测试
	ht.Print();
	//ht.Erase(24);
	//ht.Print();

	//ht.Count();
}

五.总结

本章重点理解this指针的作用 / Insert函数不再是简单的复用逻辑，优化进行空间处理 / Erase函数两种情况的处理及思想学习

End ！！！