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

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

整体设计

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

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

3:保存链表头 跟尾;

处理流程如下图:

主要代码

1:Node 节点类

/**  * 缓存值保存类，  * Class Node  * @package appcommonmodel  */ 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 appcommonmodel  */ 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视频教程》