哈希表(散列表)基礎(chǔ)

引入哈希表

什么是哈西表：
　　一種具有相同特性的數(shù)據(jù)元素的集合，每個元素具有唯一標(biāo)識自己的關(guān)鍵字。
基本原理：
　　說明：
　　　　順序查找、二分查找或者二叉樹的查找是基于待查關(guān)鍵字與表中元素的關(guān)鍵字進(jìn)行比較而實現(xiàn)的查找方法。
　　　　散列查找是通過計算哈希函數(shù)來得到待查關(guān)鍵字的地址，理論上在哈希表中查找元素?zé)o需進(jìn)行關(guān)鍵字間的比較。
　　　　計算哈希函數(shù)給出地址，從而找到元素K.
　　
　　 例如：
　　　　假設(shè)有一個關(guān)鍵字序列18,75,60,43,54,90,46，給定哈希函數(shù)H(k)=k % 13，存貯區(qū)的內(nèi)存地址從0到15，則可以得到每個關(guān)鍵字的散列地址：
　　　　　　H(18) = 18%13 = 5 H(75) = 75%13 = 10
　　　　　　H(60) = 60%13 = 8 H(43) = 43%13 = 4
　　　　　　H(54) = 54%13 = 2 H(90) = 90%13 = 12
　　　　根據(jù)散列地址，將7個關(guān)鍵字序列存儲到一個一維數(shù)組(哈希表)中：
　　　　H(46) = 46%13 = 7
　　
　　 小結(jié)：
　　　　存儲記錄時，通過散列函數(shù)計算出記錄的存儲位置并按此存儲位置存儲記錄：記錄位置 ＝ Hash(記錄的關(guān)鍵字)
　　　　訪問記錄時，利用散列函數(shù)計算存儲位置，然后根據(jù)存儲位置訪問記錄。

散列函數(shù)的構(gòu)造方法

　　1.直接定址法：
　　　　H(key)=a*key+b a 和 b均為常數(shù)
　　2.數(shù)字分析法：
　　　　分析關(guān)鍵字的各個位的構(gòu)成，截取其中若干位作為散列函數(shù)值，盡可能使關(guān)鍵字具有大的敏感度。
　　　　
　　3.平方取中法：
　　　　這種方法是先求關(guān)鍵字的平方值，然后在平方值中取中間幾位為散列函數(shù)的值。因為一個數(shù)平方后的中間幾位和原數(shù)的每一位都相關(guān)，因此，使用隨機(jī)分布的關(guān)鍵字得到的記錄的存儲位置也是隨機(jī)的。
　　4.折疊法：
　　　　將關(guān)鍵字分割成位數(shù)相同的幾部分(最后一部分的位數(shù)可以不同)，然后取這幾部分的疊加和(舍去進(jìn)位)作為散列函數(shù)的值，稱為折疊法。
　　　　例如，假設(shè)關(guān)鍵字為某人身份證號碼430104681015355，則可以用4位為一組進(jìn)行疊加，即有5355＋8101＋1046＋430＝14932，舍去高位，則有H(430104681015355)＝4932。
　　5.除留余數(shù)法：
　　　　Hash(key) = key % p
　　　　其中，p為不大于散列表表長m的整數(shù)

?解決沖突的方法

1.開放地址法：

　　?開放定址法就是從發(fā)生沖突的那個單元開始，按照一定的次序，從哈希表中找出一個空閑的存儲單元，把發(fā)生沖突的待插入關(guān)鍵字存儲到該單元中，從而解決沖突。在哈希表未填滿時，處理沖突需要的“下一個”空地址在哈希表中解決。
　　?公式：Hi = (H(key)+di) MOD m i=1,2,…K(K<=m-1) di為增量序列、m為散列表長度。
　　?根據(jù)di的取值，細(xì)分為：
　　? 線性探測再散列
　　　　?
　　　　? 若一個關(guān)鍵字在地址d處發(fā)生沖突，則依次探查d+1，d+2，…，達(dá)到表尾時，又從0，1，2，….開始探查，直到找到一個空閑位置來存儲沖突的關(guān)鍵字。
　　　　? d1= 1 d2= 2 d3= 3 … dm-1= m-1
　　? 二次探測再散列
　　　　? 假設(shè)哈希表的地址為0~m-1，則哈希表的長度為m。若一個關(guān)鍵字在地址d處發(fā)生沖突，則依次探查位置d+1²，d-1², d+2², d-2², …, 直到找到一個空閑位置為止。
　　　　? Hi = (H(key)+di) MOD m i = 1,2,…,k (k≤m-1)
　　　　? d1= 1² d2= -1² d3= 2² d4= -2² …

2.鏈地址法

　　?鏈地址法也稱為拉鏈法 ，是將所有關(guān)鍵字為同義詞的記錄存儲在同一個線性鏈表中。
　　? 實例：
　　　　? 例如: 給定關(guān)鍵字序列如下，散列函數(shù)為H(k)=k%13 。19，14，23，1，68，20，84，27，55，11，10，79 試用鏈地址法建立散列表。
　　　　? 計算散列值:
　　　　?
　　　　?

散列查找

流程圖

散列查找性能分析：

　　線性探測法：
　　

說明：

　　a為裝填因子= n/m 其中n=存入的元素個數(shù)，m=哈希表的大小

　　鏈地址法：
　　

?

轉(zhuǎn)載于:https://www.cnblogs.com/MrSaver/p/6194593.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的数据结构：哈希表(散列表)基础的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。