模拟实现哈希表超详解(C++)

这篇具有很好参考价值的文章主要介绍了模拟实现哈希表超详解(C++)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

模拟实现哈希表超详解(C++)

😇 😇hello!我是bug。前面几期我们讲解了树的相关结构,今天我们就要进入哈希表的学习了:
(代码可能会有一点问题,请各位老铁指正 😘 😘 )

一、哈希

🌵🌵在前面,我们学习了红黑树、AVL树的相关性质,他们增删查改的时间复杂度都是O(logN),这个效率已经是比较高的了。但是有没有一种数据结构,(不需要进行比较就可以直接增删查改)它进行增删查改的时间复杂度为O(1) 呢?下面我们就要介绍这种数据结构——哈希表。

🍉 1、什么是哈希?

🌵🌵哈希(Hash)散列函数,其本质是映射

🌻 🌻那么映射又是什么呢?如下图:(例如医院的挂号系统)
模拟实现哈希表超详解(C++)
其中我们存入一对键值,通过序号我们就可以找到人员。而序号和姓名之间就是一种映射关系。(也就是KV模型)


🌵🌵 哈希表(HashTable)是根据关键码值(Key value)而直接进行访问的数据结构。通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
通过这种映射关系,那么我们就可以直接通过key值直接找的相应的数据,插入和删除数据时也可以直接根据key值进行插入删除,其时间复杂度就是O(1) 。

🌵🌵作用哈希表在增删查改上的效率都是十分优秀的,一般我们都是通过哈希表来快速查找数据是否出现在表中。

🌵🌵哈希冲突在绝大多数情况下,我们都会面临一个问题,那就是如何使一个位置映射一个数据。当我们开辟一个数组时,我们是采用下标来进行映射的,即每一个下标都会映射数据。但是当多个数据都映射到同一个位置时,那么就产生了哈希冲突。对于哈希冲突我们是要尽量避免的,因为哈希冲突会降低我们增删查改的效率。(具体原因下面再介绍)

🌵🌵哈希表的K模型和KV模型和前面的红黑树(AVL树)一样,所以哈希表也可以封装map和set。C++中的unordered_map和unordered_set的底层就是哈希表。

🌵🌵缺点当我们要对大量数据进行操作时,要开辟大量的空间来存储数据。而且,散列函数的采用也是至关重要的(尽量避免哈希冲突),那么我们要采取哪种散列函数来进行映射呢?(下面进行介绍)


🍉 2、直接定址法

假设有这样一个数组,我们要将它存入哈希表中:

模拟实现哈希表超详解(C++)

我们直接根据元素的实际大小进行插入。
模拟实现哈希表超详解(C++)
如上图,即每一个下标都对应一个相应的数据,没有对应的数据就为空

🍏 注意 ❗️ ❗️

🌳🌳 (1)开辟数组的时候,一定要知道数据的范围,并根据数据的范围开辟数组,如果数据的大小超过了数组的大小就会越界。
🌳🌳(2)采用直接定址法一定要数据比较集中,因为最大最小数据如果相差太大,那么浪费的空间也会很多。
🌳🌳(3)如果我们存储的是整型,那么不需要担心哈希冲突,因为每个数值都对应唯一的位置。

🌻 🌻但是,当我们存入的数据不是整型的时候我们就要考虑如何来进行映射?
🌻 🌻其实在大多数情况下,我们采用unordered_map和unordered_set存储的都是字符串,那我们如何将字符串和下标联系起来呢?

可能你会觉得字符都有对应的ASCII码,我们可以用字符的ASCII来进行对应。但是这种情况下就不可避免的会出现哈希冲突,因为只要我们不规定字符串的长度,那么字符串就是无穷无尽的,通过其ASCII来对应是一定会产生冲突的。(对于哈希冲突的解决我们下面再来进行详细的介绍)

🍉3、除留余数法(重点)

当一组数据中的最大和最小相差比较大时,就会浪费大量的空间。所以直接定址法就不再适用了,这时候我们就要采用除留余数法。

🌻 🌻什么是除留余数法呢?
假设有这样一个数组,如下图:
模拟实现哈希表超详解(C++)
🌻 🌻如何通过除留余数法将数据存入哈希表中呢?

即我们将每一个数据对表的大小进行取模,取模过后数据就可以通过下标来映射相应的位置。

模拟实现哈希表超详解(C++)
所以插入后数据如图:
模拟实现哈希表超详解(C++)

除留余数法可以很好的避免空间大量的浪费,所以一般我们都采用除留余数法。当然,除留余数法也会产生哈希冲突。

除了直接定址法和除留余数法,我们还有其他的方法比如:平方取中法、折叠法、随机数法、数学分析法。(但是这些方法不常用,这里不做介绍)

🍏 注意❗️ ❗️

🌳🌳 哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突。


模拟实现哈希表超详解(C++)
🍓 🍓 下面就是实现重点了,嘿嘿。


🍉4、解决哈希冲突

上面直接定址法和除留余数法都会产生哈希冲突的问题,下面我们就来解决:

🌱 闭散列

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

🍄 (1) 线性探测

🌵🌵线性探测 线性探测是计算机程序解决哈希表冲突时所采取的一种策略。

还是这个数组:

模拟实现哈希表超详解(C++)
我们通过除留余数法,可以算得8和15取模后,其对应同一个位置,那么我们从这个位置开始,一个一个往后面去探测,直到找到一个空位置,就将数据插入。
模拟实现哈希表超详解(C++)

