C++之哈希

unordered系列容器的效率之所以比较高(尤其是查找),是因为它底层使用了哈希结构,即哈希表.

哈希概念

前言:

顺序结构以及平衡树中, 元素关键码与其存储位置之间没有对应的关系, 因此在查找一个元素
时, 必须要经过关键码的多次比较.

顺序查找时间复杂度为O(N), 平衡树中为树的高度, 即O(log2 N), 搜索的效率取决于搜索过程中元素的比较次数.

理想的搜索方法:

可以不经过任何比较, 一次直接从表中得到要搜索的元素.如果构造一种存储结构, 通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系, 那么在查找时通过该函数可以很快找到该元素.

哈希思想:

插入元素

根据待插入元素的关键码, 以此函数计算出该元素的存储位置并按此位置进行存放.

搜索元素

对元素的关键码进行同样的计算, 把求得的函数值当做元素的存储位置, 在结构中按此位置
取元素比较, 若关键码相等, 则搜索成功.
该方式即为哈希(散列)方法, 哈希方法中使用的转换函数称为哈希(散列)函数, 构造出来的结构称为哈希表(Hash Table)(或者称散列表) .

注意:

哈希/散列: 映射, 关键字和另一个值建立一个关联关系, 哈希是一种方法.
哈希表/散列表: 映射, 关键字和存储位置建立一个关联关系, 哈希表是一种结构.

例如: 数据集合{1，7，6，4，5，9}；
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

用该方法进行搜索不必进行多次关键码的比较, 因此搜索的速度比较快.

哈希冲突

按照上述哈希方式, 向集合中插入元素44, 会出现什么问题？

44和4的位置按照哈希函数计算出的存储位置冲突了.

对于两个数据元素的关键字 ki 和 kj (ki != kj), 有 ki != kj , 但有: Hash(ki) ==Hash(kj).

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

发生哈希冲突该如何处理呢？

哈希函数

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

哈希函数设计原则：

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

常见哈希函数

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种不同的符号在各位上出现的频率不一定
相同, 可能在某些位上分布比较均匀, 每种符号出现的机会均等, 在某些位上分布不均匀只
有某几种符号经常出现. 可根据散列表的大小, 选择其中各种符号分布均匀的若干位作为散
列地址.例如：

设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同
的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现冲突，还
可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移
位、前两数与后两数叠加(如1234改成12+34=46)等方法。
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的
若干位分布较均匀的情况

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

哈希冲突解决

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

闭散列

插入

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

线性探测

线性探测: 从发生冲突的位置开始, 依次向后探测, 直到寻找到下一个空位置为止. 将新插入的值放到该空位置. Hash(key) = ( Hash(key) + i ) % m ,i = 1,2,3,....

为什么加完i还要模m呢, 因为一直加的话可能会超过表长,这时就要回到开头往后进行探测了.

比如上面的场景, 现在需要插入元素44, 先通过哈希函数计算哈希地址, hashAddr为4，
因此44理论上应该插在该位置, 但是该位置已经放了值为4的元素, 即发生哈希冲突.

线性探测插入: 通过哈希函数获取待插入元素在哈希表中的位置, 如果该位置中没有元素则直接插入新元素, 如果该位置中有元素发生哈希冲突, 使用线性探测找到下一个空位置, 插入新元素. 44应该插入4的位置, 4的位置被占了, 就一直向后找, 直到找到空位置插入, 如果找不到空位置就说明哈希表满了, 需要扩容, 找到相同的值就插入失败.后续的插入如果发生冲突也是如此, 插入444一直向后找, 找到0位置为空, 就插入.

线性探测优点: 实现简单.
线性探测缺点: 一旦发生哈希冲突, 所有的冲突连在一起, 容易产生数据“堆积”(我向后探测放到后面的空位置就占用了别的位置, 其它key定位到这个位置也需要再向后探).

即:冲突值占据了可利用的空位置, 使得寻找某关键码的位置需要许多次比较(从冲突位置可能要向后查找多次),导致搜索效率降低, 可以认为闭散列本质是就是一种零和游戏.

如何缓解呢？

二次探测（平方探测法）

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

二次探测它在向后探测的过程中使用了二次增量(第一次冲突+1^2, 第二次+2^2, 第三次+3^2
…), 而不是线性增量, 这样在寻找下一个可用槽位时, 可以跳过一些位置, 从而减少关键字在哈希表中的聚集程度.

