ホームページ >php教程 >php手册 >PHP核心技术与最佳实践之Hash表冲突

PHP核心技术与最佳实践之Hash表冲突

WBOY
WBOYオリジナル
2016-06-13 09:06:54884ブラウズ

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) 如果整个链表都没有要查找的关键字,查找失败。

经测试,使用拉链法解决了冲突问题。

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。