但是会有这种情况,即:取模后发生冲突,然后向后面探测,直到探测到最后一个位置都没有发现空位置,那么我们就再从头开始进行探测。

(线性探测中探测的终点就是取模后对应的位置,因为当我们从开始取模位置探测,探测到最后一个位置都没有,那么我们再从头开始探测,如果还是没有,那么会又回到取模位置。所以我们表的大小一定要超过数据的个数。)

🍐 优点 十分简单,好操作。

🍐 缺点 会造成成片冲突。一旦发生哈希冲突,所有的冲突连在一起,容易产生数据“堆积”。(如下图)

如下数组:
模拟实现哈希表超详解(C++)
其中每个数据取模后都对应下标为1的位置,通过线性探测插入后,如下图:
模拟实现哈希表超详解(C++)
当我们进行删除查找的时候,都是通过取模找到位置1,如果位置1不是我们要查找的数据,就会向后面遍历,直到找到数据为止。这也是为什么哈希冲突的发生会造成效率下降,而当大量的哈希冲突扎堆时,其效率更会大幅度下降。所以,也就引出了下面的二次探测来缓解成堆的哈希冲突。

🍄 (2) 二次探测

🌵🌵二次探测线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一空位置有关系,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为: Hi= (H0 + i2)% m,或者:Hi = (H0 - i2)% m。其中:i = 1,2,3…, 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置,m是表的大小。

还是看图,有这样一组数据:
模拟实现哈希表超详解(C++)

通过二次探测后,即15、22和8都对应位置1,先插入15,接着我们插入22时,二次探测,从i^2开始向后找空位置。i = 1时,就是取模位置的下一个,插入22 。插入8,向后面探测,i = 1时,已经插入了22。那么再探测i = 2时,也就是第一次位置的后面第四个位置,插入8 。

模拟实现哈希表超详解(C++)

🍏 注意❗️ ❗️

🌳🌳 二次探测可以防止成堆的哈希冲突都连续存储,缓解了效率的下降。


🌱 开散列

🌵🌵开散列也叫做 拉链法、哈希桶。首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。其本质就是一个指针数组,数组中存储的是单链表的首元素地址。

还是这个数组:

模拟实现哈希表超详解(C++)
我们要将它插入哈希表(开散列)中,如下图:
模拟实现哈希表超详解(C++)
当我们插入15、22和8时,取模计算位置,然后采用头插的方式,直接插入。发生哈希冲突的元素就通过链表进行存储。

二、闭散列(哈希)的模拟实现

🌻 🌻问题一:哈希表内部有什么结构?
(迭代器+哈希结点+哈希表。)

迭代器正向迭代器内部成员有结点指针+哈希表的指针,因为结点和结点之间没有联系,我们要从一个结点跳转到下一个结点就要通过哈希表来进行调整。所以需要哈希表的指针,同时传参过程可以很巧妙地利用this指针完成。反向迭代器通过封装正向迭代器来实现,闭散列的哈希表可以完成自减的重载,所以反向迭代器可以实现。
哈希结点成员变量有data数据,state状态。
哈希表封装哈希结点和迭代器于一体。

🌻 🌻 问题二:当我们插入删除数据时,怎么判断当前位置是否可以操作?
使用一个枚举类型,里面包含EMPTY、EXITS、DELETE三种状态。默认状态为EMPTY,插入数据后状态变为EXITS,删除数据时,只要把状态改成DELETE即可。

🌻 🌻 是不是会觉得很困惑,为什么存在三种状态?DELETE有什么作用呢?

假设有一个哈希表,如下图:
模拟实现哈希表超详解(C++)
当我们删除数据22时,将其置为EMPTY,但是会影响查找过程。查找时先计算数据的下标,如果当前位置数据不是查找的数据,那么向后依次查找,直到查到当前位置被标记为EMPTY时停止。在我们查找的过程中,如果删除数据就将其置EMPTY,当发生扎堆的哈希冲突,删除冲突中间的一个数据,就会影响对后面冲突数据的查询,所以要用DELETE进行标识,这样不会影响查找过程。如下图:
模拟实现哈希表超详解(C++)

当我们查找8的时候,计算下标为1 。但是如果22被标记成EMPTY,那么查找到22这个位置时就停止,但是如果是DELETE,那么会继续向后面查找。

🌻 🌻 问题三:怎么控制哈希表的大小?
当我们的表过小时,会产生大量的哈希冲突,效率会大幅度下滑。但是当我们的表过大时,哈希冲突得到了缓解,但是大量的空间又会被浪费。所以这里我们引入负载因子,负载因子即:有效的数据的数量/哈希表的长度,当负载因子超过0.7的时候,我们就要给哈希表扩容。为什么选中0.7作为标准值呢?在0.7的时候,哈希冲突和空间浪费之间得到了平衡,算的上是比较好的选择了。
当我们对哈希表进行扩容后,映射关系要进行调整。因为扩容的本质是重新开辟更大的空间,再将数据拷贝过去。但是,当哈希表扩容,其映射关系也会发生改变。所以我们不能直接将数据原封不动的拷贝过去,而是要重新建立映射关系。
在VS的编译器里,其采用了 素数表。因为按照素数进行扩容,取模计算下标时不容易发生哈希冲突。(虽然我也不太清楚怎么计算的)

🌻 🌻问题四:哈希表有K模型和KV模型,我们如何实现呢?
采用仿函数来取pair键对中的key,即如果是K模型,那么直接返回;如果是键对模型,那么选出里面的key再返回。

