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

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

一、哈希表

散列表(Hash table，也叫哈希表)，是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。

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

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

鏈接法

即當不同的關鍵字映射到同一單元時，在同一單元內使用鏈表來保存這些關鍵字

開放尋址法

即當插入數據時，如果發現關鍵字被映射到的單元存在數據了，說明發生了沖突，就繼續尋找下一個單元，直到找到可用單元為止

而因為開放尋址法方案屬于占用其他關鍵字映射單元的位置，所以后續的關鍵字更容易出現哈希沖突，因此容易出現性能下降

二、鏈表

鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。 相比于線性表順序結構，操作。

對于數據結構的內容，我們不過多展開，我們之后會有專門的內容去詳細介紹數據結構

三、php數組

php解決哈希沖突的方式是使用了鏈接法，所以php數組是由哈希表+鏈表實現，準確來說，是由哈希表+雙向鏈表實現

四、內部結構-哈希表

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

Bucket結構體則用于保存數據的具體內容

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

上述內容就是PHP用哈希表和鏈表解決哈希沖突的方法，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。