LeCMS
ClassCMS
Fastadmin
iCMS
PbootCMS
PHPCMS
易优CMS
YzmCMS
讯睿CMS
极致CMS
Wordpress
HkCMS
YznCMS
WellCMS
ThinkCMF
帝国CMS
SIYUCMS《PHP实战：php 实现Hash表功能实例详解》要点：
本文介绍了PHP实战：php 实现Hash表功能实例详解，希望对您有用。如果有疑问，可以联系我们。
php 实现Hash表功能PHP编程
Hash表作为最重要的数据结构之一,也叫做散列表.使用PHP实现Hash表的功能.PHP可以模拟实现Hash表的增删改查.通过对key的映射到数组中的一个位置来访问.映射函数叫做Hash函数,存放记录的数组称为Hash表.
PHP编程
Hash函数把任意长度的和类型的key转换成固定长度输出.不同的key可能拥有相同的hash.
Hash表的时间复杂度为O(1)PHP编程
<?phpclass HashTable{ private $arr = array(); private $size = 10; public function __construct(){ //SplFixedArray创建的数组比一般的Array()效率更高,因为更接近C的数组.创建时需要指定尺寸 $this->arr = new SplFixedArray($this->size); } /** * Description: 简单hash算法.输入key,输出hash后的整数 * @param $key * @return int */ private function simpleHash($key){ $len = strlen($key); //key中每个字符所对应的ASCII的值 $asciiTotal = 0; for($i=0; $i<$len; $i++){ $asciiTotal += ord($key[$i]); } return $asciiTotal % $this->size; } /** * Description: 赋值 * @param $key * @param $value * @return bool */ public function set($key, $value){ $hash = $this->simpleHash($key); $this->arr[$hash] = $value; return true; } /** * Description: 取值 * @param $key * @return mixed */ public function get($key){ $hash = $this->simpleHash($key); return $this->arr[$hash]; } public function getList(){ return $this->arr; } public function editSize($size){ $this->size = $size; $this->arr->setSize($size); }}?>下面对我们的HashTable进行测试.PHP编程
<?php//测试1$arr = new HashTable();for($i=0; $i<15; $i++){ $arr->set('key'.$i, 'value'.$i);}print_r($arr->getList());//测试2$arr->editSize(15);for($i=0; $i<15; $i++){ $arr->set('key'.$i, 'value'.$i);}print_r($arr->getList());?>改变了值之后可以存放更多的元素.但是仍然存在不同的key可能产生相同的hash值,那么赋值的时候后操作会覆盖前操作的问题.这种冲突的问题我们来用拉链法解决.PHP编程
拉链法解决冲突.拉链法解决冲突的做法是将所有的相同Hash值的key放在一个链表中,比如key3和key14在hash之后都是0,那么在数组的键为0的地方存储这两个值,形式是链表.如果不能理解我的文字,请看下面的示例,看一下打印信息就明白了.拉链法是什么,就是链表.PHP编程
创建一个HashNode类,用来存储key和value的值,并且存储相同hash的另一个元素.在同一条链上,查找越后的元素越费时.时间复杂度为O(n).PHP编程
<?phpclass HashNode{ public $key; public $value; public $nextNode; public function __construct($key, $value, $nextNode=Null){ $this->key = $key; $this->value = $value; $this->nextNode = $nextNode; }}class NewHashTable{ private $arr; private $size = 10; public function __construct(){ $this->arr = new SplFixedArray($this->size); } private function simpleHash($key){ $asciiTotal = 0; $len = strlen($key); for($i=0; $i<$len; $i++){ $asciiTotal += ord($key[$i]); } return $asciiTotal % $this->size; } public function set($key, $value){ $hash = $this->simpleHash($key); if(isset($this->arr[$hash])){ $newNode = new HashNode($key, $value, $this->arr[$hash]); }else{ $newNode = new HashNode($key, $value, null); } $this->arr[$hash] = $newNode; return true; } public function get($key){ $hash = $this->simpleHash($key); $current = $this->arr[$hash]; while(!empty($current)){ if($current->key == $key){ return $current->value; } $current = $current->nextNode; } return NULL; } public function getList(){ return $this->arr; }}?>对我们新的HashTable进行测试PHP编程
<?php//测试1$newArr = new NewHashTable();for($i=0; $i<30; $i++){ $newArr->set('key'.$i, 'value'.$i);}print_r($newArr->getList());var_dump($newArr->get('key3'));?>希望以上内容对你有所帮助！如果还有其他问题，请随时提问。 各类知识收集 拥有多年CMS企业建站经验，对 iCMS， LeCMS， ClassCMS， Fastadmin， PbootCMS， PHPCMS， 易优CMS， YzmCMS， 讯睿CMS， 极致CMS， Wordpress， HkCMS， YznCMS， WellCMS， ThinkCMF， 等各类cms的相互转化，程序开发，网站制作，bug修复，程序杀毒，插件定制都可以提供最佳解决方案。
未经允许不得转载：Str Tom工作室 » PHP实战：php 实现Hash表功能实例详解
