使用PHP實現(xiàn)LRU緩存淘汰算法

class LRUCache {
 private $capacity;
 private $list;
 /**
 * @param Integer $capacity
 */
 function __construct($capacity) {
 $this->capacity=$capacity;
 $this->list=new HashList();
 }
 /**
 * @param Integer $key
 * @return Integer
 */
 function get($key) {
 if($key<0) return -1;
 return $this->list->get($key);
 }
 /**
 * @param Integer $key
 * @param Integer $value
 * @return NULL
 */
 function put($key, $value) {
 $size=$this->list->size;
 $isHas=$this->list->checkIndex($key);
 if($isHas || $size+1 > $this->capacity){
 $this->list->removeNode($key);
 }
 $this->list->addAsHead($key,$value);
 }
}
class HashList{
 public $head;
 public $tail;
 public $size;
 public $buckets=[];
 public function __construct(Node $head=null,Node $tail=null){
 $this->head=$head;
 $this->tail=$tail;
 $this->size=0;
 }
 //檢查鍵是否存在
 public function checkIndex($key){
 $res=$this->buckets[$key];
 if($res){
 return true;
 }
 return false;
 }
 public function get($key){
 $res=$this->buckets[$key];
 if(!$res) return -1;
 $this->moveToHead($res);
 return $res->val;
 }
 //新加入的節(jié)點
 public function addAsHead($key,$val)
{
 $node=new Node($val);
 if($this->tail==null && $this->head !=null){
 $this->tail=$this->head;
 $this->tail->next=null;
 $this->tail->pre=$node;
 }
 $node->pre=null;
 $node->next=$this->head;
 $this->head->pre=$node;
 $this->head=$node;
 $node->key=$key;
 $this->buckets[$key]=$node;
 $this->size++;
 }
 //移除指針(已存在的鍵值對或者刪除最近最少使用原則)
 public function removeNode($key)
{
 $current=$this->head;
 for($i=1;$i<$this->size;$i++){
 if($current->key==$key) break;
 $current=$current->next;
 }
 unset($this->buckets[$current->key]);
 //調(diào)整指針
 if($current->pre==null){
 $current->next->pre=null;
 $this->head=$current->next;
 }else if($current->next ==null){
 $current->pre->next=null;
 $current=$current->pre;
 $this->tail=$current;
 }else{
 $current->pre->next=$current->next;
 $current->next->pre=$current->pre;
 $current=null;
 }
 $this->size--;
 }
 //把對應(yīng)的節(jié)點應(yīng)到鏈表頭部(最近get或者剛剛put進(jìn)去的node節(jié)點)
 public function moveToHead(Node $node)
{
 if($node==$this->head) return ;
 //調(diào)整前后指針指向
 $node->pre->next=$node->next;
 $node->next->pre=$node->pre;
 $node->next=$this->head;
 $this->head->pre=$node;
 $this->head=$node;
 $node->pre=null;
 }
}
class Node{
 public $key;
 public $val;
 public $next;
 public $pre;
 public function __construct($val)
{
 $this->val=$val;
 }
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * $obj = LRUCache($capacity);
 * $ret_1 = $obj->get($key);
 * $obj->put($key, $value);