Hash详解

我就是我 2022-03-20 13:50 192阅读 0赞

# Hash详解 #

2018年07月23日 10:00:22 [弓小长-Gsc][-Gsc] 阅读数：1155

# Hash(哈希) #

**Hash** ：**散列**，通过关于**键值(key)**的函数，将数据**映射**到内存存储中一个位置来访问。这个过程叫做**Hash**，这个映射函数称做**散列函数**，存放记录的数组称做**散列表(Hash Table)**,又叫**哈希表**。JAVA函数hashCode()即请求对象的哈希值。

## **Hash的优点** ##

**先分类再查找，通过计算缩小范围，加快查找速度。**

例：

集合：｛13,19,25,27，17｝

若是采用数组或链表结构：

访问其中的一个元素（如18），需要遍历整个集合的元素，时间复杂度为O(n).

而采用哈希表时:

1.  `假如散列函数为H[key] = key % 5；则集合元素对应的hash值分别为｛3,4,0,2,2｝。`
2.  `访问元素（18）只需要在Hash值为2的集合中寻找即可.`
3.  `如果访问没有哈希冲突的元素，例如访问（25），可以直接访问哈希值为（0）的值。`
4.  `故hash时间复杂度最差才为O(n),最优情况下只需要O(1);`
5.  ``

由上面的例子，我们可以想象，如果由大量的数据，采用数组或是链表存储时，访问需要遍历，耗费的时间非常多，而Hash表通过[哈希计算][Link 1]，可以直接定位到数据所在位置（发生哈希冲突时，哈希值相同，可以定位到较小范围）大大加快了 查找的速度，节省了大量时间。

## 散列函数（Hash函数） ##

Hash通过Hash函数，将Key值映射为地址，Address = F\[key\];

常见的几种Hash函数：直接定址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法

1.  直接定址法：取Key或者Key的某个线性函数值为散列地址。Hash(k) = k，或者Hash(k) = a\*k + b, (a\\b均为常数).
    
    如下例所示：a = 1/100,b = -5.
    
    <table> 
     <thead> 
      <tr> 
       <th>Key</th> 
       <th>Hash(Key)</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>1005200</td> 
       <td>10047</td> 
      </tr> 
      <tr> 
       <td>3009800</td> 
       <td>30093</td> 
      </tr> 
      <tr> 
       <td>1506400</td> 
       <td>15059</td> 
      </tr> 
      <tr> 
       <td>7604300</td> 
       <td>76038</td> 
      </tr> 
     </tbody> 
    </table>
    
     
2.  数字分析法：需要知道Key的集合，并且Key的位数比地址位数多，选择Key数字分布均匀的位。如下：
    
    Hash(Key) 取六位：
    
    列数 ： 1   (2)   3   (4)   5   (6)   (7)   8   (9)   10   11   12   (13)
    
    --------------------
    
    key1：  5    2    4    2    7    5     8     5     3     6     5     1      3
    
    --------------------
    
    key2：  5    4    4    8    7    7     7     5     4     8     9     5      1
    
    --------------------
    
    key3：  3    1    5    3    7    8    5      4     6     3      5     5     2
    
    --------------------
    
    key4：  5    3    6    4    3    2      5    4     5      3      2    6     4
    
     
    
    其中(2、4、6、7、9、13) 这6列数字无重复，分布较均匀，取此六列作为Hash(Key)的值。
    
    Hash(Key1) :225833
    
    Hash(Key2):487741
    
    Hash(Key3):138562
    
    Hash(Key4):342554
    
     
3.  平方取中法：取Key平方值的中间几位作为Hash地址。因为在设置散列函数时不一定知道所有关键字，选取哪几位不确定。一个数的平方的中间几位和数本身的每一位都有关，这样可以使随机分布的Key，得到的散列地址也是随机分布的 。如下：
    
    <table> 
     <thead> 
      <tr> 
       <th>Key</th> 
       <th>Key值平方</th> 
       <th>Hash地址(5位)</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>111112113</td> 
       <td>123459<u>01655</u>324769</td> 
       <td>01655</td> 
      </tr> 
      <tr> 
       <td>010111101</td> 
       <td>001022<u>34363</u>432201</td> 
       <td>34363</td> 
      </tr> 
      <tr> 
       <td>210222134</td> 
       <td>441933<u>45623</u>513956</td> 
       <td>45623</td> 
      </tr> 
     </tbody> 
    </table>
4.  折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。 当Key的位数较多的时候数字分布均匀适合采用这种方案.
    
    具体的叠加方法有两种，移位法和折叠法：
    
    例子：若Key为下列数串，地址位数为7，两种方法的Hash(key)分别如下：
    
    Key：7982374 | 1861215 | 9892154 | 56923
    
    <table> 
     <thead> 
      <tr> 
       <th>&nbsp;</th> 
       <th>移位折叠法：</th> 
       <th>&nbsp;</th> 
       <th>折叠折叠法：</th> 
       <th>&nbsp;</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>第一段</td> 
       <td>7982374</td> 
       <td>d1-dr</td> 
       <td>7982374</td> 
       <td>d1-dr</td> 
      </tr> 
      <tr> 
       <td>第二段</td> 
       <td>1861215</td> 
       <td>d(r+1)-d(2r)</td> 
       <td>5121681</td> 
       <td>d(2r)-d(r+1)</td> 
      </tr> 
      <tr> 
       <td>第三段</td> 
       <td>9892154</td> 
       <td>d(2r+1)-d(3r)</td> 
       <td>4512989</td> 
       <td>d(3r)-d(2r+1)</td> 
      </tr> 
      <tr> 
       <td>第四段</td> 
       <td>+ 56923</td> 
       <td>d(3r+1)-d(end)</td> 
       <td>+ 32965</td> 
       <td>d(end)-d(3r+1)</td> 
      </tr> 
      <tr> 
       <td>结果：</td> 
       <td>19792666</td> 
       <td>&nbsp;</td> 
       <td>17650009</td> 
       <td>&nbsp;</td> 
      </tr> 
      <tr> 
       <td>Hash(key):</td> 
       <td>9792666</td> 
       <td>&nbsp;</td> 
       <td>7650009</td> 
       <td>&nbsp;</td> 
      </tr> 
     </tbody> 
    </table>
