1.概念
LRU : 最近最少使用算法
2.代码
<?php class Node { public $preKey = null; //链表前一个节点 public $nextKey = null; //链表后一个节点 public $key= null; //当前的值 public $value= null; //当前key public function __construct($key,$value){ $this->key = $key; $this->value = $value; } public function setPre($preKey) { $this->preKey = $preKey; } public function setNext($nextKey) { $this->nextKey = $nextKey; } } class LRUCache{ public $cacheTable = []; /** Node null */ private $headNode = null; private $lastNode = null; private $cacheCount = 0; private $cacheMax = 3; public function addNode($key,$value) //此处采用头插法 { $addNode = new Node($key,$value); if ( !empty($this->headNode)) { $this->headNode->preKey = $addNode; //如果链表存在,将节点添加到节点前一个 } $addNode->nextKey = $this->headNode; //第一次保存最后一个节点为头结点 if ($this->lastNode == null){ $this->lastNode = $addNode; } $this->headNode = $addNode; $this->cacheTable[$key] = $addNode; $this->cacheCount++; } public function set($key,$value) { //先判断是否需要删除 $this->shiftNode(); $this->addNode($key,$value); return true; } //自动删除 public function shiftNode() { while ($this->cacheCount >= $this->cacheMax){ if (!empty($this->lastNode)){ if ($this->lastNode->preKey){ $this->lastNode->preKey->nextKey = null; $this->lastNode = $this->lastNode->preKey; } unset($this->cacheTable[$this->lastNode->key]); } $this->cacheCount --; } } public function dumpAllData() { $node = $this->headNode; while (($node)){ echo "key=".$node->key."value=".$node->value."\n"; $node = $node->nextKey; } } } $Cache = new LRUCache(); $Cache->set("a","aaaaaaaaaaa"); $Cache->set("b","bbbbbbbbbbb"); $Cache->set("c","ccccccccccc"); $Cache->set("d","dddddddddddd"); $Cache->set("e","eeeeeeeeeeee"); //$Cache->set("f","ffffffffffff"); $Cache->dumpAllData(); //var_dump($Cache); //是一个深度的数组(对象)
结果
[root@VM-16-13-centos ~]# php LRU.php
key=evalue=eeeeeeeeeeee
key=dvalue=dddddddddddd
key=cvalue=ccccccccccc
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:mmqy2019@163.com进行举报,并提供相关证据,查实之后,将立刻删除涉嫌侵权内容。
长按识别二维码并关注微信
更方便到期提醒、手机管理