半天撸完一个PHP 实现LRU 算法的知识

概述半天撸完一个PHP 实现LRU 算法的知识

我们学习了解了这么多关于PHP的知识，今天学习如何半天撸完一个PHP 实现LRU 算法的知识，不知你们是否已经完全掌握了呢，如果没有，那就跟随本篇文章一起继续学习吧整体设计

1:用数组保存缓存对象(Node);

2:缓存对象(Node)之间通过nextKey,preKey组成一个双向链表;

3:保存链表头 跟尾;

处理流程如下图:

主要代码

1:Node 节点类

/** * 缓存值保存类， * Class Node * @package app\common\model */class Node{    private $preKey=null;//链表前一个节点    private $nextKey=null;//链表后一个节点    private $value=null;//当前的值    private $key=null;//当前key    public function __construct(string  $key,$value)    {        $this->value=$value;        $this->key=$key;    }    public function setPreKey($preValue){        $this->preKey=$preValue;    }    public function setNextKey($nextValue){        $this->nextKey=$nextValue;    }    public function getPreKey(){        return $this->preKey;    }    public function getNextKey(){        return $this->nextKey;    }    public function getValue(){        return $this->value;    }    public function setValue($value){        $this->value=$value;    }    public function setKey(string  $key){        $this->key=$key;    }    public function getKey(){        return $this->key;    }}

2:缓存类

/** * 实现lru缓存 * Class LruCache * @package app\common\model */class LruCache{    public $cachetable =[];    private $headNode=null;    private $lastNode=null;    private $cacheCount=0;    private $cacheMax=100;    /**     * 测试输出使用     */    public function dumpAllData(){        if (!empty($this->headNode)){            $node=$this->headNode;            while (!empty($node)){                echo 'key='.$node->getKey().'  nextKey='.(empty($node->getNextKey())?'null':$node->getNextKey()->getKey()).' preKey='.(empty($node->getPreKey())?'null':$node->getPreKey()->getKey()).' value='.$node->getValue()."</br>";                $node=$node->getNextKey();            }        }    }    /**     * @param int $count     */    public function setCacheMax(int $count){        $this->cacheMax=$count;    }    /**     * @param string $key     * @param $value     * @return bool     */    public function set(string $key,$value){        //设置值为null，则认为删除缓存节点        if ($value===null){            $this->del($key);            return true;        }        //判断是否存在表中,存在则更新连表        if (!empty($this->cachetable[$key])){            $this->updateList($key);            return true;        }        //先判断是否要删除        $this->shiftNode();        $this->addNode($key,$value);        return true;    }    /**     * @param string $key     * @return bool     */    public function del(string $key){        if (!empty($this->cachetable[$key])){            $node=&$this->cachetable[$key];            //摘出节点            $this->jumpNode($node);            //置空删除            $node->setPreKey(null);            $node->setNextKey(null);            unset($this->cachetable[$key]);            return true;        }        return false;    }    /**     * @param string $key     * @return null     */    public function get(string $key){        if (!empty($this->cachetable[$key])){            $this->updateList($key);            return $this->cachetable[$key]->getValue();        }        return null;    }    //直接添加节点    private function addNode($key,$value){        $addNode=new Node($key,$value);        if (!empty($this->headNode)){            $this->headNode->setPreKey($addNode);        }        $addNode->setNextKey($this->headNode);        //第一次保存最后一个节点为头节点        if ($this->lastNode==null){            $this->lastNode=$addNode;        }        $this->headNode=$addNode;        $this->cachetable[$key]=$addNode;        $this->cacheCount++;    }    //主动删超出的缓存    private function shiftNode(){        while ($this->cacheCount>=$this->cacheMax){            if (!empty($this->lastNode)){                if (!empty($this->lastNode->getPreKey())){                    $this->lastNode->getPreKey()->setNextKey(null);                }                $lastKey=$this->lastNode->getKey();                unset($this->cachetable[$lastKey]);            }            $this->cacheCount--;        }    }    //更新节点链表    private function updateList($key){        //这里需要使用引用传值        $node=&$this->cachetable[$key];        //当前结点为头结点 直接不用处理        if ($this->headNode===$node){            return true;        }        //摘出结点        $this->jumpNode($node);        //跟头结点交换        $node->setNextKey($this->headNode);        $this->headNode->setPreKey($node);        $node->setPreKey(null);        $this->headNode=$node;        return true;    }    //将某个节点摘出来    private function jumpNode(Node &$node){        if (!empty($node->getPreKey())){            $node->getPreKey()->setNextKey($node->getNextKey());        }        if (!empty($node->getNextKey())){            $node->getNextKey()->setPreKey($node->getPreKey());        }        //如果是最后一个节点,则更新最后节点为它的前节点        if ($node->getNextKey()==null){            $this->lastNode=$node->getPreKey();        }        //如果是头结点        if ($node->getPreKey()==null){            $this->headNode=$node->getNextKey();        }    }}

3:测试代码

    public function tt(){    $cath=model("LruCache");    $cath->setCacheMax(3);    $cath->set("aa","aaaaaaaaaaa");    $cath->set("bb","bbbbbbbbbbbb");    $cath->set("cc","ccccccccccccc");    $cath->get("aa");//        $cath->dumpAllData();        $cath->set("dd","ddddddddddddd");//        $cath->del("cc");//        var_dump($cath->cachetable);        $cath->dumpAllData();        exit();    }

推荐学习：《PHP视频教程》 总结

以上是编程之家为你收集整理的半天撸完一个PHP 实现LRU 算法的知识全部内容，希望文章能够帮你解决半天撸完一个PHP 实现LRU 算法的知识所遇到的程序开发问题。

如果觉得编程之家网站内容还不错，欢迎将编程之家网站推荐给程序员好友。