天天看點

【細談資料結構】最最最詳細的散清單(哈希表)講解!!!(二)

細談散清單系列一共有三篇文章

1、散清單的概述

2、散列函數的作用與構造

3、散清單查找的代碼實作

文章目錄

    • 細談散清單系列一共有三篇文章
    • 1、查找時的:散列函數?
    • 2、散列函數的構造方法
        • 1、直接定址法
        • 2、數字分析法
        • 3、平方取中法
        • 4、折疊法
        • 5、除留餘數法
        • 6、随機數法
    • 3、采用散列函數的參考因素:
    • 4、解決散列沖突:
        • 1、開方定制法
        • 2、再散列函數法
        • 3、鍊位址法
        • 4、公共溢出區法
    • 5、散清單的查找
    • 6、散清單查找算法實作
    • 7、散清單的查找效率

上篇文章我們提到,散列函數在存儲時會發生沖突,并且也解釋了沖突是如何産生的。

但我們先不着急去解決沖突的問題,我們首先來補充一個概念,散清單是基于散列函數建立的一種查找表。

那散列函數在查找中,具體是幹什麼的呢?

别急,本章内容就帶你了解散列函數的作用以及構造

1、查找時的:散列函數?

  1. 散列函數就是根據key 計算出應該存儲位置的位置;
  2. 根據這個函數和查找關鍵字key,可以直接确定查找值所在位置;
  3. 位址index = f(key)。

簡單來說就是,存哪去?存哪了?

2、散列函數的構造方法

散列函數的構造方法一共有六種,并且每種方法的适應場景都不一樣。

1、直接定址法

  • 取關鍵字的某個線性函數值為散列位址
    • 如:f(key) = a * key + b
  • 優點:簡便、均勻,也不會産生沖突
  • 缺點:僅限于位址大小 = 關鍵字集合的情況
    • 簡單,但不常用
    • 需要事先知道關鍵字的分布情況
    • 适合查找表較小且連續的情況

2、數字分析法

  • 抽取
    • 抽取方法是使用關鍵字的一部分來計算散列存儲位置的方法。
    • 散列函數中常常用到的手段
  • 假設關鍵字集合中的每個關鍵字key 都由s 位數字組成(k1, k2, k3, ···,kn),分析key 中的全體資料,并從中提取分布均勻的若幹位或他們的組合構成全體。
    • 分布均勻的意思是,不容易重複或沖突。
  • 通常用于處理關鍵字位數較長的情況

如果事先知道關鍵字的分布且關鍵字的若幹位分布較均勻,就可以考慮用這個方法。

【細談資料結構】最最最詳細的散清單(哈希表)講解!!!(二)

3、平方取中法

  • 關鍵字的每一位都有某些數字重複出現頻率很高的現象,可以先求關鍵字的平方值,通過平方擴大差異,而後取中間數作為最終存儲位址

适合于不知道關鍵字的分布,而位數又不是很大的情況。

4、折疊法

  • 将關鍵字從左到右分割成位數相等的幾部分
    • 最後一部分位數不夠可以短些
    • 将這幾部分疊加求和
    • 并按照散清單表長,取後幾位作為散列位址
  • 有時這可能還不能夠保證分布均勻,不妨從一端向另外一端來回折疊後對齊相加。

事先不需要知道關鍵字的分布,适合關鍵字位數較多的情況。

5、除留餘數法

  • 常用的構造散列函數方法
    • H(key)= key MOD p
      • p <= m
      • m 為表長
  • 如何選取p 為關鍵
    • 本方法的關鍵在于選取合适的p,p如果選的不好,可能會容易産生同義詞
    • p 應為小于等于m,最好是接近m 的最小質數
      • 質數:大于1的自然數,并且隻能被1和本身整除
    • 或是不包含小于20 質因子的合數
      • 質因子:質數的因子
      • 合數: 整數中除了能被1和本身整除外,還能被0除外的其他數整除的數
      • 合數的性質:
        • 1、所有大于2的偶數都是合數
        • 2、所有大于5的奇數中,個位為5的都是合數
        • 3、除0以外,所有個位為0的自然數都是合數

這樣可以減少位址的重複(沖突)

6、随機數法

  • 選擇一個随機數,取關鍵字的随機函數值為它的散列位址
  • H(key)= Random(key)
    • random 為随機函數

關鍵字的長度不等,采用該方法比較合适

3、采用散列函數的參考因素:

既然有那麼多種方法,那我具體該用哪一種呢?

選擇困難症發作······

别着急,我這裡有一份參考标準,你隻要綜合這些因素,就能決策選擇哪種散列函數更合适了:

  1. 計算散列位址所需的時間
  2. 關鍵字的長度
  3. 散清單的大小
  4. 關鍵字的分布情況:關鍵字分布是否均勻,是否有規律可循
  5. 記錄查找的頻率

設計的散列函數在滿足以上條件的情況下盡量減少沖突

4、解決散列沖突:

講了這麼久的散列函數結構,那麼我們接下來的重頭戲來了,就算你散列函數設計的再好,但是資料那麼多,你難免會遇到沖突。

