【C++】哈希

梦里梦外; 2024-04-27 07:34 8阅读 0赞

#### 文章目录 ####

*  一、unordered系列关联式容器
 *   *  1. unordered\_map
     *  2. unordered\_set
     *  3. 在线OJ练习
     *   *  在长度为2N的数组中找出重复N次的元素
         *  两个数组的交集
         *  两个数组的交集II
 *  二、哈希表的底层结构
 *   *  1. 哈希概念
     *  2. 哈希函数
 *  三、哈希表的模拟实现（闭散列）
 *   *  1. 线性探测法
     *  2. 基本框架
     *  3. 哈希表的插入删除与查找
     *  4. 哈希表的仿函数
     *  5. 字符串哈希算法
     *  6. 整体代码实现

--------------------

## 一、unordered系列关联式容器 ##

> 在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 l o g 2 N log\_2 N log2N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。unordered系列的容器的底层结构是哈希桶。也就是我们后面要讲的拉链法封装实现的哈希表。`unordered_set`的桶中节点存储的是一个key值，`unordered_map`的桶中节点存储的是一个键值对。

--------------------

### 1. unordered\_map ###

> 1.  unordered\_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
> 2.  在unordered\_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
> 3.  在内部,unordered\_map没有对`<kye, value>`按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered\_map将相同哈希值的键值对放在相同的桶中 — 哈希冲突。
> 4.  unordered\_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
> 5.  unordered\_map实现了直接访问操作符(`operator[]`)，它允许使用key作为参数直接访问value。
> 6.  unordered\_map的迭代器是单向迭代器。

**构造**

![在这里插入图片描述][c212b90e77d24d12ac9e1255771fdfb8.png]

**capacity**

![在这里插入图片描述][1eebb40a43bd41f2963027ab6cd920bd.png]

**Iterator**

unordered\_map的迭代器是单向迭代器，因为unordered\_map底层是开散列的哈希表，开散列的哈希表的哈希桶是单链表。单链表只支持`++`，不支持 `--`。这里我们需要注意的是：哈希桶可能是红黑树或者其他结构，不一定是单链表。

**\[ \]的重载**

和map一样，unordered\_map的`[]`同样兼具插入、查找和修改的功能。

**Modifiers**

![在这里插入图片描述][d280b0ecae3341f292c05065a5511500.png]

**Hash policy**

![在这里插入图片描述][49ebf328a47d47bfa4d4dcf5016a56b9.png]

我们在模拟实现哈希表的时候提到闭散列的哈希表一般在平衡因子达到 0.7 时就需要进行扩容，否则发生哈希冲突的概率太大，影响效率；而开散列的哈希表一般将平衡因子控制在 1，这样大部分元素只需要查找 0~2 次就能够找到；

unordered\_map 也提供了一系列与 平衡因子相关的函数，其中 `load_factor` 是获取当前平衡因子，`max_load_factor` 是最大平衡因子，也就是什么时候扩容，需要注意的是 `max_load_factor` 中提供了两个函数，一个用于获取最大平衡因子，一个用于设置最大平衡因子，即用户可以通过 `max_load_factor` 函数根据自己的业务场景来设定最大平衡因子；其中 `unordered_map` 中的默认最大平衡因子也是 1。

--------------------

### 2. unordered\_set ###

`unordered_set` 和 `unordered_map` 的区别再于 unordered\_set 是 `K模型` 的容器，而 unordered\_map 是 `KV模型` 的容器，虽然二者底层都是开散列的哈希表，但是哈希表中每个节点的 data 的类型是不同的 – unordered\_set 是key，而 unordered\_map 是 `KV 构成的键值对`，只是 哈希表 通过 KeyOfT 仿函数使得自己能够兼容 K模型 的 unordered\_set 和 KV模型 的 unordered\_map 而已。

>  *  unordered\_set 的查询效率是O(1)。
>  *  unordered\_set遍历得到序列的元素顺序是不确定的。
>  *  unordered\_set 的底层结构为开散列的哈希表。
>  *  unordered\_set 对key的要求是能能够转换为整形。