删除

采用闭散列处理哈希冲突时, 不能随便物理删除哈希表中已有的元素, 若直接删除元素会影响其他元素的搜索. 比如删除元素44, 如果直接删除掉, 444查找起来可能会受影响:

首先删除的策略是先查找, 查找到这个元素再删除, 如何查找呢?

如果映射到的位置刚好存储的是这个值, 那就查找到了, 如果不是, 就要线性探测式的向后找.什么时候判定找不到? 如果遇到了空就可以判断找不到了, 因为如果遇到了空还没找到, 后面的值就不可能是要查找的值了.

所以直接删除的话是会影响查找的, 比如删除44后, 线性探测查找找到8的位置就为空了, 就会误认为444不在哈希表中, 从而出现找不到的情况, 因此线性探测采用标记的伪删除法来删除一个元素.

// 哈希表每个空间给个标记
// EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
enum State{EMPTY, EXIST, DELETE};

每个位置最开始都为EMPTY, 如果插入元素状态就改为EXIST, 如果删除了就改为DELETE(不修改值, 只改变状态, 实现伪删除), 查找的时候遇到EXIST或DELETE就继续找, 直到找到状态既为EXIST,值又为要查找的值的位置才算找到, 如果遇到EMPTY就是没找到该元素.

DELETE状态的意义:

1、再插入, 这个位置可以覆盖值.
2、防止后面冲突的值, 出现找不到的情况。遇到删除状态, 还是继续往后找

扩容

哈希表什么情况下进行扩容？如何扩容？

载荷因子/负载因子

对于哈希表来说, 它的扩容不是等到当前表插入满了才去扩容, 而是去衡量哈希表的装满程度, 如果当前表里面插入的元素已经比较多了, 那这时再去插入新元素, 发生冲突的可能性就比较大了, 那冲突值就会增多, 冲突值越多, 那哈希表查找的效率就越低了.所以当哈希表的装满程度已经比较大的时候, 即使还没满, 这个时候就要扩容了。

闭散列哈希表实现

闭散列的插入

接下来以闭散列线性探测的方式处理哈希冲突(哈希函数以除留余数法为例).

数据的状态:

数据的结构:

用pair类型存储值, 用枚举类型设置状态, 默认都是EMPTY.

哈希表的结构和插入操作:

哈希表元素包括一个vector用来存储数据, 还有一个_n用来记录表内的有效元素, 哈希表默认大小先设为10.

插入操作包括扩容和普通的插入两个过程, 普通的插入就先用hashi记录数据映射的位置, 如果是EMPTY或者DELETE就直接插入并修改状态, 如果是EXIST就要向后探测, 直到不是EXIST为止.

这里可以取0.7为负载因子的最大值, 大于等于这个值就扩容:

这里的扩容操作,不能在原表的基础上进行扩容, 如果只是单纯把vector的size更改了, 原来的映射关系就全乱了, 所以要重新去开一块空间, 该空间的大小就是扩容之后的大小, 然后在新表上面把旧表的元素重新进行散列定位和插入.

此外这里插入的时候新表可以直接调用自己的insert插入就行了, 新表的负载因子已经小于0.7了, 它会执行自己的插入逻辑, 并不会出现死循环. 最后把新旧表的vector交换一下就可以.

闭散列的查找和删除:

如果查找到的状态是EMPTY就返回空指针, 否则就线性探测查找, 找到就返回该位置.

删除如果没找到就直接返回false, 找到了就把状态修改为DELETE,_n--

插入就可以先在插入前先判断要插入的值是否存在, 存在就返回false.

关于find的一个bug: 另外查找的时候可能会出现一个bug, 可能在插入的过程中插入又删除插入又删除导致一直没发生扩容, 而此时表里的状态标记全都变成了DELETE或者EXIST, 没有EMPTY那查找就会一直进行, 陷入死循环, 所以可以多加一个判断条件先记录最开始的映射位置, 如果hashi和index相等了,就说明查了一圈没查到, 返回空指针即可.

测试:

先写一个打印函数方便测试

扩容前:

void TestHT1()
{
	test::HashTable<int, int> ht;
	int a[] = { 5,6,7,9,11,14,444 };
	for (auto e : a)
	{
		ht.insert(make_pair(e, e));
	}
	ht.Print();
}

