PHP核心技術與最佳實踐之Hash表沖突
接著上一篇文章，測試後輸出value1value2.當
$ht->insert(‘key12’,’value12’);
Echo $ht ->find(‘key12’);時，
發現輸出value12value12.這是什麼原因呢？
這個問題稱為Hash表的沖突。由於insert的是字符串，采用的算法是將字符串的ASIIC碼相加，按照此方法，沖突產生了。通過打印key12和key1的Hash值，發現他們都為8，也就說，value1和value12同時被存儲咋Hash表的第9個位置上，（索引從0開始），所以，value1的值被value12覆蓋了。
解決沖突常用的方法有：開放定址法和拉鏈法。因為拉鏈容易理解，本文采用拉鏈法解決沖突問題。
拉鏈法解決沖突：
做法是將所有相同的Hash值得關鍵字節點鏈接在同一個鏈表中。
拉鏈法把相同的hash值得關鍵節點以一個鏈表連接起來，那麼在查找元素時就必須遍歷這條鏈表，比較鏈表中的每個元素的關鍵字與查找的關鍵字是否相等，如果相等就是我們要查找的元素。
因為節點需要保存關鍵字（key）和數據（value），同時還要記錄具有相同hash值的節點。所以創建一個HashNode類存儲這些信息。
HashNode結構如下：
key = $key;
$this ->value = $value;
$this ->nextNode = $nextNode;
}
}
?>
HashNode有3個屬性：$key,$value,和$nextNode。$key是節點的關鍵字，$value是節點的值，而$nextNode是指向具有相同Hash值節點的指針。現把插入方法修改如下：
Public function insert($key,$value){
$index= $this -> hashfunc($key);
//新建一個節點
if(isset($this->buckets[$index])){
$newNode = new HashNode($key,$value,$this->buckets[$index])
}else{
$newNode = newHashNode($key,$value,null);
}
$this -> buckets[$index] = $newNode;//保存新節點
}
修改後的插入的算法流程如下：
1) 使用Hash函數計算關鍵字的Hash值，通過Hash值定位到Hash表的指定位置。
2) 如果此位置已經被其他節點占用，把新節點的$nextNode指向此節點，否則把新節點$nextNode設置為null。
3) 把新節點保存到Hash表的當前位置。
經過這三個步驟，相同的Hash值得節點會被連接到同一個鏈表。
查找算法相應的修改為如下格式：
Public functionfind($key){
$index = $this ->hashfunc($key);
$current =$this->buckets[$index];
while(isset($current)){//遍歷當前鏈表
if($current->key== $key){ //比較當前節點的關鍵字
return$current -> value;//查找成功
}
$current =$current ->nextNode; //比較下一個節點
}
Return null; //查找失敗
}
修改後的查找算法流程如下：
1) 使用Hash函數計算關鍵字的Hash值，通過Hash值定位到Hash表的指定位置。
2) 遍歷當前鏈表，比較鏈表中的每個節點的關鍵字與查找關鍵字是否相等。如果相等，查找成功。
3) 如果整個鏈表都沒有要查找的關鍵字，查找失敗。
經測試，使用拉鏈法解決了沖突問題。
