【C++---哈希表】哈希表的魅力，不仅在于其高效与便捷，更在于其背后所蕴含的深刻哲理。它告诉我们，即使面对再复杂、再混乱的世界，只要我们用心去寻找、去创造，总能找到一种方法，将其变得有序而美好。

id="article_content" class="article_content clearfix"> id="content_views" class="markdown_views prism-atom-one-dark">

class="toc">

哈希表

在这里插入图片描述

1 unordered_map和unordered_set的使⽤

在介绍哈希表之前，我们先了解下unordered_map和unordered_set

1.1 unordered_set和unordered_multiset参考⽂档

链接: 参考⽂档

1.2 unordered_set类的介绍

在这里插入图片描述

这里的unordered_set其实与set相似，只不过底层实现是不一样，还有其他特殊的不同.
不过他们大部分功能是相同的。
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2

unordered_set的声明如下，Key就是unordered_set底层关键字的类型

• unordered_set默认要求Key⽀持转换为整形，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现⽀持将Key转成整形的仿函数传给第⼆个模板参数

• unordered_set默认要求Key⽀持⽐较相等，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现⽀持将Key⽐较相等的仿函数传给第三个模板参数

• unordered_set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给第四个参数。

• ⼀般情况下，我们都不需要传后三个模板参数

• unordered_set底层是⽤哈希桶实现，增删查平均效率是 ，迭代器遍历不再有序，为了跟set区分，所以取名unordered_set。O(1)

• 前⾯部分我们已经学习了set容器的使⽤，set和unordered_set的功能⾼度相似，只是底层结构不同，有⼀些性能和使⽤的差异.

template < class Key, //
unordered_set::key_type/value_type
class Hash = hash<Key>, // unordered_set::hasher，支持key转型为无符号整型
class Pred = equal_to<Key>, // unordered_set::key_equal，支持key相等
class Alloc = allocator<Key> // unordered_set::allocator_type

> class unordered_set;
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

1.3unordered_set和set的差异

• 查看⽂档我们会发现unordered_set的⽀持增删查且跟set的使⽤⼀模⼀样，关于使⽤我们这⾥就不再赘述和演⽰了。

• unordered_set和set的第⼀个差异是对key的要求不同，set要求Key⽀持⼩于⽐较，⽽unordered_set要求Key⽀持转成整形且⽀持等于⽐较，要理解unordered_set的这个两点要求得后续我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。

•unordered_set和set的第⼆个差异是迭代器的差异，set的iterator是双向迭代器，unordered_set是单向迭代器，其次set底层是红⿊树，红⿊树是⼆叉搜索树，⾛中序遍历是有序的，所以set迭代器遍历是有序+去重。⽽unordered_set底层是哈希表，迭代器遍历是⽆序+去重。

•unordered_set和set的第三个差异是性能的差异，整体⽽⾔⼤多数场景下，unordered_set的增删查改更快⼀些，因为红⿊树增删查改效率是
,⽽哈希表增删查平均效率是 ，具体可以参看下⾯代码的演⽰的对⽐差异。

在这里插入图片描述