可以看到是对应的

扩容后:

void TestHT1()
{
	test::HashTable<int, int> ht;
	int a[] = { 5,6,7,9,11,14,444 };
	for (auto e : a)
	{
		ht.insert(make_pair(e, e));
	}
    ht.insert(make_pair(3, 3));
	ht.Print();
}

也是对应的

删除3:

void TestHT1()
{
	test::HashTable<int, int> ht;
	int a[] = { 5,6,7,9,11,14,444 };
	for (auto e : a)
	{
		ht.insert(make_pair(e, e));
	}

	ht.insert(make_pair(3, 3));
	ht.Erase(3);
	ht.Print();
}

查找3:

void TestHT1()
{
	test::HashTable<int, int> ht;
	int a[] = { 5,6,7,9,11,14,444 };
	for (auto e : a)
	{
		ht.insert(make_pair(e, e));
	}

	ht.insert(make_pair(3, 3));
	//ht.Print();

	
	ht.Erase(3);
	ht.Print();
	
	if (ht.Find(3))
	{
		cout << "3存在" << endl;
	}
	else
	{
		cout << "3不存在" << endl;
	}
}

存储整型之外的其它类型元素

我们上面实现的哈希表测试时里面存的都是整型, 而我们的哈希函数用整型进行计算刚好是比较好的(比如我们上面用的是除留余数法).
但是如果是其它类型, 要是浮点型或者char类型, 还比较好处理, 因为可以强转, 但是如果是除此之外的其它类型, 比如string, 或者其它的自定义类型, 我们的程序还能很好的处理吗？

比如说用哈希表实现一个统计次数的操作:

void TestHT2()
{
	string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

	test::HashTable<string, int> ht;
	for (auto& e : arr)
	{
		test::HashData<string, int>* ret = ht.Find(e);
		if (ret)
		{
			ret->_data.second++;
		}
		else
		{
			ht.insert(make_pair(e, 1));
		}
	}

	ht.Print();
}

可以看到string并不支持与整型之间的转换, 那怎么处理?

我们可以用一个仿函数来解决, 这个仿函数的作用就是把key(无论是什么类型 )转换成整型。

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

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

对于默认的key能转成size_t就直接转, 对于string则可以用到模板的特化进行特殊处理, 这里可以先尝试把所有字符的ASIIC码值相加并返回.

此外, 对于其它自定义类型也是一样, 可以根据实际情况写仿函数控制.

类模板参数要添加一个:

需要计算散列地址的地方都要调用一下仿函数.

Print稍作修改, 把value值也打印出来:

void Print()
{
	for (int i = 0; i < _tables.size(); i++)
	{
		if (_tables[i]._s == EXIST)
			cout << "[" << i << "]" << "->" << _tables[i]._data.first << ":" << _tables[i]._data.second << endl;
	}
}

可以看到运行成功.

注意: 上面把字符串所有的字符之和作为key去散列, 在一定程度上可以减少冲突, 但是避免不了这样的情况：

如果两个字符串是不相同的, 但是它们的字符ASCII码值之和是相同的,比如两个字符串只是有些字符顺序不同(abc和acb).
如果这样情况比较多的话, 还是会造成大量冲突.

解决方式:

各种字符串Hash函数 - clq - 博客园 (cnblogs.com)

字符串哈希函数种类很多, 这里重点来了解一种BKDRHash:

也是去计算字符串所有字符的ASCII码值之和, 但是它每次都把前一个值乘一个数, 这个数也可以取好多种值.

取31为例, 顺便打印出来看一看:

void TestHT2()
{
	test::HashTable<string, int> ht;	
    ht.insert(make_pair("apple", 1));
	ht.insert(make_pair("sort", 1));

	ht.insert(make_pair("abc", 1));
	ht.insert(make_pair("acb", 1));
	ht.insert(make_pair("aad", 1));

	ht.Print();
}

如果只是单纯ASSIC码值的加和的话, abc,acb和aad对应的hash地址应该是一样的, 处理之后可以看到abc,acb和aad的hash值就不一样了, 这里每种打印了两次是因为insert里find还会调用一次, 注重结果即可.

注意: 不管怎么优化虽然会减少冲突, 但是不能避免冲突, 字符串可以有无数多种组合方式, 整型对应的大小是固定的,不同的字符串还是有可能映射相同的整型值最终还是会冲突, 而这里的方法是尽可能让它们不要冲突到固定的几个值, 尽可能分散一些.

