赞
踩
LFU 算法是通过存储每个缓存使用的频率,在缓存容量满了之后,删除使用频率最少的缓存来给新的缓存留出空间。
如果多个缓存节点都拥有最少使用频率,则删除最久未使用的节点。
HashMap 以及LinkedHashSet(链表)。
链表中的 Node 需要存储 key, value, frequency。使用一个 HashMap (frequencyTable)存储键值 frequency -> 链表, 另一个 HashMap(cacheTable)存储键值 key -> Node。
定义一个 minFrequency 记录最少使用的频率。
对于 get 操作,我们首先使用 key 来获取 cacheTable 中对应的 node:
1, 如果 key 不存在,则直接返回 null。
2, 如果 key 存在,我们直接从 node 所在的链表中移除该节点,从 node 中获取当前的 frequency 值并加1, 把该 node 插入到 frequency+1 对应的链表尾部,判断是否需要更新minFrequency。
对于 put 操作,我们首先使用 key 来获取 cacheTable 中对应的 node:
1. 如果 key 不存在, 如果没有的话,相当于是新加入的缓存,如果缓存已经到达容量,通过 minFrequency 找到并删除最近最少使用的缓存,再进行插入。
2. 如果 key 存在,其实操作等价于 get(key) 操作,唯一的区别就是我们需要将当前的缓存里的值更新为 value。
如果需要线程安全,只需在 get 和 put方法加上 synchronized 修饰符。
- import java.util.HashMap;
- import java.util.LinkedHashSet;
- import java.util.Map;
-
- public class LFUCache<K, V> {
-
- class CacheNode {
- K key;
- V value;
- int frequency;
- CacheNode(K key, V value, int frequency) {
- this.key = key;
- this.value = value;
- this.frequency = frequency;
- }
- }
-
- private Map<Integer, LinkedHashSet<CacheNode>> frequencyTable = new HashMap<>();
- private Map<K, CacheNode> cacheTable = new HashMap<>();
- private int minFrequency;
- private int capacity;
-
- public LFUCache(int capacity) {
- this.capacity = capacity;
- this.minFrequency = 0;
- }
-
- public void put(K key, V value) {
- if (capacity <= 0) {
- return;
- }
- CacheNode node = cacheTable.get(key);
- if (node != null) {
- node.value = value;
- increaseFrequency(node);
- } else {
- if (cacheTable.size() == capacity) {
- removeMinFrequencyNode();
- }
- addNewCacheNode(key, value);
- }
- }
-
- public V get(K key) {
- if (capacity <= 0) {
- return null;
- }
- CacheNode node = cacheTable.get(key);
- if (node != null) {
- increaseFrequency(node);
- return node.value;
- }
- return null;
- }
-
- private void addNewCacheNode(K key, V value) {
- CacheNode newCacheNode = new CacheNode(key, value, 1);
- LinkedHashSet<CacheNode> set = frequencyTable.computeIfAbsent(1, k -> new LinkedHashSet<>());
- set.add(newCacheNode);
- cacheTable.put(key, newCacheNode);
- minFrequency = 1;
- }
-
- private void removeMinFrequencyNode() {
- LinkedHashSet<CacheNode> minFrequencySet = frequencyTable.get(minFrequency);
- CacheNode minFrequencyNode = minFrequencySet.iterator().next();
- cacheTable.remove(minFrequencyNode.key);
- minFrequencySet.remove(minFrequencyNode);
- if (minFrequencySet.size() == 0) {
- frequencyTable.remove(minFrequency);
- }
- }
-
- private void increaseFrequency(CacheNode node) {
- int of = node.frequency;
- LinkedHashSet<CacheNode> set = frequencyTable.get(node.frequency);
- set.remove(node);
- if (set.isEmpty()) {
- frequencyTable.remove(of);
- if (of == minFrequency) {
- minFrequency++;
- }
- }
- int nf = node.frequency + 1;
- node.frequency++;
- LinkedHashSet<CacheNode> newSet = frequencyTable.computeIfAbsent(nf, k -> new LinkedHashSet<>());
- newSet.add(node);
- }
-
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。