C++学习记录（19）哈希表

2401_85751795

930人浏览 · 2025-10-15 20:31:03

2401_85751795 · 2025-10-15 20:31:03 发布

前言

一直嚷嚷着unordered系列容器像哈希像哈希，那么哈希到底是什么玩意呢？肯定还是需要系统了解。

一、哈希

咬文嚼字分析，hash其实是把……弄乱，散乱的意思。

经常说的哈希表其实实际意译应该为散列表，当然，音译一直沿用至今，我们大多数人也差不多就都接受了这个叫法，一说哈希表就知道是干啥的。

哈希可以说是一种思想，利用这个思想我们往往作为一种组织数据的方式，笼统地讲，哈希是将任意长度的数据通过某种计算方式转变为固定长度的思想，所得到的固定长度的值称为哈希值。

按照我们unordered_set和unordered_map角度理解（因为它们俩底层用的哈希实现），如果存储的key是整型那就不做处理；如果key是其它类型的，比如string，那么必须提供对应的Hash函数，使其可以转换成整型，在此过程中会出现长度转化的情况。

二、哈希函数

1.直接定址法

哈希最重要的环节就是计算，转换的过程。

当关键字的范围比较集中时，直接定址法就是非常简单又高效的方法。

比如：

387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

这道题好像不止做过一次了吧，核心思想就是：

利用：

字符串中只含小写字母，即ASCII码为[a,z]有：

将字符串中每个字母在字符串中出现的次数作为值，字母与'a'的ASCII码差值视为下标，这样字母与出现次数之间建立了联系，再遍历一次字符串就可以找到第一个不重复的字符。

在当时我们说这是计数排序的思想，其实这是哈希的直接定址法。

其实仔细想想，计数排序的过程跟这个过程差不多，都是根据一组范围不大的关键字确定下标，来存对应的值。

2.直接定址法的缺陷

但是往往实际中，大多数情况，随机序列的值其实哪里能就一定很小范围，你这就跟要求序列基本有序一样，真能随便要求那冒泡还是个好排序算法呢，人家稳定，加上这个前提还高效来着，比O（nlogn）都快，最好情况基本不用调换是O（n）。

所以这样的问题驱使着我们谋求新的哈希函数。

3.除法散列法/除留余数法

除法散列法，或者更生动的名字除留余数法已经说明了这个方法对于原定值的哈希处理办法，就除法。假设哈希表长度为M，则除留余数法的哈希函数是h(key) = key % M，并以此余数作为数据在哈希表中存储的下标。

注意事项：

这个方法定址对于M有要求，一般情况下要求M不能是2的幂，10的幂等；建议M取一个不太接近2的整数次幂的质数。

解释：

如果M是2的幂，按照二进制的角度，对32位bit位的int，能够参与运算的个数如下：

比如举例M = $2^{5}$

我们知道余数一定小于被除数，因为一旦余数大于被除数，说明上商的时候写错了，多余的数应该是属于商的，小学算术常识了。

按照我们这个方法在这个M下等于只看二进制位的最后5位，但是这样的话，后5位相同的数按道理来说应该是有 $2^{32 - 5}$ * $2^{5}$ 这么多，因为要求余数相同，那么每一种后5位都能有那么多不同的前27位，在这个方法中余数相同代表着不同的数可能会抢同一个位置，也被称为哈希冲突，哈希冲突是不可避免的，但是我们应当尽量减少哈希冲突的可能性，所以肯定希望key的每一个值都参与运算，也就是32个bit为都参与运算。

M为10次幂同理，很简单，就算一个数是16515641110 % 100，那也是只看后两位10，这样的话也是仅有少量的位数参与运算，哈希冲突的概率又上升。

如果按照建议，比如M = 11，这你总不能说有一大堆的11次幂等着吧，能与之构成倍数关系的数变的很少很少了。

哈希冲突

道理很简单，两个不同的key经过哈希函数计算下标时想要插入同一个位置，这种问题就叫哈希冲突和哈希碰撞。

实际情况中，哈希冲突一定是不可避免的，不管你怎么选哈希函数，总有可能不同的key算出来相同的下标，毕竟只要选定哈希函数计算方式是一样的，数又是无限的，那么总能找到。

就拿除留余数法举例，假设M = 11，你说12的余数是1，再加11的23余数是不是也是1。

