細談散清單系列一共有三篇文章
1、散清單的概述
2、散列函數的作用與構造
3、散清單查找的代碼實作
文章目錄
-
- 細談散清單系列一共有三篇文章
- 1、查找時的:散列函數?
- 2、散列函數的構造方法
-
-
- 1、直接定址法
- 2、數字分析法
- 3、平方取中法
- 4、折疊法
- 5、除留餘數法
- 6、随機數法
-
- 3、采用散列函數的參考因素:
- 4、解決散列沖突:
-
-
- 1、開方定制法
- 2、再散列函數法
- 3、鍊位址法
- 4、公共溢出區法
-
- 5、散清單的查找
- 6、散清單查找算法實作
- 7、散清單的查找效率
上篇文章我們提到,散列函數在存儲時會發生沖突,并且也解釋了沖突是如何産生的。
但我們先不着急去解決沖突的問題,我們首先來補充一個概念,散清單是基于散列函數建立的一種查找表。
那散列函數在查找中,具體是幹什麼的呢?
别急,本章内容就帶你了解散列函數的作用以及構造
1、查找時的:散列函數?
- 散列函數就是根據key 計算出應該存儲位置的位置;
- 根據這個函數和查找關鍵字key,可以直接确定查找值所在位置;
- 位址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 為表長
- H(key)= key MOD p
- 如何選取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、采用散列函數的參考因素:
既然有那麼多種方法,那我具體該用哪一種呢?
選擇困難症發作······
别着急,我這裡有一份參考标準,你隻要綜合這些因素,就能決策選擇哪種散列函數更合适了:
- 計算散列位址所需的時間
- 關鍵字的長度
- 散清單的大小
- 關鍵字的分布情況:關鍵字分布是否均勻,是否有規律可循
- 記錄查找的頻率
設計的散列函數在滿足以上條件的情況下盡量減少沖突
4、解決散列沖突:
講了這麼久的散列函數結構,那麼我們接下來的重頭戲來了,就算你散列函數設計的再好,但是資料那麼多,你難免會遇到沖突。
當我們遇到沖突的時候,程式又不是像你一樣,聰明機靈,會懂得去找别的位址。他隻是一個憨憨的愣頭青,遇到困難隻會傻傻的停在那裡。是以我們需要為他規劃Plan B。
散清單沖突的解決方法有四種:
- 開方定址法
- 再散列函數法
- 鍊位址法
- 公共溢出區法
接下來我們來詳細的講解四種方法:
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 的位置
解決沖突的三種方法:
- 線性探測法
- 通過不斷的增大di 的值來尋找空的散列位址:di = di++
- 堆積
- 如果碰到48 和 37 這種本來不是同義詞卻需要争奪一個位址的情況,稱為堆積
- 堆積的出現,使得我們需要不斷處理沖突,無論是存入還是查找效率都會大大降低
- 二次探測法
- 線性是不斷的向後探索,但是如果它前面還有一個空位置,可是我們卻不斷向後求,雖然也能得出結果,但是效率很差。
- 是以我們可以采用雙向尋找到可能的位置。
- 二次探測法就是:增加平方運算的目的是為了不讓關鍵字都聚集在某一塊區域
- fi ( key ) = ( f ( key ) + di ) MOD m
- di = 12, -12, 22, -22 ···
- 随機探測法
- di 是一組僞随機數列
- 在沖突時,對于位移量di 采用随機函數計算得到
- 這裡使用的随機函數是僞随機函數
- 因為使用的随機種子是相同的,是以不斷調用随機函數可以生成不會重複的數列。
- 查找
- 若我們的随機種子是相同的,每次得到的數列也是相同的,相同的di 當然可以得到相同的散列位址
- fi ( key ) = ( f ( key ) + di ) MOD m
- di 是一個随機數列
總之,開方定址法隻要在散清單未填滿時,總能找到不發生沖突的位址。是我們常用的解決沖突的方法。
2、再散列函數法
- 準備若幹個散列函數,若該散列函數沖突,則使用下一個
- fi ( key ) = RHi ( key )
- i = 1, 2, ···, k
- RHi:就是不同的散列函數
- fi ( key ) = RHi ( key )
這種方法使得關鍵字不産生聚集,當然,相應地也增加了計算的時間。
3、鍊位址法
- 不使用其他空間,直接在原地解決沖突
- 在散清單中隻存儲所有同義詞子表的頭指針
- 同義詞子表
- 将所有關鍵字為同義詞的記錄存儲在一個單連結清單中
- 同義詞子表
- 優點:有效的處理了沖突,為其提供了絕不會找不到位址的保障
- 缺點:查找時需要周遊單連結清單的性能損耗
4、公共溢出區法
- 建立一個特殊存儲空間,專門存放沖突的資料
- 在查找時
- 對給定值通過散列函數計算出散列位址後
- 先于基本表的相應位置進行對比
- 相等,查找成功
- 不相等,到溢出表裡進行順序查找
适用于資料和沖突較少的情況
既然我們已經解決了沖突的問題,那麼現在就最後補充三個關于查找的知識點。
5、散清單的查找
查找過程和造表過程一緻
假設采用開放位址法處理沖突,查找過程為:
- 對于給定的key,計算hash 位址index = f(key)
- 如果數組 arr[index] 的值為空,則查找不成功
-
如果數組 arr[index] == key,則查找成功
否則,使用沖突解決方法求下一個位址,直到
arr[index] == key or arr[index] == null
6、散清單查找算法實作
- 首先是需要定義一個散清單的結構以及一些相關的常數
- HashTable:散清單結構
- 結構中的elem:動态數組
7、散清單的查找效率
決定散清單查找的ASL 因素
- 用的散列函數
- 選用的處理沖突的方法
- 散清單的飽和度,裝載因子α = n / m
- n 表示實際裝載資料長度
- m 為表長
一般情況下,假設散列函數是均勻的,則在讨論ASL 時可以不考慮它的因素。
散列的ASL 是處理沖突方法和裝載因子的函數
散清單的理論到這裡就結束了,接下來的那篇,也是我們散清單系列的最後一篇,會具體講講散清單如何實作。
以上就是本篇文章的所有内容了,如果覺得有幫助到你的話,
麻煩動動小手,點贊收藏轉發!!!
你的每一次點贊都是我更新的最大動力~
我們下期再見!