【C++】Hash闭散列

enum State {EMPTY,EXIST,DELETE};   //每个位置有三种状态

template<class K,class V>
struct HashDate
{
	pair<K, V> _kv;
	State _state;
};

template<class K,class V>
class HashTable
{
public:
    //成员函数
private:
	vector<HashDate<K, V>> _table;
	size_t _size=0;				 
};

2.2 Insert 插入

通过哈希函数(保留余数法)获取待插入元素在哈希表中的位置
如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素。

接下来有几个问题

1. 确定质数p我们应该取vector的size()还是capacity()作为质数

使用size()因为capacity()是vector开辟的总空间超过size()的部分是不能直接使用的只能使用size()以内的空间而size要通过我们插入数据或resize进行改变。简而言之vector中超过size()小于capacity()的部分我们是不能直接访问的尽管已经开辟。

2.如果线性探测一直探测到 i 下标超过hash_table.size()我们应该如何做。

如果一直探测超过数组的下标应该绕回数组的开始处所以每次 i++ 后我们可以继续进行取模如果超过了size()会自动从数组0下标处开始探测当然使用if判断 i 超过size()超过就置0也是可以的。

3.当装载因子超过0.7之后我们应该怎么做。

即_size / _table.size() >=7 时我们要进行扩容创建一个新哈希表然后将旧表中的数据拷贝到新表中此时我们可以复用 Insert 函数因为新表是不存在扩容问题的所以会使用 Insert 中插入逻辑的代码然后将数据全部插入到新表中最后我们将新表与旧表的进行swap一下就将新表扩容指向的内容交换给了临时变量临时变量调用析构函数自动释放这样扩容问题就得到了解决。

代码如下


bool Insert(const pair<K, V>& kv)
{
	//如果 size==0 或装载因子 >=0.7 进行扩容
	if (_table.size() == 0 || 10 * _size / _table.size() >= 7)
	{
		size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
		HashTable<K, V> newHash;
		newHash._table.resize(newSize);
		//将旧表中的数据拷贝到新表中  --- 复用Insert继续拷贝数据
		for (auto e : _table)
		{
			if (e._state == EXIST)
			{
				newHash.Insert(e._kv);
			}
		}
		//进行交换  newHash自动调用其析构函数
		_table.swap(newHash._table);
	}
	size_t hashi = kv.first % _table.size();
	while (_table[hashi]._state == EXIST)   //如果存在数据就一直往后找
	{
		hashi++;
		//如果hashi++超过size()需要绕回数组的开始
		hashi %= _table.size();
	}
	//找到位置插入数据
	_table[hashi]._kv = kv;
	_table[hashi]._state = EXIST;
	++_size;
	return  true;
}

注意如果插入的是负数会发生整形提升int类型会转变为我们的size_t 类型此时负数再进行取模就可以得到一个合法的映射位置也可以被查找的。

接下来还有一个问题如果数据发生冗余怎么办。就是如果插入的是已经存在的值应该如何处理呢

2.3 Find 查找

所以我们可以在插入之前编写一个find函数如果该数据存在则不进行插入。

HashDate<K, V>* Find(const K& key)
{
	//判断表为空的情况
	if (_table.size() == 0)
		return nullptr;
	size_t hashi = key % _table.size();
	while (_table[hashi]._state != EMPTY)
	{
		//如果找到key了并且状态不是DELETE
		if (_table[hashi]._kv.first == key && _table[hashi]._state != DELETE)
		{
			return &_table[hashi];
		}
		hashi++;
		//如果超过表的长度则除以表的大小让其回到表头。
		hashi %= _table.size();
	}
	return nullptr;
}

此时有一个问题我们的循环是_state !=EMPT如果遍历重回到起点这些遍历到的数据_state都为EMPTY就可能导致死循环所以我们还要保存起始位置的状态如果重回起点则也返回false(当然这是一种非常极端的情况但是会出现)。

2.4 Erase删除

删除的思路非常简单如果find查找到该值直接将其对应的state改为DELETE即可。


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

然后我们测试一下这插入、查找、删除这三个接口。

2.5 插入复杂类型

那如果我们想实现一个统计次数的哈希表则 key 值是string类型的怎么办呢string类型或字符串类型是无法被取模的。那再如果我们想插入一个自己定义的复杂类型呢

我们先来看看STL库中是如何解决这个问题的。

所以我们要编写默认的hash取key的仿函数作为缺省参数。

在任何进行取模的地方我们要让key值调用默认的仿函数取出key值。

所以我们可以自定义编写将string类型(或其它复杂类型)转化为 size_t 类型的仿函数

struct HashFuncString
{
	size_t operator()(const string& key)
	{
		size_t val = 0;
		for (auto ch : key)
			val += ch;
		return val;
	}
};

然后我们将测试代码跑起来

void test_hash04_string()
{
	string arr[] = { "苹果","西瓜","菠萝","草莓","菠萝","草莓" ,"菠萝","草莓" 
		, "西瓜", "菠萝", "草莓", "西瓜", "菠萝", "草莓","苹果" };
	HashTable<string,int, HashFuncString> countHT;
	for (auto& str : arr)
	{
		auto ptr = countHT.Find(str);
		if (ptr)
			ptr->_kv.second++;
		else
			countHT.Insert({ str,1 });
	}
	countHT.Print();
}

但是在库中的unordered_map并不需要我们自己传入仿函数因为string是一个挺常见的类型库中使用了模板的特化对string类型进行了特殊处理我们接下来也将其进行改动为特化的形式。

