PHP用哈希表和鏈表解決哈希沖突的方法

本篇文章為大家展示了PHP用哈希表和鏈表解決哈希沖突的方法，代碼簡(jiǎn)明扼要并且容易理解，絕對(duì)能使你眼前一亮，通過(guò)這篇文章的詳細(xì)介紹希望你能有所收獲。

成都創(chuàng)新互聯(lián)公司專注于阿克塞哈薩克族自治網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠(chéng)為您提供阿克塞哈薩克族自治營(yíng)銷(xiāo)型網(wǎng)站建設(shè)，阿克塞哈薩克族自治網(wǎng)站制作、阿克塞哈薩克族自治網(wǎng)頁(yè)設(shè)計(jì)、阿克塞哈薩克族自治網(wǎng)站官網(wǎng)定制、小程序制作服務(wù)，打造阿克塞哈薩克族自治網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供阿克塞哈薩克族自治網(wǎng)站排名全網(wǎng)營(yíng)銷(xiāo)落地服務(wù)。

一、哈希表

散列表(Hash table，也叫哈希表)，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。

給定表M，存在函數(shù)f(key)，對(duì)任意給定的關(guān)鍵字值key，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址，則稱表M為哈希(Hash)表，函數(shù)f(key)為哈希(Hash) 函數(shù)。

哈希沖突的解決方案，要么使用鏈接法，要么使用開(kāi)放尋址法

鏈接法

即當(dāng)不同的關(guān)鍵字映射到同一單元時(shí)，在同一單元內(nèi)使用鏈表來(lái)保存這些關(guān)鍵字

開(kāi)放尋址法

即當(dāng)插入數(shù)據(jù)時(shí)，如果發(fā)現(xiàn)關(guān)鍵字被映射到的單元存在數(shù)據(jù)了，說(shuō)明發(fā)生了沖突，就繼續(xù)尋找下一個(gè)單元，直到找到可用單元為止

而因?yàn)殚_(kāi)放尋址法方案屬于占用其他關(guān)鍵字映射單元的位置，所以后續(xù)的關(guān)鍵字更容易出現(xiàn)哈希沖突，因此容易出現(xiàn)性能下降

二、鏈表

鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。 相比于線性表順序結(jié)構(gòu)，操作。

對(duì)于數(shù)據(jù)結(jié)構(gòu)的內(nèi)容，我們不過(guò)多展開(kāi)，我們之后會(huì)有專門(mén)的內(nèi)容去詳細(xì)介紹數(shù)據(jù)結(jié)構(gòu)

三、php數(shù)組

php解決哈希沖突的方式是使用了鏈接法，所以php數(shù)組是由哈希表+鏈表實(shí)現(xiàn)，準(zhǔn)確來(lái)說(shuō)，是由哈希表+雙向鏈表實(shí)現(xiàn)

四、內(nèi)部結(jié)構(gòu)-哈希表

HashTable結(jié)構(gòu)體主要用來(lái)存放哈希表的基本信息
typedef struct _hashtable { 
    uint nTableSize;        // hash Bucket的大小，即哈希表的容量，最小為8，以2x增長(zhǎng)。
    uint nTableMask;        // nTableSize-1 ， 索引取值的優(yōu)化
    uint nNumOfElements;    // hash Bucket中當(dāng)前存在的元素個(gè)數(shù)，count()函數(shù)會(huì)直接返回此值 
    ulong nNextFreeElement; // 下一個(gè)可使用的數(shù)字鍵值
    Bucket *pInternalPointer;   // 當(dāng)前遍歷的指針（foreach比f(wàn)or快的原因之一）
    Bucket *pListHead;          // 存儲(chǔ)整個(gè)哈希表的頭元素指針
    Bucket *pListTail;          // 存儲(chǔ)整個(gè)哈希表的尾元素指針
    Bucket **arBuckets;         // 存儲(chǔ)hash數(shù)組
    dtor_func_t pDestructor;    // 在刪除元素時(shí)執(zhí)行的回調(diào)函數(shù)，用于資源的釋放
    zend_bool persistent;       //指出了Bucket內(nèi)存分配的方式。如果persisient為T(mén)RUE，則使用操作系統(tǒng)本身的內(nèi)存分配函數(shù)為Bucket分配內(nèi)存，否則使用PHP的內(nèi)存分配函數(shù)。
    unsigned char nApplyCount; // 標(biāo)記當(dāng)前hash Bucket被遞歸訪問(wèn)的次數(shù)（防止多次遞歸）
    zend_bool bApplyProtection;// 標(biāo)記當(dāng)前hash桶允許不允許多次訪問(wèn)，不允許時(shí)，最多只能遞歸3次
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

Bucket結(jié)構(gòu)體則用于保存數(shù)據(jù)的具體內(nèi)容

typedef struct bucket {
    ulong h;            // 對(duì)char *key進(jìn)行hash后的值，或者是用戶指定的數(shù)字索引值
    uint nKeyLength;    // hash關(guān)鍵字的長(zhǎng)度，如果數(shù)組索引為數(shù)字，此值為0
    void *pData;        // 指向value，一般是用戶數(shù)據(jù)的副本，如果是指針數(shù)據(jù)，則指向pDataPtr
    void *pDataPtr;     // 如果是指針數(shù)據(jù)，此值會(huì)指向真正的value，同時(shí)上面pData會(huì)指向此值
    struct bucket *pListNext;   // 指向整個(gè)哈希表的該單元的下一個(gè)元素
    struct bucket *pListLast;   // 指向整個(gè)哈希表的該單元的上一個(gè)元素
    struct bucket *pNext;       // 指向由于哈希沖突導(dǎo)致存放在同一個(gè)單元的鏈表中的下一個(gè)元素
    struct bucket *pLast;       // 指向由于哈希沖突導(dǎo)致存放在同一個(gè)單元的鏈表中的上一個(gè)元素
    // 保存當(dāng)前值所對(duì)于的key字符串，這個(gè)字段只能定義在最后，實(shí)現(xiàn)變長(zhǎng)結(jié)構(gòu)體
    char arKey[1];              
} Bucket;

上述內(nèi)容就是PHP用哈希表和鏈表解決哈希沖突的方法，你們學(xué)到知識(shí)或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識(shí)儲(chǔ)備，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

本文題目：PHP用哈希表和鏈表解決哈希沖突的方法
URL地址：http://bm7419.com/article42/jjsjec.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站維護(hù)、網(wǎng)站制作、云服務(wù)器、網(wǎng)站內(nèi)鏈、外貿(mào)建站、網(wǎng)站改版

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

成都網(wǎng)頁(yè)設(shè)計(jì)公司