数据结构知识点总结--哈希

港控/mmm° 2022-05-30 02:58 277阅读 0赞

# 哈希的各种知识点总结 #

主要结合各个经典面试题总结：

*  哈希函数
 *  哈希冲突
 *  K模型哈希表
 *  K-V模型哈希表
 *  字符串哈希函数
 *  解决哈希冲突的两种方法：  
    
    
     *  开放定址法（闭散列）  
        
        
         *  线性探测
         *  二次探测
         *  负载因子
         *  素数表
     *  拉链法（开散列）
 *  哈希变形  
    
    
     *  位图
     *  布隆过滤器
     *  哈希切割和top K

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

## 哈希函数 ##

<table> 
 <thead> 
  <tr> 
   <th>哈希表构造方法</th> 
   <th>一般法</th> 
   <th>直接定制法</th> 
   <th>除留余数法</th> 
   <th>随机数法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>哈希函数表达式HASH(key)=</td> 
   <td>key%m</td> 
   <td>A*key+B</td> 
   <td>key%p(p&lt;=m)</td> 
   <td>random(key)</td> 
  </tr> 
  <tr> 
   <td>注释：表中只列举了方便写出公式的方法</td> 
   <td>m是数组的长度</td> 
   <td></td> 
   <td>p是最接近或等于m的质数</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

常见的其他方法还有：平均取中法、折叠法、数学分析法等，这里不一一说明，有兴趣的读者可以自行搜索。

> **题目：查找出一个字符串中第一个出现n次的字符**  
> 代码如下：

//该题所需的哈希表的构造使用的就是直接定制法
    //创建一个长度为256（字符类型的范围），使用字符自身大小对应下标，从而构建哈希表
    char GetFirstKCountChar(char* str, int k)
    {
        int hash[256] = { 0 };
        char* cur = str;
        while (*cur)
        {
            hash[*cur]++;
            cur++;
        }
    
        cur = str;
        while (*cur)
        {
            if (hash[*cur] == k)
                return *cur;
    
            cur++;
        }
        return -1;
    }

## 哈希冲突 ##

<table> 
 <thead> 
  <tr> 
   <th>定义</th> 
   <th>不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>产生哈希冲突的原因</td> 
   <td>哈希函数设计的不合理</td> 
  </tr> 
 </tbody> 
</table>

## 解决哈希冲突的两种方法： ##

### 1.开放定址法（闭散列） ###

> 定义：当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到表中“下一个” 空位中去

*  线性探测  
    文字描述：
    
    > ①当产生哈希冲突时，从发生冲突的位置开始向下寻找空位  
    > ②如果找到尾，再从头开始依次寻找，直到找到空位，将key存放进去  
    > ![这里写图片描述][SouthEast]
 *  二次探测  
    二次探测的优点：
    
    > 因为线性探测产生的后果是可能产生某个位置周围连续都不为空，这大大增加了哈希冲突的连续发生的可能性，为了解决这一问题，使得数据分布的比较均匀，采用二次探测
    
    文字描述：
    
    > 二次探测与线性探测的不同点在于，发生哈希冲突时二次探测寻找空位的方式是**向发生冲突的位置的左边和右边都隔2个位置寻找**  
    > ps:①隔的位置个数可以为i^2（i=1,2,3,…）个；②这里为了简单演示，只进行向右隔两个位置寻找  
    > ![这里写图片描述][SouthEast 1]
 *  负载因子  
    负载因子的意义：
    
    > 不论是线性探测还是二次探测，都有可能产生一种现象：**当散列表已满或者接近满的状态时，无法寻找到新的空位，会一直出现哈希冲突，陷入死循环**  
    > 散列表的负载因子定义为：**α=表中的元素个数 / 表的长度**  
    > 对于开放定址法，负载因子十分重要，**应严格限制在0.7~0.8以下，当不满足这个范围的时候，就要进行增容**
 *  素数表  
    素数表中的数据可以在增容是选取作为新的容量大小，使用素数作为容量可以降低哈希冲突

// 使用素数表对齐做哈希表的容量，降低哈希冲突
    const int _PrimeSize = 28;
    static const unsigned long _PrimeList [_PrimeSize] =
    {
    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
    };

### 2.拉链法（开散列） ###

> 定义：首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中

![这里写图片描述][SouthEast 2]

<table> 
 <thead> 
  <tr> 
   <th>对比</th> 
   <th>开放定址法</th> 
   <th>拉链法</th> 
   <th>顺序表</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>时间复杂度</td> 
   <td>O（1）</td> 
   <td>最好的情况：O（1）最坏的情况O（n）</td> 
   <td>O（n）</td> 
  </tr> 
  <tr> 
   <td>平均查找长度</td> 
   <td>1次</td> 
   <td>n/m次（n是元素个数，m是哈希表长度）</td> 
   <td>n次</td> 
  </tr> 
  <tr> 
   <td>负载因子α控制范围</td> 
   <td>0.7~0.8以下</td> 
   <td>α &lt;= 1</td> 
   <td>无</td> 
  </tr> 
 </tbody> 
</table>

代码链接：[开放定址法和拉链法][Link 1]

## 字符串哈希函数 ##

上面提到的哈希函数主要是针对整型数据使用的，当我们需要在文件中查找某些字符串的时候，就需要用到字符串哈希函数，具体的字符串哈希函数算法和代码可以参看链接：  
[字符串哈希函数][Link 2]

## 哈希变形 ##

这部分主要结合经典面试题总结：

*  位图
 *  布隆过滤器
 *  哈希切割和top K  
    可参考链接：[海量数据面试题][Link 3]

[SouthEast]: /images/20220530/361b23dccb124ed2b3a9ca34377ddbec.png
[SouthEast 1]: /images/20220530/7ee388c8474e4be289d6459b80ea6199.png
[SouthEast 2]: /images/20220530/38909498d78d4ba8a509ac836bb53dce.png
[Link 1]: http://blog.csdn.net/w_y_x_y/article/details/79437474
[Link 2]: http://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html
[Link 3]: http://blog.csdn.net/Tianzez/article/details/79423091