首页 > 代码库 > LeetCode 之 LRU Cache Java实现

LeetCode 之 LRU Cache Java实现

2024-07-16 04:26:34   214人阅读

　　LeetCode刷了41道题了，流程是按照戴兄的小书，很多不会的是参考Kim姐的代码，自己用Java抠腚的。

　　前几天做到了LRU Cache：

　　C++的实现方法大同小异，大都用的是一个list加一个hash，hash中存储list节点地址，每次get从hash中寻key，有则将list相应节点放到链表头，没有则返回-1；每次set先判断hash中是否存在，存在则将相应节点移到表头，重置value值，如果不存在，判定长度是否达到预设的capacity，如果达到，删除表尾节点，新节点插入表头。

　　但是用Java如此实现的话就有点绕了，倒是也看到有同学用HashMap和自己定义的双向链表实现的。

　　之前用LikedHashMap不是很多，这次就用它实现LRU Cache。LikedHashMap中有一个方法叫removeEldestEntry，作用是判断map中的entry是否超了容量，超了的话会自动删掉最早插入的entry，其实功能已经很接近LRU了，但是不论访问还是set已有的元素，都不会对删除顺序有影响。实现如下：

 

 1 import java.util.LinkedHashMap; 2 import java.util.Map.Entry; 3  4 /** 5  * Problem: LRU Cache 6  * Description: Design and implement a data structure for Least Recently Used 7  * (LRU) cache. It should support the following operations: get and set. 8  * get(key) - Get the value (will always be positive) of the key if the key 9  * exists in the cache, otherwise return -1.10  * set(key, value) - Set or insert the value if the key is not already present.11  * When the cache reached its capacity, it should invalidate the least recently12  * used item before inserting a new item.13  * Date: Aug 4 , 201414  * 15  * @author Chyace16  * 17  */18 public class LRUCache {19 // 用来装item的LinkedHashMap子类对象20     CacheMap cache;21 22     public LRUCache(int capacity) {23         cache = new CacheMap(capacity);24     }25 /**26  * 每次get容器中的值，都将相应元素删除重新插入，这时它就会位于最新的位置27  * @param key28  * @return29  */30     public int get(int key) {31         if (cache.containsKey(key)) {32             int value =http://www.mamicode.com/ cache.get(key);33             cache.remove(key);34             set(key, value);35             return value;36         }37         return -1;38     }39 40     public void set(int key, int value) {41         if (cache.containsKey(key)) cache.remove(key);42         cache.put(key, value);43     }44 }45 46 /**47  * LinkedHashMap只能实现最旧移除而不会更新48  * 49  * @author Chyace50  * 51  */52 class CacheMap extends LinkedHashMap<Integer, Integer> {53 54     private static final long serialVersionUID = 3240765461462956414L;55 56     private int MAX;57 58     CacheMap(int max) {59         this.MAX = max;60     }61 62     protected boolean removeEldestEntry(Entry<Integer, Integer> eldest) {63         return size() > MAX;64     }65 66 }

 

　　最后提交的时候没加import行，编译错，之前用到util的时候都不需要导入，但是这次提交两行都得加，费解……　　

　　对了，这位仁兄貌似是在工程里实际应用Java 版LRU Cache，很有参考价值。

 


联系
我们