HashTable实现代码分享

<?php
include 'HashNode.php';
/**
 * HashTable实现
 */
class HashTable 
{
    private $buckets;
    private $size = 10;

    public function __construct()
    {
        // SplFixedArray Object ( [0] => [1] => [2] => [3] => [4] => [5] => [6] => [7] => [8] => [9] => )
        $this->buckets = new SplFixedArray($this->size);
    }

    /**
     * hash算法
     *
     * @param string $key
     * @return void
     */
    private function hash($key)
    {
        $strlen = strlen($key);
        $hashval = 0;
        for($i=0;$i<$strlen;$i++)
        {
            // ord 返回 ASCII值
            $hashval += ord($key.$i);
        }

        return $hashval % $this->size;
    }

    /**
     * 添加数据
     *
     * @param string $key
     * @param string $val
     * @return void
     */
    public function add($key,$val)
    {
        // 生成 key
        $index = $this->hash($key);
        // 判断当前key节点是否存在,存在返回
        if(isset($this->buckets[$index])) {
            $newNode = new HashNode($key,$val,$this->buckets[$index]);
        }else{
            // 不存在新增节点
            $newNode = new HashNode($key,$val,null);
        }
        // arr[$index] = $val
        $this->buckets[$index] = $newNode;
    }

    /**
     * 根据key获取数据
     *
     * @param string $key
     * @return void
     */
    public function get($key)
    {
        $index = $this->hash($key);
        $current = $this->buckets[$index];
        // var_dump($current,$key);die;
        // D:\phpstudy_pro\WWW\phpcore\05-code\HashTable.php:68:
        // object(HashNode)[4]
        // public 'key' => string 'key2' (length=4)
        // public 'value' => string 'ass' (length=3)
        // public 'nextNode' => 
        //     object(HashNode)[3]
        //     public 'key' => string 'key1' (length=4)
        //     public 'value' => 
        //         array (size=2)
        //         0 => string 'zs' (length=2)
        //         1 => int 18
        //     public 'nextNode' => null
        // D:\phpstudy_pro\WWW\phpcore\05-code\HashTable.php:68:string 'key1' (length=4)
        while(isset($current)) {
            /**
             * key2 == key1 false
             * $current = $current->nextNode;
             * 此时$current->key = key1 
             * $current->key == $key
             */
            if($current->key == $key)
            {
                return $current->value;
            }
            $current = $current->nextNode;
        }
        return null;
    }
}
<?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;
    }
}
<?php

include 'HashTable.php';


$ht = new HashTable;
$ht->add('key1',['zs',18]);
$ht->add('key2','ass');

print_r($ht->get('key1'));
print_r($ht->get('key2'));

本作品采用《CC 协议》,转载必须注明作者和本文链接
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
讨论数量: 1
wanghan

挺好的

2个月前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!