但是并不是说哈希冲突不可避免我们就听之任之了，随随便便就弄个哈希函数算了，因为造成哈希冲突一定是需要调整的，冲突越少，调整越少，哈希表的效率才能相对更高。

负载因子

既然哈希冲突都补充了，再补充一个哈希的术语，负载因子。

假设哈希表已经存储了N个值，哈希表的大小为M，负载因子 = $\frac{N}{M}$ 。

可以知道，一般情况下M是一定的，则有：

负载因子越大，哈希冲突的概率越高，空间利用率高。因为这预示着N几乎快把哈希表填满了，没有几个映射值留着了。

负载因子越小，哈希冲突的概率越低，空间利用率低。

这就体现了辩证的思想，如果把哈希表开的很大很大，那么经常会产生空间的浪费，但是很少造成冲突，也就很少需要调整，时间成本就会降低；相反，如果哈希表开的很小，空间会被充分利用，但是哈希冲突就常常发生，调整一定是按照某种规律去找另外的空的地方插入值，调整过多时间成本就高，哈希表的效率就会下降。

4.乘法散列法（了解）

乘法散列法函数关系大致是这样的：

h(key) = floor(M ×((A ×key)%1.0))，floor代表向下取整，大致就是为了让key所有位数参与运算，因此让一个常数A(0 < A < 1)乘key，得到的值去其小数部位，再乘M向下取整，得到的值对应的下标一定在M内。这个方法对于M没有要求，因为M乘以一个与key关联且小于1的数再向下取整，其值一定在表内。

关于这个A，Knuth建议使用黄金分割比例的近似值0.6180339887...，即 A = （√5 - 1）/ 2,选择这个值是因为它能使关键字的小数部分在0到1之间分布得更加均匀，从而减少冲突。

5.全域散列法（了解）

如果存在黑客或者竞争对手之类的对象，那么被它们知道了哈希函数以后很容易就能造出来一组冲突的值，让你的哈希表每插入一个值就需要调整，从而降低你的哈希表效率。

比如你用除留余数法，将M设计成11，如果有这样一个序列：

12,23,34,45,56,67,78,89,100……

这一组值用循环很容易生成出来，不难发现它们的key最后算出来的哈希值全部为1，如果把这样的插入到哈希表里，完全冲突了，正常情况下咋可能所有的key算出来的哈希值完全相同。

为了解决这样的问题，给散列函数增加随机性，让攻击者无法找到对应计算逻辑，也就无法知道怎么计算出冲突的一组值。

大致思路是这样的：

h (key) = ((a ×key +b)%P)%M ，P需要选一个足够大的质数，a可以随机选[1,P-1]之间的任意整数，b可以随机选[0,P-1]之间的任意整数，这些函数构成了⼀个P*(P-1)组全域散列函数组。假设P=17，M=6，a=3，b=4,则 h(8) = ((3 * 8 + 4)%17)%6 = 5 。

每次创建哈希表的时候就随机生成一组a，b，这样就创建出来不一样的哈希函数，记录下来这个a，b，每调用这个表就用这样的哈希函数计算。这样也可以避免程序自己不能通过对应的key找到下标。

6.小结

对于这几种哈希函数，重点掌握除留余数法，这个方法最实用，一般哈希函数就用的这个方法。因为除了我上面举例的方法，还存在：平方取中法、折叠法、随机数法等。但是哈希表一般设计的时候其实吧，都不用上。

7.处理哈希冲突的常见方法

无论选择什么样的哈希函数，冲突是避免不了的，因此总得有办法处理哈希冲突，主要有两种方法来解决冲突：开放定址法和链地址法。

三、开放定址法

开放定址法有一个前提，那就是用开放定址法处理哈希冲突的哈希表的负载因子必须小于1。

因为如果碰到哈希冲突，开放定址法会以某种规则去找表中其它为空的位置，为了有空位置给开放定址法解决冲突用，负载因子必须小于1。

1.线性探测

从发生冲突的位置一个一个往后找，直到找到第一个空位置再插入数据。如果走到表末尾都没有找到空位置，那就直接回绕到表头再继续往后找。

线性探测公式表达：

h(key) = hash0 = key % M；//首次计算

//冲突则

hc(key,i) = hashi = (hash0 + i) % M，其中i最坏{1,2,3,4……M - 1}

因为负载因子小于1，则最多探测M-1次，⼀定能找到⼀个存储key的位置。

比如将{19,30,5,36,13,20,21,12}一组值映射到M = 11的表中

