PHP实现LRU算法的原理详解

1.概念

LRU ： 最近最少使用算法

2.代码

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97

<?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

总结

本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注服务器之家的更多内容!   

原文链接：https://blog.csdn.net/kevlin_V/article/details/123764118