#include
#include
#include
using namespace std;
int test_set2()
{
	const size_t N = 1000000;
	unordered_set<int> us;
	set<int> s;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; ++i)
	{
		//v.push_back(rand()); // N⽐较⼤时，重复值⽐较多
		v.push_back(rand() + i); // 重复值相对少
		//v.push_back(i); // 没有重复，有序
	}
	// 21:15
	size_t begin1 = clock();
	for (auto e : v)
	{
		s.insert(e);
	}
	size_t end1 = clock();
	cout << "set insert:" << end1 - begin1 << endl;
		size_t begin2 = clock();
	us.reserve(N);
	for (auto e : v)
	{
		us.insert(e);
	}
	size_t end2 = clock();
	cout << "unordered_set insert:" << end2 - begin2 << endl; 
	int m1 = 0;
	size_t begin3 = clock();
	for (auto e : v)
	{
		auto ret = s.find(e);
		if (ret != s.end())
		{
			++m1;
		}
	}
	size_t end3 = clock();
	cout << "set find:" << end3 - begin3 << "->" << m1 << endl;
	int m2 = 0;
	size_t begin4 = clock();
	for (auto e : v)
	{
		auto ret = us.find(e);
		if (ret != us.end())
		{
			++m2;
		}
	}
	size_t end4 = clock();
	cout << "unorered_set find:" << end4 - begin4 << "->" << m2 << endl;
	cout << "insert数据个数：" << s.size() << endl;
	cout << "insert数据个数：" << us.size() << endl << endl;
	size_t begin5 = clock();
	for (auto e : v)
	{
		s.erase(e);
	}
	size_t end5 = clock();
	cout << "set erase:" << end5 - begin5 << endl;
	size_t begin6 = clock();
		for (auto e : v)
		{
			us.erase(e);
		}
	size_t end6 = clock();
	cout << "unordered_set erase:" << end6 - begin6 << endl << endl;
	return 0;
}
int main()
{
	test_set2();
	return 0;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
class="hide-preCode-box">

1.4 unordered_map和map的使⽤差异

• 查看⽂档我们会发现unordered_map的⽀持增删查改且跟map的使⽤⼀模⼀样，关于使⽤我们这⾥就不再赘述和演⽰了。

•unordered_map和map的第⼀个差异是对key的要求不同，map要求Key⽀持⼩于⽐较，⽽unordered_map要求Key⽀持转成整形且⽀持等于⽐较，要理解unordered_map的这个两点要求得后续我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。

•unordered_map和map的第⼆个差异是迭代器的差异，map的iterator是双向迭代器，unordered_map是单向迭代器，其次map底层是红⿊树，红⿊树是⼆叉搜索树，⾛中序遍历是有序的，所以map迭代器遍历是Key有序+去重。⽽unordered_map底层是哈希表，迭代器遍历是Key⽆序+去重。

•unordered_map和map的第三个差异是性能的差异，整体⽽⾔⼤多数场景下，unordered_map的增删查改更快⼀些，因为红⿊树增删查改效率是，⽽哈希表增删查平均效率是 ，具体可以参看下⾯代码的演⽰的对⽐差异。

2 哈希表实现

有上面可以得知,unordered_set、unordered_map底层是哈希表实现的，我们不禁好奇，哈希表是怎么样的呢？哈希表是怎么样实现O(1)的效率的呢？为什么会无序呢？

2.1 哈希概念

哈希(hash)⼜称散列，是⼀种组织数据的⽅式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建⽴⼀个映射关系，查找时通过这个哈希函数计算出Key存储的位置，进⾏快速查找。

2.2 直接定址法

当关键字的范围⽐较集中时，直接定址法就是⾮常简单⾼效的⽅法，⽐如⼀组关键字都在[0,99]之间，那么我们开⼀个100个数的数组，每个关键字的值直接就是存储位置的下标。再⽐如⼀组关键字值都在[a,z]的⼩写字⺟，那么我们开⼀个26个数的数组，每个关键字acsii码-a ascii码就是存储位置的下标。也就是说直接定址法本质就是⽤关键字计算出⼀个绝对位置或者相对位置。这个⽅法我们在计数排序部分已经⽤过了，其次在string章节的下⾯OJ也⽤过了。

直接定址法：
这种方法高效，简单
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

字符串中的第一个唯一字符

class Solution {
public:
int firstUniqChar(string s) {
// 每个字⺟的ascii码-'a'的ascii码作为下标映射到count数组，数组中存储出现的次数
int count[26] = {0};
// 统计次数
  for(auto ch : s)
  {
  count[ch-'a']++;
  }
  for(size_t i = 0; i < s.size(); ++i)
  {
  if(count[s[i]-'a'] == 1)
  return i;
  }
  return -1;
 }
 };
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">

总结：直接定地址法：是最简洁、最高效的哈希，但是也有限制条件:数据要集中。 如果数据离散那么就会导致空间利用率低、关键字范围限制、机动性差

2.3 哈希冲突

哈希冲突体现了直接定址法的弊端：

直接定址法的缺点也⾮常明显，当关键字的范围⽐较分散时，就很浪费内存甚⾄内存不够⽤。假设我们只有数据范围是[0, 9999]的N个值，我们要映射到⼀个M个空间的数组中(⼀般情况下M >= N)，那么就要借助哈希函数(hashfunction)hf，关键字key被放到数组的h(key)位置，这⾥要注意的是h(key)计算出的值必须在[0, M)之间。这⾥存在的⼀个问题就是，两个不同的key可能会映射到同⼀个位置去，这种问题我们叫做哈希冲突，或者哈希碰撞。理想情况是找出⼀个好的哈希函数避免冲突，但是实际场景中，冲突是不可避免的，所以我们尽可能设计出优秀的哈希函数，减少冲突的次数，同时也要去设计出决冲突的⽅案。

总结：在哈希表中避免不了哈希映射，为了解决或适应哈希冲突，人们要去设计出减缓哈希冲突或适应哈希冲突的方案。

2.4 负载因子

假设哈希表中已经映射存储了N个值，哈希表的⼤⼩为M，那么 ，负载因⼦有些地⽅也翻译为载荷因⼦/装载因⼦等，他的英⽂为load factor。负载因⼦越⼤，哈希冲突的概率越⾼，空间利⽤率越⾼；负载因⼦越⼩，哈希冲突的概率越低，空间利⽤率越低；

2.5 将关键字转为整数

我们将关键字映射到数组中位置，⼀般是整数好做映射计算，如果不是整数，我们要想办法转换成整数，这个细节我们后⾯代码实现中再进⾏细节展⽰。下⾯哈希函数部分我们讨论时，如果关键字不是整数，那么我们讨论的Key是关键字转换成的整数。

【注意】
这是对哈希的数据类型Key值的要求如下：
要求1：Key值要由string、float、double------>无符号整形
要求2：Key值要支持比较相等

2.6 哈希函数

⼀个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中，但是实际中却很难做到，但是我们要尽量往这个⽅向去考量设计.

【说明】
哈希函数功能：
映射对应数据的位置，以方便在哈希表中存储,减少哈希冲突

2.6.1 哈希函数之除法散列法

• 除法散列法也叫做除留余数法，顾名思义，假设哈希表的⼤⼩为M，那么通过key除以M的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。

•当使⽤除法散列法时，要尽量避免M为某些值，如2的冥，10的冥等。如果是 ，那么key %2^x本质相当于保留key的后X位，那么后x位相同的值，计算出的哈希值都是⼀样的，就冲突了。如：{63 , 31}看起来没有关联的值，如果M是16，也就是 ，那么计算出的哈希值都是15，因为63的⼆进制后8位是 00111111，31的⼆进制后8位是 00011111。如果是 ，就更明显了，保留的都是10进值的后x位，如：{112, 12312}，如果M是100，也就是 ，那么计算出的哈希值都是12。

•当使⽤除法散列法时，建议M取不太接近2的整数次冥的⼀个质数(素数)。

出了除法散列之外还有许多的哈希函数，这提一下:
乘法散列法

• 乘法散列法对哈希表⼤⼩M没有要求，他的⼤思路第⼀步：⽤关键字 K 乘上常数 A (0A 的⼩数部分。第⼆步：后再⽤M乘以kA 的⼩数部分，再向下取整。

• h(key) = floor(M × ((A × key)%1.0))，其中floor表⽰对表达式进⾏下取整，A∈(0,1)，这⾥ 最重要的是A的值应该如何设定，Knuth认为 (⻩⾦分割点]) ⽐较好。 h(key) = floor(M × ((A ×key)%1.0)) A = ( 5 − 1)/2 = 0.6180339887…

• 乘法散列法对哈希表⼤⼩M是没有要求的，假设M为1024，key为1234，A = 0.6180339887, Akey = 762.6539420558，取⼩数部分为0.6539420558, M×((A×key)%1.0) = 0.65394205581024 =669.6366651392，那么h(1234) = 669。

2.7 哈希的防御措施

全域散列法

• 如果存在⼀个恶意的对⼿，他针对我们提供的散列函数，特意构造出⼀个发⽣严重冲突的数据集，⽐如，让所有关键字全部落⼊同⼀个位置中。这种情况是可以存在的，只要散列函数是公开且确定的，就可以实现此攻击。解决⽅法⾃然是⻅招拆招，给散列函数增加随机性，攻击者就⽆法找出确定可以导致最坏情况的数据。这种⽅法叫做全域散列。

解决方案

• 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, 则 h34 (8) = ((3 × 8 + 4)%17)%6 = 5*

• 需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的⼀个散列函数使⽤，后续增删查改都固定使⽤这个散列函数，否则每次哈希都是随机选⼀个散列函数，那么插⼊是⼀个散列函数，查找⼜是另⼀个散列函数，就会导致找不到插⼊的key了。

2.8 开放定址法

在开放定址法中所有的元素都放到哈希表⾥，当⼀个关键字key⽤哈希函数计算出的位置冲突了，则按照某种规则找到⼀个没有存储数据的位置进⾏存储，开放定址法中负载因⼦⼀定是⼩于的。这⾥的规则有三种：线性探测、⼆次探测、双重探测。

线性探测

• 从发⽣冲突的位置开始，依次线性向后探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果⾛到哈希表尾，则回绕到哈希表头的位置。

•h(key) = hash0 = key % M, hash0位置冲突了，则线性探测公式为： hc(key,i) = hashi =(hash0 + i) % M， i = {1, 2, 3, …, M −1}，因为负载因⼦⼩于1，则最多探测M-1次，⼀定能找到⼀个存储key的位置。

•线性探测的⽐较简单且容易实现，线性探测的问题假设，hash0位置连续冲突，hash0，hash1，hash2位置已经存储数据了，后续映射到hash0，hash1，hash2，hash3的值都会争夺hash3位置，这种现象叫做群集/堆积。下⾯的⼆次探测可以⼀定程度改善这个问题。

• 下⾯演⽰ {19,30,5,36,13,20,21,12} 等这⼀组值映射到M=11的表中。

h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) =10，h(12) = 1
在这里插入图片描述

