中国体彩网唯一官网
首頁 > php教程 > C#.Net教程 > 正文

數據結構中散列表(哈希表)經典之沖突處理

原創 2019-04-04 14:46:48 0 778
第六期線上培訓班
散列是在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系f,使得每個關鍵字key對應一個存儲位置f(key),建立了關鍵字與存儲位置的相互對應關系,這種關系 f 稱為散列函數(哈希函數)。本文小編主要講述散列函數的沖突處理問題。


未標題-1.jpg

查找過程中,關鍵碼的比較次數,取決于產生沖突的多少,產生的沖突少,查找效率就高,產生的沖突多,查找效率就低。因此,影響產生沖突多少的因素,也就是影響查找效率的因素。影響產生沖突多少有以下三個因素:

1. 散列函數是否均勻;

2. 處理沖突的方法;

3. 散列表的裝填因子。

散列表的裝填因子定義為:α= 填入表中的元素個數 / 散列表的長度

α是散列表裝滿程度的標志因子。由于表長是定值,α與“填入表中的元素個數”成正比,所以,α越大,填入表中的元素較多,產生沖突的可能性就越大;α越小,填入表中的元素較少,產生沖突的可能性就越小。

實際上,散列表的平均查找長度是裝填因子α的函數,只是不同處理沖突的方法有不同的函數。

解決哈希沖突的方法一般有:

NO.1開放定址法

所謂的開放定址法就是一旦發生了沖突,就去尋找下一個空的散列地址,只要散列表足夠大,空的散列地址總能找到,并將記錄存入。

公式:f(key)=(f(key)+di)%m(di=1,2,3….m-1)

比如說,關鍵字集合為{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34},表長為12。散列函數f(key) = key mod 12。

當計算前5個數{12, 67, 56, 16, 25}時,都是沒有沖突的散列地址,直接存入;計算key = 37時,發現f(37) = 1,此時就與25所在的位置沖突。于是應用上面的公式f(37) = (f(37) + 1) mod 12 =2,。于是將37存入下標為2的位置。接下來22,29,15,47都沒有沖突,正常的存入。到了48,計算得到f(48) = 0,與12所在的0位置沖突了,不要緊,我們f(48) = (f(48) + 1) mod 12 = 1,此時又與25所在的位置沖突。于是f(48) = (f(48) + 2) mod 12 = 2,還是沖突......一直到f(48) = (f(48) + 6) mod 12 = 6時,才有空位,如下表所示。

序號01234567891011
關鍵字1225

16

6756


NO.2再哈希法

對于散列表來說,可以事先準備多個散列函數。

公式:fi(key)=RHi(key)(i=1,2,3…,k)

這里RHi 就是不同的散列函數,可以把除留余數、折疊、平方取中全部用上。每當發生散列地址沖突時,就換一個散列函數計算。

這種方法能夠使得關鍵字不產生聚集,但相應地也增加了計算的時間。

NO.3鏈地址法(拉鏈法)

將所有關鍵字為同義詞的記錄存儲在一個單鏈表中,稱這種表為同義詞子表,在散列表中只存儲所有同義詞子表前面的指針。對于關鍵字集合{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34},用前面同樣的12為余數,進行除留余數法,可以得到下圖結構。

1554359872619087.png

NO.4建立公共溢出區

這個方法是當你時重新給你找個地址,為所有沖突的關鍵字建立一個公共的溢出區來存放。

就前面的例子而言,共有三個關鍵字37、48、34與之前的關鍵字位置有沖突,那就將它們存儲到溢出表中。如下圖所示。

1554360040919771.png

在查找時,對給定值通過散列函數計算出散列地址后,先與基本表的相應位置進行比對,如果相等,則查找成功;如果不相等,則到溢出表中進行順序查找。如果相對于基本表而言,有沖突的數據很少的情況下,公共溢出區的結構對查找性能來說還是非常高的。

【推薦課程:C++相關課程

以上就是數據結構中散列表(哈希表)經典之沖突處理的詳細內容,更多請關注php中文網其它相關文章!

php中文網最新課程二維碼
  • 相關標簽:C++ 數據結構 散列表
  • 本文原創發布php中文網 ,轉載請注明出處,感謝您的尊重!
  • 相關文章


  • php數據結構和算法
  • PHP數據結構基礎之雙鏈表
  • PHP實現的棧數據結構示例講解
  • PHP數據結構基礎之遞歸
  • Python中數據結構與算法的應用(附示例)
  • 數據結構:堆棧和隊列之間的差異
  • 數據結構中散列表(哈希表)經典之沖突處理
  • 網友評論

    文明上網理性發言,請遵守 新聞評論服務協議

    我要評論
    獨孤九賤(5)_ThinkPHP5視頻教程

    獨孤九賤(5)_ThinkPHP5視頻教程

    ThinkPHP是國內最流行的中文PHP開發框架,也是您Web項目的最佳選擇。《php.cn獨孤九賤(5)-ThinkPHP5視頻教程》課程以ThinkPHP5最新版本為例,從最基本的框架常識開始,將...

    獨孤九賤(4)_PHP視頻教程

    獨孤九賤(4)_PHP視頻教程

    江湖傳言:PHP是世界上最好的編程語言。真的是這樣嗎?這個梗究竟是從哪來的?學會本課程,你就會明白了。 PHP中文網出品的PHP入門系統教學視頻,完全從初學者的角度出發,絕不玩虛的,一切以實用、有用...

    獨孤九賤(1)_HTML5視頻教程

    獨孤九賤(1)_HTML5視頻教程

    《php.cn原創html5視頻教程》課程特色:php中文網原創幽默段子系列課程,以惡搞,段子為主題風格的php視頻教程!輕松的教學風格,簡短的教學模式,讓同學們在不知不覺中,學會了HTML知識。 ...

    ThinkPHP5實戰之[教學管理系統]

    ThinkPHP5實戰之[教學管理系統]

    本套教程,以一個真實的學校教學管理系統為案例,手把手教會您如何在一張白紙上,從零開始,一步一步的用ThinkPHP5框架快速開發出一個商業項目。

    PHP入門視頻教程之一周學會PHP

    PHP入門視頻教程之一周學會PHP

    所有計算機語言的學習都要從基礎開始,《PHP入門視頻教程之一周學會PHP》不僅是PHP的基礎部分更主要的是PHP語言的核心技術,是學習PHP必須掌握的內容,任何PHP項目的實現都離不開這部分的內容,通...

    相關視頻教程

  • 數據結構探險—隊列篇 數據結構探險—隊列篇
  • 數據結構探險之棧篇 數據結構探險之棧篇
  • 數據結構探險之線性表篇 數據結構探險之線性表篇
  • 相關視頻章節

    第六期線上培訓班 中国体彩网唯一官网