计算得哈希值为上图所示，则以此插入：

19插入到8；

30插入到8，但是8位置已经有了值，因此直接往后挨着找（线性探测），30插入到9；

5插入到5；

36插入3；

13插入2；

20插入9，但是9位置有了值，所以只能往后找，20插入到10；

21插入10，单10位置有了值，只能往后找，往后找已经到表尾，回绕到表头，所以20插入到0；

12插入到1。

经过这个例子我们体验到了线性探测解决冲突的用法。

2.二次探测（了解）

从发生冲突的位置开始，一次左右二次方跳跃探测，直到找到第一个值为空的位置。

如果走到表尾就回绕到表头；如果走到表头就回绕到表尾

二次探测公式表达：

h(key) = hash0 = key % M //首次计算

//冲突则

hc(key,i) = hashi = (hash0 ± $i^{2}$ ) % M ， i = M {1,2,3,..., $\frac{M}{2}$ }

比如将{19,30,52,63,11,22}存到表M = 11中

插入则为：

19插入到8；

30插入到8，但是8有值了，因此- $1^{2}$ ，就到7；

52插入到8，但是8有值了，因此- $1^{2}$ ，发现7也有值，于是+ $1^{2}$ ；

63插入到8，但是8有值了，并且左右都被占了，我这里弄的是+ $2^{2}$ ，于是发生回绕，插入到1，二次探测只有保证+-有规律就行了，+4回绕最后63插入到1；

11插入到0；12插入到1，但是被占了，于是先- $1^{2}$ ，回绕到表尾，所以22插入到10。

3.双重散列（了解）

双重散列就不再演示例子了，大概说一下原理，基本上就复合函数的意思：

h1(key) = hash0 = key % M

//冲突则：

hc(key,i) = hashi = (hash0+ i∗h2(key)) % M，i = {1,2,3,..., M}

运用两次hash函数，你大致感觉就是，哈希值能重一次，我再搞个其他逻辑的哈希函数，哈希值重的概率就大大减少了。

四、借助除留余数法作为哈希函数，开放定址法解决冲突实现哈希表

学习了解了除留余数法后，不妨尝试按照其逻辑设计一个哈希表。

1.哈希表结点设计

enum Status
{
	EMPTY,
	EXIST,
	DELETE
};

template <class K,class V>
struct HashNode
{
	pair<K, V> _kv;
	Status _status = EMPTY;
};

为什么将哈希表结点这么设计呢？

因为哈希表可以用来存储key或key-value，那么这样一来，直接设计成key-value结构就行，类似于红黑树作为底层设计map/set一样。

但是如果直接让哈希表存pair，是这样的情形：

问题就产生了，存的时候肯定都是pair，但是怎么判断这个位置有没有值呢？

比如就说存个key-value是int-int类型的，最多分默认值和插入值，那么这就很难说了，先说int，你设置0为空地标志吗？很显然不合理，0就不能作为value存起来了吗？同理，-1等值都有可能作为value存起来。并且难道哈希表的pair不可能存自定义类型吗，那这种情况下如何让默认值和插入值区分呢？

所以这就是为什么要用枚举类型，用枚举类型直接记录状态，EXIST代表这个位置有值，EMPTY代表这个位置没值，举个不太恰当的例子，厕所如果带着指示灯的话，可以说哈希表每个结点都是一个坑位，绿就代表坑里没人，红就代表坑里有人，虽然这个例子带点味道，但是确实是目前没文化的我能想到的最合适的类比了。

至于DELETE，等到讲Erase方法是再来说为什么要设计这个状态。

另外就是对于HashNode，为何不给它弄个构造函数，这一点到方法实现时再说

2.哈希表基本结构

通过画的图也能很方便的观察到，其实哈希表底层内存应当是数组，但是存放数据的顺序不一定按照顺序存储，而是严格根据哈希函数的映射存储。

为了方便对底层数据管理，底层套vector：

template <class K,class V>
class HashTable
{
	typedef struct HashNode<K,V> Node;
public:
	HashTable()
		;_tables(11)
	{}

private:
	std::vector<Node> _tables;
	size_t _n = 0;//有效数据个数
};

哈希表底层直接借助vector就能快速开辟一个顺序空间，因为我们也模拟实现过vector，底层其实是三个指针，不过一般就当成顺序表来管理。

