本文主要是介绍自定义 LRU、LFU Cache（Java 版），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
前置准备
定义 BaseCache 接口，包含 put、get 方法和 Cache 实际存储的数据结构等
public interface BaseCache<K, V> {/*** 将 <Key, Val> 组装成 Node 节点放入 Cache 中** @param key CacheKey* @param val CacheValue*/void put(K key, V val);/*** 获取指定 CacheKey 对应的 Value，不存在返回 null** @param key CacheKey* @return CacheValue*/V get(K key);/*** Cache 实际的数据结构** @param <K> Cache Key* @param <V> Cache Value*/class DoubleLinkedList<K, V> {Node<K, V> head;Node<K, V> tail;DoubleLinkedList() {head = new Node<>();tail = new Node<>();head.next = tail;tail.prev = head;}/*** 添加节点到链表的末尾** @param node 待添加的节点*/void addLast(Node<K, V> node) {node.prev = tail.prev;node.next = tail;tail.prev.next = node;tail.prev = node;}/*** 删除指定节点** @param node 待删除的节点*/void remove(Node<K, V> node) {node.prev.next = node.next;node.next.prev = node.prev;}void prettyPrint() {Node<K, V> current = head.next;while (current != tail) {System.out.print("CacheKey: " + current.key + ", CacheValue: " + current.val);current = current.next;if (current != tail) {System.out.println();System.out.print(" <=> ");}System.out.println();}}}/*** DoubleLinkedList 中实际存储的元素类型** @param <K> Node Key* @param <V> Node Value*/class Node<K, V> {K key;V val;Node<K, V> next;Node<K, V> prev;Node() {}Node(K key, V val) {this.key = key;this.val = val;}}}定义 Person 类【CacheValue】和 PersonCacheUtils 用来辅助测试
public class Person {private Long id;private String name;private Integer age;public Person(String name, Integer age) {this.id = System.currentTimeMillis() + (long) (Math.random() * 1000);this.name = name;this.age = age;}public Long getId() {return id;}public void setId(Long id) {this.id = id;}public String getName() {return name;}public void setName(String name) {this.name = name;}public Integer getAge() {return age;}public void setAge(Integer age) {this.age = age;}@Overridepublic String toString() {return "Person{" +"id=" + id +", name='" + name + '\'' +", age=" + age +'}';}}public class PersonCacheUtils {private static final String CACHE_KEY_PREFIX = "Person_";private static final String PERSON_NAME_PREFIX = "Person-";public static void addPersonsToCache(BaseCache<String, Person> cache, int personCount) {Random random = new Random();for (int i = 0; i < personCount; i++) {String name = PERSON_NAME_PREFIX + UUID.randomUUID().toString().substring(0, 4);Integer age = 10 + random.nextInt(50);Person person = new Person(name, age);cache.put(getCacheKey(person.getId()), person);}}public static String getCacheKey(Long id) {return CACHE_KEY_PREFIX + id;}}Cache 实现
LRU Cache
/*** 自定义 LRU Cache** @param <K> CacheKey* @param <V> CacheValue*/
public class LRUCache<K, V> implements BaseCache<K, V> {/*** 提供 CacheKey -> Node 的映射表，可以方便 O(1) 时间复杂度获取节点*/private final Map<K, Node<K, V>> keyToNodeMap;/*** LRU Cache 的实际数据载体*/private final DoubleLinkedList<K, V> linkedList;/*** Cache 的容量*/private final int capacity;/*** 使用无参构造器赋予 Cache 的默认容量*/private static final int DEFAULT_CAPACITY = 10;/*** Cache 当前大小*/private int size;/*** LRU Cache 无参构造器*/public LRUCache() {this.capacity = DEFAULT_CAPACITY;this.keyToNodeMap = new HashMap<>();this.linkedList = new DoubleLinkedList<>();}/*** LRU Cache 有参构造器** @param initialCapacity 初始容量*/public LRUCache(int initialCapacity) {if (initialCapacity <= 0) {throw new IllegalArgumentException("initialCapacity needs to be greater than zero.");} else {this.capacity = initialCapacity;}this.keyToNodeMap = new HashMap<>();this.linkedList = new DoubleLinkedList<>();size = 0;}/*** 将 <Key, Val> 组成节点放入 LRU Cache 中** @param key CacheKey* @param val CacheValue*/@Overridepublic void put(K key, V val) {// 如果已经存在该 CacheKey，需要更新if (keyToNodeMap.containsKey(key)) {deleteNodeByKey(key);addNode(key, val);}// 判断容量是否充足if (this.capacity <= this.size) {removeFirst();}addNode(key, val);}/*** 删除指定 CacheKey 对应的节点** @param key 待删除节点的 CacheKey*/private void deleteNodeByKey(K key) {Node<K, V> delNode = keyToNodeMap.get(key);linkedList.remove(delNode);keyToNodeMap.remove(key);size--;}/*** 移除 Cache 链的首位元素*/private void removeFirst() {Node<K, V> delNode = linkedList.head.next;keyToNodeMap.remove(delNode.key);linkedList.remove(delNode);size--;}/*** 添加节点到 Cache 链中** @param key CacheKey* @param val CacheValue*/private void addNode(K key, V val) {Node<K, V> newNode = new Node<>(key, val);linkedList.addLast(newNode);keyToNodeMap.put(key, newNode);size++;}/*** 获取指定 CacheKey 对应的 Value，不存在返回 null** @param key CacheKey* @return CacheValue*/@Overridepublic V get(K key) {if (!keyToNodeMap.containsKey(key)) {return null;}// 当次访问后放到链表末尾moveNodeToTail(key);return keyToNodeMap.get(key).val;}/*** 将指定 CacheKey 对应的 node 移到链表尾部** @param key CacheKey*/private void moveNodeToTail(K key) {Node<K, V> node = keyToNodeMap.get(key);linkedList.remove(node);linkedList.addLast(node);}public int getFreeCapacity() {return this.capacity - this.size;}public int getSize() {return this.size;}/*** 测试使用** @return 返回第一个 CacheKey*/public K getFirstKey() {Node<K, V> firstNode = linkedList.head.next;if (firstNode == null) {return null;}return linkedList.head.next.key;}public void printCacheNodes() {linkedList.prettyPrint();}}LRUCacheApplication
public class LRUCacheApplication {public static void main(String[] args) {LRUCache<String, Person> lruCache = new LRUCache<>(4);System.out.println("size: " + lruCache.getSize() + ", freeCapacity: " + lruCache.getFreeCapacity());// size: 0, freeCapacity: 4PersonCacheUtils.addPersonsToCache(lruCache, 2);System.out.println("size: " + lruCache.getSize() + ", freeCapacity: " + lruCache.getFreeCapacity());// size: 2, freeCapacity: 2lruCache.printCacheNodes();/*** CacheKey: Person_1711262106797, CacheValue: Person{id=1711262106797, name='Person-e4eb', age=16}* <=>* CacheKey: Person_1711262106916, CacheValue: Person{id=1711262106916, name='Person-b24b', age=31}*/PersonCacheUtils.addPersonsToCache(lruCache, 2);System.out.println("size: " + lruCache.getSize() + ", freeCapacity: " + lruCache.getFreeCapacity());// size: 4, freeCapacity: 0lruCache.printCacheNodes();/*** CacheKey: Person_1711262106797, CacheValue: Person{id=1711262106797, name='Person-e4eb', age=16}* <=>* CacheKey: Person_1711262106916, CacheValue: Person{id=1711262106916, name='Person-b24b', age=31}* <=>* CacheKey: Person_1711262107050, CacheValue: Person{id=1711262107050, name='Person-4624', age=32}* <=>* CacheKey: Person_1711262106635, CacheValue: Person{id=1711262106635, name='Person-33b1', age=42}*/PersonCacheUtils.addPersonsToCache(lruCache, 2);lruCache.printCacheNodes();/*** CacheKey: Person_1711262107050, CacheValue: Person{id=1711262107050, name='Person-4624', age=32}* <=>* CacheKey: Person_1711262106635, CacheValue: Person{id=1711262106635, name='Person-33b1', age=42}* <=>* CacheKey: Person_1711262107223, CacheValue: Person{id=1711262107223, name='Person-4c21', age=34}* <=>* CacheKey: Person_1711262106792, CacheValue: Person{id=1711262106792, name='Person-f540', age=56}*/System.out.println(lruCache.get(lruCache.getFirstKey())); // Person{id=1711262107050, name='Person-4624', age=32}lruCache.printCacheNodes();/*** CacheKey: Person_1711262106635, CacheValue: Person{id=1711262106635, name='Person-33b1', age=42}* <=>* CacheKey: Person_1711262107223, CacheValue: Person{id=1711262107223, name='Person-4c21', age=34}* <=>* CacheKey: Person_1711262106792, CacheValue: Person{id=1711262106792, name='Person-f540', age=56}* <=>* CacheKey: Person_1711262107050, CacheValue: Person{id=1711262107050, name='Person-4624', age=32}*/}}LFU Cache
/*** 自定义 LFU Cache** @param <K> CacheKey* @param <V> CacheValue*/
public class LFUCache<K, V> implements BaseCache<K, V> {/*** 访问频率 1*/private static final int FREQUENT_ONE = 1;/*** Cache 的容量*/private final int capacity;/*** 使用无参构造器时 Cache 的默认容量*/private static final int DEFAULT_CAPACITY = 10;/*** Cache 当前大小*/private int size;/*** 提供 CacheKey -> Node 的映射表，可以方便 O(1) 时间复杂度获取节点*/private final Map<K, LFUNode<K, V>> keyToNodeMap;/*** <Frequent, CacheLinkedList> 映射表*/private final Map<Integer, DoubleLinkedList<K, V>> freqLinkedListMap;/*** Cache 中最小的访问频次*/private int minFrequent;/*** LFU Cache 无参构造器*/public LFUCache() {this.capacity = DEFAULT_CAPACITY;keyToNodeMap = new HashMap<>();freqLinkedListMap = new TreeMap<>(Integer::compareTo);size = 0;minFrequent = 0;}/*** LFU Cache 有参构造器** @param initialCapacity 初始容量*/public LFUCache(int initialCapacity) {if (initialCapacity <= 0) {throw new IllegalArgumentException("initialCapacity needs to be greater than zero.");} else {this.capacity = initialCapacity;}keyToNodeMap = new HashMap<>();freqLinkedListMap = new HashMap<>();size = 0;minFrequent = 0;}/*** 将 <Key, Val> 组成节点放入 LFU Cache 中** @param key CacheKey* @param val CacheValue*/@Overridepublic void put(K key, V val) {// 若该 Key 已经存在 Cache 链中则直接更新访问频次和缓存值LFUNode<K, V> node = keyToNodeMap.get(key);if (node != null) {node.val = val;increFrequent(node);return;}// 不存在则判断容量是否充足if (this.size >= this.capacity) {// 不充足则需要找到 minFrequent 对应的 Cache 链，移除队列首元素DoubleLinkedList<K, V> minFreqList = freqLinkedListMap.get(minFrequent);Node<K, V> firstNode = minFreqList.head.next;keyToNodeMap.remove(firstNode.key);minFreqList.remove(firstNode);size--;}// 添加节点到 FREQUENT_ONE 链中LFUNode<K, V> newNode = new LFUNode<>(key, val);keyToNodeMap.put(key, newNode);DoubleLinkedList<K, V> oneFreqList = freqLinkedListMap.get(FREQUENT_ONE);if (oneFreqList == null) {oneFreqList = new DoubleLinkedList<>();freqLinkedListMap.put(FREQUENT_ONE, oneFreqList);}oneFreqList.addLast(newNode);size++;minFrequent = FREQUENT_ONE;}/*** 获取指定 CacheKey 对应的 Value，不存在返回 null** @param key CacheKey* @return CacheValue*/@Overridepublic V get(K key) {LFUNode<K, V> node = keyToNodeMap.get(key);if (node == null) {return null;}increFrequent(node);return node.val;}/*** 增加指定节点的访问频次** @param node 待增加频次的节点*/private void increFrequent(LFUNode<K, V> node) {// 先从原来频次的 Cache 链上删除该节点int originalFreq = node.frequent;DoubleLinkedList<K, V> originalFreqList = freqLinkedListMap.get(originalFreq);originalFreqList.remove(node);int newFreq = originalFreq + 1;// 如果 originalFreqList 中就这一个节点需要更新 minFrequentif (originalFreq == minFrequent && originalFreqList.head.next == originalFreqList.tail) {minFrequent = newFreq;}// 更新节点访问频次并将其添加到 originalFrq + 1 Cache 链中node.frequent = newFreq;DoubleLinkedList<K, V> newFreqList = freqLinkedListMap.get(newFreq);if (newFreqList == null) {newFreqList = new DoubleLinkedList<>();freqLinkedListMap.put(newFreq, newFreqList);}newFreqList.addLast(node);}public int getFreeCapacity() {return this.capacity - this.size;}public int getSize() {return this.size;}/*** 测试使用** @return 返回 frequentCache 链上的第一个元素*/public K getFirstKeyByFrequent(int frequent) {DoubleLinkedList<K, V> freqLinkedList = freqLinkedListMap.get(frequent);if (freqLinkedList == null) {return null;}Node<K, V> firstNode = freqLinkedList.head.next;if (firstNode == null) {return null;}return freqLinkedList.head.next.key;}public void printCacheNodes() {Set<Map.Entry<Integer, DoubleLinkedList<K, V>>> freqToDoubleLinkedListEntries = freqLinkedListMap.entrySet();for (Map.Entry<Integer, DoubleLinkedList<K, V>> freqToDoubleLinkedListEntry : freqToDoubleLinkedListEntries) {Integer frequent = freqToDoubleLinkedListEntry.getKey();DoubleLinkedList<K, V> doubleLinkedList = freqToDoubleLinkedListEntry.getValue();System.out.println("frequent: " + frequent);doubleLinkedList.prettyPrint();System.out.println();}}/*** LFUNode 需要 frequent 属性** @param <K> CacheKey* @param <V> CacheValue*/private static class LFUNode<K, V> extends BaseCache.Node<K, V> {int frequent;LFUNode(K key, V val) {super(key, val);this.frequent = FREQUENT_ONE;}}}LFUCacheApplication
public class LFUCacheApplication {public static void main(String[] args) {LFUCache<String, Person> lfuCache = new LFUCache<>(4);System.out.println("size: " + lfuCache.getSize() + ", freeCapacity: " + lfuCache.getFreeCapacity());// size: 0, freeCapacity: 4PersonCacheUtils.addPersonsToCache(lfuCache, 2);System.out.println("size: " + lfuCache.getSize() + ", freeCapacity: " + lfuCache.getFreeCapacity());// size: 2, freeCapacity: 2lfuCache.printCacheNodes();/*** frequent: 1* CacheKey: Person_1711269533213, CacheValue: Person{id=1711269533213, name='Person-840a', age=19}* <=>* CacheKey: Person_1711269533233, CacheValue: Person{id=1711269533233, name='Person-c7cb', age=14}*/PersonCacheUtils.addPersonsToCache(lfuCache, 2);System.out.println("size: " + lfuCache.getSize() + ", freeCapacity: " + lfuCache.getFreeCapacity());// size: 4, freeCapacity: 0lfuCache.printCacheNodes();/*** frequent: 1* CacheKey: Person_1711269533213, CacheValue: Person{id=1711269533213, name='Person-840a', age=19}* <=>* CacheKey: Person_1711269533233, CacheValue: Person{id=1711269533233, name='Person-c7cb', age=14}* <=>* CacheKey: Person_1711269532769, CacheValue: Person{id=1711269532769, name='Person-5712', age=58}* <=>* CacheKey: Person_1711269533111, CacheValue: Person{id=1711269533111, name='Person-258f', age=31}*/PersonCacheUtils.addPersonsToCache(lfuCache, 2);lfuCache.printCacheNodes();/*** frequent: 1* CacheKey: Person_1711269532769, CacheValue: Person{id=1711269532769, name='Person-5712', age=58}* <=>* CacheKey: Person_1711269533111, CacheValue: Person{id=1711269533111, name='Person-258f', age=31}* <=>* CacheKey: Person_1711269533476, CacheValue: Person{id=1711269533476, name='Person-0415', age=38}* <=>* CacheKey: Person_1711269533573, CacheValue: Person{id=1711269533573, name='Person-cd37', age=22}*/System.out.println(lfuCache.get(lfuCache.getFirstKeyByFrequent(1))); // Person{id=1711269532769, name='Person-5712', age=58}lfuCache.printCacheNodes();/*** frequent: 1* CacheKey: Person_1711269533111, CacheValue: Person{id=1711269533111, name='Person-258f', age=31}* <=>* CacheKey: Person_1711269533476, CacheValue: Person{id=1711269533476, name='Person-0415', age=38}* <=>* CacheKey: Person_1711269533573, CacheValue: Person{id=1711269533573, name='Person-cd37', age=22}** frequent: 2* CacheKey: Person_1711269532769, CacheValue: Person{id=1711269532769, name='Person-5712', age=58}*/System.out.println(lfuCache.get(lfuCache.getFirstKeyByFrequent(2))); // Person{id=1711269532769, name='Person-5712', age=58}lfuCache.printCacheNodes();/*** frequent: 1* CacheKey: Person_1711269533111, CacheValue: Person{id=1711269533111, name='Person-258f', age=31}* <=>* CacheKey: Person_1711269533476, CacheValue: Person{id=1711269533476, name='Person-0415', age=38}* <=>* CacheKey: Person_1711269533573, CacheValue: Person{id=1711269533573, name='Person-cd37', age=22}** frequent: 2** frequent: 3* CacheKey: Person_1711269532769, CacheValue: Person{id=1711269532769, name='Person-5712', age=58}*/}
}这篇关于自定义 LRU、LFU Cache（Java 版）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