这里我们需要注意的是：unordered\_set 不需要修改value，所以不支持operator\[\]函数。想要详细了解的可以参考文档[【unordered\_set】][unordered_set]

--------------------

### 3. 在线OJ练习 ###

#### [在长度为2N的数组中找出重复N次的元素][2N_N] ####

> ![在这里插入图片描述][ee47676f11cc4cd38d309100ce3516aa.png]

class Solution {
        
    public:
        int repeatedNTimes(vector<int>& nums) {
        
            size_t N = nums.size() / 2;
            // 用unordered_map统计每个元素出现的次数
            unordered_map<int, int> m;
            for(auto e : nums)
                m[e]++;
            // 找出出现次数为N的元素
            for(auto& e : m)
            {
        
                if(e.second == N)
                return e.first;
            }
            return -1;
        }
    };

--------------------

#### [两个数组的交集][Link 1] ####

> ![在这里插入图片描述][84e905d07e0a4328bd2f9d2ef4c7479d.png]

class Solution {
        
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        
            // 用unordered_set对nums1中的元素去重
            unordered_set<int> s1;
            for (auto e : nums1)
            s1.insert(e);
            
            // 用unordered_set对nums2中的元素去重
            unordered_set<int> s2;
            for (auto e : nums2)
            s2.insert(e);
    
            // 遍历s1，如果s1中某个元素在s2中出现过，即为交集
            vector<int> vRet;
            for (auto e : s1)
            {
        
                if (s2.find(e) != s2.end())
                vRet.push_back(e);
            }
    
            return vRet;
        }
    };

--------------------

#### [两个数组的交集II][II] ####

> ![在这里插入图片描述][38714c2603c945f7b4b3e49ad1193b8b.png]

class Solution {
        
    public:
        vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        
            if (nums1.size() > nums2.size()) {
        
                return intersect(nums2, nums1);
            }
            unordered_map <int, int> m;
            for (int num : nums1) {
        
                ++m[num];
            }
            vector<int> intersection;
            for (int num : nums2) {
        
                if (m.count(num)) {
        
                    intersection.push_back(num);
                    --m[num];
                    if (m[num] == 0) {
        
                        m.erase(num);
                    }
                }
            }
            return intersection;
        }
    };

--------------------

## 二、哈希表的底层结构 ##

### 1. 哈希概念 ###

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

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

当向该结构中：

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

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

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

![在这里插入图片描述][2c490bc1538f4a44baa1ce9d3352daad.png]

--------------------

### 2. 哈希函数 ###

💕 **直接定址法(常用)**

直接定址法的优点是简单，且不会引起哈希冲突 – 哈希冲突是指多个不同的 key 值映射到同一个存储位置，由于直接定址法的 key 值经过哈希函数转换后得到的值一定是唯一的，所以不存在哈希冲突。

直接定址法适用于数据范围集中的情况，这样 key 值映射到哈希表后，哈希表的空间利用率高，浪费的空间较少；如下：

![在这里插入图片描述][2f9e684fe57545fca58f8b7c3596e73e.png]

但直接定址法不适用于数据范围分散的情况，因为这样会导致哈希表的空间利用率很低，从而导致空间的浪费。例如：`arr[] = { 123, 126, 125, 138, 122331, 1};`

💕 **除留余数法(常用)**

为了应对数据范围分散的情况，有人设计出了除留余数法 – 设哈希表中允许的地址数为m，取一个不大于m，但最接近或者等于m的素数p作为除数，按照 哈希函数 `Hash(key) = key % p (p<=m)`, 将关键码转换成哈希地址；

简单来说就是用 key 值除以哈希表的大小得到的余数作为哈希映射的地址，将 key 保存到该地址中；除留余数的优点是可以处理数据范围分散的数据，缺点是会引发哈希冲突；例如对于数据集合 \{1，7，6，4，5，9\}，它的哈希表如下：