看到这里就可以解释为什么不给结点那个类搞构造了，原因很简单，因为按道理来说创建一个哈希表对象，下一步就是往里存储数据，肯定事先得开好一定大小的空间，当然，不够再扩容。这里我们调用的是vector的fill构造去申请一定大小的空间：

对于vector内部，肯定是：

class vector
{
public:

private:
    Node* _arr;
    size_t _size;
    size_t _capacity;
}

vector的底层结构以及我们调用的构造函数注定了，我们就算在底层申请内存也不需要给Node初始化什么值，但是在new的时候不初始化就得有默认构造，Node的pair确实也没啥可赋值的，所以只给_status搞个缺省值。

3.Insert方法

问题1：M是谁

	bool Insert(const pair<K,V>& kv)
	{
		//扩容

		//插入
		int hash0 = kv.first % ;



	}

先写插入逻辑，写插入逻辑上来就得算哈希值，但是M是谁呢？

底层容器是：

那么M是size还是capacity呢？画个图看看：

假设M是capacity，那么很有可能算出来如图位置需要插入数据，但是vector我们知道只能在0~size-1位置插入，在如图位置插入将是不可控行为。

因此M就是size。

问题2：如果线性探测到尾怎么回绕

这个就不卖关子了，如果需要回绕，那肯定是加到等于M了，回绕的话下标为0，所以直接取模就行：

	bool Insert(const pair<K,V>& kv)
	{
		//扩容

		//插入
		int hash0 = kv.first % _tables.size();
		int hashi = hash0;
		//线性探测
		while (_tables[hashi]._status == EXIST)
		{
			if (_tables[hashi]._kv.first == kv.first)
				return false;
			hashi = (hashi + 1) % _tables.size();
		}
		_tables[hashi]._kv = kv;
		_tables[hashi]._status = EXIST;
		++_n;

		return true;
	}

由于vector内部存的是Node，所以插入数据直接修改kv和状态即可。

随便插入几个值测试测试：

看起来没啥问题。

扩容

大致上负载因子在0.7~0.8就得扩容，扩容还是扩size，那就还是二倍扩：

这句代码一写下去就感觉不对劲了，如果是扩容：

比如这个哈希表，下标会增长到21，M增长到22，h(19) = 19，h(21) = 21，也就是说，哈希表里已经存起来的值很有可能映射关系都不对了，因为M的增长，直接原地扩容是行不通的，所以还是得把原哈希表里的值全部重新映射到新表里：

		if ((double)_n / _tables.size() >= 0.7)
		{
			vector<Node> newtables(_tables.size() * 2);
			for (auto& e : _tables)
			{
				if (e._status == EXIST)
				{
					int hash0 = e._kv.first;
					int hashi = hash0;
					//线性探测
					while (_newtables[hashi]._status == EXIST)
					{
						if (_newtables[hashi]._kv.first == kv.first)
							return false;
						hashi = (hashi + 1) % _tables.size();
					}
					_newtables[hashi]._kv = kv;
					_newtables[hashi]._status = EXIST;
				}
			}
			_tables.swap(newtables);
		}

写完又感觉不大对劲，我一个一个的去找EXIST，最后插入还是得拿到key一个一个插入，等于把插入的逻辑又写了一遍，只不过这次是从一个vector里拿的数据，不是参数传过来的，实在是怪怪的。

所以考虑以后：

		//简单扩容
		if ((double)_n / _tables.size() >= 0.7)
		{
			HashTable<K, V> newHT;
			newHT._tables.resize(2 * _tables.size());
			for (size_t i = 0; i < _tables.size(); i++)
				if (_tables[i]._status == EXIST)
					newHT.Insert(_tables[i]._kv);
			_tables.swap(newHT._tables);
		}

思路就是干脆直接创建个新表，新表底层vector初始化大小为当前表的两倍，然后再遍历原表，把能插的全部插入到新表里，这样不就复用了Insert函数的插入逻辑，最后swap一下底层的vector就完成任务了，原vector里的Node全部都随着局部域结束而结束。

再测试测试：

不再截了，100个值全进去了。而且按照顺序搞得。

遗留问题

还是有个问题未解决：

都说过了，M不让搞2次幂啥的，你还搞个二次扩容，一般建议都是素数，那不让二倍扩容该怎么扩容。

stl里面是这么做的：

inline unsigned long __stl_next_prime(unsigned long n)
{
	// Note: assumes long is at least 32 bits.
	static const int __stl_num_primes = 28;
	static const unsigned long __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
	};
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}