🌻 🌻问题五:字符串(比较常用)通过什么方式进行转化可以更好的避免哈希冲突呢?
(这里我们也要采用仿函数来实现。)


(不可取)
(1)首字符的ACSII码
字符总共只有256个,如果只用首字符来映射的话,很容易产生哈希冲突。
(2)字符串内所有字符ASCII码值之和
所有字符ACSII码值之和也容易冲突,即字符串中的字符相同,但是顺序不同时,全部都会冲突。


对于字符串,一群大佬经过研究后得出了下面几种不容易冲突的算法:

🍋 BKDR哈希算法⬇️ ⬇️ :

hash = hash * 131 + ch;   // 也可以乘以31、131、1313、13131、131313..

🍋 SDBM哈希算法⬇️ ⬇️ :

`hash = 65599 * hash + ch; `

🍋 RS哈希算法⬇️ ⬇️ :

template<class T>  
size_t RSHash(const T *str)  
{  
    register size_t hash = 0;  
    size_t magic = 63689;     
    while (size_t ch = (size_t)*str++)  
    {  
        hash = hash * magic + ch;  
        magic *= 378551;  
    }  
    return hash;  
}  

(剩下的就不介绍了,有兴趣的可以去看看。网址: 哈希算法

🌻 🌻问题六:查找中怎么判断当前数据是否是我们需要的查找内容?
如果是内置类型,直接用等号比较即可。但是如果是自定义类型,它的比较就需要我们自己来完成。例如:字符串的比较,我们可以用string自己的等号重载来判断。所以采用仿函数来完成这项内容,需要比较自定义类型,那么就自己来写仿函数进行判断。

🌻 🌻 问题七:方括号(“[]”)的重载?
在KV模型中,方括号的重载是很重要的。即可以直接使用方括号进行插入数据,或者对数据进行修改。
进行重载中,调用insert函数进行插入,insert函数的返回是键对值。键对值中第一个参数迭代器类型,是插入位置的迭代器;第二个参数是布尔类型,判断插入是否成功。我们根据返回值中的迭代器参数可以获得插入位置的指针,然后再通过指针获得插入键对值中的V(这里插入过程中,V值为默认值),将V返回后,我们可以通过等号进行修改
⬇️ ⬇️

	V& operator[](const K& key) 
	{ 
		return (insert(std::make_pair(key, V())).first._pnode->_data).second; 
	}

	//使用方式
	HTs["look"] = "看";
	HTs.operator[]("eat") = "吃";

🌻 🌻其他问题:
因为迭代器中要使用哈希表的指针,而哈希表又要使用迭代器,所以我们需要添加一个前置声明。
迭代器中需要访问哈希表的私有成员_table,所以我们要把迭代器定义为哈希表的友元类。(不到万不得已,不使用友元,因为友元会破坏封装)

🍒 🍒 HashTable(闭散列)的完整代码⬇️ ⬇️ :

#pragma once
#include<iostream>
#include<vector>
#include<string>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using std::pair;
using std::make_pair;

//选出key
template<class K, class V>
struct PairSelect1st
{
	const K& operator()(const pair<K, V>& kv) { return kv.first; }
};
template<class K>
struct KSelect1st
{
	const K& operator()(const K& k) { return k; }
};

//转成整型
template<class K>
struct HashFunc
{
	size_t operator()(const K& val) { return val; }
};
//模板的特化
template<>
struct HashFunc<std::string>
{
	size_t operator()(const std::string& s1)
	{
		size_t sum = 0;
		for (size_t i = 0; i < s1.size(); i++)
		{
			sum = sum * 131 + s1[i];
		}

		return sum;
	}
};

//比较判断
template<class K>
struct equal_to
{
	bool operator()(const K& lval, const K& rval) { return lval == rval; }
};
template<>
//模板特化
struct equal_to<std::string>
{
	bool operator()(const std::string& s1, const  std::string& s2) { return s1 == s2; }
};

//素数表
const int PRIMECOUNT = 28;
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
};

namespace CloseHash
{
	enum State { EMPTY, EXITS, DELETE };

	template<class T>
	struct HashData
	{
		T _data;//存储可能是k,可能是kv
		State _state = EMPTY;//标识状态

		HashData(const T& data = T(), State state = EMPTY) :_data(data), _state(state) {}
	};

	template<class K, class V, class T, class Pred, class Select1st, class HashFunc>
		class HashTable;

	template<class K, class V, class T, class Ref, class Ptr, class Pred = equal_to<K>
	, class Select1st = PairSelect1st<K, V>, class HashFunc = HashFunc<K>>
	struct Iterator
	{
		typedef HashData<T> HD;
		typedef HashTable<K, V, T, Pred, Select1st, HashFunc> HT;
		typedef Iterator<K, V, T, Ref, Ptr, Pred, Select1st, HashFunc> self;
		typedef Ref reference;
		typedef Ptr pointer;
		HD* _pnode;
		HT* _pht;
		
		Iterator(HD* pnode = nullptr, HT* pht = nullptr) :_pnode(pnode), _pht(pht) {  }

		bool operator!=(const self& it)const { return _pnode != it._pnode; }
		bool operator==(const self& it)const { return _pnode == it._pnode; }

