请用Java设计一个Least Recently Used (LRU) 缓存

LRU介绍：

LRU是Least Recently Used的缩写，即最少使用页面置换算法，是为虚拟页式存储管理服务的。

思路介绍：

可以使用两个标准的数据结构来实现，Map和Queue。因为需要支持多线程，需要使用实现了java.utili.concurrent.*的Map和Queue。

主要思路是使用一个Queue来维护FIFO和Map来对数据进行排序，当向缓存添加新的元素时，共有以下三种可能：

1. 如果该元素已经在Cache中存在（Map），我们会从queue中删除改元素并将其添加到queue的第一个位置。

2. 如果缓存已满无法新增新的元素，我们会从queue和Map中删除最后面的那个元素并把新元素添加进来。

3. 同时在Map和Queue中增加新的元素

参考答案：

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
 
public class LRUCache<K, V> {
 
	//LRU缓存的最大容量.
	private final int capacity;
	//用来保持最近使用的元素的Queue.
	private ConcurrentLinkedQueue<K> queue;
	private ConcurrentHashMap<K, V> map;
 
	/**
	 * 初始化LRU缓存
	 * @param capacity
	 */
	public LRUCache(final int capacity) {
		this.capacity = capacity;
		this.queue	= new ConcurrentLinkedQueue<K>();
		this.map	= new ConcurrentHashMap<K, V>(capacity);
	}
 
	/**
	 * 检查该元素释放在缓存中存在，如果不存在则返回null
	 * @param key
	 * @return 
	 */
	public V get(final K key) {
		return map.get(key);
	}
 
	/**
	 * 将元素添加到LRU缓存。如果Key已存在，则将其放到缓存的第一位置
	 * @param key
	 * @param value
	 * @throws NullPointerException
	 */
	public synchronized void put(final K key, final V value) {
		if(key == null || value == null) {
			throw new NullPointerException();
		}
		if (map.containsKey(key)) {
			queue.remove(key);
		}
		while (queue.size() >= capacity) {
			K expiredKey = queue.poll();
			if (expiredKey != null) {
				map.remove(expiredKey);
			}
		}
		queue.add(key);
		map.put(key, value);
	}
}