⼆次探测

• 从发⽣冲突的位置开始，依次左右按⼆次⽅跳跃式探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果往右⾛到哈希表尾，则回绕到哈希表头的位置；如果往左⾛到哈希表头，则回绕到哈希表 尾的位置；

• h(key) = hash0 = key % M , hash0位置冲突了，则⼆次探测公式为： hc(key,i) = hashi = (hash0 ± i2 ) % M，i = {1, 2, 3, …, 2/M}

• ⼆次探测当 hashi = (hash0 − i2)%M时，当hashi<0时，需要hashi += M • 下⾯演⽰ {19,30,52,63,11,22} 等这⼀组值映射到M=11的表中。

2.8.1 开放定址法代码实现

开放定址法在实践中，不如下⾯讲的链地址法，因为开放定址法解决冲突不管使⽤哪种⽅法，占⽤的
都是哈希表中的空间，始终存在互相影响的问题。所以开放定址法，我们简单选择线性探测实现即 可。

开放定址法的哈希表结构

enum State
{
EXIST,
EMPTY,
DELETE
};
template<class K, class V>
struct HashData
 {
   pair<K, V> _kv;
   State _state = EMPTY;
 };

 template<class K, class V>
 class HashTable
 {
 private:
 vector<HashData<K, V>> _tables;
 size_t _n = 0; // 表中存储数据个数
 };

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">