		Ref operator*() { return _pnode->_data; }
		Ptr operator->() { return &_pnode->_data; }
		self& operator++()
		{
			size_t index = HashFunc()(Select1st()(_pnode->_data)) % _pht->_table.size();
			HD* cur = &_pht->_table[index];
			//找到_pnode的位置
			while (_pnode != cur)
			{
				index++;
				//如果到尾没找到,就从头开始找
				if (index >= _pht->_table.size())
					index = 0;

				cur = &_pht->_table[index];
				if (_pnode == cur)
					break;
			}

			index++;
			if (index >= _pht->_table.size())
			{
				_pnode = nullptr;
				return *this;
			}
			//去找_pnode后面的一个数据
			cur = &_pht->_table[index];
			while (cur->_state != EXITS)
			{
				index++;
				//如果下标不小于_table的大小时,遍历结束
				if (index >= _pht->_table.size())
				{
					_pnode = nullptr;
					return *this;
				}
				cur = &_pht->_table[index];
			}

			_pnode = cur;
			return *this;
		}
		self operator++(int) { self tmp = *this; ++*this; return tmp; }

		self& operator--()
		{
			int index = HashFunc()(Select1st()(_pnode->_data)) % _pht->_table.size();
			HD* cur = &_pht->_table[index];
			//找到_pnode的位置
			while (_pnode != cur)
			{
				index++;
				if (index >= _pht->_table.size())
					index = 0;

				cur = &_pht->_table[index];
				if (_pnode == cur)
					break;
			}

			index--;
			if (index < 0)
			{
				_pnode = nullptr;
				return *this;
			}
			//去找_pnode前面的一个数据
			cur = &_pht->_table[index];
			while (cur->_state != EXITS)
			{
				index--;
				//如果index小于0,那么就置空返回。
				if (index < 0)
				{
					_pnode = nullptr;
					return *this;
				}
				cur = &_pht->_table[index];
			}
			_pnode = cur;
			return *this;
		}
		self operator--(int) { self tmp = *this; --(*this); return tmp; }
	};

	template<class iterator>
	struct Reverse_Iterator
	{
		typedef const iterator const_reverse_iterator;
		typedef typename iterator::reference Ref;
		typedef typename iterator::pointer Ptr;
		typedef Reverse_Iterator self;
		iterator _it;

		Reverse_Iterator(iterator it) :_it(it) {}

		Ref operator*() { return *_it; }
		Ptr operator->() { return &(*_it) ; }
		self& operator++() { _it--; return *this; }
		self operator++(int) { self tmp = *this; _it--; return tmp; }
		bool operator ==(const self& it) { return _it._pnode == it._it._pnode; }
		bool operator != (const self& it) { return _it._pnode != it._it._pnode; }
	};

	template
		<class K,class V,class T,class Pred = equal_to<K>
		,class Select1st = PairSelect1st<K, V>, class HashFunc = HashFunc<K>>
	class HashTable
		//参数有KVT(键对值),仿函数选择键对值的key,仿函数将非整型转换成整型,仿函数进行比较
	{
		template<class K, class V, class T, class Ref, class Ptr, class Pred, class Select1st, class >
		friend struct Iterator;
		typedef HashData<T> HD;
		typedef HashTable<K, V, T, Pred, Select1st, HashFunc> HT;
	public:
		typedef Iterator<K, V, T, const T&, const T*, Pred, Select1st, HashFunc> const_iterator;
		typedef Iterator<K, V, T, T&, T *, Pred, Select1st, HashFunc> iterator;
		typedef Reverse_Iterator<const_iterator> const_reverse_iterator;
		typedef Reverse_Iterator<iterator> reverse_iterator;

	private:
		vector<HD> _table;
		size_t _n;//记录有效数据的个数
	public:
		HashTable() :_n(0) { }

		HashTable(const HT& h)
		{
			for (auto& e : h._table)
			{
				if(e._state == EXITS)
				insert(e._data);
			}
			_n = h._n;
		}

		HT& operator=(const HT& h) { HT tmp(h); swap(tmp); return *this; }

		iterator begin()
		{
			//如果迭代器为空直接返回
			if (_n == 0)
				return iterator(nullptr, this);
			size_t index = 0;
			HD* cur = &_table[index];
			while (cur->_state != EXITS)
			{
				index++;
				if (index >= _table.size())
					return iterator(nullptr, this);
				cur = &_table[index];
			}
				return iterator(cur, this);
		}
		iterator end() { return iterator(nullptr, this); }

		const_iterator cbegin()
		{
			//如果迭代器为空直接返回
			if (_n == 0)
				return const_iterator(nullptr, this);
			size_t index = 0;
			HD* cur = &_table[index];
			while (cur->_state != EXITS)
			{
				index++;
				if (index >= _table.size())
					return const_iterator(nullptr, this);
				cur = &_table[index];
			}
				return const_iterator(cur, this);
		}
		const_iterator cend() { return const_iterator(nullptr, this); }

		reverse_iterator rbegin()
		{
			//如果迭代器为空直接返回
			if (_n == 0)
				return reverse_iterator(iterator(nullptr, this));
			size_t index = _table.size() - 1;
			HD* cur = &_table[index];
			while (cur->_state != EXITS)
			{
				index--;
				if (index < 0)
					return reverse_iterator(iterator(nullptr, this));
				cur = &_table[index];
			}
			return reverse_iterator(iterator(cur, this));
		}
		reverse_iterator rend() { return reverse_iterator(iterator(nullptr, this)); }

		const_reverse_iterator crbegin()
		{
			//如果迭代器为空直接返回
			if(_n == 0)
				return const_reverse_iterator(const_iterator(nullptr, this));

			size_t index = _table.size() - 1;
			HD* cur = &_table[index];
			while (cur->_state != EXITS)
			{
				index--;
				if (index < 0)
					return const_reverse_iterator(const_iterator(nullptr, this));
				cur = &_table[index];
			}
			return const_reverse_iterator(const_iterator(cur, this));
		}
		const_reverse_iterator crend() { return const_reverse_iterator(const_iterator(nullptr, this)); }

		void swap(HT& h)
		{
			_table.swap(h._table);
			std::swap(_n, h._n);
		}

		V& operator[](const K& key) { return (insert(std::make_pair(key, V())).first._pnode->_data).second; }

		pair<iterator,bool> insert(const T& data)
		{	
			//仿函数挑选
			Select1st st1;
			//仿函数转化
			HashFunc hf;

			if (!_table.size())
				_table.resize(53ul);

			//先判断是否key重复
			iterator ret = find(data);
			if (ret._pnode != nullptr)
				return std::make_pair(ret,false);

			//负载因子调节表的大小
			if ((double)_n  / (double) _table.size() >= 0.7)
			{	
				HT tmp;
				tmp._table.resize(GetNextPrime(_table.size()));
				auto it = _table.begin();
				while (it != _table.end())
				{
					if (it->_state == EXITS)
						tmp.insert(it->_data);
					it++;
				}
				_table.swap(tmp._table);
			}
	
			//插入过程
			size_t i = 1;//探测的数据
			size_t index = (hf(st1(data))) % _table.size();//下标计算
			while (_table[index]._state == EXITS)
			{		
				//线性探测
				index += i;
				//二次探测
				//index += i * i;
				//i++;
				if (index >= _table.size())
					index %= _table.size();
			}

			_table[index]._data = data;
			_table[index]._state = EXITS;
			_n++;
			return std::make_pair(iterator(& _table[index],this),true);
		}

		iterator find(const T& data)
		{
			Select1st slt;
			HashFunc hf;
			size_t index = hf(slt(data)) % _table.size();

			//相等为真,这里需要先判断一次,再进循环
			if (Pred()(slt(_table[index]._data), slt(data)))
				return iterator(&_table[index], this);

			while(1)
			{
				//相等为真
				if (Pred()(slt(_table[index]._data), slt(data)))
					return iterator(&_table[index], this);

				if (_table[index]._state == EMPTY)
					break;
				index++;
				//超过了,就取模
				if (index >= _table.size())
					index %= _table.size();
			}

			return iterator(nullptr,this);
		}

		bool erase(const T& data)
		{
			if (!empty())
			{
				iterator ret = find(data);
				if (ret._pnode != nullptr)
				{
					ret._pnode->_state = DELETE;
					_n--;		
					return true;
				}
			}
			return false;
		}
		//获得素数
		size_t GetNextPrime(size_t prime)
		{
			size_t i = 0;
			for (; i < PRIMECOUNT; i++)
			{
				if (primeList[i] > prime)
					return primeList[i];
			}

			return primeList[i];
		}

		bool empty()const { return _n == 0; }
		size_t size()const { return _n; }
	};
}