直接搞了一个静态的数组，可以看到数组里全部都是素数，而且基本上每两个相邻的数之间基本上是个二倍的关系。

返回值的核心就是利用lower_bound

可以看到对于lower_bound返回值的描述的意思是返回这个区间内，比val大的第一个元素。

假设哈希表现在M = 53，如果需要扩容，stl里的逻辑就是通过这个函数找97。

套用到我们自己的逻辑里就是：

	HashTable()
		:_tables(__stl_next_prime(1))
	{}

初始化的时候叫他求比1大的数，其实就是给个53；


		//简单扩容
		if ((double)_n / _tables.size() >= 0.7)
		{
			HashTable<K, V> newHT;
			newHT._tables.resize(__stl_next_prime(_tables.size() + 1));
			for (size_t i = 0; i < _tables.size(); i++)
				if (_tables[i]._status == EXIST)
					newHT.Insert(_tables[i]._kv);
			_tables.swap(newHT._tables);
		}

扩容的时候给个_tables.size() + 1找比当前size大的值就行。

另外补充一句，为啥人家这静态数组的搞到42亿多就不管了，道理其实也好说，就按我们实现的代码来说，哈希Node存储一个pair和enum，而pair我们就按最小来算，pair<char,char>两个字节吧，enum实际上都是整形，就当4个字节，考虑内存对齐就是8个字节，也就是说，最小一个哈希Node是多大，8个字节。

在研究vector的max_size的时候我们算过一笔账，40亿个字节大概就是个4G，存40亿个哈希Node那不就是8 * 4一共32个G，内存开32G哈希表痴心妄想呢，能够负担得起这种玩意儿估计也就是服务器用的内存条了。

4.Find方法

这里讲一下DELETE这个状态的作用：

插入的时候20的哈希值为9，但是被30占了，所以线性探测到10了；

现在删了30，状态改成DELETE，查找的时候很明显，碰见DELETE也得继续查找，因为哈希冲突可能导致位置与哈希值不照应，得继续查找，直到碰见EMPTY，说明按照规律找到空都没找到这个key，这个key根本就没插入，因为插入只要碰见空就插入。

间接说明，DELETE存在的原因：如果只在Insert方法的角度来考虑的话，那确实，真没话说，EXIST和EMPTY就够用了，但是站在删除以后查找的角度，如果只有这两种状态，那就可能导致存在但是你不继续查找了。

另外再补充一下，其实Insert插入逻辑循环结束，可能是碰见了EMPTY，也可能是碰见了DELETE，不管这两种状态哪一个，反正都相当于值无效，可以在这个位置插入。

懂了这个以后，Find就好实现了：

	Node* Find(const K& key)
	{
		int hashi = key % _tables.size();
		while (_tables[hashi]._status != EMPTY)
		{
			if (_tables[hashi]._status == EXIST && _tables[hashi]._kv.first == key)
				return &_tables[hashi];
			hashi = (hashi + 1) % _tables.size();
		}

		return nullptr;
	}

不是空一直找，如果碰见一个结点状态是存在而且key符合要求，直接返回对应Node*；

出了循环还没找到，说明找到空都没找到，直接return nullptr。

5.Erase方法

其实Erase是先Find再删除：

	bool Erase(const K& key)
	{
		Node* des = Find(key);

		if (des)
		{
			des->_status = DELETE;
			--_n;
			return true;
		}
		else
			return false;
	}

直接复用吧，累了，能找到就删，找不到就不删；删的时候也不是真删，顺着指针改状态就行。

测试

Find跟Erase俩人逻辑粘到一起了，因此一个没忍住，直接都搞了，其实核心还是Find的逻辑，现在再测试也不耽误：

插入的时候，30是因为19已经占了8，有哈希冲突，所以委身到9。

我的测试思路：

哈希冲突的线性探测调整后的值能否查找到？

find(30)

如果哈希值对应的地方的值Erase会不会影响调整后的值？

erase(19) + find(30)

能否对哈希冲突后正确的值Erase？

erase(30)

6.非整型值存储问题

很明显我们上面写的代码都是针对，正整型值才能插入，对于其他类型的值可谓说是漏洞百出。

比如假如要是存的key为负值，在insert方法中：

请问你算出来的hash值是不是成负数了。

所以往往针对这种情况我们会像库里面的unordered系列容器一样，准备第三个模板参数，哈希函数：

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

