PHP如何实现LRU算法

小编给大家分享一下PHP如何实现LRU算法，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！

整体设计

用数组保存缓存对象(node);

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

保存链表头 跟尾;

处理流程如下图:

主要代码

Node 节点类

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;    }}

缓存类

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();            }        }    }        public function setCacheMax(int $count){        $this->cacheMax=$count;    }        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;    }        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;    }        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();        }    }}

测试代码

    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如何实现LRU算法”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注编程网PHP编程频道！