[C++] 哈希详解

我就是我 2022-09-09 02:19 272阅读 0赞

### 目录 ###

*  1. 哈希概念
 *  2. 实现机制
 *   *  2.1 插入时
     *  2.2 查找时
     *  2.3 缺陷
     *  2.4 常见哈希函数
     *   *  2.4.1 直接定制法
         *  2.4.2 除留余数法
         *  2.4.3 平方取中法
         *  2.4.4 折叠法
         *  注意
 *  3. 解决哈希冲突
 *   *  3.1 闭散列
     *   *  3.1.1 线性探测
         *  3.1.2 二次探测
         *  3.1.3 闭散列缺点
     *  3.2 开散列
     *   *  3.2.1 容量问题
     *  4. 开散列的代码实现

# 1. 哈希概念 #

哈希是一种高效用来搜索的数据结构，与传统的查找方式进行比较，发现传统的方式都需要进行元素的比较，性能高低取决于元素的比较次数。**让元素在查找时不进行比较，或者减少比较次数。**

>   顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log2 N)，搜索的效率取决于搜索过程中元素的比较次数。  
>   理想的搜索方法：**可以不经过任何比较，一次直接从表中得到要搜索的元素**。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立**一对一映射**的关系，那么在查找时通过该函数可以很快找到该元素。

# 2. 实现机制 #

## 2.1 插入时 ##

> 1.通过函数计算插入位置，该函数成为**哈希函数**  
> 2.通过计算出的存储位置进行元素的插入，通过这种方法构造出来结构称为**哈希表(散列表)**

## 2.2 查找时 ##

> 1.通过哈希函数对关键码进行计算，得出元素的存储位置  
> 2.根据存储位置在哈希表中，取出元素进行比较，若关键码相同，则查找成功。

这里使用除留余数法举例  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZOm5ZOm5ZG15ZG1_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

## 2.3 缺陷 ##

对于两个数据元素的关键字 ki 和 kj (i != j)，有 ki != kj，但有：Hash(ki) == Hash(kj)，即：**不同关键字通过相同哈希哈数计算出相同的哈希地址**，该种现象称为**哈希冲突或哈希碰撞**。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

**举例：**  
上述图片中，1的位置上已经插入了一，如果我们还想插入`11`，使用除留余数法`11 % 10 = 1`，插入位置还是 1 的位置，这就发生了哈希冲突。

## 2.4 常见哈希函数 ##

### 2.4.1 直接定制法 ###

> **原理**：取关键字的某个线性函数为散列地址：Hash（Key）= A\*Key + B  
> **优点**：简单、均匀 缺点：需要事先知道关键字的分布情况  
> **使用场景**：适合查找比较小且连续的情况

### 2.4.2 除留余数法 ###

> **原理**：设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址。  
> **注意**: 一般情况下，**p最好是一个不超过m的最大素数**

### 2.4.3 平方取中法 ###

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

### 2.4.4 折叠法 ###

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

### 注意 ###

> 不论一个哈希函数设计的有多么精妙，都不能完全解决哈希冲突，只能是，**哈希函数越精妙，产生的哈希冲突概率越低**

# 3. 解决哈希冲突 #

## 3.1 闭散列 ##

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

### 3.1.1 线性探测 ###

**原理**  
  从发生冲突的位置逐个挨着一次往后查找，如果查找到空间的末尾，也没有发现空位置时，再折回空间起始位置继续查找，直到找到空位置插入进去。

**缺陷**  
  容易产生数据堆积，如果发生了冲入，冲突的元素可能连成一片，因为查找下一个空位置的方式，是逐个向后查找到。

**如何避免**  
不要挨着依次向后查找空位置，`二次探测`。

### 3.1.2 二次探测 ###

解决数据堆积的问题，每次查找空位置时，**都向后偏移不同的举例进行检测**。

**查找下一个空位置的方法**

> `H(i) = (H0 + i ^ 2) % cap` / `H(i) = (H0 - i ^ 2) % cap`  
> 所以: `H(i + 1) = H(i) + 2 * i + 1`

**缺陷**  
  当表格中空位置比较少时，可能需要查找很多次

### 3.1.3 闭散列缺点 ###

当表格中数据较多时，或者哈希表中的空位置较少时，发生冲突的概率非常高，而且找下一个空位置的效率比较低，不论是线性探测还是二次探测都需要找好多次才能找到。

>   当哈希表中有效元素比较多时，对哈希表的性能影响非常大。  
>   哈希期望查找时间复杂度是 O(1)，但空位置比较少时，性能远远超过O(1).  
> **哈希使用时间换空间**

**解决方法**  
  不要让表格存储太多元素，达到一定程度时就进行扩容，即: **哈希表中的元素一定不会存满**

`负载因子 = 填入表的有效元素的个数 / 散列表的长度` 线性探测为：70%左右，二次探测为：50%~60%，在**这个区间内就需要扩容了**，存的多了就会导致冲突概率上升，存的少了就会空间利用率降低。

