數(shù)據(jù)結構課件c語言-在線瀏覽
2025-07-17 21:43本頁面
【正文】 查找 我們希望能找到盡可能 產生均勻映射的 哈希函數(shù)，從而盡可能降低發(fā)生沖突的概率；哈希方法需要解決以下兩個問題： ⑴ 盡量構造好的哈希函數(shù)， 好的哈希函數(shù)有三個方面的含義： 一是 所構造的函數(shù)應該盡可能簡單，以便提高哈希地址的計算速度； 二是 所構造的函數(shù)應該盡量減少存儲空間的浪費； 三是 根據(jù)所選函數(shù)計算出的地址，應在哈希地址集中大致均勻分布，減少沖突。 第 8章 查找 8. 哈希函數(shù)的構造方法 ? 1. 直接定址法 【 構造 】 取關鍵字或關鍵字的某個線性函數(shù)作哈希地址，即 H(key)=key 或 H(key)=a 【特點】 ? 直接定址法所得地址集合與關鍵字集合大小相等，不會發(fā)生沖突 ? 實際中能用這種哈希函數(shù)的情況很少 第 8章 查找 2. 數(shù)字分析法 【 構造 】 對 關鍵字 進行分析，取關鍵字的若干位或其組合作哈希地址。 11 0611 2 01 樓號 層號 房間號 【 特點 】 適于關鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關鍵字事先知道的情況。 第 8章 查找 4. 折疊法 ? 構造：將關鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的 疊加 和（舍去進位）做哈希地址 ? 種類 187。間界疊加 ：從一端沿分割界來回折送，然后對齊相加 ? 適于關鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻情況 第 8章 查找 例 關鍵字為 ： 0442205864，哈希地址位數(shù)為 4 5 8 6 4 4 2 2 0 0 4 1 0 0 8 8 H(key)=0088 移位疊加 5 8 6 4 0 2 2 4 0 4 6 0 9 2 H(key)=6092 間界疊加 第 8章 查找 5. 除留余數(shù)法 ?構造： 取關鍵字被某個不大于哈希表表長 m的數(shù) p除后所得余數(shù)作哈希地址，即 H(key)=key MOD p， p?m ?特點 ?簡單、常用，可與上述幾種方法結合使用 ?p的選取很重要； p選的不好，容易產生同義詞 第 8章 查找 ? 例：設有關鍵碼序列 {2049， 1756， 0056， 3187， 4356， 6349} 若 p = 100， 則對應的哈希地址就是關鍵碼的后兩位即 49， 56， 56， 87， 56， 49，很不均勻 ? 實踐證明 一般選取 p=m的最大質數(shù)效果比較好。,1178。,2178。,?? 177。(k?m/2) ? 偽隨機探測再散列： di=偽隨機數(shù)序列 第 8章 查找 例 表長為 11的哈希表中已填有關鍵字為 17， 60， 29的記錄， H(key)=key MOD 11,現(xiàn)有第 4個記錄，其關鍵字為 38， 按三種處理沖突的方法，將它填入表中 0 1 2 3 4 5 6 7 8 9 10 60 17 29 (1) H(38)=38 MOD 11=5 沖突 H1=(5+1) MOD 11=6 沖突 H2=(5+2) MOD 11=7 沖突 H3=(5+3) MOD 11=8 不沖突 38 (2) H(38)=38 MOD 11=5 沖突 H1=(5+1178。) MOD 11=4 不沖突 38 (3) H(38)=38 MOD 11=5 沖突 設偽隨機數(shù)序列為 9，則： H1=(5+9) MOD 11=3 不沖突 38 第 8章 查找 2. 再哈希法 ?方法 ： 構造若干個哈希函數(shù)，當發(fā)生沖突時，計算下一個哈希地址，即： Hi=Rhi(key) i=1,2,……k 其中： Rhi—— 不同的哈希函數(shù) ?特點 ： 計算時間增加 第 8章 查找 3. 鏈地址法（拉鏈法） ?方法 ： 將所有關鍵字為同義詞的
法律信息相關推薦
鄂ICP備17016276號-1