5.  随机数法：伪随机探测再散列
    
    具体实现：建立一个伪随机数发生器，Hash(Key) = random(Key). 以此伪随机数作为哈希地址。
6.  除留余数法：取关键字被某个除数 p 求余，得到的作为散列地址。
    
    即 H(Key) = Key % p；
    
    例子如下：
    
    <table> 
     <thead> 
      <tr> 
       <th>Key</th> 
       <th>P</th> 
       <th>Hash(Key) (4位)</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>11076302</td> 
       <td>1000</td> 
       <td>6302</td> 
      </tr> 
      <tr> 
       <td>13635279</td> 
       <td>1000</td> 
       <td>5279</td> 
      </tr> 
      <tr> 
       <td>41076553</td> 
       <td>1000</td> 
       <td>6553</td> 
      </tr> 
      <tr> 
       <td>76553027</td> 
       <td>1000</td> 
       <td>3027</td> 
      </tr> 
     </tbody> 
    </table>

以上就是6种构造哈希函数的方法，选择时要本着尽量减少产生冲突的原则，根据Key值的位数，分布情况，范围大小做出更优的选择。

## 哈希冲突 ##

不管选用何种散列函数，[不可避免][Link 2]的都会产生不同Key值对应同一个Hash地址的情况，这种情况叫做哈希冲突。

## 哈希冲突的处理 ##

当冲突发生时，我们需要想办法解决冲突，一般常用的方法有：开放定址法、单独链表法、双散列法、再散列法以及建业公共溢出取等方法。

1.  开放定址法：
    
    当冲突发生时，探测其他位置是否有空地址 (按一定的增量逐个的寻找空的地址)，将数据存入。根据探测时使用的增量的取法，分为：线性探测、平方探测、伪随机探测等。
    
    新的Hash地址函数为 Hash\_new (Key) = (Hash(Key) + d i) mod m；i = 1，2...k (k<= m-1).m表示集合的元素数，i表示已经探测的次数。
    
     *  线性探测(Linear Probing)
        
        d i = a \* i + b; a\\b为常数。
        
        相当于逐个探测地址列表，直到找到一个空置的，将数据放入。
     *  平方探测(Quadratic Probing)
        
        d i = a \* i 2 (i <= m/2) m是Key集合的总数。a是常数。
        
        探测间隔 i2 个单元的位置是否为空，如果为空，将地址存放进去。
     *  伪随机探测
        
        d i = random(Key);
        
        探测间隔为一个伪随机数。
        
         
        
         
    
    **例子：**
    
    Key集合为(15,36,25,46,75)，采用除留余数法，模10 ，冲突时采用线性探测法d i = i;
    
    ![70][]
    
    如图，15和36放入时无冲突发生，分别对应地址 5 和6 。
    
    但是当25放入时，Hash(25) = 25%10 = 5,和Key= 15发生冲突，则令d 1 = 1,Hash(25) = (25 + 1) %10 = 6.
    
    此时已然与Key = 36发生冲突，令d 2 = 2，Hash(25) = (25+2) %10 = 7,无冲突，放入。
    
    此后46,75也发生冲突，解决方法同上。

1.  链表法
    
    将散列到同一个位置的所有元素依次存储在单链表中，或者也有存储在栈中。具体实现根据实际情况决定这些元素的数据存储结构。
    
    如下图所示：
    
    ![70 1][]
    
    首页Hash地址为 i 的结点，均插入到以 T\[i\] 为头指针的单链表中。T 中各分量的初值均应为空指针。
    
    在拉链法中，装填因子 α 可以大于 1，但一般均取 α ≤ 1。
    
     
    
    **装填因子(载荷因子)**
    
    散列表的载荷因子定义为：
    
     α = 填入表中的元素个数 / 散列表的长度.
    
    α 是散列表装满程度的标志因子。由于表长是定值，α 与“填入表中的元素个数”成正比，所以，α 越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之，α 越小，标明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子α 的函数，只是不同处理冲突的方法有不同的函数。
    
    对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中（cache missing）按照指数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了荷载因子为0.75，超过此值将resize散列表。

[-Gsc]: https://me.csdn.net/yt618121
[Link 1]: https://www.baidu.com/s?wd=%E5%93%88%E5%B8%8C%E8%AE%A1%E7%AE%97&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[Link 2]: https://www.baidu.com/s?wd=%E4%B8%8D%E5%8F%AF%E9%81%BF%E5%85%8D&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[70]: /images/20220320/782f531997714b17adbad659ad7e5e68.png
[70 1]: /images/20220320/2fd4ab6aa0834591874b048b32b705c1.png