## 3.2 开散列 ##

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

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZOm5ZOm5ZG15ZG1_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]  
**操作**  
  插入或查找时，当中存在一个循环，即：遍历链表，检测data是否存在，表面上时间复杂度O(n)，但实际认为操作时的时间复杂度为O(1)，因为**链表不会很长**

### 3.2.1 容量问题 ###

**1. 如果元素特别多，或元素特别特殊，大部分元素都集中到了某一个链表中**

导致某些链表特别长，在哈希桶中查找某个元素，就退化成了在单链表中查找。

>   如果每个哈希桶中的元素不是特别多的情况下，哈希桶的时间复杂度为O(1).  
>   如果哈希桶当中某些链表中挂的结点非常多，哈希桶就退化成了在链表中进行查找，时间复杂度变成了O(n)。

所以在插入元素的过程中，需要避免上述的情况，在闭散列中，元素多到一定程度通过扩容来降低冲突概率，哈希桶中也是如此，通过扩容，把链表中的结点分散开来。

**2. 什么情况下进行扩容？什么情况下哈希桶最优(空间利用率高、查找性能高)?**  
  最优状态: 每个桶只挂一个结点。**当哈希桶中元素个数与桶的个数相同时就要考虑扩容**。因为扩容之后，哈希桶的容量变了，哈希函数计算出来的结果就发生了变化，再将旧哈希桶中的元素往新哈希桶中插入，就可以基本到达较优。

**3. 随着哈希桶中的元素不断增多，哈希桶的的容量也会不断增大，怎么解决？**  
  扩容之后，继续往哈希桶中插入元素，或者对方在向哈希表中插入元素是，每个插入哈希桶中的元素都是发生哈希冲突的，可能又会出现某些链表特别长的场景出现，扩容之后依旧不能达到目的。(哈希桶性能又下降了，但是还没有达到扩容的时机)。

**解决方案**  
  当链表中的结点达到一定的阈值，还没有达到扩容的条件时，可以将链表转换成**红黑树**，当结点个数小于阈值就转换成链表。

**4. 哈希函数**  
  除留取余法：最好模上一个素数，发生冲突的概率相对而言能稍微低一些，而元素的个数与表格容量相等时，需要扩容，按照两倍的方式扩容。可以用素数表将含有两倍关系的素数存下来。

const int PRIMECOUNT = 28;
    const size_t primeList[PRIMECOUNT] =
    { 
    	53ul, 97ul, 193ul, 389ul, 769ul,
    	1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
    	49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    	1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
    	50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
    	1610612741ul, 3221225473ul, 4294967291ul
    };

**5. 泛型存储**  
  哈希函数中任意类型都能存储，但是使用除留取余法，只能转换整数，所以还要传入一个模板参数，可以将其它类型进行转换，使之能够使用除留取余法。

## 4. 开散列的代码实现 ##