闭散列的缺陷:

空间利用率低, 冲突频率高:
开放定址法容易产生冲突, 特别是当哈希表的负载因子较大时, 即哈希表的装满程度更高.这会导致性能下降, 因为冲突的数量会增加, 导致查找的效率降低, 而一旦减小负载因子, 又会导致频繁扩容，空间利用率低.
线性聚集问题:
开放定址法在处理冲突时, 有时会出现聚集问题, 聚集是指数据项在哈希表中被连续地存储在相邻的位置上, 这样会导致冲突更加频繁, 并且会造成某些位置的利用率低而其他位置的利用率高的情况。

所以实际应用中, 处理哈希冲突更常用的是下面的方法:

开散列(拉链法)

开散列概念

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

插入44发生哈希冲突:

从上图可以看出, 开散列中每个桶中放的都是发生哈希冲突的元素

开散列哈希表实现

还是以KV模型为例:

析构函数:

那由于我们这样实现vector里面存的是一个个的结点, 这些结点可能指向空也可能指向一个链表(vector里面存的链表的头指针),我们的元素就是存在每个哈希桶(链表)里面的.里面的链表空间自己开辟出来的, 涉及到资源管理需要手动释放.

开散列的插入

根据哈希函数算出元素的散列地址, 将它链接到对应的单链表(哈希桶)上就行了, 至于插入的方式，头插尾插都可以, 这里我们选择头插, 因为单链表的头插是比较方便的.

扩容

其实我们这里如果不对哈希表进行扩容, 也可以不断插入值, 即使有冲突, 那我们就一直往每个对应的链表后面链接就行了, 但是如果我们插入的值比较多, 而表的长度有限, 那它每个链表里面的冲突值肯定会一直增多, 那这样效率就会大打折扣.

所以这里依然使用负载因子来控制扩容：

那对于这里的拉链法我们可以把负载因子设置成1, 1就是哈希表里面所有的链表(哈希桶)里面插入的元素之和等于表的长度的时候, 我们进行扩容. 相当于每个哈希桶中都有一个元素.

遍历旧表,依次把每个哈希桶里面的数据重新插入到新表里面.

但是我们可以进行一些优化:

上面的写法,调用inert的时候, 在insert里面还是会拿旧表里面每个结点的_kv去重新开结点然后插入, 最后还要一个一个结点释放旧表。

所以这样优化一下:

直接把旧表的结点直接拿下来插入到新表里面, 这样即不用开新结点, 最终交换之后也不用释放旧表的结点, 那这样的话我们就不去复用insert了，自己去搞

需要注意的是每次插入完之后原来表的元素要置为空, 否则出作用域会自动调用析构, 释放结点空间, 因为我们是直接把原来的表的结点链接到新表, 而不是利用这个值创建新结点插入, 所以空间不能被释放.

开散列的查找和删除

查找与删除其实就是单链表的查找与删除.

查找就是根据散列地址去对应的链表里面查找:

那删除的话也是先走查找的逻辑, 先根据散列地址去对应的链表里面找, 找到了就进行删除(那这就是链表里面删除元素的操作了), 找不到返回false即可.

测试:

Print函数:

void TestHT1()
{
	hash_bucket::HashTable<int, int> ht;
	int a[] = { 1,4,5,6,7,9,34 };
	for (auto e : a)
	{
		ht.insert(make_pair(e, e));
	}

	ht.Print();
}

比对可以发现和示意图中打印的顺序是一样的.

void TestHT1()
{
	hash_bucket::HashTable<int, int> ht;
	int a[] = { 1,4,5,6,7,9,34 };
	for (auto e : a)
	{
		ht.insert(make_pair(e, e));
	}

	ht.insert(make_pair(3, 3));
	ht.insert(make_pair(44, 44));
	ht.insert(make_pair(11, 11));
	//扩容
	ht.insert(make_pair(2, 2));
}

扩容后也符合预期, 这里4和44位置先访问了4再访问44, 因为扩容的时候先插入的44再插入4, 结果是合理的.

