哈希（1）闭散列

哈希（1）

回顾概念

哈希冲突处理方法（低级）

1. 闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？

1. 线性探测

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

• 插入：

• 查找：

• 删除：

讲清楚规则之后，我们就开始写代码：

完整代码

Hash.h

#pragma once
#include<iostream>
#include<cassert>
#include<utility>
#include<vector>
using namespace std;

enum State
{
	EMPTY,
	EXIST,
	DELETE
};

template<class K, class V>
struct HashData
{
	pair<K, V> _data;
	State _state = EMPTY;

};

template<class K, class V>
class HashTables
{
public:
	HashTables(size_t size = 10)
	{
		_Table.resize(size);
	}
	HashData<K, V>* find(const K& key);
	bool insert(const pair<K, V>& data);
	bool erase(const K& key);


private:
	vector<HashData<K, V>> _Table;
	size_t _n = 0;//存储已有数据个数
};

template<class K, class V>
HashData<K, V>* HashTables<K, V>::find(const K& key)
{
	//先用哈希函数算位置
	size_t Hash_i = key % _Table.size();

	//判断是否理想下标处是否是目标值
	while (_Table[Hash_i]._state != EMPTY)
	{
		if (_Table[Hash_i]._state == EXIST && _Table[Hash_i]._data.first == key)
		{
			return &_Table[Hash_i];
		}
		++Hash_i;
		/*if (Hash_i >= _Table.size())
		{
			Hash_i = 0;
		}*/
		Hash_i %= _Table.size();
	}

	return nullptr;
}


template<class K, class V>
bool HashTables<K, V>::insert(const pair<K, V>& data)
{
	//先判断新数据是否是重复值
	if (find(data.first) != nullptr)
	{
		return false;
	}

	//然后计算负载因子,判断是否扩容
	double LoadFactor = (double)_n / (double)_Table.size();
	if (LoadFactor >= 0.7)
	{
		//扩容
		size_t newsize = _Table.size() * 2;
		//用newsize创建一个新的哈希表对象
		HashTables<K, V> newtable(newsize);
		for (const auto& e : _Table)
		{
			if (e._state == EXIST)
			{
				newtable.insert(e._data);
			}
		}
		_Table.swap(newtable._Table);
	}

	size_t Hash_i = data.first % _Table.size();
	while (_Table[Hash_i]._state == EXIST)
	{
		++Hash_i;
		/*if (Hash_i >= _Table.size())
		{
			Hash_i = 0;
		}*/
		Hash_i %= _Table.size();
	}
	_Table[Hash_i]._data = data;
	_Table[Hash_i]._state = EXIST;
	_n++;
	return true;
}


template<class K, class V>
bool HashTables<K, V>::erase(const K& key)
{
	HashData<K, V>* ret = find(key);
	if (ret == nullptr)
	{
		return false;
	}

	ret->_state = DELETE;
	_n--;

	return true;

}

test.cpp

#include"Hash.h"

void test1()
{
	HashTables<int, int> ht;
	ht.insert(make_pair(23, 1));
	ht.insert(make_pair(45, 1));
	ht.insert(make_pair(78, 1));
	ht.insert(make_pair(12, 1));
	ht.insert(make_pair(67, 1));
	ht.insert(make_pair(89, 1));
	ht.insert(make_pair(3, 1));
	ht.insert(make_pair(56, 1));
	ht.insert(make_pair(92, 1));
	ht.insert(make_pair(19, 1));

	ht.erase(23);
	//ht.insert(make_pair(43,1));
	HashData<int, int>* rt = ht.find(3);
	ht.erase(45);

	ht.erase(78);

}

int main()
{
	test1();//这里大家可以用vs的监视窗口来验证正确与否

	return 0;
}

• 结构

vector 中 resize() 和 reserve() 的区别图示

文字图示比较

初始状态:
vector<int> vec;
+-----------------+
| size: 0         |
| capacity: 0     |
| 元素: 无        |
+-----------------+