要注意的是这⾥需要给每个存储值的位置加⼀个状态标识，否则删除⼀些值以后，会影响后⾯冲突的
值的查找。如下图，我们删除30，会导致查找20失败，当我们给每个位置加⼀个状态标识
{EXIST,EMPTY,DELETE} ，删除30就可以不⽤删除值，⽽是把状态改为 DELETE ，那么查找20
时是遇到 EMPTY 才能，就可以找到20。

扩容
这⾥我们哈希表负载因⼦控制在0.7，当负载因⼦到0.7以后我们就需要扩容了，我们还是按照2倍扩
容，但是同时我们要保持哈希表⼤⼩是⼀个质数，第⼀个是质数，2倍后就不是质数了。那么如何解决
了，⼀种⽅案就是上⾯1.4.1除法散列中我们讲的Java HashMap的使⽤2的整数冥，但是计算时不能直
接取模的改进⽅法。另外⼀种⽅案是sgi版本的哈希表使⽤的⽅法，给了⼀个近似2倍的质数表，每次去
质数表获取扩容后的⼤⼩。

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;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">

Key不能取模的问题

当key是string/Date等类型时，key不能取模，那么我们需要给HashTable增加⼀个仿函数，这个仿函
数⽀持把key转换成⼀个可以取模的整形，如果key可以转换为整形并且不容易冲突，那么这个仿函数
就⽤默认参数即可，如果这个Key不能转换为整形，我们就需要⾃⼰实现⼀个仿函数传给这个参数，实
现这个仿函数的要求就是尽量key的每值都参与到计算中，让不同的key转换出的整形值不同。string
做哈希表的key⾮常常⻅，所以我们可以考虑把string特化⼀下。

