PHP核心技术与最佳实践之Hash表摩擦
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了PHP核心技术与最佳实践之Hash表摩擦,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2811字,纯文字阅读大概需要5分钟。
内容图文
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结构如下:
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) 如果整个链表都没有要查找的关键字,查找失败。
经测试,使用拉链法解决了冲突问题。
内容总结
以上是互联网集市为您收集整理的PHP核心技术与最佳实践之Hash表摩擦全部内容,希望文章能够帮你解决PHP核心技术与最佳实践之Hash表摩擦所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。