网站首页  汉语字词  英语词汇  考试资料  写作素材  旧版资料

请输入您要查询的考试资料：

　

标题 利用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());
    //SplFixedArray Object
    //(
    // [0] => value14
    // [1] => value4
    // [2] => value5
    // [3] => value6
    // [4] => value7
    // [5] => value8
    // [6] => value10
    // [7] => value11
    // [8] => value12
    // [9] => value13
    //)
    //不同的key可能产生相同的hash值，那么赋值的时候后操作会覆盖前操作。
    //测试2
    $arr->editSize(15);
    for($i=0; $i<15; $i++){
    $arr->set('key'.$i, 'value'.$i);
    }
    print_r($arr->getList());
    //SplFixedArray Object
    //(
    // [0] => value14
    // [1] => value4
    // [2] => value0
    // [3] => value1
    // [4] => value2
    // [5] => value3
    // [6] => value10
    // [7] => value11
    // [8] => value12
    // [9] => value13
    // [10] => value14
    // [11] => value9
    // [12] =>
    // [13] =>
    // [14] =>
    //)
    ?>
    改变了值之后可以存放更多的元素。但是仍然存在不同的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'));
    //SplFixedArray Object
    //(
    // [0] => HashNode Object
    //(
    // [key] => key23
    // [value] => value23
    // [nextNode] => HashNode Object
    //(
    // [key] => key14
    // [value] => value14
    // [nextNode] => HashNode Object
    //(
    // [key] => key3
    // [value] => value3
    // [nextNode] =>
    // )
    //
    // )
    //
    // )
    //
    // [1] => HashNode Object
    //(
    // [key] => key24
    // [value] => value24
    // [nextNode] => HashNode Object
    //(
    // [key] => key15
    // [value] => value15
    // [nextNode] => HashNode Object
    //(
    // [key] => key4
    // [value] => value4
    // [nextNode] =>
    // )
    //
    // )
    //
    // )
    //
    // [2] => HashNode Object
    //(
    // [key] => key25
    // [value] => value25
    // [nextNode] => HashNode Object
    //(
    // [key] => key16
    // [value] => value16
    // [nextNode] => HashNode Object
    //(
    // [key] => key5
    // [value] => value5
    // [nextNode] =>
    // )
    //
    // )
    //
    // )
    //
    // [3] => HashNode Object
    //(
    // [key] => key26
    // [value] => value26
    // [nextNode] => HashNode Object
    //(
    // [key] => key17
    // [value] => value17
    // [nextNode] => HashNode Object
    //(
    // [key] => key6
    // [value] => value6
    // [nextNode] =>
    // )
    //
    // )
    //
    // )
    //
    // [4] => HashNode Object
    //(
    // [key] => key27
    // [value] => value27
    // [nextNode] => HashNode Object
    //(
    // [key] => key18
    // [value] => value18
    // [nextNode] => HashNode Object
    //(
    // [key] => key7
    // [value] => value7
    // [nextNode] =>
    // )
    //
    // )
    //
    // )
    //
    // [5] => HashNode Object
    //(
    // [key] => key28
    // [value] => value28
    // [nextNode] => HashNode Object
    //(
    // [key] => key19
    // [value] => value19
    // [nextNode] => HashNode Object
    //(
    // [key] => key8
    // [value] => value8
    // [nextNode] =>
    // )
    //
    // )
    //
    // )
    //
    // [6] => HashNode Object
    //(
    // [key] => key29
    // [value] => value29
    // [nextNode] => HashNode Object
    //(
    // [key] => key10
    // [value] => value10
    // [nextNode] => HashNode Object
    //(
    // [key] => key9
    // [value] => value9
    // [nextNode] =>
    // )
    //
    // )
    //
    // )
    //
    // [7] => HashNode Object
    //(
    // [key] => key20
    // [value] => value20
    // [nextNode] => HashNode Object
    //(
    // [key] => key11
    // [value] => value11
    // [nextNode] => HashNode Object
    //(
    // [key] => key0
    // [value] => value0
    // [nextNode] =>
    // )
    //
    // )
    //
    // )
    //
    // [8] => HashNode Object
    //(
    // [key] => key21
    // [value] => value21
    // [nextNode] => HashNode Object
    //(
    // [key] => key12
    // [value] => value12
    // [nextNode] => HashNode Object
    //(
    // [key] => key1
    // [value] => value1
    // [nextNode] =>
    // )
    //
    // )
    //
    // )
    //
    // [9] => HashNode Object
    //(
    // [key] => key22
    // [value] => value22
    // [nextNode] => HashNode Object
    //(
    // [key] => key13
    // [value] => value13
    // [nextNode] => HashNode Object
    //(
    // [key] => key2
    // [value] => value2
    // [nextNode] =>
    // )
    //
    // )
    //
    // )
    //
    //)
    //string(6) "value3"
    ?>
随便看

　

在线学习网考试资料包含高考、自考、专升本考试、人事考试、公务员考试、大学生村官考试、特岗教师招聘考试、事业单位招聘考试、企业人才招聘、银行招聘、教师招聘、农村信用社招聘、各类资格证书考试等各类考试资料。

　

Copyright © 2002-2024 cuapp.net All Rights Reserved
更新时间：2025/5/20 6:05:56