php 实现Hash表功能实例详解

php  /  管理员 发布于 7年前   375

php 实现Hash表功能

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

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

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

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).

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

set('key'.$i, 'value'.$i);}print_r($newArr->getList());var_dump($newArr->get('key3'));?>

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

您可能感兴趣的文章:

• PHP 数组和字符串互相转换实现方法
• PHP中使用cURL实现Get和Post请求的方法
• PHPMyadmin 配置文件详解(配置)
• php日期转时间戳,指定日期转换成时间戳
• PHP 页面跳转到另一个页面的多种方法方法总结
• 特详细的PHPMYADMIN简明安装教程
• php下intval()和(int)转换使用与区别
• PHP 页面编码声明方法详解(header或meta)
• PHP date函数参数详解
• PHP中文处理 中文字符串截取(mb_substr)和获取中文字符串字数