void TestHT1()
{
	hash_bucket::HashTable<int, int> ht;
	int a[] = { 1,4,5,6,7,9,34 };
	for (auto e : a)
	{
		ht.insert(make_pair(e, e));
	}

	ht.insert(make_pair(3, 3));
	ht.insert(make_pair(44, 44));
	ht.insert(make_pair(11, 11));
	//扩容
	ht.insert(make_pair(2, 2));

	ht.Erase(3);
	ht.Print();
	
	if (ht.Find(3))
	{
		cout << "3存在" << endl;
	}

	else
	{
		cout << "3不存在" << endl;
	}
}

字符串统计个数也是可以的:

void TestHT2()
{
	string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

	hash_bucket::HashTable<string, int> ht;
	for (auto& e : arr)
	{
		//auto ret = ht.Find(e);
		hash_bucket::HashNode<string, int>* ret = ht.Find(e);
		if (ret)
		{
			ret->_data.second++;
		}
		else
		{
			ht.insert(make_pair(e, 1));
		}
	}
	ht.Print();
}

哈希表性能测试分析

在哈希表里面查找一个元素, 时间复杂度是多少？

对于哈希表的查找, 如果我们考虑最坏的情况的话, 是O(N), 即在插入的元素里面, 大部分的值都冲突到一个位置, 被放到同一个桶里面.但是, 这种最坏的情况几乎不会出现.

因为我们插入的过程还会不断扩容, 而扩容的过程旧表的值重新散列到扩容之后的新表里面, 它的冲突值是会不断减少的, 另外我们的负载因子也在控制, 像我们上面设置负载因子为1, 平均情况就是每个哈希桶上面挂一个值再插入就要扩容了,所以如果按平均情况的话哈希表的查找就是O(1),是很快的.

随机数测试:

用大量随机值, 插入到哈希表里面, 然后我们可以观察一下插入这么多随机值以后, 哈希表里面所有的哈希桶中高度最高是多少, 如果它的高度能一直保存在一个比较低的水平, 那它的效率就一定是很高的.

在哈希表里添加一个成员函数打印bucket的相关参数:

void BucketSizes()
{
	size_t bucketSize = 0;
	size_t maxBucketLen = 0;
	size_t sum = 0;
	double averageBucketLen = 0;

	for (size_t i = 0; i < _table.size(); i++)
	{
		Node* cur = _table[i];
		if (cur)
		{
			++bucketSize;
		}

		size_t bucketLen = 0;
		while (cur)
		{
			++bucketLen;
			cur = cur->_next;
		}

		sum += bucketLen;

		if (bucketLen > maxBucketLen)
		{
			maxBucketLen = bucketLen;
		}
	}

	averageBucketLen = (double)sum / (double)bucketSize;

	printf("all bucketSize:%d\n", _table.size());
	printf("bucketSize:%d\n", bucketSize);
	printf("maxBucketLen:%d\n", maxBucketLen);
	printf("averageBucketLen:%lf\n\n", averageBucketLen);
}

void TestHT3()
{
	srand(time(nullptr));
	size_t N = 1000000;
	hash_bucket::HashTable<int, int> ht;
	for (int i = 0; i < N; i++)
	{
		size_t num = rand()+i;
		ht.insert(make_pair(num, num));
	}

	ht.BucketSizes();
}

可以看到最大桶的高度是2, 平均下来每个桶的长度是1.2, 查找起来是很快的.

如果现在就是出现了某种比较特殊,比较极端的场景, 使得哈希表里面某些桶比较长, 那我们可以如何解决呢？

首先我们可能会想到缩小负载因子, 这肯定能缓解一下.
然后这里有人提供这样一种思路:
就是如果真的出现了某个桶特别长, 那针对这个桶我们可以不用链表, 而改用挂红黑树去存储该桶里面的值, 即有的桶长度小就挂链表, 有的桶长度长, 就把里面的值放到红黑树里面挂上去(有的位置挂链表, 有的位置挂红黑树).

除留余数法最好模一个素数

有些书上提出, 用除留余数法的时候, 模一个素数是比较好的, SGI版本的STL里面就使用了这种方式.

如何每次快速取一个类似两倍关系的素数?

STL库中:

它其实就是给了一个现成的素数表, 每次扩容就从这里面选取一个比当前size大的数作为下一次的容量(第一次取53).而且我们的哈希表去扩容, 它是不会扩到大于这里的最大值的,因为42亿九千万个哈希桶的指针, 就是大约16G, 桶里还存放着数据, 那内存就更大了, 所以用不了这么大的哈希表.