當我們遇到沖突的時候,程式又不是像你一樣,聰明機靈,會懂得去找别的位址。他隻是一個憨憨的愣頭青,遇到困難隻會傻傻的停在那裡。是以我們需要為他規劃Plan B。

散清單沖突的解決方法有四種:

  1. 開方定址法
  2. 再散列函數法
  3. 鍊位址法
  4. 公共溢出區法

接下來我們來詳細的講解四種方法:

1、開方定制法

一旦發生沖突,就去尋找下一個空的散列位址

  • 隻要散清單足夠大,空的散列位址總能找到,并将記錄存入
  • fi( key) = ( f ( key ) + di ) MOD m
    • di = 1, 2, 3, ···, m - 1

例子:

  • 散列函數f( key ) = key mod 12
  • key = 37 時,發現f ( 37 ) = 1,與25 所在位置發生沖突
  • 采用上面公式
    • f ( 37) = ( f ( 37 ) + 1 ) mod 12 = 2
    • 于是将37 存入下标為2 的位置

解決沖突的三種方法:

  1. 線性探測法
    • 通過不斷的增大di 的值來尋找空的散列位址:di = di++
    • 堆積
      • 如果碰到48 和 37 這種本來不是同義詞卻需要争奪一個位址的情況,稱為堆積
      • 堆積的出現,使得我們需要不斷處理沖突,無論是存入還是查找效率都會大大降低
  2. 二次探測法
    • 線性是不斷的向後探索,但是如果它前面還有一個空位置,可是我們卻不斷向後求,雖然也能得出結果,但是效率很差。
    • 是以我們可以采用雙向尋找到可能的位置。
    • 二次探測法就是:增加平方運算的目的是為了不讓關鍵字都聚集在某一塊區域
      • fi ( key ) = ( f ( key ) + di ) MOD m
      • di = 12, -12, 22, -22 ···
  3. 随機探測法
    • di 是一組僞随機數列
    • 在沖突時,對于位移量di 采用随機函數計算得到
      • 這裡使用的随機函數是僞随機函數
      • 因為使用的随機種子是相同的,是以不斷調用随機函數可以生成不會重複的數列。
    • 查找
      • 若我們的随機種子是相同的,每次得到的數列也是相同的,相同的di 當然可以得到相同的散列位址
      • fi ( key ) = ( f ( key ) + di ) MOD m
        • di 是一個随機數列

總之,開方定址法隻要在散清單未填滿時,總能找到不發生沖突的位址。是我們常用的解決沖突的方法。

2、再散列函數法

  • 準備若幹個散列函數,若該散列函數沖突,則使用下一個
    • fi ( key ) = RHi ( key )
      • i = 1, 2, ···, k
      • RHi:就是不同的散列函數

這種方法使得關鍵字不産生聚集,當然,相應地也增加了計算的時間。

3、鍊位址法

  • 不使用其他空間,直接在原地解決沖突
  • 在散清單中隻存儲所有同義詞子表的頭指針
    • 同義詞子表
      • 将所有關鍵字為同義詞的記錄存儲在一個單連結清單中
  • 優點:有效的處理了沖突,為其提供了絕不會找不到位址的保障
  • 缺點:查找時需要周遊單連結清單的性能損耗
【細談資料結構】最最最詳細的散清單(哈希表)講解!!!(二)

4、公共溢出區法

  • 建立一個特殊存儲空間,專門存放沖突的資料
  • 在查找時
    • 對給定值通過散列函數計算出散列位址後
    • 先于基本表的相應位置進行對比
      • 相等,查找成功
      • 不相等,到溢出表裡進行順序查找

适用于資料和沖突較少的情況

【細談資料結構】最最最詳細的散清單(哈希表)講解!!!(二)

既然我們已經解決了沖突的問題,那麼現在就最後補充三個關于查找的知識點。

5、散清單的查找

查找過程和造表過程一緻

假設采用開放位址法處理沖突,查找過程為:

  1. 對于給定的key,計算hash 位址index = f(key)
  2. 如果數組 arr[index] 的值為空,則查找不成功
  3. 如果數組 arr[index] == key,則查找成功

    否則,使用沖突解決方法求下一個位址,直到

    arr[index] == key or arr[index] == null

6、散清單查找算法實作

  • 首先是需要定義一個散清單的結構以及一些相關的常數
    • HashTable:散清單結構
    • 結構中的elem:動态數組

7、散清單的查找效率

決定散清單查找的ASL 因素

  1. 用的散列函數
  2. 選用的處理沖突的方法
  3. 散清單的飽和度,裝載因子α = n / m
    • n 表示實際裝載資料長度
    • m 為表長

一般情況下,假設散列函數是均勻的,則在讨論ASL 時可以不考慮它的因素。

散列的ASL 是處理沖突方法和裝載因子的函數

散清單的理論到這裡就結束了,接下來的那篇,也是我們散清單系列的最後一篇,會具體講講散清單如何實作。

以上就是本篇文章的所有内容了,如果覺得有幫助到你的話,

麻煩動動小手,點贊收藏轉發!!!

你的每一次點贊都是我更新的最大動力~

我們下期再見!

繼續閱讀