php 实现Hash表功能实例详解

php 实现Hash表功能
Hash表作为最重要的数据结构之一，也叫做散列表。使用PHP实现Hash表的功能。PHP可以模拟实现Hash表的增删改查。通过对key的映射到数组中的一个位置来访问。映射函数叫做Hash函数，存放记录的数组称为Hash表。

Hash函数把任意长度的和类型的key转换成固定长度输出。不同的key可能拥有相同的hash。
Hash表的时间复杂度为O（1）

<?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//测试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值，那么赋值的时候后操作会覆盖前操作的问题。这种冲突的问题我们来用拉链法解决。
拉链法解决冲突。拉链法解决冲突的做法是将所有的相同Hash值的key放在一个链表中，比如key3和key14在hash之后都是0，那么在数组的键为0的地方存储这两个值，形式是链表。如果不能理解我的文字，请看下面的示例，看一下打印信息就明白了。拉链法是什么，就是链表。
创建一个HashNode类，用来存储key和value的值，并且存储相同hash的另一个元素。在同一条链上，查找越后的元素越费时。时间复杂度为O（n）.

<?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//测试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"））;?>

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！