半天撸完一个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 算法的知识的详细内容...