🍒 🍒 测试代码⬇️ ⬇️

//CloseHash(闭散列)
void Test_KV1()//KV模型:字典
{
	CloseHash::HashTable
		<string, string, pair<string, string>, equal_to<string>,PairSelect1st<string, string>> HTs;

	pair<string, string> arr[] = {
			make_pair("left", "左边") ,make_pair("right", "右边"),make_pair("up", "向上")
			,make_pair("down", "向下"),make_pair("left","左边"),make_pair("eat","吃")
			,make_pair("sleep","睡觉"),make_pair("run","跑"),make_pair("jump","跳") };
	for (auto e : arr)
		HTs.insert(e);

	//方括号测试
	HTs["look"] = "看";

	//非const迭代器
	CloseHash::HashTable<string, string, pair<string, string>
		, equal_to<string>, PairSelect1st<string, string>>::iterator it1 = HTs.begin();
	while (it1 != HTs.end())
	{
		cout << it1->first << ":" << it1->second << endl;
		it1++;
	}
	cout << endl;

	//反向迭代器
	auto rit1 = HTs.rbegin();
	while (rit1 != HTs.rend())
	{
		cout << rit1->first << ":" << rit1->second << endl;
		rit1++;
	}
	cout << endl;

	//删除测试
	HTs.erase(make_pair("left", "左边"));
	HTs.erase(make_pair("left", "左边"));
	HTs.erase(make_pair("left", "左边"));
	HTs.erase(make_pair("down", "向下"));

	//const迭代器
	CloseHash::HashTable<string, string, pair<string, string>
		, equal_to<string>, PairSelect1st<string, string>>::const_reverse_iterator crit1 = HTs.crbegin();
	while (crit1 != HTs.crend())
	{
		cout << crit1->first << ":" << crit1->second << endl;
		crit1++;
	}
	cout << endl;
}

void Test_K1()//K模型
{
	CloseHash::HashTable<string, string, string, equal_to<string>, KSelect1st<string>>HTs;
	string arr[] = {
	"left", "左边" ,"right", "右边","up", "向上"
	,"down", "向下","left","左边","eat","吃"
	,"sleep","睡觉","run","跑","jump","跳" };
	for (auto e : arr)
		HTs.insert(e);

	//非const迭代器
	CloseHash::HashTable<string, string, string, 
		equal_to<string>, KSelect1st<string>>::iterator it = HTs.begin();
	while (it != HTs.end())
	{
		cout << *it << endl;
		it++;
	}
	cout << endl;

	//删除功能
	HTs.erase("r");
	HTs.erase("up");
	HTs.erase("up");
	HTs.erase("dowm");
	
	//const迭代器
	auto cit = HTs.cbegin();
	while (cit != HTs.cend())
	{
		cout << *cit << endl;
		cit++;
	}
	cout << endl;
}

