php 实现Hash表功能实例详解

yipeiwu_com5年前PHP代码库

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中检查isset()和!empty()函数的必要性

isset()函数是PHP中的内置函数,它检查变量是否已设置且不为NULL。此函数还检查声明的变量,数组或数组键是否具有空值,如果是,isset()返回false,它在所有其他可能的情况...

PHP获取文件扩展名的方法实例总结

本文实例总结了PHP获取文件扩展名的方法。分享给大家供大家参考,具体如下: 在PHP面试中或者考试中会有很大几率碰到写出五种获取文件扩展名的方法,下面是我自己总结的一些方法 $fil...

WordPress中创建用户角色的相关PHP函数使用详解

WordPress中创建用户角色的相关PHP函数使用详解

WordPress 默认有 “订阅者”、“投稿者”、“作者”、“编辑” 和 “管理员” 五个用户角色,权限由低到高,但默认的五个角色可能不够我们用,这时可以使用 add_role() 函...

PHP的APC模块实现上传进度条

PHP的APC模块实现上传进度条

APC模块,它的全称是Alternative PHP Cache。APC可以将所有PHP代码会被缓存起来, 另外它可提供一定的内存缓存功能.但是这个功能并不是十分完美,有报告说如果频繁使...

php查找指定目录下指定大小文件的方法

本文实例讲述了php查找指定目录下指定大小文件的方法。分享给大家供大家参考。具体实现方法如下: php查找文件大小的原理是遍历目录然后再利用filesize来计算文件大小,然后我们再加一...