[LeetCode] LRU Cache

One of straightforward implementation of LRUCache is to use JDK's LinkedHashMap. However to implement it correctly, overriding its removeOldestEntry() method is not enough.

We need to use the correct LinkedHashMap constructor with correct arguments to make sure it behaves as LRU cache. Below is the doc from JDK:

"A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). "

And here is the code which passed the LeetCode tests and beat 90% Java implementation in terms of the runtime.

	public class LRUCache {
	LinkedHashMap<Integer, Integer> cache;
	public LRUCache(int capacity){
	cache = new LinkedHashMap<Integer, Integer>(capacity, (float) 0.75, true){
	@Override
	protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest){
	return this.size() > capacity;
	}
	};
	}
	public List<Integer> getValuesAsList(){
	return new ArrayList<>(cache.values());
	}
	public int get(int key) {
	Integer result = cache.get(key);
	if(result==null)
	result = -1;
	return result;
	}
	public void set(int key, int value) {
	cache.put(key, value);
	}
	}

view raw LRUCache.java hosted with ❤ by GitHub