原理

LRU Cache是Least Recently Used Cache的缩写，当缓存满了之后，首先淘汰最久未使用的。

构造一个队列，队列的长度为缓存的长度，将最近使用的放到队尾，队首即为最久未使用的数据。

当缓存满了之后，再插入新的元素时，就将队列头部的元素删除，然后将新的元素插入到队列尾部。

LinkedHashMap实现

利用LinkedHashMap的removeEldestEntry方法，当缓存满了之后，就删除队列头部的元素。

class LRUCache<K, V> {
    private int capacity;

    private Map<K, V> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > capacity;
            }
        };
    }
}

对于LinkedHashMap的构造方法，第一个参数是初始容量，第二个参数是负载因子，第三个参数是排序模式，如果为true，那么就按照访问顺序排序，如果为false，那么就按照插入顺序排序。

应为需要在并发环境中使用，所以缓存存取需操作要加锁

public synchronized V get(K key) {
    V value = cache.get(key);
    if (value != null) {
        cache.remove(key);
        cache.put(key, value);
        return value;
    }
    return null;
}

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

优化 LinkedHashMap+分段锁

缓存主要解决高频读取数据的问题，上述实现存取数据都要加锁，当并发量上去后，还是会影响性能。参考ConcurrentHashMap1.8之前版本的实现，将缓存分成多个段，每个段都有自己的锁，这样就可以提高并发量。

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantLock;

class LRUCache<K, V> {
    private int capacity;
    private int segmentSize;
    private Map<K, V>[] segments;
    private ReentrantLock[] locks;

    public LRUCache(int capacity, int numSegments) {
        this.capacity = capacity;
        this.segmentSize = capacity / numSegments;
        this.segments = new LinkedHashMap[numSegments];
        this.locks = new ReentrantLock[numSegments];

        for (int i = 0; i < numSegments; i++) {
            segments[i] = new LinkedHashMap<>(segmentSize, 0.75f, true) {
                @Override
                protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                    return size() > segmentSize;
                }
            };
            locks[i] = new ReentrantLock();
        }
    }

    private int getSegmentIndex(K key) {
        int hashCode = key.hashCode();
        return (hashCode ^ (hashCode >>> 16)) % segments.length;
    }

    public V get(K key) {
        int segmentIndex = getSegmentIndex(key);
        locks[segmentIndex].lock();
        try {
            Map<K, V> segment = segments[segmentIndex];
            V value = segment.get(key);
            if (value != null) {
                segment.remove(key);
                segment.put(key, value);
                return value;
            }
            return null;
        } finally {
            locks[segmentIndex].unlock();
        }
    }

    public void put(K key, V value) {
        int segmentIndex = getSegmentIndex(key);
        locks[segmentIndex].lock();
        try {
            Map<K, V> segment = segments[segmentIndex];
            segment.put(key, value);
        } finally {
            locks[segmentIndex].unlock();
        }
    }
}

ConcurrentHashMap + ConcurrentLinkedDeque +读写锁 实现

经过优化后，一定程度上降低了锁竞争程度。但是在高并发遇到热点数据的情况下，在一个分段上还是会有锁竞争问题。而且每次被淘汰的只是当前分段内最久未被使用的缓存，而不一定是全局最久未被使用的。

可以使用ConcurrentHashMap+ConcurrentLinkedDeque实现。利用这两个工具的CAS特性，使得锁粒度为Entry级别,进一步降低锁竞争程度。

缓存往往是读远大于写的场景，所以考虑使用读写锁，增大读的并发量。

其中需要指出的是对于 ConcurrentHashMap ，JDK7中使用的是分段锁，JDK8中使用的是CAS+Synchronized实现的。

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedDeque;
import java.util.concurrent.locks.ReentrantLock;

class LRUCache<K, V> {
    private int capacity;
    private Map<K, V> cache;
    private ConcurrentLinkedDeque<K> deque;
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
    private final Lock readLock = lock.readLock();
    private final Lock writeLock = lock.writeLock();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new ConcurrentHashMap<>(capacity);
        this.deque = new ConcurrentLinkedDeque<>();
    }

    public V get(K key) {
        readLock.lock();
        try { 
            V value = cache.get(key);
            if (value != null) {
                synchronized (value) {
                    deque.remove(key);
                    deque.addFirst(key);
                }
            }
            return value;
        } finally {
            readLock.unlock();
        }
        return value;
    }

    public void put(K key, V value) {
        writeLock.lock();
        try {
            if (cache.containsKey(key)) {
                deque.remove(key);
            } else if (cache.size() >= capacity) {
                K lastKey = deque.removeLast();
                cache.remove(lastKey);
            }
            cache.put(key, value);
            deque.addFirst(key);
        } finally {
            writeLock.unlock();
        }
    }
}