LRUCache的Java实现

方案一
通过链表保存访问key的时间顺序，因为get和set都需要遍历列表所以时间复杂度为O(n)

import java.util.HashMap;
import java.util.LinkedList;

public class LRUCache<K, V> {
    private long size;
    private HashMap<K, V> cacheMap;
    private LinkedList<K> accessList;

    public LRUCache(long size) {
        this.size = size;
        cacheMap = new HashMap<>();
        accessList = new LinkedList<>();
    }

    public V get(K key) {
        V value = cacheMap.get(key);
        if (value == null) {
            return null;
        }
        accessList.remove(key);
        accessList.push(key);
        return value;
    }

    public V put(K key, V value) {
        V orgValue = cacheMap.get(key);
        if(orgValue == null) {
            if (cacheMap.size() >= size) {
                K eldKey = accessList.pop();
                cacheMap.remove(eldKey);
                accessList.remove(eldKey);
            }
        } else {
            accessList.remove(key);
        }
        cacheMap.put(key, value);
        accessList.push(key);
        return orgValue;
    }

    public boolean remove(K key) {
        cacheMap.remove(key);
        accessList.remove(key);
        return true;
    }
}

方案二

实现一个类似于redis zset类型，通过分数进行排序的set
因为都是采用map实现，元素的增加和删除可以达到O(logn)

public class ZSet<Long, E> {
    /**
     * 通过元素获取分值
     * Key: 元素
     * Value: 用于排序的分值
     */
    HashMap<E, Long> scoreMap;

    /**
     * 按照分值进行排序
     * Key: 用于排序的分值
     * Value: 元素
     */
    TreeMap<Long, E> elementMap;

    /**
     * 删除并返回排在第一的元素
     * @return
     */
    public E pop() {
        Iterator<Map.Entry<Long, E >> iter = elementMap.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry<Long, E > entry =  iter.next();
            E element = entry.getValue();
            scoreMap.remove(element);
            iter.remove();
            return element;
        }
        return null;
    }

    /**
     * 添加元素
     */
    public Boolean add(Long score, E element) {
        elementMap.put(score, element);
        scoreMap.put(element, score);
        return true;
    }

    /**
     * 删除元素
     */
    public void remove(E element) {
        Long score = scoreMap.get(element);
        scoreMap.remove(element);
        elementMap.remove(score, element);
    }
}

利用Zset通过保存时间戳，对key进行排序。从而避免了列表的操作
时间复杂度可以降低到O(logn)

public class LRUCache<K, V> {
    private long size;
    private HashMap<K, V> cacheMap;
    private ZSet<Long, K> timeKeySet;

    public LRUCache(long size) {
        this.size = size;
        cacheMap = new HashMap<>();
        timeKeySet = new ZSet<>();
    }

    public V get(K key) {
        V value = cacheMap.get(key);
        if (value == null) {
            return null;
        }
        timeKeySet.add(System.currentTimeMillis(), key);
        return value;
    }

    public V put(K key, V value) {
        V orgValue = cacheMap.get(key);
        if(orgValue != null) {
            // 若缓存已经满淘汰最老的元素
            if (cacheMap.size() >= size) {
                K eldKey = timeKeySet.pop();
                cacheMap.remove(eldKey);
            }
        }
        cacheMap.put(key, value);
        timeKeySet.add(System.currentTimeMillis(), key);
        return orgValue;
    }

    public boolean remove(K key) {
        cacheMap.remove(key);
        timeKeySet.remove(key);
        return true;
    }
}

方案三
直接使用LinkedHashMap，网上有相关的实现