哈希表——我欲修仙（功法篇）

àì夳堔傛蜴生んèń 2024-04-13 14:15 64阅读 0赞

> 个人主页：[【?个人主页】][Link 1]  
> 系列专栏：[【❤️我欲修仙】][Link 2]  
> 学习名言：莫等闲、白了少年头，空悲切。——岳飞

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

## 系列文章目录 ##

第一章 ❤️ [学习前的必知知识][Link 3]  
第二章 ❤️ [二分查找][Link 4]

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

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

*  系列文章目录
 *  什么是哈希表？
 *  使用哈希表的常用方法
 *   *  直接寻址法
     *  数字分析法
     *  平方取中法
     *  折叠法
     *  随机数法
     *  除留余数法
 *  哈希碰撞
 *   *  拉链法
     *  线性探测法
 *  三种哈希结构
 *   *  set
     *  map
 *  总结

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

## 什么是哈希表？ ##

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

> 给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希(Hash) 函数

总的来说：
     - 哈希表是一种数据结构
     - 哈希表表示了关键码值和记录的映射关 
     - 哈希表可以加快查找速度
     - 任意哈希表，都满足有哈希函数f(key)，代入任意key值都可以获取包含该key值的记录在表中的地址

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

## 使用哈希表的常用方法 ##

哈希表有多种使用方式，通常我们选择何种方式需要通过以下几点进行分析：

> · 计算哈希函数所需时间  
> · 关键字的长度  
> · 哈希表的大小  
> · 关键字的分布情况  
> · 记录的查找频率

### 直接寻址法 ###

> 取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）。若其中H（key）中已经有值了，就往下一个找，直到H（key）中没有值了，就放进去。

### 数字分析法 ###

> 分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

### 平方取中法 ###

> 当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址

### 折叠法 ###

> 将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。

### 随机数法 ###

> 选择一随机函数，取关键字的随机值作为散列地址，即H(key)=random(key)其中random为随机函数,通常用于关键字长度不等的场合。

### 除留余数法 ###

> 取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p≤m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。

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

## 哈希碰撞 ##

> 对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=(k2)，这种现象称为冲突（英语：Collision）——我们也称之为哈希碰撞  
> 我们有两种方式来解决这个问题：**拉链法和线性探测法**

### 拉链法 ###

将发生碰撞的元素都存进哈希表中，我们通过索引去查找它们的位置，这种方法即拉链法。  
![在这里插入图片描述][b4f1012e180147e78e59c9442b3d68dd.png_pic_center]

> 其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

### 线性探测法 ###

使用线性探测法，一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。

> 例如冲突的位置有两种元素（a与b），在哈希表中存放a，那么就向下找一个空位放置b。所以要求哈希表可存放的个数一定要大于数据元素个数 ，要不然哈希表上就没有空置的位置来存放冲突的数据了。

![在这里插入图片描述][531175ddb77845f2a2ea83e87a150096.webp_pic_center]

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

## 三种哈希结构 ##

在我们使用哈希表进行解决问题时通常有三种结构可供我们选择：

*  数组
 *  set（集合）
 *  map（映射）

### set ###

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

> std::unordered\_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

### map ###

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

> std::unordered\_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的

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

## 总结 ##

> 大多数情况下，使用哈希表和哈希集合的场景都会使用 HashMap 类和 HashSet 类的对象。如果哈希表的键范围有限或者哈希集合的元素范围有限，例如只能是数字或者只能是字母，则可以用数组代替哈希表。虽然从复杂度分析的角度而言，数组和哈希表的时间复杂度和空间复杂度相同，但是在实际运行时，数组的操作时间和占用空间都优于哈希表。

![在这里插入图片描述][65ef50df91434184885c888ce6d8dfe9.gif_pic_center]  
(图片与部分内容来源于网络，侵权请联系删除)

[Link 1]: https://blog.csdn.net/weixin_73602725?type=blog
[Link 2]: https://blog.csdn.net/weixin_73602725/category_12259807.html?spm=1001.2014.3001.5482
[Link 3]: https://blog.csdn.net/weixin_73602725/article/details/129406349
[Link 4]: https://blog.csdn.net/weixin_73602725/article/details/129731407?spm=1001.2014.3001.5501
[b4f1012e180147e78e59c9442b3d68dd.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/9b50c009e0b84ebe8c616d35e5a68ce5.png
[531175ddb77845f2a2ea83e87a150096.webp_pic_center]: https://img-blog.csdnimg.cn/531175ddb77845f2a2ea83e87a150096.webp#pic_center
[acd675bf724647ec845ae6bdcf33b8e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/048998ad94364d29a17151d956b45e9c.png
[44c18bc5bc684d6aa5f06bdf57f990f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/897b7d99a3704e44acfcacc8d1375d65.png
[65ef50df91434184885c888ce6d8dfe9.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/2e4b5bdecc14464da13f9c49cf880e17.gif