Design and implement a data structure for Least Recently Used (LRU) cache. It
should support the following
operations: get and set.
get(key) - Get the value (will always be positive) of the
key if the key exists in the cache, otherwise return -1.set(key,
value) - Set or insert the value if the key is not already present.
When the cache reached its capacity, it should invalidate the least recently
used item before inserting a new item.
public class LRUCache { private int capacity; Map<Integer,Integer> map; public LRUCache(int capacity) { this.capacity=capacity; map =new LRULinkedHashMap<Integer,Integer>(capacity); } public int get(int key) { if(map.containsKey(key)) return map.get(key); return -1; } public void set(int key, int value) { map.put(key, value); } } class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V>{ private int capacity; private static final long serialVersionUID = 1L; LRULinkedHashMap(int capacity){ super(16,0.75f,true); this.capacity=capacity; } @Override public boolean removeEldestEntry(Map.Entry<K, V> eldest){ return size()>capacity; } }
借鉴大神的文章 LinkedHashMap
LinkedHashMap默认的元素顺序是put的顺序，但是如果使用带参数的构造函数，那么LinkedHashMap会根据访问顺序来调整内部 顺序。 LinkedHashMap的get()方法除了返回元素之外还可以把被访问的元素放到链表的底端，这样一来每次顶端的元素就是remove的元素。
【LeetCode】LRU Cache,布布扣,bubuko.com
原文：http://www.cnblogs.com/yixianyixian/p/3737901.html