#include <iostream>
    using namespace std;
    
    #include <vector>
    #include "Common.h"
    
    // 哈希桶：数组+链表(无头单链表)
    
    template<class T>
    struct HashBucketNode
    { 
    	HashBucketNode<T>* next;
    	T data;
    
    	HashBucketNode(const T& x = T())
    		: next(nullptr)
    		, data(x)
    	{ }
    };
    
    
    // T 如果是整形家族
    template<class T>
    class T2IntDef
    { 
    public:
    	const T& operator()(const T& data)
    	{ 
    		return data;
    	}
    };
    
    
    class Str2Int
    { 
    public:
    	size_t operator()(const string& s)
    	{ 
    		const char* str = s.c_str();
    		unsigned int seed = 131; // 31 131 1313 13131 131313
    		unsigned int hash = 0;
    		while (*str)
    		{ 
    			hash = hash * seed + (*str++);
    		}
    		return (hash & 0x7FFFFFFF);
    	}
    };
    
    
    // 假设：当前实现的哈希表中元素唯一
    // T：哈希表中存储的元素的类型
    // T2Int: 将T转换为整形的结果
    
    template<class T, class T2Int = T2IntDef<T>>
    class HashBucket
    { 
    	typedef HashBucketNode<T> Node;
    public:
    	HashBucket(size_t capacity = 53)
    		: table(GetNextPrime(capacity))    // n个值为data的构造方法在构造哈希桶
    		, size(0)
    	{ }
    
    	~HashBucket()
    	{ 
    		Destroy();
    	}
    
    	/* 虽然从代码层面来看，Insert当中存在一个循环，即：遍历链表，检测data是否存在---->表面上Insert的时间复杂度O(N) 但是实际认为Insert的时间复杂度仍旧为O(1)---->因为：在哈希桶中，每个桶对应的链表当中的节点的格式都不是非常多 */
    	bool Insert(const T& data)
    	{ 
    		// 0. 检测是否需要扩容
    		CheckCapacity();
    
    		// 1. 通过哈希函数计算元素所在桶号
    		size_t bucketNo = HashFunc(data);
    
    		// 2. 检测元素是否存在
    		Node* cur = table[bucketNo];
    		while (cur)
    		{ 
    			if (data == cur->data)
    				return false;
    
    			cur = cur->next;
    		}
    
    		// 3. 插入元素
    		cur = new Node(data);
    		cur->next = table[bucketNo];
    		table[bucketNo] = cur;
    		++size;
    		return true;
    	}
    
    	bool Erase(const T& data)
    	{ 
    		// 1. 先通过哈希函数计算元素所在的桶号
    		size_t bucketNo = HashFunc(data);
    
    		// 2. 找元素在bucketNo桶中是否处在，存在则删除
    		// 核心操作--->删除链表当中只为data的节点
    		// 该节点可能是链表中的第一个节点
    		// 该节点可能是链表中的非第一个节点
    
    		Node* cur = table[bucketNo];
    		Node* prev = nullptr;   // 标记cur的前一个节点
    		while (cur)
    		{ 
    			if (data == cur->data)
    			{ 
    				// 删除cur节点
    				// 删除的节点如果是第一个节点
    				if (nullptr == prev)
    					table[bucketNo] = cur->next;
    				else
    					prev->next = cur->next;
    
    				delete cur;
    				--size;
    				return true;
    			}
    			else
    			{ 
    				// 当前节点不是要找的data，则两个指针同时往后移动
    				prev = cur;
    				cur = cur->next;
    			}
    		}
    
    		// 哈希桶中不存在值为data的元素，无法删除即删除失败
    		return false;
    	}
    
    	Node* Find(const T& data)
    	{ 
    		// 1. 先通过哈希函数计算元素所在的桶号
    		size_t bucketNo = HashFunc(data);
    
    		// 2. 在检测该元素是否存在对应的链表中
    		Node* cur = table[bucketNo];
    		while (cur)
    		{ 
    			if (data == cur->data)
    				return cur;
    
    			cur = cur->next;
    		}
    
    		return nullptr;
    	}
    
    	size_t Size()const
    	{ 
    		return size;
    	}
    
    	bool Empty()const
    	{ 
    		return 0 == size;
    	}
    
    	/
    	// 为了方便对哈希桶的理解，实现打印哈希桶的方法
    	void Print()
    	{ 
    		for (size_t i = 0; i < table.capacity(); ++i)
    		{ 
    			Node* cur = table[i];
    
    			cout << "table[" << i << "]:";
    
    			while (cur)
    			{ 
    				cout << cur->data << "--->";
    				cur = cur->next;
    			}
    
    			cout << "NULL" << endl;
    		}
    		cout << "=========================================" << endl;
    	}
    
    	void Swap(HashBucket<T, T2Int>& ht)
    	{ 
    		table.swap(ht.table);
    		std::swap(size, ht.size);
    	}
    
    private:
    	// 哈希函数---除留余数法
    	size_t HashFunc(const T& data)
    	{ 
    		T2Int t2Int;
    		return t2Int(data) % table.capacity();
    	}
    
    	void Destroy()
    	{ 
    		// 循环去销毁：table中的每个链表
    		for (size_t i = 0; i < table.capacity(); ++i)
    		{ 
    			Node* cur = table[i];
    
    			// 采用：头删法删除链表中的每个节点
    			while (cur)
    			{ 
    				table[i] = cur->next;
    				delete cur;
    				cur = table[i];
    			}
    		}
    
    		size = 0;
    	}
    
    	void CheckCapacity()
    	{ 
    		if (size == table.capacity())
    		{ 
    			// 扩容---将表格放大----然后将桶中的元素往新桶中插入
    			HashBucket<T, T2Int> newHT(GetNextPrime(table.capacity()));
    
    			// 将就哈希桶中的节点拆下来，移动到新哈希桶中
    			for (size_t i = 0; i < table.capacity(); ++i)
    			{ 
    				Node* cur = table[i];
    				while (cur)
    				{ 
    					// 1. 将cur节点拆下来
    					table[i] = cur->next;
    
    					// 2. 将cur节点往newHT中插入
    					// 找位置
    					size_t bucketNo = newHT.HashFunc(cur->data);
    
    					// 头插法
    					cur->next = newHT.table[bucketNo];
    					newHT.table[bucketNo] = cur;
    					newHT.size++;
    
    					cur = table[i];
    				}
    			}
    
    			// 已经将旧哈希桶中的元素全部移动到新哈希桶当中了
    			this->Swap(newHT);
    		}
    	}
    private:
    	// table当中将来存放所有的链表--->实际只需要存放链表首节点的地址
    	std::vector<Node*> table;
    	size_t size;   // 有效元素的个数
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZOm5ZOm5ZG15ZG1_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220829/334e7ddb35514485ac162f2ad541bb3d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZOm5ZOm5ZG15ZG1_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]: /images/20220829/dc637fd5f8b34b5b83605f49fb81ab7f.png