可以添加一个类似的扩容:

初始化size和扩容的newsize也要修改:

代码:

HashTable.h

#pragma once
#include <map>
#include <vector>

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

template<>
struct kt<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash = hash * 31 + e;
		}
		//cout << key << ":" << hash << endl;
		return hash;
	}
};

namespace test
{
	enum Status
	{
		EMPTY,
		EXIST,
		DELETE
	};

	template<class K ,class V>
	struct HashData
	{
		pair<K, V> _data;
		Status _s  = EMPTY;
	};

	template<class K, class V, class KeyToInt = kt<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}

		bool insert(const pair<K,V>& kv)
		{
			if (Find(kv.first))
				return false;

			//扩容
			//判断负载因子是否超过0.7
			if (_n* 10/ _tables.size() >= 7)
			{
				//创建一个新表
				size_t newsize = _tables.size() * 2;
				HashTable<K, V,KeyToInt> newtable;
				newtable._tables.resize(newsize);

				for (int i = 0; i < _tables.size(); i++)
				{
					//旧表里的元素重新映射到新表里
					if (_tables[i]._s != EMPTY)
						newtable.insert(_tables[i]._data);
				}
				//交换新旧表
				swap(_tables, newtable._tables);
			}

			size_t hashi = KeyToInt()(kv.first) % _tables.size();
			while (_tables[hashi]._s == EXIST)
			{
				hashi++;
				hashi %= _tables.size();
			}

			_tables[hashi]._data = kv;
			_tables[hashi]._s = EXIST;
			_n++;
			return true;
		}

		HashData<K, V>* Find(const K& key)
		{
			size_t hashi = KeyToInt()(key) % _tables.size();
			size_t index = hashi;//index记录最开始的映射位置
			while (_tables[hashi]._s != EMPTY)
			{
				if (_tables[hashi]._s == EXIST && key == _tables[hashi]._data.first)
					return &_tables[hashi];
				hashi++;
				hashi %= _tables.size();
				//如果找了一圈回到初始位置就是查找失败
				if (hashi == index)
					return nullptr;
			}

			return nullptr;
		}

		bool Erase(const K& key)
		{
			HashData<K, V>* target = Find(key);

			if (!target)
				return false;
			else
			{
				target->_s = DELETE;
				_n--;
			}

		}

		void Print()
		{
			for (int i = 0; i < _tables.size(); i++)
			{
				if (_tables[i]._s == EXIST)
					cout << "[" << i << "]" << "->" << _tables[i]._data.first << ":" << _tables[i]._data.second << endl;
			}
		}
	private:
		vector<HashData<K,V>> _tables;
		size_t _n = 0; //表中有效元素的个数
	};
}

namespace hash_bucket
{
	template<class K,class V>
	struct HashNode
	{
		HashNode(const pair<K, V>& kv)
			:_data(kv)
			, _next(nullptr)
		{}
		
		pair<K, V> _data;
		HashNode<K, V>* _next;
	};

	template<class K, class V,class KeyToInt = kt<K>>
	class HashTable
	{
		
		inline unsigned long __stl_next_prime(unsigned long n)
		{
			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
			};

			for (size_t i = 0; i < __stl_num_primes; i++)
			{
				if (__stl_prime_list[i] > n)
					return __stl_prime_list[i];
			}
			return __stl_prime_list[__stl_num_primes-1];
		}

		typedef HashNode<K, V>  Node;
	public:
		HashTable()
		{
			//_table.resize(10);
			_table.resize(__stl_next_prime(0));//默认容量为素数表的第一个数
		}

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

		bool insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;

			//扩容
			/*if (_n == _table.size())
			{
				size_t newsize = _table.size() * 2;
				HashTable<K, V, KeyToInt> newtable;
				newtable._table.resize(newsize);

				size_t hashi = 0;
				while (hashi < _table.size())
				{
					Node* cur = _table[hashi];
					while (cur)
					{
						newtable.insert(cur->_data);
						cur = cur->_next;
					}
					hashi++;
				}
				_table.swap(newtable._table);
			}*/
			if (_n == _table.size())
			{
				//size_t newsize = _table.size() * 2;
				size_t newsize = __stl_next_prime(_table.size()); //扩容就找到素数表下一个素数
				HashTable<K, V, KeyToInt> newtable;
				newtable._table.resize(newsize,nullptr);

				for(size_t i = 0; i<_table.size();i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->_next;

						size_t hashi = KeyToInt()(cur->_data.first) % newsize;
						cur->_next = newtable._table[hashi];
						newtable._table[hashi] = cur;	

						cur = next;
					}
					_table[i] = nullptr; // 这一步很关键
				}

