Hash沖突及其解決方法 （學習筆記）

這裡寫目錄标題

• hash簡介
• hash沖突
• 解決hash沖突的方法
• • 一、開放定址法
  • 二、拉鍊法（鍊位址法）
  • 三、再hash
  • 四、建立公共溢出區

hash簡介

• Hash，一般翻譯做散列、雜湊，或音譯為哈希，是把任意長度的輸入（又叫做預映射pre-image）通過雜湊演算法變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，是以不可能從散列值來确定唯一的輸入值。簡單的說就是一種将任意長度的消息壓縮到某一固定長度的消息摘要的函數。

hash沖突

• 對不同的關鍵字可能得到同一散列位址，即key1≠key2，而f(key1)=f(key2)，這種現象就稱為hash沖突

解決hash沖突的方法

一、開放定址法

• 當關鍵字key的哈希位址 p=f(key) 現沖突時，以p為基礎，産生另一個哈希位址p1，如果p1仍然沖突，再以p為基礎，産生另一個哈希位址p2，…，直到找出一個不沖突的哈希位址pi ，将相應元素存入其中。
• Hi = ( h(key) + di ) Mod m

• 優點：1、記錄更容易進行序列化（serialize）操作

             2、如果記錄總數可以預知，可以建立完美哈希函數，此時處理資料的效率是非常高的

• 缺點：1、存儲記錄的數目不能超過桶數組的長度，如果超過就需要擴容，而擴容會導緻某次操作的時間成本飙升，這在實時或者互動式應用中可能會是一個嚴重的缺陷

二、拉鍊法（鍊位址法）

• 将所有哈希位址為 i 的元素構成一個稱為同義詞鍊的單連結清單，并将單連結清單的頭指針存在哈希表的第 i 個單元中，因而查找、插入和删除主要在同義詞鍊中進行。鍊位址法适用于經常進行插入和删除的情況。

• 優點：1、對于記錄總數頻繁可變的情況，處理的比較好（也就是避免了動态調整的開銷）

             2、由于記錄存儲在結點中，而結點是動态配置設定，不會造成記憶體的浪費，是以尤其适合那種記錄本身尺寸（size）很大的情況，因為此時指針的開銷可以忽略不計了

             3、删除記錄時，比較友善，直接通過指針操作即可

• 缺點：1、存儲的記錄是随機分布在記憶體中的，這樣在查詢記錄時，相比結構緊湊的資料類型（比如數組），哈希表的跳轉通路會帶來額外的時間開銷

三、再hash

• 即構造過個不同的哈希函數，當f1(key) 發生沖突時，使用f2(key)計算，直至不再産生沖突；
• 這種方法不易産生聚集，但增加了計算時間

四、建立公共溢出區

• 将哈希表分為基本表和溢出表兩部分，凡是和基本表發生沖突的元素，一律填入溢出表。