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

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

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

3:保存链表头 跟尾;

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

2:缓存类

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()."
";
  $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();
 }
    }



}

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 算法的知识的详细内容，更多请关注考高分网其它相关文章！