![在这里插入图片描述][5d2899687a904666b981cd30875c8478.png]

但是当我们再插入一个元素44时，通过哈希函数我们计算出44应该存储在下标为4的位置，但是下标为4的位置已经被元素4占用了，所以此时就会发生哈希冲突。

💕 **平方取中法 (了解)**

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址。平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况。

💕 **折叠法 (了解)**

折叠法是将关键字从左到右分割成位数相等的几部分 (最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况。

💕 **随机数法 (了解)**

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即 H(key) = random(key), 其中 random 为随机数函数。随机数法通常应用于关键字长度不等的情况。

💕 **数学分析法 (了解)**

设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。

假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现冲突，还可以对抽取出来的数字进行反转 (如1234改成4321)、右环位移 (如1234改成4123)、左环移位、前两数与后两数叠加 (如1234改成12+34=46) 等方法。

![在这里插入图片描述][ac46ae7d1f354552b62c7a87e72142b7.jpeg]

数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况。

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

--------------------

## 三、哈希表的模拟实现（闭散列） ##

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

### 1. 线性探测法 ###

线性探测法是指从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止，比如上面的例子：现在需要插入元素44，先通过哈希函数计算哈希地址，计算出的哈希地址是4，虽说44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。因此我们可以向后寻找第一个空位置即下标为8的位置进行插入：

![在这里插入图片描述][ea712442cbd14a73a89d9bc6bd3a5e85.png]

--------------------

### 2. 基本框架 ###

enum State
    {
        
    	EMPTY,
    	EXIST,
    	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;  //存储的数据个数
    };

在哈希表中我们使用vector来存储数据，并增加了一个变量n来记录表中有效数据的个数，同时，哈希表的每个下标位置存储的数据都是一个`K-V`模型的键值对，这里我们需要重点关注的是哈希表中还需要一个state变量来记录该位置的状态，这是什么原因呢？

这里我们来举一个例子说明，假设我们现在要将arr映射到哈希表中，设哈希表的大小为10，则哈希函数为：

> **int arr\[\] = \{ 18, 8, 7, 27, 57, 3, 38 \};**  
> **`hash(key) = key % HashTable.size()`**

![在这里插入图片描述][59e3e3ac20894405894e96e493876b2c.png]

当key映射的下标位置被占用时，key会向后寻找下一个空位置进行插入，但如果key走到数组尾都还没找到空位置，那么key就会从数组起始位置重新往后寻找。比如插入27时由于7、8、9位置都被占用，所以它只能从数组起始位置重新寻找空位置插入。

**但是如果这里我们需要一个需求，那就是将27删除掉然后再插入17呢？**

>  *  27如何删除，即我们应该将27原来位置的数据置为几？貌似这里置为几都不合适，因为你要删除的数据可能和你用于标识删除状态的数字恰好相同 (比如删除后将对应位置的数据置为0/-1，但是key也有可能等于0/-1，此时是删了还是没删呢？；
>  *  删除后我们再插入17，此时17按道理来说应该插入到27原来的位置，因为此时27已经被删除，0号下标的位置就空出来了；但是17如何知道0号下标位置是空的呢？-- 我们上面说了27删除后该位置的数据被置为几都不合适；

所以，在哈希表的每个位置的数据中还增加了一个state变量来记录该位置的状态(存在、删除、空)是非常有必要的。

--------------------

### 3. 哈希表的插入删除与查找 ###

>  *  插入：通过哈希函数得到余数即数组下标，如果该下标的状态为删除或为空则插入，如果为存在则向后寻找下一个状态为删除/空的位置进行插入；
>  *  查找：通过哈希函数得到余数即数组下标，取出小标位置的key与目标key进行比较，相等就返回该位置的地址，不相等就继续往后查找，如果查找到状态为空的下标位置就返回 nullptr；
>  *  删除：复用查找函数，查找到就通过查找函数的返回值将小标位置数据的状态置为 删除，找不到就返回 false。

这里我们需要注意三点：

*  当遇到状态为空的下标位置才返回 nullptr，而不是遇到状态为 删除的位置就返回 nullptr，因为你要查找的数据可能在已删除位置的后面；
 *  将查找函数返回值定义为 `HashData<K, V>*`，而不是 bool，这样可以方便我们进行删除和修改 (修改 key 对应的 value) – 查找到之后直接通过指针解引用来修改 value 与 state；
 *  哈希表经过不断插入删除，最终可能会出现一种极端情况 – 哈希表中元素的状态全为 EXIST 和 DELETE，此时如果我们找空就会造成死循环，所以我们需要对这种情况单独进行处理；

💕 **扩容操作**

>  *  由于哈希表中的有效元素个数与哈希表长度都是整数，且有效元素个数一定小于哈希表长度，所以它们的商一定为0 (整数除法)，所以我们需要在前面乘以一个小数使得它们的商为小数；
>  *  哈希表的扩容并不是简单的扩大空间，而是需要将已经插入哈希表的元素取出全部重新插入一遍，因为扩容后哈希表的长度改变，那么 key 通过哈希函数映射到的位置也会改变；比如17扩容前插入的位置为7，扩容后插入位置就变为17，所以需要将其取出重新插入。

💕 **代码实现**

template<class K, class V>
    class HashTable
    {
        
    public:
    
    	//哈希表的插入
    	bool Insert(const pair<K, V>& kv)
    	{
        
    		if (Find(kv.first))
    			return false;
    		//这里我们需要注意一下，负载因子如果超过一定范围扩容
    		if (_tables.size() == 0 || _n * 10 / _tables.size() >= 10)
    		{
        
    			//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
    			//
    			//vector<HashData<K, V>> newtables;
    			//newtables.resize(newsize);
    			遍历旧表，重新映射到新的哈希表
    			//for (auto& data : _tables)
    			//{
        
    			//	if (data._state == EXIST)
    			//	{
        
    			//		size_t hashi = data._kv.first % newtables.size();
    
    			//		//线性探测
    			//		size_t i = 1;
    			//		size_t index = hashi;
    			//		while (newtables[index]._state == EXIST)
    			//		{
        
    			//			index = hashi + i;
    			//			index %= newtables.size();
    			//			i++;
    			//		}
    			//		newtables[index]._kv = data._kv;
    			//		newtables[index]._state = EXIST;
    			//	}
    			//}
    			//_tables.swap(newtables);
    
    			size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
    			HashTable<K, V> newht;
    			newht._tables.resize(newsize);
    
    			//遍历旧表，重新映射到哈希表
    			for (auto& data : _tables)
    			{
        
    				if (data._state == EXIST)
    				{
        
    					newht.Insert(data._kv);
    				}
    			}
    			_tables.swap(newht._tables);
    		}
    
    
    		//计算映射关系
    		size_t hashi = kv.first % _tables.size();
    
    		//线性探测
    		size_t i = 1;
    		size_t index = hashi;
    		while (_tables[index]._state == EXIST)
    		{
        
    			index = hashi + i;
    			index %= _tables.size();
    			i++;
    		}
    		_tables[index]._kv = kv;
    		_tables[index]._state = EXIST;
    		_n++;
    
    		return true;
    	}
    
    	//哈希表的查询
    	HashData<K, V>* Find(const K& key)
    	{
        
    		if (_tables.size() == 0)
    			return nullptr;
    
    		//线性探测查询目标值
    		size_t hashi = key % _tables.size();
    		size_t i = 1;
    		size_t index = hashi;
    
    		while (_tables[index]._state != EMPTY)
    		{
        
    			if (_tables[index]._state == EXIST
    				&& _tables[index]._kv.first == key)
    				return &_tables[index];
    
    			index = hashi + i;
    			index %= _tables.size();
    			i++;
    
    			//如果查找完一圈以后发现还没有找到，就直接退出
    			if (index == hashi)
    				break;
    		}
    		return nullptr;
    	}
    
    	//哈希表的删除
    	bool Erase(const K& key)
    	{
        
    		HashData<K, V>* ret = Find(key);
    		if (ret)
    		{
        
    			ret->_state = DELETE;
    			_n--;
    			return true;
    		}
    		else
    			return false;
    	}
    
    private:
    	vector<HashData<K, V>> _tables;
    	size_t _n = 0;  //存储的数据个数
    };

--------------------

### 4. 哈希表的仿函数 ###

我们上面实现的哈希表的 key 值只能是整数，因为我们要让 key 与哈希表长度取模得到映射位置，那么如果我们 key 是一个字符串呢？比如我们要统计水果的数量；此时我们就需要进行两层转换 – **先将字符串转换为整数，再将该整数作为 key 转换为下标**；

因为哈希表在实现的时候并不知道用户会将key定义为什么类型，所以在这里我们可以为哈希表添加一个模板参数，这个模板参数是一个仿函数，仿函数分为设计者提供的默认仿函数和用户提供的仿函数，系统默认的仿函数可以将一些常见的key的类型全部转换为整形，比如People类、Date类等等。

template<class K>
    struct HashFunc
    {
        
    	size_t operator()(const K& key)
    	{
        
    		return key;
    	}
    };
    
    //类模板的特化
    template<>
    struct HashFunc<string>
    {
        
    	size_t operator()(const string& key)
    	{
        
    		return key[0];
    	}
    };
    template<class K, class V, class Hash = HashFunc<K>>
    	class HashTable
    	{
        
    	public:
    
    		//哈希表的插入
    		bool Insert(const pair<K, V>& kv)
    		{
        
    			if (Find(kv.first))
    				return false;
    			//这里我们需要注意一下，负载因子如果超过一定范围扩容
    			if (_tables.size() == 0 || _n * 10 / _tables.size() >= 10)
    			{
        
    				size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
    				HashTable<K, V> newht;
    				newht._tables.resize(newsize);
    
    				//遍历旧表，重新映射到哈希表
    				for (auto& data : _tables)
    				{
        
    					if (data._state == EXIST)
    					{
        
    						newht.Insert(data._kv);
    					}
    				}
    				_tables.swap(newht._tables);
    			}
    
    			Hash hash;
    
    			//计算映射关系
    			size_t hashi = hash(kv.first) % _tables.size();
    
    			//线性探测
    			size_t i = 1;
    			size_t index = hashi;
    			while (_tables[index]._state == EXIST)
    			{
        
    				index = hashi + i;
    				index %= _tables.size();
    				i++;
    			}
    			_tables[index]._kv = kv;
    			_tables[index]._state = EXIST;
    			_n++;
    
    			return true;
    		}
    
    		//哈希表的查询
    		HashData<K, V>* Find(const K& key)
    		{
        
    			if (_tables.size() == 0)
    				return nullptr;
    
    			Hash hash;
    
    			//线性探测查询目标值
    			size_t hashi = hash(key) % _tables.size();
    			size_t i = 1;
    			size_t index = hashi;
    
    			while (_tables[index]._state != EMPTY)
    			{
        
    				if (_tables[index]._state == EXIST
    					&& _tables[index]._kv.first == key)
    					return &_tables[index];
    
    				index = hashi + i;
    				index %= _tables.size();
    				i++;
    
    				//如果查找完一圈以后发现还没有找到，就直接退出
    				if (index == hashi)
    					break;
    			}
    			return nullptr;
    		}
    
    		//哈希表的删除
    		bool Erase(const K& key)
    		{
        
    			HashData<K, V>* ret = Find(key);
    			if (ret)
    			{
        
    				ret->_state = DELETE;
    				_n--;
    				return true;
    			}
    			else
    				return false;
    		}
    
    	private:
    		vector<HashData<K, V>> _tables;
    		size_t _n = 0;  //存储的数据个数
    	};

### 5. 字符串哈希算法 ###

上面使用的字符串第一个字符作为key的方法虽然可以将成功映射到下标，但是他也很容易发生哈希冲突——只要字符串首字母相同就会发生冲突；所以我们可以考虑将字符串所有字符的ASCII码加起来作为key，如下：

template<>
    struct HashFunc<string>
    {
        
    	size_t operator()(const string& key)
    	{
        
    		size_t sum = 0;
    		for (auto ch : key) {
        
    			sum += ch;
    		}
    		return sum;
    	}
    };

但是他还是会发生冲突，比如 `“abc” 与 “acb” “bac” “bca” “aad” ...`；

下面是一个大佬介绍字符串哈希算法的博客，里面包含了多种优秀的字符串哈希算法，大家可以看看：[各种字符串哈希函数][Link 2]

其中 BKDR 哈希字符串算法是最出名也是平均得分最高的，所以这里我们采用它，其思路很简单，在每次与字符的 ASCII 相加之前除以一个数即可，这个数一般为 131/31，如下：

template<>
    struct HashFunc<string>
    {
        
    	size_t operator()(const string& key)
    	{
        
    		size_t sum = 0;
    		for (auto ch : key)
    			sum = sum * 131 + ch;
    		return sum;
    	}
    };

--------------------

### 6. 整体代码实现 ###

到这里，哈希函数的除留余数法 (使用闭散列的线性探测法来解决哈希冲突) 的模拟实现就基本完成了，其中哈希表的拷贝构造、析构、赋值重载我们使用编译器默认生成的即可 – 对于自定义类型编译器会调用自定义类型的拷贝构造、析构、赋值重载，由于 tables 是 vector 类型的变量，而 vector 中实现了深拷贝与析构，所以我们不用再自己实现。

但是，由于线性探测法对于发生哈希冲突的概率非常的高，所以导致数据插入与搜索的效率较低，因此我们学习的重点将会是下面的**开散列**：

#pragma once
    
    
    //闭散列实现哈希表(开放寻址法)
    namespace OpenAddress
    {
        
    	template<class K>
    	struct HashFunc
    	{
        
    		size_t operator()(const K& key)
    		{
        
    			return key;
    		}
    	};
    
    	//类模板的特化
    	template<>
    	struct HashFunc<string>
    	{
        
    		size_t operator()(const string& key)
    		{
        
    			size_t sum = 0;
    			for (auto ch : key)
    				sum = sum * 131 + ch;
    			return sum;
    		}
    	};
    
    	enum State
    	{
        
    		EMPTY,
    		EXIST,
    		DELETE
    	};
    
    	template<class K, class V>
    	struct HashData
    	{
        
    		pair<K, V> _kv;
    		State _state = EMPTY; // 状态
    	};
    
    	template<class K, class V, class Hash = HashFunc<K>>
    	class HashTable
    	{
        
    	public:
    
    		//哈希表的插入
    		bool Insert(const pair<K, V>& kv)
    		{
        
    			if (Find(kv.first))
    				return false;
    			//这里我们需要注意一下，负载因子如果超过一定范围扩容
    			if (_tables.size() == 0 || _n * 10 / _tables.size() >= 10)
    			{
        
    				size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
    				HashTable<K, V> newht;
    				newht._tables.resize(newsize);
    
    				//遍历旧表，重新映射到哈希表
    				for (auto& data : _tables)
    				{
        
    					if (data._state == EXIST)
    					{
        
    						newht.Insert(data._kv);
    					}
    				}
    				_tables.swap(newht._tables);
    			}
    
    			Hash hash;
    
    			//计算映射关系
    			size_t hashi = hash(kv.first) % _tables.size();
    
    			//线性探测
    			size_t i = 1;
    			size_t index = hashi;
    			while (_tables[index]._state == EXIST)
    			{
        
    				index = hashi + i;
    				index %= _tables.size();
    				i++;
    			}
    			_tables[index]._kv = kv;
    			_tables[index]._state = EXIST;
    			_n++;
    
    			return true;
    		}
    
    		//哈希表的查询
    		HashData<K, V>* Find(const K& key)
    		{
        
    			if (_tables.size() == 0)
    				return nullptr;
    
    			Hash hash;
    
    			//线性探测查询目标值
    			size_t hashi = hash(key) % _tables.size();
    			size_t i = 1;
    			size_t index = hashi;
    
    			while (_tables[index]._state != EMPTY)
    			{
        
    				if (_tables[index]._state == EXIST
    					&& _tables[index]._kv.first == key)
    					return &_tables[index];
    
    				index = hashi + i;
    				index %= _tables.size();
    				i++;
    
    				//如果查找完一圈以后发现还没有找到，就直接退出
    				if (index == hashi)
    					break;
    			}
    			return nullptr;
    		}
    
    		//哈希表的删除
    		bool Erase(const K& key)
    		{
        
    			HashData<K, V>* ret = Find(key);
    			if (ret)
    			{
        
    				ret->_state = DELETE;
    				_n--;
    				return true;
    			}
    			else
    				return false;
    		}
    
    	private:
    		vector<HashData<K, V>> _tables;
    		size_t _n = 0;  //存储的数据个数
    	};
    
    	void TestHashTable1()
    	{
        
    		int a[] = {
         3, 33, 2, 13, 5, 12, 1002 };
    		HashTable<int, int> ht;
    		for (auto e : a)
    		{
        
    			ht.Insert(make_pair(e, e));
    		}
    
    
    		if (ht.Find(13))
    			cout << "13在" << endl;
    		else
    			cout << "13不在" << endl;
    
    		ht.Erase(13);
    
    		if (ht.Find(13))
    			cout << "13在" << endl;
    		else
    			cout << "13不在" << endl;
    	}
    }

--------------------

[c212b90e77d24d12ac9e1255771fdfb8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/fa80443a7cba4929a9a53e065108a41e.png
[1eebb40a43bd41f2963027ab6cd920bd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/ad6a589c99344002a113e35eeb4dbbf9.png
[d280b0ecae3341f292c05065a5511500.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/be48f476566b4e1b9be33a325aa8e57e.png
[49ebf328a47d47bfa4d4dcf5016a56b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/6ac119a962b6457bb50a23de1c8cc3a2.png
[unordered_set]: https://cplusplus.com/reference/unordered_set/unordered_set/?kw=unordered_set
[2N_N]: https://leetcode.cn/problems/n-repeated-element-in-size-2n-array/
[ee47676f11cc4cd38d309100ce3516aa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/4b19410fa7d7491fbf9d7c70a3b43f53.png
[Link 1]: https://leetcode.cn/problems/intersection-of-two-arrays/
[84e905d07e0a4328bd2f9d2ef4c7479d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/f47f2c07a8f0471eba93dd987c76e1c3.png
[II]: https://leetcode.cn/problems/intersection-of-two-arrays-ii/
[38714c2603c945f7b4b3e49ad1193b8b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/c4d8cc0bb2794ca6bafb2989d5ea14dc.png
[2c490bc1538f4a44baa1ce9d3352daad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/daa52b036a2147ccaa72f371abde9026.png
[2f9e684fe57545fca58f8b7c3596e73e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/608a2c144dc945a9bb58cd9ace22b617.png
[5d2899687a904666b981cd30875c8478.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/8b28d36151814ce2a2419bd52c148faa.png
[ac46ae7d1f354552b62c7a87e72142b7.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/b6b6746e20024f81bcfca7e55feb7189.jpeg
[ea712442cbd14a73a89d9bc6bd3a5e85.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/bd0719bae3624c50a30edbf7681b55ff.png
[59e3e3ac20894405894e96e493876b2c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/b74bea47d59644ea8756027e94951817.png
[Link 2]: https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html