三、开散列(哈希)的模拟实现

开散列中许多内容和闭散列一致,这里我们主要谈谈它的区别:

🌻 🌻 问题一:开散列需不需要状态来进行标识?
开散列不需要标识,插入发生哈希冲突时,直接头插即可。删除结点,如果只有一个结点,直接释放后,将_table中的指针置空。如果有多个结点,释放结点后,直接将前一个结点和后一个结点相连。查找也只需要计算下标后,找到对应的桶,然后进行查找。

🌻 🌻 问题二:开散列的迭代器如何实现?
和闭散列的迭代器类似,即需要结点指针和哈希表的指针。遍历过程就是一个一个桶进行遍历,桶内遍历直接根据next指针即可。桶间的转换需要借助哈希表的指针。因为我们的哈希表采用的是vector+forward_list,所以不能够重载自减,即无法实现反向迭代器。(单链表不支持,双向链表可以支持)

🌻 🌻 问题三:迭代器中的自增如何重载?
先计算当前结点指针处于哪一个桶中,然后去桶中遍历,直到找到当前结点指针,然后再判断,如果为尾,那么我们就去找下一个桶,直到找到存储数据的桶,然后将我们的结点指针修改成桶中的第一个指针。

🌻 🌻 问题四:极端情况应该怎么解决?
模拟实现哈希表超详解(C++)
极端情况发生的概率极低,而且发生之后即使效率大幅度降低也只是暂时的,只要继续插入数据,效率又会恢复。但是在java中对这种情况还是进行了处理,即每次插入数据之后都会统计链表的长度,如果链表中的结点个数达到了8个,那么就会将单链表转化成红黑树来进行存储。如果发生扩容,即重新映射后,结点的个数小于8,那么又会转化成单链表进行存储。

🌻 🌻问题五:开散列的平衡因子该怎么来控制?
在开散列中其平衡因子设置为达到1时,进行扩容。即数据个数等于桶的个数。在开散列中,我们不用去担心数据的插入问题,因为不论多少个数据一定都可以插入,因为数据存储在链表中。但是当链表的长度过长时,其操作效率会大幅度下降,所以我们要控制好扩容时机,不能浪费过多的空间,同时也不能使效率下降的过多。

🍒 🍒 HashTable(开散列)的完整代码⬇️ ⬇️

#pragma once
#include<iostream>
#include<vector>
#include<string>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using std::pair;
using std::make_pair;

//选出key
template<class K, class V>
struct PairSelect1st
{
	const K& operator()(const pair<K, V>& kv) { return kv.first; }
};
template<class K>
struct KSelect1st
{
	const K& operator()(const K& k) { return k; }
};

//转成整型
template<class K>
struct HashFunc
{
	size_t operator()(const K& val) { return val; }
};
//模板的特化
template<>
struct HashFunc<std::string>
{
	size_t operator()(const std::string& s1)
	{
		size_t sum = 0;
		for (size_t i = 0; i < s1.size(); i++)
		{
			sum = sum * 131 + s1[i];
		}

		return sum;
	}
};

//比较判断
template<class K>
struct equal_to
{
	bool operator()(const K& lval, const K& rval) { return lval == rval; }
};
template<>
//模板特化
struct equal_to<std::string>
{
	bool operator()(const std::string& s1, const  std::string& s2) { return s1 == s2; }
};

//素数表
const int PRIMECOUNT = 28;
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
};
namespace OpenHash
{
	template<class T>
	struct HashNode
	{
		typedef HashNode<T> Node;
		typedef HashNode<T>* pNode;

		HashNode<T>* _next;
		T _data;

	public:
		HashNode(const T& data = T())
			:_next(nullptr)
			,_data(data)
		{}
	};

	template<class K, class V, class T, class Pred, class Select1st ,class HashFunc>
	class HashTable;

	template<class K, class V, class T, class Ref, class Ptr, class Pred, class Select1st, class HashFunc>
	struct Iterator
	{
		typedef HashNode<T> Node;
		typedef HashTable<K, V, T, Pred, Select1st, HashFunc> HashTable;
		typedef Iterator<K, V, T, Ref, Ptr, Pred, Select1st, HashFunc> self;

		Node* _pnode;
		HashTable* _pHT;

		Iterator(Node* pnode = nullptr, HashTable* pHT = nullptr) : _pnode(pnode), _pHT(pHT) {  }

		Ref operator*() { return _pnode->_data; }
		const Ref operator*()const { return _pnode->_data; }
		Ptr operator->() { return &_pnode->_data; }
		const Ptr operator->()const { return &_pnode->_data; }

		self& operator++()
		{
			if (_pnode == nullptr)
				return *this;

			if (_pnode->_next != nullptr)
			{
				_pnode = _pnode->_next;
				return *this;
			}

			//_pnode->next == nullptr我们要去找现在的结点属于哪一个桶
			size_t index = HashFunc()(Select1st()(_pnode->_data)) % _pHT->_table.size() + 1;
			for (; index < _pHT->_table.size(); index++)
			{
				Node* cur = _pHT->_table[index];
				if (cur != nullptr)
				{
					_pnode = cur;
					return *this;
				}
			}
			_pnode = nullptr;
			return *this;
		}
		self operator++(int)
		{
			self tmp = *this;
			++(*this);
			return tmp;
		}

		bool operator!=(const self& it)const { return _pnode != it._pnode; }
		bool operator==(const self& it)const { return _pnode == it._pnode; }
	};

