LRU算法，Least Recently Used的缩写，即最近最少使用，这样的数据淘汰。所以也就是等于一旦新增或者新访问的数据就要被提到前面去。下面就是使用链表加哈希实现了LRU算法。可以在最后面测试效果

<?php

class LRUCache{
    private $capacity;
    public $list;

    function __construct($capacity){
        $this->capacity = $capacity;
        $this->list = new HashList();
    }

    function get($key){
        if ($key < 0)
            return -1;
        return $this->list->get($key);
    }

    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){
        return isset($this->buckets[$key]) && $this->buckets[$key] ? true : false;
    }

    public function get($key){
        $res = $this->buckets[$key];
        if (!$res) return -1;

        $this->moveToHead($res);
        return $res->val;
    }

    //put的时候，新加入节点的时候
    public function addAsHead($key, $val){
        $node = new Node($val);

        $node->pre = null;
        $node->next = $this->head;
        $node->key = $key;

        if($this->head){//如果是非空的情况下，老的head需要有个pre
            $this->head->pre = $node;
        }
        $this->head = $node;//新加入的作为head

        $this->buckets[$key] = $node;
        $this->size++;
    }


    //get的时候，获取节点的时候
    public function moveToHead(Node $node){
        if ($node == $this->head) return;

        //调整前后指针指向
        $node->pre->next = $node->next;//对前节点的影响

        if($node->next){
            $node->next->pre = $node->pre;//对后节点的影响
        }

        $node->next = $this->head;//自己有个next了，就是原来的头

        $this->head->pre = $node;//对老的头的影响
        $this->head = $node;//自己作为新的头了

        $node->pre = null;
    }

    //移除指针(已存在的键值对或者删除最近最少使用原则)
    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]);

        //调整指针
        if ($current->pre == null) {//被删除的是最前面的一个
            $this->head = $current->next;
        } else if ($current->next == null) {//被删除的是最后一个，重置链表的tail
            $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--;
    }
}

class Node{
    public $key;
    public $val;
    public $next;
    public $pre;

    public function __construct($val){
        $this->val = $val;
    }
}

$capacity = 5;//容量
$obj = new LRUCache($capacity);
$obj->put('key1', 'value1');
$obj->put('key2', 'value2');
$obj->put('key3', 'value3');
$obj->put('key4', 'value4');
$obj->put('key5', 'value5');

$obj->get('key1');
$obj->get('key2');

$obj->put('key6', 'value6');
$obj->put('key7', 'value7');


//按照顺序打印出来
printNode($obj->list->head);

function printNode($node){
    echo $node->val."<br>";
    if($node->next){
        printNode($node->next);
    }
}