调用 vec.reserve(5) 后:
+-----------------+
| size: 0         |  ← 大小不变
| capacity: 5     |  ← 容量增加
| 元素: [?, ?, ?, ?, ?]  ← 内存已分配但未初始化
+-----------------+

调用 vec.resize(3) 后:
+-----------------+
| size: 3         |  ← 大小增加
| capacity: 5     |  ← 容量不变（已有足够空间）
| 元素: [0, 0, 0] |  ← 新元素被初始化为默认值(0)
+-----------------+

调用 vec.resize(5, 42) 后:
+-----------------+
| size: 5         |  ← 大小增加
| capacity: 5     |  ← 容量不变
| 元素: [0, 0, 0, 42, 42]  ← 新元素被初始化为指定值(42)
+-----------------+

调用 vec.reserve(10) 后:
+-----------------+
| size: 5         |  ← 大小不变
| capacity: 10    |  ← 容量增加
| 元素: [0, 0, 0, 42, 42, ?, ?, ?, ?, ?]  ← 原有元素保留，新增空间未初始化
+-----------------+

可视化图表

reserve(n) 操作:
+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |   |  ← 分配内存但不初始化
+---+---+---+---+---+---+---+---+---+---+
  ↑                   ↑
容量增加            大小不变

resize(n) 操作:
+---+---+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 |   |   |   |   |   |  ← 分配内存并初始化新元素
+---+---+---+---+---+---+---+---+---+---+
  ↑       ↑           ↑
容量增加  大小增加    新元素初始化为默认值

resize(n, value) 操作:
+---+---+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 |42 |42 |42 |42 |42 |  ← 分配内存并用指定值初始化新元素
+---+---+---+---+---+---+---+---+---+---+
  ↑       ↑           ↑
容量增加  大小增加    新元素初始化为指定值

关键区别总结

在哈希表中的应用

在哈希表实现中，使用 resize() 而不是 reserve()，是因为：

1. 哈希表需要实际存在的元素（即使是空的）
2. 每个元素需要有明确的状态（EMPTY, EXIST, DELETE）
3. 哈希函数计算出的索引需要对应实际存在的元素

如果使用 reserve()，虽然会分配内存，但不会创建实际的 HashData 对象，这会导致访问未初始化的内存，从而引发未定义行为。接着往下看。

• 查找

大家也可以用下面这段代码感受一下，什么是size( )和capacity( )会不相同，大家观察t1和t2这两个值的变化：

#include<vector>

int main()
{
	vector<int> v1;
	size_t t1 = v1.size();
	size_t t2 = v1.capacity();
	v1.resize(4);
	t1 = v1.size();
	t2 = v1.capacity();
	v1.push_back(1);
	t1 = v1.size();
	t2 = v1.capacity();
	v1.push_back(2);
	t1 = v1.size();
	t2 = v1.capacity();
	v1.push_back(3);
	t1 = v1.size();
	t2 = v1.capacity();
	v1.push_back(4);
	v1.resize(2);
	t1 = v1.size();
	t2 = v1.capacity();

	return 0;
}

• 插入

• 删除

完善

虽然我们这个方法下的哈希表已经写的差不多了，但是还有一个很重要的问题没解决。如果我的Key是string类型的数据，我怎么计算理想下标位置？如果我的Key是自定义类型，我该怎么计算理想下标位置？

那该怎么解决呢，大家往下看：

Hash.h

#pragma once
#include<iostream>
#include<cassert>
#include<utility>
#include<vector>
using namespace std;

enum State
{
	EMPTY,
	EXIST,
	DELETE
};

template<class K, class V>
struct HashData
{
	pair<K, V> _data;
	State _state = EMPTY;

};

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

//模版特化,当数据类型是string类型的时候,会直接用写好了的这个
//讲模版的时候讲过了:如果有现成的,就用现成的.
template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto e : s)
		{
			hash += e;//这里是 + e的Ascll码
			hash *= 13;
		}
		return hash;
	}
};