在哈希表内：

根据哈希函数这个实现了仿函数的类创建一个对象，这样就可以实现：

大致就是把所有可能需要转换的地方全部套上仿函数的逻辑。

但是仅仅这样往往还是不足。

不说其他的例子，就说哈希表经常性的可能被当成字典来用：

	HashTable<string, string> ht;

对照上面的逻辑，string真的能插入进去吗？

很显然是不可能的，仿函数它都过不去，因为仿函数逻辑对于string来说相当于(size_t)string，不相关的类型强转是不允许的，因此string还必须拥有自己的一套仿函数逻辑，专供string类的key使用，这里就用到模板的知识，模板的特化：

template <>
class HashFunc<string>
{
public:
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash += e;
		}
		return hash;
	}
};

string专门就用这套逻辑，以string所有的字符的ASCII码值和作为哈希值。

补充

当然，早有人研究过这样的逻辑，其实我们上面写的代码还是有不足：

有很多不同的字符串可能仅仅是内部顺序变了一下，也有可能是刚好字符串与字符串之间ASCII码和相同。

对于此有人提出了这样的解决方案：

template <>
class HashFunc<string>
{
public:
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash += e;
			hash *= 131;
		}
		return hash;
	}
};

可以解决不同字符串ASCII码相同的问题。

但是其实还是不难想到

这样的问题还是没有解决，当然，在这里我们就不再讨论了，因为string长度理论上无限的，那么转换成哈希值可能出现的问题有很多，碰见一个解决一个不是现在最需要理解的，重点是借助string这个类型的例子明白哈希表对于非整型值需要特殊处理后才能存储这个问题。

五、链地址法

来放定址法不失为一种有效的解决冲突的办法，不说最后的双重散列；其实前面线性探测和二次探测有很明显的规律性，也就是说很容易出现大范围的冲突。因此实践中往往不采用开放定址法去解决冲突，而是链地址法。

解决冲突的思路

啥都不说，直接上图：

链地址法就是在哈希表中存储结点的指针，如果有冲突不用探测，直接继续往里面挂，哈希表每个位置其实存储的数据类似于链表一样。

这种方法也被称为哈希桶，因为这里哈希表每个位置其实就像是一个桶一样，如果需要插入数据就直接往里扔；如果需要查找数据就找到结点所在的桶再查找；如果需要删除数据先找到对应的哈希桶再去里面删除对应结点。

也就是说基本控制数据结构的思路就是先根据哈希值算出结点所在哈希桶，再到哈希桶，或者说就是链表再进行对应操作。

负载因子

其实不难想到，链地址法负载因子根本无上限。

当然，太大自然也不好，如果负载因子太大，难免会有哈希表某个位置挂的链表过长，量化的话就说find的效率，find的效率很低，因为相当于退化成链表的查找了，链表的查找就是遍历整个数组，故而实践中不会让链地址法的负载因子过大。

六、利用除留余数法作为哈希函数，链地址法结局哈希冲突实现哈希表

1.哈希表结点设计

重点是要像链表一样给每个哈希表结点挂结点，因此：

	template <class K,class V>
	struct HashNode
	{
		pair<K, V> _kv;
		struct HashNode* _next;
	};

2.哈希表基础结构

	template <class K,class V>
	class HashTable
	{
		typedef struct HashNode<K, V> Node;
	public:
		HashTable()
			:_tables(__stl_next_prime(1),nullptr)
		{}




	private:
		vector<Node*> _tables;
		size_t _n = 0;//有效数据个数
	};

暂时就能想到这么多，我们给_tables里存的都是链表的第一个结点的地址，vector<Node*>不用解释；

构造还是用素数表来搞，而且这个时候需要给每个值置空，毕竟是指针，还是谨慎一点。

其他暂时想不到，就只能写这么多。

3.Insert方法

插入逻辑

先随便举个例子昂，假如往这张表里面插入16，那么一算哈希值就是5，现在怎么插入？

能够拿到的就是这个位置存的链表结点的指针，哈希表数据没有固定的顺序关系，因此直接把新插入的结点入对应位置的链表即可：

这样是最简单的，类似于单链表的头插。再次强调，哈希表数据没有硬性顺序要求，所以直接头插没啥毛病。

		bool Insert(const pair<K, V>& kv)
		{
			//扩容

			//插入
			int hashi = kv.first % _tables.size();
			//_tables[hashi] newnode 
			Node* newnode = new Node(kv);
		}

