php 实现Hash表功能实例详解

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'));
?>

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

(0)

相关推荐

  • PHPMyadmin 配置文件详解(配置)

    非常适合对数据库操作命令不熟悉的数据库管理者,下面我就说下怎么安装该工具: 1.先到网上下载phpmyadmin,再解压到可以访问的web目录下(如果是虚拟空间,可以解压后通过ftp等上传到web目录下),当然您可以修改解压后该文件的名称. 2.配置config文件 打开libraries下的config.default.php文件,依次找到下面各项,按照说明配置即可: A.访问网址 引用: $cfg['PmaAbsoluteUri'] = '';这里填写phpmyadmin的访问网址 B.my

  • PHP date函数参数详解

    time()在PHP中是得到一个数字,这个数字表示从1970-01-01到现在共走了多少秒,很奇怪吧 不过这样方便计算, 要找出前一天的时间就是 time()-60*60*24; 要找出前一年的时间就是 time()*60*60*24*365 那么如何把这个数字换成日期格式呢,就要用到date函数了 $t=time();  echo date("Y-m-d H:i:s",$t); 第一个参数的格式分别表示: a - "am" 或是 "pm"  A

  • PHP中文处理 中文字符串截取(mb_substr)和获取中文字符串字数

    一.中文截取:mb_substr() mb_substr( $str, $start, $length, $encoding ) $str,需要截断的字符串 $start,截断开始处,起始处为0 $length,要截取的字数 $encoding,网页编码,如utf-8,GB2312,GBK 实例: 复制代码 代码如下: <?php $str='我们:http://www.jb51.net'; echo mb_substr($str,0,4,'utf-8');//截取头5个字,假定此代码所在php

  • php下intval()和(int)转换使用与区别

    复制代码 代码如下: <?php echo "<br/>数值强制转换:"; $string="2a"; $string1=intval($string); echo '$string1的值:'.$string1.'$string2的值:';//单引号不会输出变量,将原样输出 $string2=(int)($string); echo $string2 ?> 手册上查不到. 这也是手册上说的:引用: int intval ( mixed $va

  • PHP 页面编码声明方法详解(header或meta)

    php的header来定义一个php页面为utf编码或GBK编码 php页面为utf编码 header("Content-type: text/html; charset=utf-8"); php页面为gbk编码 header("Content-type: text/html; charset=gb2312"); php页面为big5编码 header("Content-type: text/html; charset=big5"); 通常情况以

  • php日期转时间戳,指定日期转换成时间戳

    写过PHP+MySQL的程序员都知道有时间差,UNIX时间戳和格式化日期是我们常打交道的两个时间表示形式,Unix时间戳存储.处理方便,但是不直观,格式化日期直观,但是处理起来不如Unix时间戳那么自如,所以有的时候需要互相转换,下面给出互相转换的几种转换方式. 一.在MySQL中完成 这种方式在MySQL查询语句中转换,优点是不占用PHP解析器的解析时间,速度快,缺点是只能用在数据库查询中,有局限性. 1. UNIX时间戳转换为日期用函数: FROM_UNIXTIME() 一般形式:selec

  • PHP 页面跳转到另一个页面的多种方法方法总结

    一.用HTTP头信息 也就是用PHP的HEADER函数.PHP里的HEADER函数的作用就是向浏览器发出由HTTP协议规定的本来应该通过WEB服务器的控制指令,例如声明返回信息的类型("Context-type: xxx/xxx"),页面的属性("No cache", "Expire")等等. 用HTTP头信息重定向到另外一个页面的方法如下: 复制代码 代码如下: <? if (isset($url)) { Header("HTT

  • 特详细的PHPMYADMIN简明安装教程

    非常适合对数据库操作命令不熟悉的数据库管理者,下面我就说下怎么安装该工具: 1.先到网上下载phpmyadmin,再解压到可以访问的web目录下(如果是虚拟空间,可以解压后通过ftp等上传到web目录下),当然您可以修改解压后该文件的名称. 2.配置config文件   打开libraries下的config.default.php文件,依次找到下面各项,按照说明配置即可: A.访问网址  引用: $cfg['PmaAbsoluteUri'] = '';这里填写phpmyadmin的访问网址 B

  • PHP 数组和字符串互相转换实现方法

    复制代码 代码如下: $array=explode(separator,$string); $string=implode(glue,$array); 使用和理解这两个函数的关键之处是分隔符(separator)和胶合符(glue)关系.当把一个数组转换成一个字符串时,将会设置胶合符--将被插入到生成字符串中的数组值之间的字符或代码. 相反,当把字符串转换成数组时,要指定分隔符,它用于标记什么应该变成独立数组元素.例如,以字符串开始: $s1='Mon-Tue-Wed-Thu-Fri'; $da

  • PHP中使用cURL实现Get和Post请求的方法

    1.cURL介绍 cURL 是一个利用URL语法规定来传输文件和数据的工具,支持很多协议,如HTTP.FTP.TELNET等.最爽的是,PHP也支持 cURL 库.本文将介绍 cURL 的一些高级特性,以及在PHP中如何运用它. 2.基本结构 在学习更为复杂的功能之前,先来看一下在PHP中建立cURL请求的基本步骤: (1)初始化 curl_init() (2)设置变量 curl_setopt() .最为重要,一切玄妙均在此.有一长串cURL参数可供设置,它们能指定URL请求的各个细节.要一次性

随机推荐