	template
		<class K, class V, class T, class Pred = equal_to<std::string>,
		class Select1st = PairSelect1st<K, V>, class HashFunc = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<T>* pNode;
		typedef HashNode<T> Node;

		template<class K, class V, class T, class Ref, class Ptr, class Pred, class Select1st, class HashFunc>
		friend  struct Iterator;
	private:
		//存结点指针
		vector<pNode> _table;
		size_t _n;	
	public:
		typedef Iterator<K, V, T, const T&, const T* ,Pred, Select1st, HashFunc> const_iterator;
		typedef Iterator<K, V, T, T&, T*, Pred, Select1st, HashFunc> iterator;

		HashTable() :_n(0) {  }

		void clear()
		{		
			for (size_t index = 0; index < _table.size(); index++)
			{
				pNode cur = _table[index];
				pNode prev = cur;
				while (cur)
				{
					prev = cur;
					cur = cur->_next;
					delete prev;
				}
			}
		}

		~HashTable()
		{
			clear();
		}

		iterator begin()
		{
			size_t index = 0;
			for (; index < _table.size(); index++)
			{
				pNode cur = _table[index];
				if (cur != nullptr)
					return iterator(cur,this);
			}
			return iterator(nullptr, this);
		}
		iterator end() { return iterator(nullptr, this); }

		const_iterator cbegin()
		{
			size_t index = 0;
			for (; index < _table.size(); index++)
			{
				pNode cur = _table[index];
				if (cur != nullptr)
					return const_iterator(cur, this);
			}
			return const_iterator(nullptr, this);
		}
		const_iterator cend() { return const_iterator(nullptr, this); }

		pair<iterator,bool> insert(const T& data)
		{
			//如果为空,则开空间
			if (!_table.size())
				_table.resize(53ul);
			//挑选key
			Select1st st1;
			//转换整型
			HashFunc hf;
			//判断是否冗余
			iterator ret = find(data);
			if (ret._pnode != nullptr)
				return std::make_pair(iterator(nullptr,this), false);

			//判断是否需要扩容
			if ((double)_n / (double)_table.size() >= 1)
			{
				vector<pNode> new_table(GetNextPrime(_table.size()));
				for (size_t i = 0; i < _table.size(); i++)
				{
					pNode cur = _table[i];
					if (cur != nullptr)
					{		
						pNode next = _table[i];
						while (cur)
						{
							next = cur->_next;
							size_t new_index = (hf(st1(cur->_data))) % new_table.size();
							//头插
							cur->_next = new_table[new_index];
							new_table[new_index] = cur;
							cur = next;
						}
						_table[i] = nullptr;
					}
					//不推荐,插入的时候重新创建结点,浪费
					/*while(e != nullptr)
					{
						tmp.insert(e->_kv);
						e = e->_next;
					}*/
				}
				new_table.swap(_table);
			}		

			//计算hashbucket的下标
			size_t index = hf(st1(data)) % _table.size();
			pNode newNode = new  Node(data);
			//头插
			newNode->_next = _table[index];
			_table[index] = newNode;
			_n++;

			return std::make_pair(iterator(newNode,this), true);
		}

		iterator find(const T& data)
		{
			HashFunc hf;
			Select1st slt;
			if (_table.size() == 0)
				return iterator(nullptr,this);

			size_t index = hf(slt(data)) % _table.size();
			pNode cur = _table[index];
			while (cur)
			{
				if (Pred()(slt(cur->_data), slt(data)))
					return iterator(cur,this);					
				else
					cur = cur->_next;
			}

			return iterator(nullptr,this);
		}

		bool erase(const T& data)
		{		
			Select1st st1;
			size_t index = HashFunc()(st1(data)) % _table.size();
			pNode cur = _table[index];
			pNode prev = cur;
			while (cur)
			{
				if (Pred()(st1(cur->_data) , st1(data)))
				{
					//找到了
					if (cur == _table[index])
					{
						_table[index] = cur->_next;
						_n--;
						delete cur;
						return true;
					}
					else
					{
						prev->_next = cur->_next;
						_n--;
						delete cur;
						return true;
					}
				}
				else//没找到
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}

		size_t GetNextPrime(size_t prime)
		{
			size_t i = 0;
			for (; i < PRIMECOUNT; i++)
			{
				if (primeList[i] > prime)
					return primeList[i];
			}

			return primeList[i];
		}

		size_t size() const{ return _n; }
	};
}

🍒 🍒 测试代码⬇️ ⬇️

//OpenHash(开散列)
void Test_KV2()//KV模型
{
	OpenHash::HashTable<string, string, pair<string, string>> hts;

	pair<string, string> arr[] = { 
		make_pair("left", "左边") ,make_pair("right", "右边"),make_pair("up", "向上")
		,make_pair("down", "向下"),make_pair("left","左边"),make_pair("eat","吃")
		,make_pair("sleep","睡觉"),make_pair("run","跑"),make_pair("jump","跳")};

	for (auto e : arr)
		hts.insert(e);

	//非const迭代器
	OpenHash::HashTable<string, string, pair<string, string>>::iterator it = hts.begin();
	while (it != hts.end())
	{
		cout << it->first << ":" << it->second << endl;
		it++;
	}
	cout << endl;

	hts.erase(make_pair("sleep", "睡觉"));
	hts.erase(make_pair("left", "左边"));
	hts.erase(make_pair("up", "向上"));

	//const类型
	OpenHash::HashTable<string, string, pair<string, string>>::const_iterator cit = hts.cbegin();
	while (cit != hts.cend())
	{
		cout << cit->first << ":" << cit->second << endl;
		cit++;
	}
	cout << endl;
}

