LRU算法的实现

https://leetcode.com/problems/lru-cache/
1.设计一个缓存系统，大小固定，包含，get,put,remove
2.自动清理key，清理的方式是Least Recently Used最近最久未使用的数据清除
思路：当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。双向链表+hashmap，双向链表的原因是为了提高删除效率，hashmap的原因是为了提高查找效率。

参考链接

get请求：当key在hashmap中命中时，说明在链表中也存在，则需要在链表中将该key移到头部（删除原来的node，头部新增一个），当key在hashmap中没命中时，直接返回-1
set请求：当key在hashmap中命中时候时，说明链表中也存在，将该key移到头部，并将data改为set请求的新value。当key在hashmap中没有命中时，链表头部新增一个value的node，此处要判断hashmap有没有达到容量上限,如果达到上限，需要删除队尾的元素，这样达到了删除最近最久未访问的数据

<?php

class LRUCache {

    /**
     * @param Integer $capacity
     */
    function __construct($capacity) {
        $this->capacity = $capacity;
        $this->hashmap  = [];
        $this->head     = new Node(null, null);
        $this->tail     = new Node(null, null);
        $this->head->setNext($this->tail);
        $this->tail->setPrevious($this->head);
    }

    /**
     * @param Integer $key
     * @return Integer
     */
    function get($key) {
        if (!isset($this->hashmap[$key])) {
            return -1;
        }
        $node = $this->hashmap[$key];
        if (count($this->hashmap) == 1) {
            return $node->getData();
        }

        $this->detach($node);
        $this->attach($this->head, $node);
        return $node->getData();
    }

    /**
     * @param Integer $key
     * @param Integer $value
     * @return NULL
     */
    function put($key, $value) {
        if ($this->capacity <= 0) {
            return false;
        }
        //如果已经有这个key，就扔到链表头
        if (isset($this->hashmap[$key]) && !empty($this->hashmap[$key])) {
            $node = $this->hashmap[$key];
            $this->detach($node);
            $this->attach($this->head, $node);
            $node->setData($value);
        } else {
            //没有这个key，重新新建
            $node                = new Node($key, $value);
            $this->hashmap[$key] = $node;
            $this->attach($this->head, $node);

            //达到最大存储上限
            if (count($this->hashmap) > $this->capacity) {
                //头指针和尾指针都是null，所以是tail的previous
                $nodetoRemove = $this->tail->getPrevious();
                $this->detach($nodetoRemove);
                unset($this->hashmap[$nodetoRemove->getKey()]);
            }
        }
        return true;
    }

    /**
     * remove
     * @param $key
     * @return bool
     * @brief 删除
     */
    public function remove($key) {
        if (!isset($this->hashmap[$key])) {
            return false;
        }

        $nodeToRemove = $this->hashmap[$key];
        $this->detach($nodeToRemove);
        unset($this->hashmap[$nodeToRemove->getKey()]);
        return true;
    }

    /**
     * attach
     * @param Node $head
     * @param Node $node
     * @return void
     * @brief node插入到链表的头部
     */
    private function attach($head, $node) {
        $node->setPrevious($head);
        $node->setNext($head->getNext());
        $node->getNext()->setPrevious($node);
        $node->getPrevious()->setNext($node);
    }

    /**
     * detach
     * @param $node
     * @return void
     * @brief 从链表中删除一个元素
     */
    private function detach($node) {
        $node->getPrevious()->setNext($node->getNext());
        $node->getNext()->setPrevious($node->getPrevious());
    }

}

class Node {

    private $key;
    private $data;
    private $next;
    private $previous;

    public function __construct($key, $data) {
        $this->key  = $key;
        $this->data = $data;
    }

    public function setData($data) {
        $this->data = $data;
    }

    public function setPrevious($previous) {
        $this->previous = $previous;
    }

    public function setNext($next) {
        $this->next = $next;
    }

    public function getData(){
        return $this->data;
    }

    public function getKey() {
        return $this->key;
    }

    public function getNext() {
        return $this->next;
    }

    public function getPrevious() {
        return $this->previous;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * $obj = LRUCache($capacity);
 * $ret_1 = $obj->get($key);
 * $obj->put($key, $value);
 */

java实现

class LRUCache {
    HashMap<Integer, DoubledLinked> map = new HashMap<Integer, DoubledLinked>();
    DoubledLinked head;
    DoubledLinked tail;
    int len;
    int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        len = 0;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }

        DoubledLinked link = map.get(key);
        removeNode(link);
        setHead(link);
        return link.val;
    }

    public void put(int key, int value) {

        //如果已经包含了该key，则在map中将key提到head位置
        if (map.containsKey(key)) {
            DoubledLinked oldlink = map.get(key);
            removeNode(oldlink);
            oldlink.val = value;
            map.put(key, oldlink);
            setHead(oldlink);
        } else {//如果不包含该key
            DoubledLinked link = new DoubledLinked(key, value);
            if (len < capacity) {
                setHead(link);
                map.put(key, link);
                len++;
            } else {
                map.remove(tail.key);
                removeNode(tail);//TODO 待定
                setHead(link);
                map.put(key, link);
            }
        }
    }


    public void removeNode(DoubledLinked node) {

        //node.pre.next = node.next;
        //node.next.pre = node.pre;
        //核心就是上面两句话，为了解决node在队列头或者队列尾的情况，才有下面这么多if else
        if (node.pre != null) {
            node.pre.next = node.next;
        } else {//此时的node就是head
            head = node.next;
        }

        if (node.next != null) {
            node.next.pre = node.pre;
        } else {//此时的node就是tail
            tail = node.pre;
        }


    }

    public void setHead(DoubledLinked node) {
//        node.pre.next = node.next;
//        node.next.pre = node.pre;

        //讲道理，对于setHead，理论上是需要上面两行代码的，因为需要对现有node的pre和next负责
        //但是，从上面的代码可以看出来，每次setHead之前都调用了removeNode
        //或者这个node就是new出来的一个新的，所以这个pre和next本身就已经被重置了
        node.next = head;
        node.pre = null;
        if (head != null) {
            head.pre = node;
        }
        head = node;
        if (tail == null) {
            tail = node;
        }

    }
}



class DoubledLinked {
    int val;
    int key;
    DoubledLinked pre;
    DoubledLinked next;

    DoubledLinked(int key, int val) {
        this.key = key;
        this.val = val;
    }
}