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()."";
$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算法”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注创新互联行业资讯频道！
网页名称：PHP如何实现LRU算法
网站地址：http://6mz.cn/article/pjsced.html