//如果要支持Key的比较,那么就需要仿函数来实现，如string 映射,在映射到哈希表中
//默认的哈希仿函数，float，负数，转为无符号整形
template<class K>
struct Hashturn
{
	size_t operator()(const K& key)
	{
		return (size_t)key;

	}
};

//如果是sring类型，那么我们就可以单独的给string，建立一个仿函数实现第一层映射
//走特化
template<>
struct Hashturn<string>
{
	size_t operator()(const string& key)
	{
		size_t m = 0;
		//把ASCALL码值加起来
		for (auto& e : key)
		{
			//用ASCALL来实现，字符转数字
			m += e;
		}
		return m;
	}
};
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">

完整代码:

enum State
{
	EXIST,
	EMPTY,
	DELETE
};

//哈希结点
template<class K,class V>
struct HashData
{
	pair<K, V> _kv;
	State _state= EMPTY;  
};


//如果要支持Key的比较,那么就需要仿函数来实现，如string 映射,在映射到哈希表中
//默认的哈希仿函数，float，负数，转为无符号整形
template<class K>
struct Hashturn
{
	size_t operator()(const K& key)
	{
		return (size_t)key;

	}
};

//如果是sring类型，那么我们就可以单独的给string，建立一个仿函数实现第一层映射
//走特化
template<>
struct Hashturn<string>
{
	size_t operator()(const string& key)
	{
		size_t m = 0;
		//把ASCALL码值加起来
		for (auto& e : key)
		{
			//用ASCALL来实现，字符转数字
			m += e;
		}
		return m; 
	}
};


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;
}



//哈希表
template<class K,class V,class Hashturn=Hashturn<K>>
class HashTable
{
public:
	HashTable()
		:_tables(__stl_next_prime(0)) 
		,_n(0)
	{}

	Hashturn con;
	bool insert(const pair<K,V>& kv)
	{

		if (Find(kv.first))
		{
			return false;
		}
		//如果空间被占满了那么程序会陷入死循环中
		//那么负载因子就有了作用
		//我们规定当负载因子大于0.7时就扩容
		//负载因子= _n/_tables.size()
		if (_n * 10 / _tables.size() >= 7)
		{
			HashTable<K, V,Hashturn> newht; 
			newht._tables.resize(__stl_next_prime(_tables.size()+1));//假设扩容2倍  
			for (auto& e : _tables) 
			{
				if (e._state == EXIST)//把_tables的存在数据重新映射给newht
				{
					newht.insert(e._kv);   
				}
			}
			_tables.swap(newht._tables);

		}
		size_t Hash0 = con(kv.first) % _tables.size(); 
		size_t Hashi = Hash0; 
		size_t i = 1;
		while (_tables[Hashi]._state == EXIST)//存在就要线性探测
		{
			//线性探测
			Hashi = (Hash0 + i) % _tables.size();
			i++; 
			//二次探测
			/*hashi = (hash0 + (i*i*flag)) % _tables.size();
			if (hashi < _tables.size())
				hashi += _tables.size();

			if (flag == 1)
			{
				flag = -1;
			}
			else
			{
				++i;
				flag = 1;
			}*/
		}
		_tables[Hashi]._kv = kv;    
		_tables[Hashi]._state = EXIST;
		++_n;
		return true;

	}

