LRU

• 常规写法

Java

public class LRUCache {
    private class Node{
        Node prev;
        Node next;
        int key;
        int value;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }

    private int capacity;
    private HashMap<Integer, Node> hs = new HashMap<Integer, Node>();
    private Node head = new Node(-1, -1);
    private Node tail = new Node(-1, -1);

    public LRUCache(int capacity) {
        this.capacity = capacity;
        tail.prev = head;
        head.next = tail;
    }

    public int get(int key) {
        if( !hs.containsKey(key)) {    		//key找不到
            return -1;
        }

        // remove current
        Node current = hs.get(key);
        current.prev.next = current.next;
        current.next.prev = current.prev;

        // move current to tail
        move_to_tail(current);			//每次get，使用次数+1，最近使用，放于尾部

        return hs.get(key).value;
    }

    public void set(int key, int value) {			//数据放入缓存
        // get 这个方法会把key挪到最末端，因此，不需要再调用 move_to_tail
        if (get(key) != -1) {
            hs.get(key).value = value;
            return;
        }

        if (hs.size() == capacity) {		//超出缓存上限
            hs.remove(head.next.key);		//删除头部数据
            head.next = head.next.next;
            head.next.prev = head;
        }

        Node insert = new Node(key, value);		//新建节点
        hs.put(key, insert);
        move_to_tail(insert);					//放于尾部
    }

    private void move_to_tail(Node current) {    //移动数据至尾部
        current.prev = tail.prev;
        tail.prev = current;
        current.prev.next = current;
        current.next = tail;
    }
}

Python

class LinkedListNode(object):
    def __init__(self, key=None, val=-1):
        self.key = key
        self.val = val
        self.pre = None
        self.next = None


class LinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def appendHead(self, node):
        node.next, node.pre = self.head, None
        if self.head:
            self.head.pre = node
        self.head = node

        if not self.tail:
            self.tail = self.head

        self.size += 1

    def remove(self, node):
        if not node:
            return

        pre, next = node.pre, node.next
        if pre:
            pre.next = next
        if next:
            next.pre = pre

        if self.head == node:
            self.head = next

        if self.tail == node:
            self.tail = pre

        self.size -= 1
        return node

    def removeTail(self):
        return self.remove(self.tail)

    def advance(self, node):
        self.remove(node)
        self.appendHead(node)


class LRUCache(object):
    def __init__(self, capacity):
        self.capacity = capacity
        self.record = {}
        self.linkedList = LinkedList()

    def get(self, key):
        if key not in self.record:
            return -1

        self.linkedList.advance(self.record[key])
        return self.record[key].val

    def set(self, key, value):
        if key not in self.record:
            node = LinkedListNode(key, value)

            self.linkedList.appendHead(node)
            self.record[key] = node

            if self.linkedList.size > self.capacity:
                del self.record[self.linkedList.removeTail().key]
        else:
            self.record[key].val = value
            self.linkedList.advance(self.record[key])

• LinkedHashMap

Java

class LRUCache {
    private int capacity;
    private Map<Integer, Integer> map;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new LinkedHashMap<>();
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        int val = map.get(key);
        map.remove(key);
        map.put(key, val);
        return val;
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.put(key, value);
            get(key);
            return;
        }
        map.put(key, value);
        if (map.size() > capacity) {
            int victim = map.entrySet().iterator().next().getKey();
            map.remove(victim);
        }
    }
}

Python

class LRUCache:

    # @param capacity, an integer
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = collections.OrderedDict()

    # @return an integer
    def get(self, key):
        if not key in self.cache:
            return -1
        value = self.cache.pop(key)
        self.cache[key] = value
        return value

    # @param key, an integer
    # @param value, an integer
    # @return nothing
    def set(self, key, value):
        if key in self.cache:
            self.cache.pop(key)
        elif len(self.cache) == self.capacity:
            self.cache.popitem(last=False)
        self.cache[key] = value