详解散列表（哈希表）原理

浅浅的花香味﹌ 2021-12-04 09:19 261阅读 0赞

场景：在我们编写基本的C语言代码的时候，比如我们需要输入一个变量，然后对变量进行操作，最后返回一个结果，那么在我们对变量进行操作的时候，我们的编译器就会对你的变量进行检查，他会看你的变量是否定义、定义格式是否正确等。这里就会存在查找问题，如果我们采用二叉查找树等查找树来进行查找的话会发现由于需要使树保持平衡，我们会多花很多额外的功夫，导致查找效率低下，此时，哈希表就应运而生。所以我们说哈希表可以用来进行查找或者说他是一种查找的手段（当然哈希表的功能不止于此）。  
**基本思想：直接“算出”要查找对象的位置**。如果读者学习过python的话，这里的散列表很像python中的字典。  
**散列查找的基本工作：  
①计算位置：通过构造散列函数来确定关键字的存储位置。  
②解决冲突：应用某种策略解决多个关键字位置相同的问题**。

注意：我们在设计散列函数的时候应该本着尽可能通过该函数可以直接找到关键字的存储位置，但是在实际情况中，我们很难做到一个函数可以使用于所有的关键字，那么如果两个关键字的存储位置一样的话，我们称之为**冲突**，发生了冲突，我们就要解决冲突，这就是散列查找的基本工作。  
**散列函数的构造方法**：一个好的散列函数应该考虑这两个因素：**计算简单**（以便提高转换速度）和关键字对应的**地址空间尽可能的分布均匀**（以减少冲突）  
①数字关键词的散列函数的构造：  
**1.直接定址法**：该方法一般是对具有线性关系的关键字使用，我们可以对关键字直接进行线性变换，得到他们的地址，然后进行存储。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]  
**2.除留余数法**：通过对一个较大数字进行取余运算得到较小的值，然后将该值2进行存储，下表中，我们一共有11个关键字，我们就可以去距离11较近的素数来进行取余即17，所以我们的地址空间就是从0-16，我们的散列函数就是关键字对17取余。这里的P一般取素数。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 1]  
**3.数字分析法**:我们拿到的关键词可能由很多位组成，每个位上数字的变化可能不同，有些关键字的某些位数甚至不变，那么我们需要将关键字中会随机变化的位数找出来组成地址，达到映射均匀的目的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][20190718144720375.png]  
因为在同一个地区的手机号中，前几位的变化都不是很大，因此我们选择后思维进行分析，所以这个方法当中，该手机号码的地址就是5678。  
**4.折叠法**：把关键字分割成位数相同的几个部分，然后相加得到地址。下图中，我们将该数字拆分成三位三位的，然后将他们相加，不够的位数我们可以通过补零来对齐位数。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 3]  
**5.平方取中法**：对于一个较大数字我们可以通过计算其平方，然后取出平方以后的结果中间的某些位数的值来进行地址的确定。例如下边的数字，我们计算出其平方之后取出中间的641当作地址。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 4]  
②字符关键字的散列函数构造：  
**1.ASCII码加和法**：我们知道每一个字母都会对应一个ASCII码值，所以我们可以将每个字符的ASCII码值进行相加，但是我们会发现冲突会很常见（如下图），因此该方法并不推荐。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 5]  
**2.前三个字符移位法**：我们有26个字母，当中可能会存在空格，所以我们采用27，但是对于前三个字符相同的情况我们会发现还是会存在冲突，而且该方法存在空间浪费情况。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 6]  
**3.移位法**：我们将所有字符进行移位操作，而不是只针对前三位进行移位  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 7]  
举例如下：我们要将’abcde’计算出来，公式如下，在数学上，我们可以将该公式写为（（a \* 32 + b) \* 32 + c) + d…即每次先将关键字乘以32，再加上下一个关键字，然后将这个整体再次乘以32，再加上下一个关键字…我们会发现，将一个数乘以32就是将其左移5，那相应的，我们可以写出如下代码。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 8]  
**冲突的处理方法：**常见思路：换个位置：**开放地址法**：当发生冲突的时候，我们重新*按照某种规则*去寻找空位来存储关键字。同一位置的冲突对象放在一起：**链地址法**，我们将同一位置*发生冲突的对象用链表放在一起*，最后再查找的时候我们就从链表的表头开始查找就OK。  
开放地址法：若发生了第i次冲突，试探的下一个地址将增加di，基本公式见下图  
![在这里插入图片描述][20190718162556163.png]  
**装填因子α：关键字序列长度除以散列表表长**。  
对于开放地址法：我们的解决方案有：**线性探测、平方探测、双散列**。  
线性探测：我们将下面的关键字序列放入到如图所示的散列地址中，按照我们寻找最小素数的原则来确定表长，散列函数可以设置成关键字模11。然后我们采用线性探测法来进行关键字的排放，即如果当前的关键字的存储位置存在冲突，我们就探测其后的存储地址是否有冲突，如果没有，我们就将关键字放在这里，如果存在冲突，我们就继续向后探测，由于是线性探测，因此我们每次只向后推进一个单位长度。*缺点*：当我们算出来的地址存在冲突时，我们会向后探测，如果这个位置还有元素要向这里放的话那么我们会继续向后探测（假设探测两个单位长度后有空位），我们可以想到，如果这种情况频繁发生的话，那么在这个位置处就会发生**聚集**现象，即**大量的数据被放在第一次冲突的位置之后的连续的很多位置上**。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 9]  
对于上图，我们将序列中的每个关键字进行模11运算，得到的结果放到对应的地址中，如果有冲突的，我们就向后查找，直到找到空位，我们就将该元素放入到该空位i中。如此循环，直至所有关键字均被放入到存储地址中。  
平方探测：增量序列为加减 i 的平方  
![在这里插入图片描述][20190718182619424.png]  
平方探测的方法跟线性探测类似，但是不是挨个查找，而是先查找 1 的平方，如果没有空位的话就查找 -1 的平方，如果还是没有空位的话就查找 +2 的平方…直到找到空位。那么我们可以发现，平方探测不像线性探测那样挨个查找，平方探测是跳跃式的进行查找，因此我们会有这样的疑问，会不会散列表中存在空位，但是我们缺不能探测出来呢？答案是肯定的，但是我们有如下结论：**如果散列表长度是某个4k + 3（k为正整数）形式的素数时，平方探测发就可以探测到整个散列空间**。  
**链地址法**：我们将模值（11）放在节点的数据域，指针域指向一个数组，但是这个数组不进行存储，只表示地址指向一个单链表，我们将有冲突的元素都放在单链表中。在查找的时候，我们先通过散列函数算出数组的下标，然后在这个下标下去遍历单链表，直到找到该数值。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 10]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]: /images/20211204/1528c2db465f4bbbbc6de7462db90e26.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 1]: /images/20211204/3e4c8d482be44ae38c63ac34b1364566.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 2]: /images/20211204/370eac87782f4ac291988ae891f75086.png
[20190718144720375.png]: /images/20211204/9e8c9e1e9166421abd06d7588cfb7e66.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 3]: /images/20211204/068528c20ce14fb986509ddbcb86af56.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 4]: /images/20211204/e97e1041379847498630ebbf160a116b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 5]: /images/20211204/d80993c9e26c45b99b08905c0296b6da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 6]: /images/20211204/af21246bb5284df98562c5fa41d7ce26.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 7]: /images/20211204/744d61ff479d4473a08d95acc5ec1786.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 8]: /images/20211204/241165194d8144c0a3fcb8f1cff22b51.png
[20190718162556163.png]: /images/20211204/a4a8f5b34231426eb1eb069e35f11da5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 9]: /images/20211204/3d78fbef61d3405e9363915bd283adcb.png
[20190718182619424.png]: /images/20211204/6f2e2954c6384f09854bd890b812f16b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 10]: /images/20211204/393f806fe4cd48ad825c5c5da0079c2d.png