先完成前置条件嘛，找对应位置，再构造个结点插入，但是写出来这个代码突然感觉不对劲，因为：

不用写默认构造确实是没啥影响，pair自然会一个类型一个类型去调默认构造，指针算内置类型，不一定啥行为，但是最好置空，不过不写默认构造也没啥事，毕竟哈希表在这里相当于指针数组，我写构造的时候就全置空了。

不过一旦new就得有对应构造函数，还得整一个：

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

		pair<K, V> _kv;
		struct HashNode* _next;
	};

逻辑继续：

		bool Insert(const pair<K, V>& kv)
		{
			//扩容

			//插入
			int hashi = kv.first % _tables.size();
			//_tables[hashi] newnode 
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
            ++_n;
		}

有newnode以后就是个单链表的头插，而且你走读代码还能发现，其实就算_tables[hashi]为nullptr也没啥毛病，毕竟也没去解引用。

扩容逻辑

插入弄完就得完善扩容去：

链地址法的负载因子理论无上限，但是我们实现的时候一般不让链地址法负载因子超过1，等于1就得着手扩容。

			//扩容
			if (_n == _tables.size())
			{
				vector<Node*> newtable(__stl_next_prime(_tables.size() + 1), nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					while (_tables[i])
					{
						int hashi = _tables[i]->_kv.first % newtable.size();

					}
				}
			}

写着写着又发现不对了，如果我还是去遍历原哈希表再一个一个插入到新哈希表，写到这里的下一步岂不是又开始走插入逻辑了，能不能像上面开放定址法一样复用逻辑呢？

			//扩容
			if (_n == _tables.size())
			{
				HashTable<K, V> newtable;
				newtable._tables.resize(__stl_next_prime(_tables.size() + 1), nullptr);

				for (size_t i = 0; i < _tables.size(); i++)
				{
					while (_tables[i])
					{
						newtable.Insert(_tables[i]->_kv);
						_tables[i] = _tables[i]->_next;
					}
				}
				_tables.swap(newtable._tables);
			}

不过呢，这样的代码总归感觉有点问题：

最后的swap是直接交换底层vector，再依靠作用域结束以后对newtable的析构对原vector析构。

不妨细扒一下：

因为vector底层肯定是这样的：

void reserve(size_t n)
{
    if(n > size())
    {
        _start = new Node*[n];
        //....
    }
}

delete的时候：

~vector()
{
    delete[] _start;
    _start = _finish = _end_od_storage = nullptr;   
}

再来，就这么说，你new Node完了，存到vector里面，那你vector销毁的时候还不delete，就好像malloc和free一样，一定是成对存在的。

如果不delete的话，相当于存放东西的容器销毁了，东西还在里面。

		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				while (_tables[i])
				{
					Node* next = _tables[i]->_next;
					delete _tables[i];
					_tables[i] = next;
				}
			}
		}

优化

其实上面给出来的方案还不是最优解，且看此图：

既然存的都是Node*，那为什么不重新挂呢？也就是把访问一个个key去insert换成直接把Node*换个位置。

			//扩容
			if (_n == _tables.size())
			{
				HashTable<K, V> newtable;
				newtable._tables.resize(__stl_next_prime(_tables.size() + 1), nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					while (_tables[i])
					{
						int hashi = _tables[i]->_kv.first % newtable._tables.size();
						Node* next = _tables[i]->_next;
						//newtable[hashi] _tables[i]
						_tables[i]->_next = newtable._tables[hashi];
						newtable._tables[hashi] = _tables[i];
						
						_tables[i] = next;
					}
				}
				_tables.swap(newtable._tables);
			}

4.Find方法

		Node* Find(const K& key)
		{
			int hashi = key % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
					return cur;
				cur = cur->_next;
			}
			return nullptr;
		}

通过哈希值，找到对应位置，然后当成遍历单链表即可。

5.Erase方法

		bool Erase(const K& key)
		{
			int 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;
					cur = nullptr;
					return true;
				}
				cur = cur->_next;
			}
			return false;
		}

本来想的是复用Find，但是我们设置的是单链表，复用的话拿不到prev，查找逻辑和Find一样。

6.非整型值存储问题

其实一个道理：

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

template <>
class HashFunc<string>
{
public:
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash += e;
			hash *= 131;
		}
		return hash;
	}
};

