php哈希沖突怎么解決

這篇文章主要介紹了php哈希沖突怎么解決，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

php有什么用

php是一個嵌套的縮寫名稱，是英文超級文本預處理語言，它的語法混合了C、Java、Perl以及php自創(chuàng)新的語法，主要用來做網(wǎng)站開發(fā)，許多小型網(wǎng)站都用php開發(fā)，因為php是開源的，從而使得php經(jīng)久不衰。

本文操作系統(tǒng)：windows7系統(tǒng)、PHP5.6版本、DELL G3電腦。

1.哈希沖突概念

對應不同的關(guān)鍵字可能獲得相同的hash地址，即 key1≠key2，但是f(key1)=f(key2)。這種現(xiàn)象就是沖突，而且這種沖突只能盡可能的減少，不能完全避免。因為哈希函數(shù)是從關(guān)鍵字集合和地址集合的映像，通常關(guān)鍵字集合比較大，而地址集合的元素僅為哈希表中的地址值。

2.沖突解決：鏈接法

鏈接法優(yōu)點：

（1）拉鏈法處理沖突簡單，且無堆積現(xiàn)象，即非同義詞絕不會發(fā)生沖突，因此平均查找長度較短；

（2）由于拉鏈法中各鏈表上的節(jié)點是動態(tài)申請的，故它更適合造表前無法確定表長的情況；

鏈接法缺點：

指針需要額外的空間，故當結(jié)點規(guī)模較小時，開放定址法較為節(jié)省空間，而若將節(jié)省的指針空間擴大散列表的規(guī)模，可是裝載因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度。

3.解決實例

（1）使用Hash函數(shù)計算關(guān)鍵字的Hash值，通過Hash值定位到Hash表的指定位置。

（2） 如果此位置已經(jīng)被其他節(jié)點占用，把新節(jié)點的$nextNode指向此節(jié)點，否則把新節(jié)點$nextNode設置為null。

（3）把新節(jié)點保存到Hash表的當前位置。

經(jīng)過這三個步驟，相同的Hash值得節(jié)點會被連接到同一個鏈表。

查找算法相應的修改為如下格式：

Public functionfind($key){
                           $index = $this ->hashfunc($key);
                           $current =$this->buckets[$index];
                           while(isset($current)){//遍歷當前鏈表
                                  if($current->key== $key){  //比較當前節(jié)點的關(guān)鍵字
                                         return$current -> value;//查找成功
                                  }
                                  $current =$current ->nextNode;  //比較下一個節(jié)點
                           }
                           Return null;  //查找失敗
               }

感謝你能夠認真閱讀完這篇文章，希望小編分享的“php哈希沖突怎么解決”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識等著你來學習!