	HashData<K, V>* Find(const K& key)
	{
		size_t Hash0 = con(key) % _tables.size();
		size_t Hashi = Hash0;
		size_t i = 1;
		while (_tables[Hashi]._state != EMPTY)
		{
			if (_tables[Hashi]._state!=DELETE && _tables[Hashi]._kv.first == key)
			{
				return &_tables[Hashi]; 
			}
			Hashi = (Hash0 + i) % _tables.size(); 
			i++; 
		}
		return nullptr;
	}


	bool erase(const K& key)
	{
		HashData<K, V>* ret = Find(key);
		if (ret == nullptr)
		{
			return false;
		}
		else
		{
			ret->_state = DELETE; 

			return true;
		}
	}
private:
	vector<HashData<K, V>> _tables; 
	size_t _n;
};

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">

2.9 链地址法

开放定址法中所有的元素都放到哈希表⾥，链地址法中所有的数据不再直接存储在哈希表中，哈希表
中存储⼀个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把
这些冲突的数据链接成⼀个链表，挂在哈希表这个位置下⾯，链地址法也叫做拉链法或者哈希桶。

链地址法代码实现

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;
}
template<class T>
struct Buket_Node
{
	T _data;
	Buket_Node<T>* _next; 

	Buket_Node(const T& data) 
		:_data(data) 
		,_next(nullptr) 
	{}
}; 
//如果要支持Key的比较,那么就需要仿函数来实现，如string 映射,在映射到哈希表中
//默认的哈希仿函数，float，负数，转为无符号整形
template<class K>
struct Hashturn
{
	size_t operator()(const K& key)
	{
		return (size_t)key;

	}
};

//如果是sring类型，那么我们就可以单独的给string，建立一个仿函数实现第一层映射
//走特化
template<>
struct Hashturn<string>
{
	size_t operator()(const string& key)
	{
		size_t m = 0;
		//把ASCALL码值加起来
		for (auto& e : key)
		{
			//用ASCALL来实现，字符转数字
			m += e;
		}
		return m;
	}
};

template<class K, class T, class KeyofT, class Hashturn> 
class hash_bucket;


template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
struct Hash_Iterator
{
	typedef Buket_Node<T> Node; 
	typedef hash_bucket<K, T, KeyOfT, Hash> HT;
	typedef Hash_Iterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;

	Node* _node;
	const HT* _ht;

	Hash_Iterator(Node* node, const HT* ht)
		:_node(node)
		, _ht(ht)
	{}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}

	// 16:46
	Self& operator++()
	{
		if (_node->_next)
		{
			// 当前桶还有数据，走到当前桶下一个节点
			_node = _node->_next;
		}
		else
		{
			// 当前桶走完了，找下一个不为空的桶
			KeyOfT kot;
			Hash hash;
			size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
			++hashi;
			while (hashi < _ht->_tables.size())
			{
				_node = _ht->_tables[hashi];

				if (_node)
					break;
				else
					++hashi;
			}

			// 所有桶都走完了，end()给的空标识的_node
			if (hashi == _ht->_tables.size())
			{
				_node = nullptr;
			}
		}

		return *this;
	}

};



