LRU数据结构设计与实现

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择距离最近时间最久未使用的页面予以淘汰。其核心思想是“如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小”。
常见使用场景：内存管理中的页面置换算法、缓存淘汰中的淘汰策略等。
设计的LRU数据结构需要实现get和set方法
get(key)：若缓存中存在key，返回对应的value，否则返回-1
set(key,value):若缓存中存在key，替换其value，否则插入key及其value，如果插入时缓存已经满了，应该使用LRU算法把最近最久没有使用的key踢出缓存。
LRU原理和Redis实现——一个今日头条的面试题
实现1：使用双向链表+HashMap
整体设计思路是使用HashMap的key存储key，这样可以做到set和get的时间复杂度都是O(1)，而HashMap的Value指向双向链表实现的LRU的Node节点，如图所示：

class DLinkedNode {
    String key;
    int value;
    DLinkedNode pre;
    DLinkedNode post;
}

public class LRUCache {
    private Hashtable<String, DLinkedNode> cache = new Hashtable<>();
    private int count;
    private int capacity;
    private DLinkedNode head, tail;

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

        head = new DLinkedNode();
        head.pre = null;

        tail = new DLinkedNode();
        tail.post = null;

        head.post = tail;
        tail.pre = head;
    }

    public int get(String key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1; // should raise exception here.
        }

        // move the accessed node to the head;
        this.moveToHead(node);

        return node.value;
    }

    public void set(String key, int value) {
        DLinkedNode node = cache.get(key);

        if (node == null) {

            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;

            this.cache.put(key, newNode);
            this.addNode(newNode);

            ++count;

            if (count > capacity) {
                // pop the tail
                DLinkedNode tail = this.popTail();
                this.cache.remove(tail.key);
                --count;
            }
        } else {
            // update the value.
            node.value = value;
            this.moveToHead(node);
        }
    }

    /**
     * Always add the new node right after head;
     */
    private void addNode(DLinkedNode node) {
        node.pre = head;
        node.post = head.post;

        head.post.pre = node;
        head.post = node;
    }

    /**
     * Remove an existing node from the linked list.
     */
    private void removeNode(DLinkedNode node) {
        DLinkedNode pre = node.pre;
        DLinkedNode post = node.post;

        pre.post = post;
        post.pre = pre;
    }

    /**
     * Move certain node in between to the head.
     */
    private void moveToHead(DLinkedNode node) {
        this.removeNode(node);
        this.addNode(node);
    }

    // pop the current tail.
    private DLinkedNode popTail() {
        DLinkedNode res = tail.pre;
        this.removeNode(res);
        return res;
    }
}

实现2：直接使用LinkedHashMap

public class LRU<K, V> {
    /**
     * LinkedHashMap负载因子默认0.75
     */
    private static final float hashLoadFactory = 0.75f;
    private LinkedHashMap<K, V> map;
    private int cacheSize;

    /**
     * @param cacheSize
     *            容量
     */
    public LRU(int cacheSize) {
        this.cacheSize = cacheSize;
        int capacity = (int) Math.ceil(cacheSize / hashLoadFactory) + 1;
        //如果accessOrder为true的话，则会把访问过的元素放在链表后面，放置顺序是访问的顺序
        //(LinkedHashMap里面的get方法，当accessOrder为true，会走afterNodeAccess方法将节点移到最后)
        //如果accessOrder为flase的话，则按插入顺序来遍历
        map = new LinkedHashMap<K, V>(capacity, hashLoadFactory, true) {
            private static final long serialVersionUID = -5291175172111746517L;

            /*
             * 当map容量大于LRU的容量时，删除最近最少使用的数据
             */
            @Override
            protected boolean removeEldestEntry(Entry<K, V> eldest) {
                return size() > LRU.this.cacheSize;
            }
        };
    }

    public synchronized V get(K key) {
        return map.get(key);
    }

    public synchronized void put(K key, V value) {
        map.put(key, value);
    }

    public synchronized void clear() {
        map.clear();
    }

    public synchronized int usedSize() {
        return map.size();
    }

    public void print() {
        for (Map.Entry<K, V> entry : map.entrySet()) {
            System.out.print(entry.getValue() + "--");
        }
        System.out.println();

    }
}

LRU算法介绍和在JAVA的实现及源码分析