				swap(_table,newtable._table);
			}

			//头插
			size_t hashi = KeyToInt()(kv.first) % _table.size();
			Node* newnode = new Node(kv);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			_n++;
			return true;
		}

		Node* Find(const K& key)
		{
			size_t hashi = KeyToInt()(key) % _table.size();
			Node* cur = _table[hashi];
			while (cur)
			{
				if (cur->_data.first == key)
					return cur;
				else
					cur = cur->_next;
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			size_t hashi = KeyToInt()(key) % _table.size();
			Node* prev = nullptr;
			Node* cur = _table[hashi];

			while (cur)
			{
				if (cur->_data.first == key)
				{
					//头删
					if (prev == nullptr)
						_table[hashi] = cur->_next;
					//非头删
					else
						prev->_next = cur->_next;
					delete(cur);
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}

		void Print()
		{
			for (int i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					cout << "[" << i << "]" << "->" << cur->_data.first << ":" << cur->_data.second<<endl;
					cur = cur->_next;
				}
			}
		}

		void BucketSizes()
		{
			size_t bucketSize = 0;
			size_t maxBucketLen = 0;
			size_t sum = 0;
			double averageBucketLen = 0;

			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				if (cur)
				{
					++bucketSize;
				}

				size_t bucketLen = 0;
				while (cur)
				{
					++bucketLen;
					cur = cur->_next;
				}

				sum += bucketLen;

				if (bucketLen > maxBucketLen)
				{
					maxBucketLen = bucketLen;
				}
			}

			averageBucketLen = (double)sum / (double)bucketSize;

			printf("all bucketSize:%d\n", _table.size());
			printf("bucketSize:%d\n", bucketSize);
			printf("maxBucketLen:%d\n", maxBucketLen);
			printf("averageBucketLen:%lf\n\n", averageBucketLen);
		}
	private:
		vector<Node*> _table;
		size_t _n = 0;
	};
}

test.cpp

#include <iostream>
using namespace std;

#include "HashTable.h"
void TestHT1()
{
	hash_bucket::HashTable<int, int> ht;
	int a[] = { 1,4,5,6,7,9,34 };
	for (auto e : a)
	{
		ht.insert(make_pair(e, e));
	}

	ht.insert(make_pair(3, 3));
	ht.insert(make_pair(44, 44));
	ht.insert(make_pair(11, 11));
	//扩容
	ht.insert(make_pair(2, 2));

	//ht.Print();

	
	ht.Erase(3);
	ht.Print();
	
	if (ht.Find(3))
	{
		cout << "3存在" << endl;
	}
	else
	{
		cout << "3不存在" << endl;
	}
	/*
	ht.insert(make_pair(3, 3));
	ht.insert(make_pair(23, 3));
	ht.Print();*/
}

void TestHT2()
{
	string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
	//HashTable<string, int, HashFuncString> ht;
	hash_bucket::HashTable<string, int> ht;

	for (auto& e : arr)
	{
		//auto ret = ht.Find(e);
		hash_bucket::HashNode<string, int>* ret = ht.Find(e);
		if (ret)
		{
			ret->_data.second++;
		}
		else
		{
			ht.insert(make_pair(e, 1));
		}
	}

	ht.Print();

	/*ht.insert(make_pair("apple", 1));
	ht.insert(make_pair("sort", 1));

	ht.insert(make_pair("abc", 1));
	ht.insert(make_pair("acb", 1));
	ht.insert(make_pair("aad", 1));*/

	//ht.Print();
}

void TestHT3()
{
	srand(time(nullptr));
	size_t N = 1000000;
	hash_bucket::HashTable<int, int> ht;
	for (int i = 0; i < N; i++)
	{
		size_t num = rand()+i;
		ht.insert(make_pair(num, num));
	}

	ht.BucketSizes();
}

int main()
{
    //TestHT1();
	//TestHT2();
    TestHT3();
	return 0;
}