template<class K,class T,class KeyofT,class Hashturn> 
class hash_bucket
{
	template<class K, class T, class ref, class ptr, class KeyofT, class Hashturn>
	friend struct  Hash_Iterator;
	typedef Buket_Node<T> Node;
public:
	typedef  Hash_Iterator<K, T, T&, T*, KeyofT, Hashturn> Iterator;
	typedef Hash_Iterator<K, T, const T&, const T*, KeyofT, Hashturn> Const_Iterator;
	//Iterator begin()
	//{
	//	if()
	//	for (int i = 0;i < _tables.size();i++)
	//	{
	//		Node* cur = _tables[i];
	//		if (cur)
	//		{
	//			return Iterator(cur, this);
	//		}
	//	}
	//}

	hash_bucket()
		:_n(0)
		, _tables(__stl_next_prime(0))
	{}
	~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;
   }
}

	Iterator begin()
	{
		if (_n == 0)
		{
			return Iterator(nullptr, this);
		}
		for (int i = 0;i < _tables.size();i++)
		{
			Node* cur = _tables[i];
			if (cur)
			{
				return Iterator(cur, this);
			}
		}
	}
	Iterator end()
	{
		return Iterator(nullptr, this);
	}

	Const_Iterator end() const
	{
		return Const_Iterator(nullptr, this);
	}

	Const_Iterator begin()const
	{
		if (_n == 0)
		{
			return Const_Iterator(nullptr, this);
		}
		for (int i = 0;i < _tables.size();i++)
		{
			Node* cur = _tables[i];
			if (cur)
				return Const_Iterator(cur, this);
		}
	}
	pair<Iterator, bool> insert(const T& data)
	{

		KeyofT kot;
		Hashturn hash;
		//判断负载因子 
		if (1 == (_n / _tables.size()))
		{
			Iterator it = Find(kot(data));
			if (it != end())
				return { it, false };
			vector<Node*> newtables(__stl_next_prime(_tables.size() + 1));
			for (int i = 0;i < _tables.size();i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					//头插
					size_t hashi = hash(kot(cur->_data)) % newtables.size();

					cur->_next = newtables[hashi];
					newtables[hashi] = cur;

					cur = next;

				}
				_tables[i] = nullptr;
			}
			_tables.swap(newtables);
		}

		size_t hashi = hash(kot(data)) % _tables.size();
		// 头插
		Node* newnode = new Node(data);
		newnode->_next = _tables[hashi];
		_tables[hashi] = newnode;
		++_n;

		return { Iterator(newnode, this), false };

	}


	Iterator Find(const K& key)
	{
		KeyofT kot;
		Hashturn hash;
		size_t hashi = hash(key) % _tables.size();
		Node* cur = _tables[hashi];
		while (cur)
		{
			if (kot(cur->_data) == key)
			{
				return Iterator(cur, this);
			}
		}
		return Iterator(nullptr, this);
	}

	bool erase(const K& key)
	{
		KeyofT kot;
		Hashturn hash;
		Node* prev = nullptr;
		size_t hashi = hash(key) % _tables.size();
		Node* cur = _tables[hashi];

		while (cur)
		{
			if (kot(cur->_data) == key)
			{
				if (prev)
				{
					//prev不为空
					prev->_next = cur->_next;
				}
				else
				{
					//prev为空
					_tables[hashi] = prev;
				}
				delete cur;
				_n--;

				return true;
			}
			else
			{
				prev = cur;
				cur = cur->_next;
			}
		}
		return false;
	}
private:
	size_t _n = 0;
	vector<Node*> _tables;
};
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">

再见，并非终点，而是另一段旅程的起点。愿我们在各自的旅途中，都能遇见更美的风景，书写更加精彩的人生篇章！！！

data-report-view="{"mod":"1585297308_001","spm":"1001.2101.3001.6548","dest":"https://blog.csdn.net/2301_80109683/article/details/145352601","extend1":"pc","ab":"new"}">>
注：本文转载自blog.csdn.net的sdzdwa的文章"https://blog.csdn.net/2301_80109683/article/details/145352601"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！