php实现Hash表功能

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

Hash函数把任意长度的和类型的key转换成固定长度输出。不同的key可能拥有相同的hash。

Hash表的时间复杂度为O(1)

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进行测试。

//测试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).

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,$this->arr[$hash]);

}else{

$newNode = new HashNode($key,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进行测试

//测试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'));

?>

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!