PHP如何實現LRU算法

小編給大家分享一下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如何實現LRU算法”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！