再多个参数，套一层：

namespace Hash_backet
{
	template <class K,class V>
	struct HashNode
	{
		HashNode(const pair<K,V>& kv)
			:_kv(kv)
			,_next(nullptr)
		{}

		pair<K, V> _kv;
		struct HashNode* _next;
	};

	template <class K,class V,class Hash = HashFunc<K>>
	class HashTable
	{
		typedef struct HashNode<K, V> Node;
		HashFunc<K> hash;
	public:
		HashTable()
			:_tables(__stl_next_prime(1), nullptr)
		{}

		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				while (_tables[i])
				{
					Node* next = _tables[i]->_next;
					delete _tables[i];
					_tables[i] = next;
				}
			}
		}

		bool Insert(const pair<K, V>& kv)
		{
			//扩容
			if (_n == _tables.size())
			{
				HashTable<K, V> newtable;
				newtable._tables.resize(__stl_next_prime(_tables.size() + 1), nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					while (_tables[i])
					{
						int hashi = hash(_tables[i]->_kv.first) % newtable._tables.size();
						Node* next = _tables[i]->_next;
						//newtable[hashi] _tables[i]
						_tables[i]->_next = newtable._tables[hashi];
						newtable._tables[hashi] = _tables[i];
						
						_tables[i] = next;
					}
				}
				_tables.swap(newtable._tables);
			}

			//插入
			int hashi = hash(kv.first) % _tables.size();
			//_tables[hashi] newnode 
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return true;
		}

		Node* Find(const K& key)
		{
			int 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)
		{
			int hashi = hash(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;
					cur = nullptr;
					return true;
				}
				cur = cur->_next;
			}
			return false;
		}

	private:
		vector<Node*> _tables;
		size_t _n = 0;//有效数据个数
	};
}

测试代码还是那个道理，不多说了。

void testHash1()
{
	//open_address::HashTable<int, int> ht;
	Hash_backet::HashTable<int, int> ht;
	int arr[] = { 19,30,5,36,13,20,21,12 };
	for (auto e : arr)
	{
		ht.Insert({ e,e });
	}

	cout << ht.Find(30) << endl;
	ht.Erase(19);
	cout << ht.Find(30) << endl;
	ht.Erase(30);
	cout << ht.Find(30) << endl;

	//for (size_t i = 0; i < 100; i++)
	//{
	//	ht.Insert({i,i});
	//}
}

void testHash2()
{
	Hash_backet::HashTable<string, string> ht;
	ht.Insert({ "preception","理解力，立场，观点" });

	HashFunc<string> hash;
	cout << hash("abcd") << endl;
	cout << hash("bacd") << endl;
	cout << hash("aadd") << endl;
}

int main()
{
	testHash1();
	testHash2();


	return 0;
}

AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

SeedVR2终极指南：如何用单步扩散模型实现专业级视频修复

还在为老旧视频的模糊画质而烦恼吗？面对抖动严重的监控录像或褪色的家庭影像，你是否曾希望有一种简单高效的修复方案？SeedVR2正是为解决这些痛点而生的一站式视频修复工具。作为字节跳动推出的先进视频修复模型，它能够在单步推理中实现专业级的视频质量提升，彻底改变了传统视频修复的工作流程。## 核心价值：为什么选择SeedVR2进行视频修复？**传统视频修复的三大瓶颈**：1. **计算成本高

AI Agent技术社区

深度解析Amlogic S9xxx电视盒子Armbian系统：从闲置设备到Linux服务器的终极实战指南

你是否拥有一台闲置的Amlogic S9xxx系列电视盒子？想让它摆脱单一的视频播放功能，变身为功能强大的Linux服务器、开发平台或家庭媒体中心？本指南将为你详细解析如何通过Armbian系统实现这一转变，让你的电视盒子重获新生，成为高性能的Linux设备。Armbian系统基于Debian/Ubuntu构建，专为ARM芯片优化，提供了完整的Linux生态支持。## 🎯 核心价值与独特优势

AI Agent技术社区

CANN/runtime Event管理API

本章节描述 CANN Runtime 的 Event 管理接口，用于事件的创建、记录、同步、计时及 IPC 跨进程共享。- [`aclError aclrtCreateEvent(aclrtEvent *event)`](#aclrtCreateEvent)：创建Event，创建出来的Event可用于统计两个Event之间的耗时、多Stream之间的任务同步等场景。- [`aclError