template<class K, class V, class Hash = HashFunc<K>>
class HashTables
{
public:
	HashTables(size_t size = 10)
	{
		_Table.resize(size);
	}
	HashData<K, V>* find(const K& key);
	bool insert(const pair<K, V>& data);
	bool erase(const K& key);


private:
	vector<HashData<K, V>> _Table;
	size_t _n = 0;//存储已有数据个数
};

template<class K, class V, class Hash>
HashData<K, V>* HashTables<K, V, Hash>::find(const K& key)
{
	Hash hs;//仿函数对象,用来调整key的,让key的类型变为为size_t
	
	//先用哈希函数算位置
	size_t Hash_i = hs(key) % _Table.size();

	//判断是否理想下标处是否是目标值
	while (_Table[Hash_i]._state != EMPTY)
	{
		if (_Table[Hash_i]._state == EXIST && _Table[Hash_i]._data.first == key)
		{
			return &_Table[Hash_i];
		}
		++Hash_i;
		/*if (Hash_i >= _Table.size())
		{
			Hash_i = 0;
		}*/
		Hash_i %= _Table.size();
	}

	return nullptr;
}


template<class K, class V, class Hash>
bool HashTables<K, V, Hash>::insert(const pair<K, V>& data)
{
	//先判断新数据是否是重复值
	if (find(data.first) != nullptr)
	{
		return false;
	}

	//然后计算负载因子,判断是否扩容
	double LoadFactor = (double)_n / (double)_Table.size();
	if (LoadFactor >= 0.7)
	{
		//扩容
		size_t newsize = _Table.size() * 2;
		//用newsize创建一个新的哈希表对象
		HashTables<K, V> newtable(newsize);
		for (const auto& e : _Table)
		{
			if (e._state == EXIST)
			{
				newtable.insert(e._data);
			}
		}
		_Table.swap(newtable._Table);
	}

	Hash hs;//仿函数对象
	size_t Hash_i = hs(data.first) % _Table.size();
	while (_Table[Hash_i]._state == EXIST)
	{
		++Hash_i;
		/*if (Hash_i >= _Table.size())
		{
			Hash_i = 0;
		}*/
		Hash_i %= _Table.size();
	}
	_Table[Hash_i]._data = data;
	_Table[Hash_i]._state = EXIST;
	_n++;
	return true;
}


template<class K, class V, class Hash>
bool HashTables<K, V, Hash>::erase(const K& key)
{
	HashData<K, V>* ret = find(key);
	if (ret == nullptr)
	{
		return false;
	}

	ret->_state = DELETE;
	_n--;

	return true;

}

test.cpp

#include"Hash.h"

void test1()
{
	HashTables<int, int> ht;
	ht.insert(make_pair(23, 1));
	ht.insert(make_pair(45, 1));
	ht.insert(make_pair(78, 1));
	ht.insert(make_pair(12, 1));
	ht.insert(make_pair(67, 1));
	ht.insert(make_pair(89, 1));
	ht.insert(make_pair(3, 1));
	ht.insert(make_pair(56, 1));
	ht.insert(make_pair(92, 1));
	ht.insert(make_pair(19, 1));

	ht.erase(23);
	//ht.insert(make_pair(43,1));
	HashData<int, int>* rt = ht.find(3);
	ht.erase(45);

	ht.erase(78);

}

void test2()
{
	HashTables<string, string, HashFunc<string>> ht;
	ht.insert(make_pair("apple", "苹果"));
	ht.insert(make_pair("sort","排序"));
	ht.insert(make_pair("black","黑色"));
	ht.insert(make_pair("hello","你好"));


	ht.erase("apple");
	

}


int main()
{
	test2();

	return 0;
}

这就是闭散列比较完整的展示了，开散列在下一节，这节已经很长了。