void Test_K2()//K模型
{
	OpenHash::HashTable<string, string, string, equal_to<string>, KSelect1st<string>, HashFunc<string>> hts;
	string arr[] = {
	"left", "左边" ,"right", "右边","up", "向上"
	,"down", "向下","left","左边","eat","吃"
	,"sleep","睡觉","run","跑","jump","跳" };
	for (auto e : arr)
		hts.insert(e);

	OpenHash::HashTable<string, string, string, equal_to<string>, KSelect1st<string>, HashFunc<string>>::iterator it = hts.begin();
	while (it != hts.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}

🔍 🔍 总结:
空间消耗在开散列中虽然增加了链表的链接指针,但是其空间消耗还是要比闭散列小,因为闭散列的平衡因子一定会比开散列的小,闭散列的平衡因子一定小于1,而且越接近1,越容易发生哈希冲突。所以相同数量的数据进行存储时,开散列开辟的空间更小。


😎 😎 今天的内容到这里就结束了,希望小伙伴们能够有所收获。文章来源地址https://www.toymoban.com/news/detail-401621.html

到了这里,关于模拟实现哈希表超详解(C++)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++】哈希unordered系列容器的模拟实现

    开散列又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,即 key 映射的下标位置,具有相同地址的关键码 (哈希冲突) 归于同一子集合,每一个子集合称为一个桶 (哈希桶),各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中;也就

    2024年02月13日
    浏览(35)
  • 【C++进阶】哈希表开散列和闭散列的模拟实现(附源码)

    这里的闭散列和开散列解决哈希冲突的方法都是 除留余数法 。 一些哈希函数:字符串哈希算法 闭散列:也叫 开放定址法 ,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有 空位置,那么可以 把key存放到冲突位置中的“下一个” 空位置中去 。 如何找到

    2024年02月08日
    浏览(56)
  • 【C++】用哈希桶模拟实现unordered_set和unordered_map

    顺序结构中(数组)查找一个元素需要遍历整个数组,时间复杂度为O(N);树形结构中(二叉搜索树)查找一个元素,时间复杂度最多为树的高度次logN。理想的搜索方法: 可以不经过任何比较,一次直接从表中得到要搜索的元素。 构造一种存储结构, 通过某种函数使元素的

    2024年04月11日
    浏览(51)
  • 【C++】详解AVL树并模拟实现

      前言:   之前我们为了让数据存储效率提高,引进了二叉搜索树。   但是我们发现,二叉搜索树的时间复杂度还是O(N),因为二叉搜索树并不是非常的平衡。   并不是所有树都是满二叉树,可能出现单边书这样极端的情况,所以我们引进了查找效率更高的 AVL树 。 目录 (一

    2024年02月09日
    浏览(57)
  • C++ string类详解及模拟实现

    目录 【本节目标】  1. 为什么学习string类? 1.1 C语言中的字符串  1.2 面试题(暂不做讲解)  2. 标准库中的string类 2.1 string类(了解)  2.2 string类的常用接口说明(注意下面我只讲解最常用的接口) 3. string类的模拟实现 3.1string类常用成员函数的模拟实现 3.2 浅拷贝和深拷贝   

    2024年03月23日
    浏览(34)
  • 【C++】详解红黑树并模拟实现

    前言:        上篇文章我们一起学习了AVL树比模拟实现,我们发现AVL树成功地把时间复杂度降低到了O(logN)。但是同时我们不难发现一个问题,在构建AVL树中我们也付出了不小的代价,频繁的旋转操作导致效率变低。为了解决这个问题,我们本章将迎来更为实用的红黑树,他

    2024年02月09日
    浏览(41)
  • 【C++初阶】STL详解(四)vector的模拟实现

    本专栏内容为:C++学习专栏,分为初阶和进阶两部分。 通过本专栏的深入学习,你可以了解并掌握C++。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:C++ 🚚代码仓库:小小unicorn的代码仓库🚚 🌹🌹🌹关注我带你学习编程知识 注:为了防止与标准库当中的vector产生命名冲突

    2024年02月05日
    浏览(41)
  • C++ STL库详解:list的详细模拟实现

    在详细学习并学习c++后,我们对stl库的例如vector、list、string都有了详细的了解,对模板的使用以及类和对象都有了熟练的掌握,而实践才是检验真理的唯一标准,在此片博客中,将利用先前学过的各模块知识来对list这个在数据结构中令许多初学者摸不到北,在c++中出场率不

    2024年01月24日
    浏览(46)
  • 【C++进阶06】红黑树图文详解及C++模拟实现红黑树

    1.1 红黑树的概念 AVL树用平衡因子让树达到高度平衡 红黑树可以认为是AVL树的改良 通过给每个节点标记颜色让树接近平衡 以减少树在插入节点的旋转 在每个结点新增一个存储位表示结点颜色 可以是Red或Black 通过对任何一条从根到叶子的路径上 各个结点着色方式的限制 红黑

    2024年01月21日
    浏览(45)
  • 【C++初阶】STL详解(二)string类的模拟实现

    本专栏内容为:C++学习专栏,分为初阶和进阶两部分。 通过本专栏的深入学习,你可以了解并掌握C++。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:C++ 🚚代码仓库:小小unicorn的代码仓库🚚 🌹🌹🌹关注我带你学习编程知识 注:为了防止与标准库当中的string类产生命名冲

    2024年02月05日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包