• C++之哈希表、哈希桶的实现


    哈希概念

    顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(logN),搜索的效率取决于搜索过程中元素的比较次数。

    理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。

    如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素。

    当向该结构中:

    • 插入元素:根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放;
    • 搜索元素:对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功。

    该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)(或者称散列表。

    例如:数据集合{1,7,6,4,5,9};
    哈希函数设置为:hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
    在这里插入图片描述

    哈希冲突

    不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

    例如此时需要插入一个44,就会出现下面的问题,44与4的位置是冲突的,这就是哈希冲突问题。
    在这里插入图片描述

    哈希函数

    引起哈希冲突的一个原因可能是:哈希函数设计不够合理。

    哈希函数设计原则

    • 哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间
    • 哈希函数计算出来的地址能均匀分布在整个空间中
    • 哈希函数应该比较简单

    常见的哈希函数

    1. 直接定址法
      取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B
      优点:简单、均匀
      缺点:需要事先知道关键字的分布情况
      使用场景:适合查找比较小且连续的情况
    2. 除留余数法
      设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:Hash(key) = key% p(p<=m),将关键码转换成哈希地址
    3. 平方取中法
      假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址;
      再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址;
      平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况。
    4. 折叠法
      折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。
      折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况
    5. 随机数法
      选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中random为随机数函数。
      通常应用于关键字长度不等时采用此法
    6. 数学分析法
      设有n个d位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现,可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址。

    我们在此主要了解直接定址法除留余数法

    哈希冲突解决

    解决哈希冲突两种常见的方法是:闭散列开散列

    闭散列

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

    1. 线性探测

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

    Hi = (H0 + i)%m ( i = 1 , 2 , 3 , . . . )
    H0:通过哈希函数对元素的关键码进行计算得到的位置。
    Hi:冲突元素通过线性探测后得到的存放位置。
    m:表的大小

    比如在上面的场景中,现在需要插入元素44,先通过哈希函数计算哈希地址,哈希地址为4,因此44理论上应该插在该位置,但是该位置已经放了值为4的元素,即发生哈希冲突。
    在这里插入图片描述
    通过观察可以发现,在插入元素的时候,通过哈希函数获取待插入元素在哈希表中的位置,如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探测找到下一个空位置,插入新元素。

    我们会发现,数据越多,产生哈希冲突的概率就越高,进行查找的效率也就越低,所以哈希表中引入了负载因子的概念:

    负载因子 = 表中有效数据个数 / 空间的大小

    • 负载因子越大,产生哈希冲突的概率也就越大,增删查改效率也就越低,空间利用率就越高;
    • 负载因子越小,产生哈希冲突的概率也就越小,增删查改效率也就越高,空间利用率就越低。

    对于闭散列(开放定址法)来说,负载因子是特别重要的因素,一般控制在0.7~0.8以下,超过0.8会导致在查表时CPU缓存不命中(cache missing)按照指数曲线上升。
    因此,一些采用开放定址法的hash库,如JAVA的系统库限制了负载因子为0.75,当超过该值时,会对哈希表进行增容。

    比如我们此时将容量扩大至20,我们就会发现,哈希冲突的概率明显减少:
    在这里插入图片描述
    我们要注意删除时哈希表中的元素是不能随便进行删除的,因为一个元素的删除可能会影响另一个元素的查找,例如我们将4这个元素删除掉,后就会影响到44的查找,因此线性探测采用标记的伪删除法来删除一个元素。

    哈希表闭散列实现

    哈希表的结构

    为了方便我们对哈希表中数据进行删除与查找,我们可以使用枚举将每个位置的状态标识出来:

    enum State
    {
    	EMPTY,   //(未存储数据的空位置)
    	EXIST,   //(已存储数据)
    	DELETE   //(数据被删除)
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    当我们对某一数据进行删除以后,我们将其状态标识为DELETE状态 ,如果该位置是存在哈希冲突的位置,我们进行查找的过程就会识别该位置并不是EMPTY状态而是DELETE状态,就会去他后面的位置寻找,删除同样也是如此操作。

    因此,闭散列的哈希表中的每个位置存储的结构,应该包括所给数据和该位置的当前状态。

    	template<class K, class V>
    	struct HashData
    	{
    		pair<K, V> _kv;
    		//每个位置最开始为空
    		State _state = EMPTY;
    	};
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    为了在插入元素时好计算当前哈希表的负载因子,我们还应该时刻存储整个哈希表中的有效元素个数,当负载因子过大时就应该进行哈希表的增容。

    template<class K, class V>
    class HashTable
    {
    public:
    	//
    private:
    	vector<HashData<K, V>> _tables;//哈希表
    	size_t n = 0;//哈希表中有效元素个数
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    哈希表的插入

    插入主要分为以下步骤:

    1. 判断哈希表中是否存在该键值对,如果存在,就返回false;
    2. 判断是否需要对哈希表大小进行调整,如果哈希表大小为0或者负载因子过大都需要进行扩容;
    3. 插入键值对;
    4. 哈希表中有效元素+1;

    我们需要注意的是,扩容以后,并不是简单的将旧表的数据给挪到新表当中去,而是在新表中重新计算所占位置,然后再依次进行插入,插入具体步骤就是:

    1. 通过哈希函数计算出相应的哈希地址;
    2. 判断该位置状态是否是DELET或者EMPTY;
    3. 将键值对进行插入,改变当前位置状态为EXIST;
    bool Insert(const pair<K, V>& kv)
    {
    	//如果此处键值对已经存在,就返回false
    	if (Find(kv.first))
    	{
    		return false;
    	}
    	//判断是需要进行扩容
    	if (_tables.size() == 0 || 10 * _size / _tables.size() >= 7)
    	{
    		size_t newSize = _tables.size() == 0 ? 10 : 2 * _tables.size();
    		//创建一个新的哈希表
    		HashTable newHT;
    		newHT._tables.resize(newSize);
    		//将旧表数据重新计算哈希地址插入到新表中
    		for (auto e : _tables)
    		{
    			if (e._state == EXIST)
    			{
    				newHT.Insert(e._kv);
    			}
    		}
    		//将旧表数据与新表数据进行交换
    		_tables.swap(newHT._tables);
    	}
    	//计算哈希地址
    	size_t hashi = kv.first % _tables.size();
    	//寻找状态为DELETE和EMPTY位置进行插入
    	while (_tables[hashi]._state == EXIST)
    	{
    		hashi++;
    		hashi %= _tables.size();
    	}
    	//插入键值对
    	_tables[hashi]._kv = kv;
    	//改变状态
    	_tables[hashi]._state = EXIST;
    	//元素个数++
    	_size++;
    
    	return true;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42

    哈希表的查找

    查找步骤如下:

    1. 先判断哈希表是否为空,为空就赶回nullptr;
    2. 然后用哈希函数计算出哈希地址,在哈希地址处开始查找,如果在EXIST位置找到该元素,则查找成功,如果到空位置,则查找失败;

    我们要注意的是必须对哈希地址进行限制,否则就会有越界的风险。

    代码如下:

    HashData<K, V>* Find(const K& key)
    {
    	//如果哈希表为空,就返回false
    	if (_tables.size() == 0)
    	{
    		return nullptr;
    	}
    	//计算哈希地址
    	size_t hashi = key % _tables.size();
    	size_t start = hashi;
    	//在状态不为EMPTY的地方进行查找
    	while (_tables[hashi]._state != EMPTY)
    	{
    		//如果此时该位置不是DELETE状态并且key值等于查找的key值,返回该位置地址
    		if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
    		{
    			return &_tables[hashi];
    		}
    		//去下一个位置进行查找
    		hashi++;
    		hashi %= _tables.size();
    
    		if (hashi == start)
    		{
    			break;
    		}
    	}
    	//找不到就返回空
    	return nullptr;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    哈希表的删除

    删除步骤如下:
    判断哈希表中是否存在该值,存在就将该位置状态设置为DELETE,不存在就直接返回false。

    bool Erase(const K& key)
    {
    	//判断该key值是否存在
    	HashData<K, V>* ret = Find(key);
    
    	//存在即为真
    	if (ret)
    	{
    		//存在就更改该位置状态
    		ret->_state = DELETE;
    		_size--;
    	}
    	//否则就返回false
    	return false;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    上述情况针对int类型的的数据没有问题,但是如果是string类型的数据,我们就会发现,就无法直接对key值比较进行判断,此时就需要针对string类型创建一个仿函数,如果我们此时传入的是一个string对象,就可以调用仿函数得到val值,然后在就可以就算哈希地址了;

    template<class K>
    struct HashFunc
    {
    	size_t operator()(const K& key)
    	{
    		//所有类型都强转为size_t类型
    		return (size_t)key;
    	}
    };
    //模板特化
    template<>
    struct HashFunc<string>
    {
    	size_t operator()(const string& key)
    	{
    		size_t val = 0;
    		for (auto ch : key)
    		{
    			val *= 131;
    			val += ch;
    		}
    		return val;
    	}
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    代码整体就可以优化为:

    namespace CloseHash
    {
    	enum State
    	{
    		EMPTY,   //(未存储数据的空位置)
    		EXIST,   //(已存储数据)
    		DELETE   //(数据被删除)
    	};
    
    	template<class K, class V>
    	struct HashData
    	{
    		pair<K, V> _kv;
    		//每个位置最开始为空
    		State _state = EMPTY;
    	};
    
    	template<class K>
    	struct HashFunc
    	{
    		size_t operator()(const K& key)
    		{
    			//所有类型都强转为size_t类型
    			return (size_t)key;
    		}
    	};
    
    	//模板特化
    	template<>
    	struct HashFunc<string>
    	{
    		size_t operator()(const string& key)
    		{
    			size_t val = 0;
    			for (auto ch : key)
    			{
    				val *= 131;
    				val += ch;
    			}
    
    			return val;
    		}
    	};
    
    	template<class K, class V, class Hash = HashFunc<K>>
    	class HashTable
    	{
    	public:
    		bool Insert(const pair<K, V>& kv)
    		{
    			//如果此处键值对已经存在,就返回false
    			if (Find(kv.first))
    			{
    				return false;
    			}
    			//判断是需要进行扩容
    			if (_tables.size() == 0 || 10 * _size / _tables.size() >= 7)
    			{
    				size_t newSize = _tables.size() == 0 ? 10 : 2 * _tables.size();
    				//创建一个新的哈希表
    				HashTable<K, V, Hash> newHT;
    				newHT._tables.resize(newSize);
    				//将旧表数据重新计算哈希地址插入到新表中
    				for (auto e : _tables)
    				{
    					if (e._state == EXIST)
    					{
    						newHT.Insert(e._kv);
    					}
    				}
    				//将旧表数据与新表数据进行交换
    				_tables.swap(newHT._tables);
    			}
    
    			Hash hash;
    			//计算哈希地址
    			size_t hashi = hash(kv.first) % _tables.size();
    			//寻找状态为DELETE和EMPTY位置进行插入
    			while (_tables[hashi]._state == EXIST)
    			{
    				hashi++;
    				hashi %= _tables.size();
    			}
    			//插入键值对
    			_tables[hashi]._kv = kv;
    			//改变状态
    			_tables[hashi]._state = EXIST;
    			//元素个数++
    			_size++;
    
    			return true;
    		}
    		HashData<K, V>* Find(const K& key)
    		{
    			//如果哈希表为空,就返回false
    			if (_tables.size() == 0)
    			{
    				return nullptr;
    			}
    			Hash hash;
    			//计算哈希地址
    			size_t hashi = hash(key) % _tables.size();
    			size_t start = hashi;
    			//在状态不为EMPTY的地方进行查找
    			while (_tables[hashi]._state != EMPTY)
    			{
    				//如果此时该位置不是DELETE状态并且key值等于查找的key值,返回该位置地址
    				if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
    				{
    					return &_tables[hashi];
    				}
    				//去下一个位置进行查找
    				hashi++;
    				hashi %= _tables.size();
    
    				if (hashi == start)
    				{
    					break;
    				}
    			}
    			//找不到就返回空
    			return nullptr;
    		}
    
    		bool Erase(const K& key)
    		{
    			//判断该key值是否存在
    			HashData<K, V>* ret = Find(key);
    
    			//存在即为真
    			if (ret)
    			{
    				//存在就更改该位置状态
    				ret->_state = DELETE;
    				_size--;
    			}
    			//否则就返回false
    			return false;
    		}
    		void Print()
    		{
    			for (size_t i = 0; i < _tables.size(); i++)
    			{
    				if (_tables[i]._state == EXIST)
    				{
    					printf("[%d:%d] ", i, _tables[i]._kv.first);
    				}
    				else
    				{
    					printf("[%d:*] ", i);
    				}
    			}
    			cout << endl;
    		}
    	private:
    		vector<HashData<K, V>> _tables;//哈希表
    		size_t _size = 0;//哈希表中有效元素个数
    	};
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    1. 二次探测

    线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为:

    Hi = (H0 + i²)%m ( i = 1 , 2 , 3 , . . . )
    H0:通过哈希函数对元素的关键码进行计算得到的位置。
    Hi:冲突元素通过线性探测后得到的存放位置。
    m:表的大小
    在这里插入图片描述

    研究表明:当表的长度为质数且表装载因子a不超过0.5时,新的表项一定能够插入,而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入时必须确保表的装载因子a不超过0.5,如果超出必须考虑增容。

    开散列

    开散列概念

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

    例如,我们用除留余数法将下图序列插入到表长为10的哈希表中,当发生哈希冲突时我们采用开散列的形式,将哈希地址相同的元素都链接到同一个哈希桶下,插入过程如下:
    在这里插入图片描述

    哈希表的结构

    在开散列的哈希表中,哈希表的每个位置存储的实际上是某个单链表的头结点,即每个哈希桶中存储的数据实际上是一个结点类型,该结点类型除了存储所给数据之外,还需要存储一个结点指针用于指向下一个结点。

    template<class K, class V>
    class HashNode
    {
    	pair<K, V> _kv;
    	HashNode<K, V>* next;
    
    	//构造函数
    	HashNode(const pair<K, V>& kv)
    		:_kv(kv)
    		,next(nullptr)
    	{}
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    与闭散列的哈希表不同的是,在实现开散列的哈希表时,我们不用为哈希表中的每个位置设置一个状态字段,因为在开散列的哈希表中,我们将哈希地址相同的元素都放到了同一个哈希桶中,并不需要经过探测寻找所谓的“下一个位置”。

    template<class K, class V>
    class HashTable
    {
    	typedef HashNode<K, V> Node;
    public:
    	//
    private:
    	vector<Node*> _tables;
    	size_t size = 0;
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    我们还需在这儿提供一个哈希表的析构函数,用于哈希表中单链表结点的释放:

    ~HashTable()
    {
    	for (size_t i = 0; i < _tables.size(); i++)
    	{
    		Node* cur = _tables[i];
    		while (cur)
    		{
    			Node* next = cur->next;
    			delete cur;
    			cur = next;
    		}
    		_tables[i] = nullptr;
    	}
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    哈希表的插入

    开散列的哈希表插入与闭散列插入思想大致相同,都需要计算哈希地址出哈希地址,但是开散列的哈希表扩容以后,只是将旧表的结点移动到新表当中,并不是复用旧表数据,当开散列的负载因子为1时,我们就创建一个新的哈希表,将旧表结点移动至新表中,在交换旧表与新表数据即可;

    bool Insert(const pair<K, V>& kv)
    {
    	//如果该键值对存在,就返回false
    	if (Find(kv.first))
    	{
    		return false;
    	}
    	//如果负载因子为1就扩容
    	if (_size == _tables.size())
    	{
    		//创建一个新的哈希表
    		vector<Node*> newTables;
    		size_t newSizes = _size == 0 ? 10 : 2 * _tables.size();
    
    		//将每个元素初始化为空
    		newTables.resize(newSizes, nullptr);
    
    		//将旧表结点插入到新表当中
    		for (size_t i = 0; i < _tables.size(); i++)
    		{
    			Node* cur = _tables[i];
    
    			while (cur)
    			{
    				//记录cur的下一个结点
    				Node* next = cur->_next;
    				//计算相应的哈希桶编号
    				size_t hashi = cur->_kv.first % newTables.size();
    
    				//将旧表结点移动值新表
    				cur->_next = newTables[hashi];
    				newTables[hashi] = cur;
    				cur = next;
    			}
    			_tables[i] = nullptr;
    		}
    		_tables.swap(newTables);
    	}
    	//计算哈希桶编号
    	size_t hashi = kv.first % _tables.size();
    
    	//插入结点
    	Node* newnode = new Node(kv);
    	newnode->_next = _tables[hashi];
    	_tables[hashi] = newnode;
    
    	//元素个数++
    	_size++;
    	return true;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    哈希表的查找

    查找步骤如下:

    1. 先判断哈希表大小是否为0,为0就返回nullptr;
    2. 通过哈希函数计算出对应的哈希地址;
    3. 通过哈希地址找到对应的哈希桶中的单链表,遍历单链表进行查找即可。
    Node* Find(const K& key)
    {
    	//哈希表为空就返回空
    	if (_tables.size() == 0)
    	{
    		return nullptr;
    	}
    	//计算哈希地址
    	size_t hashi = key % _tables.size();
    	Node* cur = _tables[hashi];
    	//遍历哈希桶
    	while (cur)
    	{
    		if (cur->_kv.first == key)
    		{
    			return cur;
    		}
    		cur = cur->_next;
    	}
    	return nullptr;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    哈希表的删除

    查找步骤如下:

    1. 先判断哈希表大小是否为0,为0就返回false;
    2. 通过哈希函数计算出对应的哈希地址;
    3. 通过哈希地址找到对应的哈希桶中的单链表,遍历单链表进行删除即可。
    bool Erase(const K& key)
    {
    	//哈希表大小为0,删除失败
    	if (_tables.size() == 0)
    	{
    		return false;
    	}
    
    	//计算哈希地址
    	size_t hashi = key % _tables.size();
    
    	Node* prev = nullptr;
    	Node* cur = _tables[hashi];
    	//遍历哈希桶,寻找删除结点是否存在
    	while (cur)
    	{
    		if (cur->_kv.first == key)
    		{
    			if (prev)
    			{
    				prev->next = cur->next;
    			}
    			else
    			{
    				_tables[hashi] = cur->next;
    			}
    			//删除该结点
    			delete cur;
    			_size--;
    
    			return true;
    		}
    		prev = cur;
    		cur = cur->next;
    	}
    	//删除结点不存在,返回false
    	return false;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    同样,我们也可以针对string提供一个仿函数,代码整体优化如下:

    namespace HashBucket
    {
    	template<class K, class V>
    	struct HashNode
    	{
    		pair<K, V> _kv;
    		HashNode<K, V>* _next;
    
    		//构造函数
    		HashNode(const pair<K, V>& kv)
    			:_kv(kv)
    			,_next(nullptr)
    		{}
    	};
    
    	template<class K, class V, class Hash = HashFunc<K>>
    	class HashTable
    	{
    		typedef HashNode<K, V> Node;
    	public:
    
    		~HashTable()
    		{
    			for (size_t i = 0; i < _tables.size(); i++)
    			{
    				Node* cur = _tables[i];
    				while (cur)
    				{
    					Node* next = cur->_next;
    					delete cur;
    					cur = next;
    				}
    				_tables[i] = nullptr;
    			}
    		}
    		bool Insert(const pair<K, V>& kv)
    		{
    			//如果该键值对存在,就返回false
    			if (Find(kv.first))
    			{
    				return false;
    			}
    
    			Hash hash;
    			//如果负载因子为1就扩容
    			if (_size == _tables.size())
    			{
    				//创建一个新的哈希表
    				vector<Node*> newTables;
    				size_t newSizes = _size == 0 ? 10 : 2 * _tables.size();
    
    				//将每个元素初始化为空
    				newTables.resize(newSizes, nullptr);
    
    				//将旧表结点插入到新表当中
    				for (size_t i = 0; i < _tables.size(); i++)
    				{
    					Node* cur = _tables[i];
    
    					while (cur)
    					{
    						//记录cur的下一个结点
    						Node* next = cur->_next;
    						//计算相应的哈希桶编号
    						size_t hashi = hash(cur->_kv.first) % newTables.size();
    
    						//将旧表结点移动值新表
    						cur->_next = newTables[hashi];
    						newTables[hashi] = cur;
    						cur = next;
    					}
    					_tables[i] = nullptr;
    				}
    				_tables.swap(newTables);
    			}
    			//计算哈希桶编号
    			size_t hashi = hash(kv.first) % _tables.size();
    
    			//插入结点
    			Node* newnode = new Node(kv);
    			newnode->_next = _tables[hashi];
    			_tables[hashi] = newnode;
    
    			//元素个数++
    			_size++;
    			return true;
    		}
    		//查找
    		Node* Find(const K& key)
    		{
    			//哈希表为空就返回空
    			if (_tables.size() == 0)
    			{
    				return nullptr;
    			}
    			Hash hash;
    			//计算哈希地址
    			size_t hashi = hash(key) % _tables.size();
    			Node* cur = _tables[hashi];
    			//遍历哈希桶
    			while (cur)
    			{
    				if ((cur->_kv.first) == key)
    				{
    					return cur;
    				}
    				cur = cur->_next;
    			}
    			return nullptr;
    		}
    		//删除
    		bool Erase(const K& key)
    		{
    			//哈希表大小为0,删除失败
    			if (_tables.size() == 0)
    			{
    				return false;
    			}
    			Hash hash;
    			//计算哈希地址
    			size_t hashi = hash(key) % _tables.size();
    
    			Node* prev = nullptr;
    			Node* cur = _tables[hashi];
    			//遍历哈希桶,寻找删除结点是否存在
    			while (cur)
    			{
    				if (hash(hash(cur->_kv.first)) == key)
    				{
    					if (prev)
    					{
    						prev->_next = cur->_next;
    					}
    					else
    					{
    						_tables[hashi] = cur->_next;
    					}
    					//删除该结点
    					delete cur;
    					_size--;
    
    					return true;
    				}
    
    				prev = cur;
    				cur = cur->_next;
    			}
    			//删除结点不存在,返回false
    			return false;
    		}
    	private:
    		vector<Node*> _tables;
    		size_t _size = 0;
    	};
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155

    我们在查看stl库中源码可以发现,哈希桶的扩容方式的大小都为素数,这是为了减小哈希冲突所设计出来的,研究发现,哈希表扩容大小设置为素数,极大地减少了哈希冲突。我们将一系列素数存储在一个数组当中,然后根据情况在进行扩容即可:

    inline size_t __stl_next_prime(size_t n)
    {
    	static const size_t __stl_num_primes = 28;
    	static const size_t __stl_prime_list[__stl_num_primes] =
    	{
    		53, 97, 193, 389, 769,
    		1543, 3079, 6151, 12289, 24593,
    		49157, 98317, 196613, 393241, 786433,
    		1572869, 3145739, 6291469, 12582917, 25165843,
    		50331653, 100663319, 201326611, 402653189, 805306457,
    		1610612741, 3221225473, 4294967291
    	};
    
    	for (size_t i = 0; i < __stl_num_primes; ++i)
    	{
    		if (__stl_prime_list[i] > n)
    		{
    			return __stl_prime_list[i];
    		}
    	}
    
    	return -1;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    最终插入代码扩容就可以优化为:

    newTables.resize(__stl_next_prime(_tables.size()), nullptr);
    
    • 1
  • 相关阅读:
    RabbitMQ 学习(六)---- 路由订阅模型
    1100w播放、45w涨粉!黑马UP在B站20天逆袭登顶!
    Program design PACT analysis
    ELK整合Filebeat监控nginx日志
    maven安装配置
    Windows计划任务权限维持
    Objective-C 基础教程第七章,深入理解Xcode
    01.MySQL(SQL分类及使用)
    Java数组遍历深度解析
    Python 配置pyqt5开发环境
  • 原文地址:https://blog.csdn.net/2303_77100822/article/details/132816176