力扣-146.LRU缓存机制

题目链接

146.LRU缓存机制

class LRUCache {HashMap<Integer, Integer> cache = new LinkedHashMap<>();int size = 0;public LRUCache(int capacity) {this.size = capacity;}public int get(int key) {if (!cache.containsKey(key)) {return -1;}move(key);return cache.get(key);}public void put(int key, int value) {if (cache.containsKey(key)) {cache.remove(key);cache.put(key, value);return;}if (cache.size() == this.size) {cache.remove(cache.keySet().iterator().next());}cache.put(key, value);}public void move(int key) {int val = cache.get(key);cache.remove(key);cache.put(key, val);}
}

小结：通俗地讲，LRU就是一个长度固定的队列，满了之后新的会把老的挤出去，特别的地方在于查询或修改操作，要把这个元素删掉重新插入，使用了这个元素就好像它是最近添加的新元素。由于在java中，LinkedHashMap是有序的，可以直接通过cache.keySet().iterator().next()找到最久远的key，可以比较方便地删除旧元素。