template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t val = 0;
		for (auto ch : key)
			val += ch;
		return val;
	}
};

此时不传入自定义的仿函数一样可以成功运行

其实我们模拟实现的string->int的仿函数写的并不规范因为key值是唯一的如果出现以下这种情况即使key值是不同的但是通过仿函数计算后的映射却是相同的。比如

所以我们要对字符串的Hash函数进行特殊处理这里有一篇博客进行了详细的讲解字符串Hash函数对比这里我就直接使用(BKDR)的规则进行改写了

template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t val = 0;
		for (auto ch : key)
			val = val * 131 + ch;
		return val;
	}
};

线性探测就实现完了接下来就是改造为二次探测的实现

2.6 二次探测

二次探测不是指探测两次而是 i 的指数方进行探测。

如下是使用线性探测和二次探测插入同一组数据的插入结果如下

然后我们在线性探测的方式上进行改动

三、源代码与测试用例

3.1 hash源代码


enum State { EMPTY, EXIST, DELETE };   //每个位置有三种状态

template<class K, class V>
struct HashDate
{
	pair<K, V> _kv;
	State _state= EMPTY;
};

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

template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t val = 0;
		for (auto ch : key)
			val = val * 131 + ch;
		return val;
	}
};



template<class K, class V,class Hash=HashFunc<K>>
class HashTable
{
public:
	bool Insert(const pair<K, V>& kv)
	{
		//如果表中已经存在该数据
		if (Find(kv.first))	return false;
		//如果 size==0 或装载因子 >=0.7 进行扩容
		if (_table.size() == 0 || 10 * _size / _table.size() >= 7)
		{
			size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
			HashTable<K, V, Hash> newHash;
			newHash._table.resize(newSize);
			//将旧表中的数据拷贝到新表中  --- 复用Insert继续拷贝数据
			for (auto e : _table)
			{
				if (e._state == EXIST)
				{
					newHash.Insert(e._kv);
				}
			}
			//进行交换  newHash自动调用其析构函数
			_table.swap(newHash._table);
		}

		Hash hash;
		size_t hashi = hash(kv.first) % _table.size();

		while (_table[hashi]._state == EXIST)   //如果存在数据就一直往后找
		{
			hashi++;
			//如果hashi++超过size()需要绕回数组的开始
			hashi %= _table.size();
		}
		//找到位置插入数据
		_table[hashi]._kv = kv;
		_table[hashi]._state = EXIST;
		++_size;
		return  true;
	}

	HashDate<K,V>*  Find(const K& key)
	{
		//判断表为空的情况
		if (_table.size() == 0)
			return nullptr;

		Hash hash;
		size_t hashi = hash(key) % _table.size();
		while (_table[hashi]._state != EMPTY)
		{
			//如果找到key了并且状态不是DELETE
			if (_table[hashi]._kv.first == key && _table[hashi]._state!=DELETE)
			{
				return &_table[hashi];
			}
			hashi++;
			//如果超过表的长度则除以表的大小让其回到表头。
			hashi %= _table.size();
		}
		return nullptr;
	}

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

	void Print()
	{
		for(int i=0;i< _table.size();i++)
		{
			if (_table[i]._state == EXIST)
			cout <<"i:" <<i<<" [" << _table[i]._kv.first << " " << _table[i]._kv.second <<"]" << endl;
		}
	}

private:
	vector<HashDate<K, V>> _table;
	size_t _size=0;
};

3.2 测试用例

void test_hash01()
{
	HashTable<int, int> Hash;
	int a[] = { 1,11,4,15,26,7};
	for (auto e : a)
	{
		Hash.Insert(make_pair(e, e));
	}
	Hash.Print();
	cout << endl;
}
void test_hash02()
{
	HashTable<int, int> Hash;
	int a[] = { 1,11,4,15,26,7,13,5,34,9 };
	for (auto e : a)
	{
		Hash.Insert(make_pair(e, e));
	}
	Hash.Print();
	cout << endl;
}

void test_hash03()
{
	HashTable<int, int> Hash;
	int a[] = { 1,11,4,15,26,7,13,5,34,9 };
	for (auto e : a)
	{
		Hash.Insert(make_pair(e, e));
	}
	Hash.Print();
	cout << endl<<"find:"<<endl;
	
	cout << (Hash.Find(11)->_kv).first << endl;
	cout << (Hash.Find(4)->_kv).first << endl;
	cout << (Hash.Find(5)->_kv).first << endl;
	cout << (Hash.Find(34)->_kv).first << endl;
	cout << "Erase:" << endl;
	Hash.Erase(11);
	cout << Hash.Find(11) << endl;
}

void test_hash04_string()
{
	string arr[] = { "苹果","西瓜","菠萝","草莓","菠萝","草莓" ,"菠萝","草莓" 
		, "西瓜", "菠萝", "草莓", "西瓜", "菠萝", "草莓","苹果" };
	HashTable<string,int> countHT;
	for (auto& str : arr)
	{
		auto ptr = countHT.Find(str);
		if (ptr)
			ptr->_kv.second++;
		else
			countHT.Insert({ str,1 });
	}
	countHT.Print();
}

void test_hash05_string()
{
	HashFunc<string> hash;
	cout << hash({ "abc" }) << endl;
	cout << hash({ "bac" }) << endl;
	cout << hash({ "cba" }) << endl;
	cout << hash({ "bbb" }) << endl;
}

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

标签: c++