PHP核心技术与最佳实践之Hash表冲突_PHP教程
- WBOY原創
- 2016-07-13 09:57:03992瀏覽
PHP核心技术与最佳实践之Hash表冲突
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结构如下：
<!--?PHP
Class HashNode{
Public $key;
Public $value;
Public $nextNode;
Public function__construct($key,$value,$nextNode = null){
$this --->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) 如果整个链表都没有要查找的关键字，查找失败。
经测试，使用拉链法解决了冲突问题。