数据结构—— 构造散列函数的六种方法【直接定址法-数字分析法-平方取中法-折叠法-除留余数法-随机数法】
目錄：
一：直接定址法
二：數(shù)字分析法
三：平方取中法
四：折疊法
五：除留余數(shù)法
六：隨機數(shù)法
這些方法原理都是將原來數(shù)字按某種規(guī)律變成另一個數(shù)字
一：直接定址法
取關(guān)鍵字的某個線性函數(shù)值作為散列地址：
?
直接定址法獲取得到的散列函數(shù)有點就是簡單，均勻也不會產(chǎn)生沖突
但問題是這需要事先知道關(guān)鍵字的分布情況
?
適合查找表較小且連續(xù)的情況
由于這樣的限制，在現(xiàn)實應(yīng)用中，此方法雖然簡單，但卻并不常用
?
二：數(shù)字分析法
如果關(guān)鍵字是位數(shù)較多的數(shù)字（比如手機號），且這些數(shù)字部分存在相同規(guī)律
則可以采用抽取剩余不同規(guī)律部分作為散列地址
?
比如手機號前三位是接入號，中間四位是 HLR 識別號，只有后四位才是真正的用戶號
也就是說，如果手機號作為關(guān)鍵字，那么極有可能前 7 位是相同的
此時我們選擇后四位作為散列地址就是不錯的選擇
?
同時，對于抽取出來的數(shù)字，還可以再進行反轉(zhuǎn)
右環(huán)位移，左環(huán)位移等操作
?
目的就是為了提供一個能夠盡量合理地將關(guān)鍵字分配到散列表的各個位置的散列函數(shù)
數(shù)字分析法通常適合處理關(guān)鍵字位數(shù)比較大的情況
如果事先知道關(guān)鍵字的分布且關(guān)鍵字的若干位分布較均勻，就可以考慮用這個方法
?
三：平方取中法
即取關(guān)鍵字平方的中間位數(shù)作為散列地址
?
比如假設(shè)關(guān)鍵字是 4321，那么它的平方就是 18671041，抽取中間的 3 位就可以是 671，也可以是 710，用做散列地址
平方取中法比較適合于不知道關(guān)鍵字的分布，而位數(shù)又不是很大的情況
?
四：折疊法
折疊法是將關(guān)鍵字從左到右分割成位數(shù)相等的幾部分（注意最后一部分位數(shù)不夠時可以短些）
然后將這幾部分疊加求和
并按散列表表長，取后幾位作為散列地址
?
比如假設(shè)關(guān)鍵字是 9876543210，散列表表長為三位
則我們可以將它分為四組 987|654|321|0
然后將它們疊加求和 987+654+321+0=1962
再取后 3 位得到散列地址即為 962
?
有時可能這還不能夠保證分布均勻
那么也可以嘗試從一端到另一端來回折疊后對齊相加
比如講 987 和 321 反轉(zhuǎn)
再與 654 和 0 相加，變成 789+654+123+0=1566
此時散列地址為 566
折疊法事先不需要知道關(guān)鍵字的分布，適合關(guān)鍵字位數(shù)較多的情況
?
五：除留余數(shù)法
此方法為最常用的構(gòu)造散列函數(shù)方法
對于散列表長為的散列函數(shù)公式為：
很顯然，本方法的關(guān)鍵就在于選擇合適的?
根據(jù)前輩們的經(jīng)驗
若散列表表長為
通常?為小于或等于表長（最好接近）的最小質(zhì)數(shù)或不包含小于 20 質(zhì)因子的合數(shù)
?
六：隨機數(shù)法
選擇一個隨機數(shù)
取關(guān)鍵字的隨機函數(shù)值為它的散列地址：
?
當關(guān)鍵字的長度不等時采用這個方法構(gòu)造散列函數(shù)是比較合適的
總結(jié)
以上是生活随笔為你收集整理的数据结构—— 构造散列函数的六种方法【直接定址法-数字分析法-平方取中法-折叠法-除留余数法-随机数法】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 中国物流产业发展形势与竞争格局展望报告2
- 下一篇： 使用Mediacoder压制带有图片的a