建站
咨詢
售后
建站咨詢
新聞中心
php 的源碼實(shí)現(xiàn)中，很多數(shù)據(jù)是用一張hash表維護(hù)的，比如對(duì)象的方法，數(shù)組等
成都創(chuàng)新互聯(lián)公司主要從事網(wǎng)站設(shè)計(jì)制作、成都網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)白云鄂,十余年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專(zhuān)業(yè),歡迎來(lái)電咨詢建站服務(wù):028-86922220
基本概念
哈希表是一種通過(guò)哈希函數(shù)，將特定的鍵映射到特定值的一種數(shù)據(jù)結(jié)構(gòu)，它維護(hù)鍵和值之間一一對(duì)應(yīng)關(guān)系。
鍵(key)：用于操作數(shù)據(jù)的標(biāo)示，例如PHP數(shù)組中的索引，或者字符串鍵等等。
槽(slot/bucket)：哈希表中用于保存數(shù)據(jù)的一個(gè)單元，也就是數(shù)據(jù)真正存放的容器。
哈希函數(shù)(hash function)：將key映射(map)到數(shù)據(jù)應(yīng)該存放的slot所在位置的函數(shù)。
哈希沖突(hash collision)：哈希函數(shù)將兩個(gè)不同的key映射到同一個(gè)索引的情況。
但是hash算法再好，在無(wú)線的數(shù)據(jù)下，總會(huì)出現(xiàn)不同key對(duì)應(yīng)相同值的情況，應(yīng)為hash后的值是等長(zhǎng)的，而這個(gè)時(shí)候，就是hash沖突了，解決沖突目前有兩個(gè)方法，鏈表發(fā)和尋址法
沖突解決 鏈接法
鏈接法通過(guò)使用一個(gè)鏈表來(lái)保存slot值的方式來(lái)解決沖突，也就是當(dāng)不同的key映射到一個(gè)槽中的時(shí)候使用鏈表來(lái)保存這些值。所以使用鏈接法是在最壞的情況下，也就是所有的key都映射到同一個(gè)槽中了，這樣哈希表就退化成了一個(gè)鏈表，這樣的話操作鏈表的時(shí)間復(fù)雜度則成了O(n)，這樣哈希表的性能優(yōu)勢(shì)就沒(méi)有了，所以選擇一個(gè)合適的哈希函數(shù)是最為關(guān)鍵的。
弱點(diǎn)
由于目前大部分的編程語(yǔ)言的哈希表實(shí)現(xiàn)都是開(kāi)源的，大部分語(yǔ)言的哈希算法都是公開(kāi)的算法，雖然目前的哈希算法都能良好的將key進(jìn)行比較均勻的分布，而這個(gè)假使的前提是key是隨機(jī)的，正是由于算法的確定性，這就導(dǎo)致了別有用心的***能利用已知算法的可確定性來(lái)構(gòu)造一些特殊的key，讓這些key都映射到同一個(gè)槽位導(dǎo)致哈希表退化成單鏈表，導(dǎo)致程序的性能急劇下降，從而造成一些應(yīng)用的吞吐能力急劇下降，尤其是對(duì)于高并發(fā)的應(yīng)用影響很大，通過(guò)大量類(lèi)似的請(qǐng)求可以讓服務(wù)器遭受DoS(服務(wù)拒絕***)，這個(gè)問(wèn)題一直就存在著，只是最近才被各個(gè)語(yǔ)言重視起來(lái)。
哈希沖突***利用的哈希表最根本的弱點(diǎn)是：開(kāi)源算法和哈希實(shí)現(xiàn)的確定性以及可預(yù)測(cè)性，這樣***者才可以利用特殊構(gòu)造的key來(lái)進(jìn)行***。要解決這個(gè)問(wèn)題的方法則是讓***者無(wú)法輕易構(gòu)造能夠進(jìn)行***的key序列。
開(kāi)放尋址法
通常還有另外一種解決沖突的方法：開(kāi)放尋址法。使用開(kāi)放尋址法是槽本身直接存放數(shù)據(jù)，在插入數(shù)據(jù)時(shí)如果key所映射到的索引已經(jīng)有數(shù)據(jù)了，這說(shuō)明發(fā)生了沖突，這是會(huì)尋找下一個(gè)槽，如果該槽也被占用了則繼續(xù)尋找下一個(gè)槽，直到尋找到?jīng)]有被占用的槽，在查找時(shí)也使用同樣的策律來(lái)進(jìn)行。
由于開(kāi)放尋址法處理沖突的時(shí)候占用的是其他槽位的空間,這可能會(huì)導(dǎo)致后續(xù)的key在插入的時(shí)候更加容易出現(xiàn)哈希沖突，所以采用開(kāi)放尋址法的哈希表的裝載因子不能太高，否則容易出現(xiàn)性能下降。
裝載因子是哈希表保存的元素?cái)?shù)量和哈希表容量的比，通常采用鏈接法解決沖突的哈希表的裝載 因子最好不要大于1，而采用開(kāi)放尋址法的哈希表最好不要大于0.5。
網(wǎng)站名稱(chēng)：php源碼學(xué)習(xí)日志hash表
當(dāng)前URL：http://fisionsoft.com.cn/article/gsihhc.html
