中文字幕av专区_日韩电影在线播放_精品国产精品久久一区免费式_av在线免费观看网站

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

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

發布時間:2020-07-01 18:26:56 來源:億速云 閱讀:244 作者:元一 欄目:編程語言

本篇文章為大家展示了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用哈希表和鏈表解決哈希沖突的方法,你們學到知識或技能了嗎?如果還想學到更多技能或者豐富自己的知識儲備,歡迎關注億速云行業資訊頻道。

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

乳山市| 志丹县| 海盐县| 区。| 万州区| 垫江县| 嘉禾县| 泗水县| 中阳县| 台湾省| 德庆县| 翼城县| 宁强县| 泰宁县| 西盟| 阳东县| 桐乡市| 秦安县| 林甸县| 旺苍县| 墨玉县| 虹口区| 连城县| 巫山县| 个旧市| 正安县| 称多县| 崇信县| 道孚县| 秀山| 托克逊县| 嘉鱼县| 洛宁县| 南平市| 望都县| 东乌| 鹤庆县| 通山县| 齐齐哈尔市| 故城县| 旬阳县|