泡泡龙2,西乌旗天气,明星童乐会范雷
php 实现hash表功能
hash表作为最重要的数据结构之一，也叫做散列表。使用php实现hash表的功能。php可以模拟实现hash表的增删改查。通过对key的映射到数组中的一个位置来访问。映射函数叫做hash函数，存放记录的数组称为hash表。
hash函数把任意长度的和类型的key转换成固定长度输出。不同的key可能拥有相同的hash。
hash表的时间复杂度为o(1)
我要评论
<?php
class 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).
<?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;
}
}
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'));
?>
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
PHP date_default_timezone_set()设置时区操作实例分析
网友评论