LFU vs LRU
LFU 最近最少使用优先
Least Frequently Used ，淘汰一段时间内使用次数最少的页面。
LRU 最久未使用
Least Recently Used ，淘汰最长时间没有使用的页面。
练习题
假设LFU方法的时期T为10分钟，访问如下页面的时间正好为10分钟，内页块大小为3，页面顺序： 2 1 2 1 2 3 4 ，当需要使用4页面时，内存块中没有页面4，就会发生缺页中断，而且此时内存块已满，需要进行页面转换。
| 次数 | LRU | LFU |
|---|---|---|
| 1 | 2 | 2（1） |
| 2 | 2，1 | 2（1），1（1） |
| 3 | 1，2 | 2（2），1（1） |
| 4 | 2, 1 | 2（2），1（2） |
| 5 | 1, 2 | 2（3），1（2） |
| 6 | 1, 2 , 3 | 2（3），1（2），3（1） |
| 7 | 2, 3, 4 (置换出1) | 2（3），1（2），4（1） 3使用次数最少，优先置换出3 |
FIFO 先进先出
First in First out， 队列
代码
LFU
package cn.com.cninfo.reply;import java.util.Hashtable;/*** @author chenxinwei* @date 2021/7/23 18:11**/public class LFUCache {class DNode {DNode prev, next;int key, value, count;@Overridepublic String toString() {return "DNode key[" + key + "] value[" + value + ']';}}//添加到头部private void addNodeFrist(DNode node) {node.next = head.next;node.prev = head;head.next = node;node.next.prev = node;}//移除nodeprivate void removeNode(DNode node) {node.prev.next = node.next;node.next.prev = head;}//将某个Node移到头部private void removeNodeToHead(DNode node) {removeNode(node);addNodeFrist(node);}//查找访问频率最低的节点进行移除private DNode removeLastNode() {DNode pNode = head.next;DNode lowVisitNode = head.next;int lowVisitTime = tail.prev.count;while (pNode != null && pNode.count > 0) {if (lowVisitTime >= pNode.count) {lowVisitTime = pNode.count;lowVisitNode = pNode;}lowVisitNode = lowVisitNode.next;}removeNode(lowVisitNode);return lowVisitNode;}private int capacity, size;private Hashtable<Integer, DNode> cache;private DNode head, tail;public LFUCache(int capacity) {this.capacity = capacity;this.cache = new Hashtable<>(capacity);this.size = 0;head = new DNode();tail = new DNode();head.next = tail;tail.prev = head;}public void put(int key, int value) {DNode node = cache.get(key);if (node == null) {DNode newNode = new DNode();newNode.key = key;newNode.value = value;cache.put(key, newNode);addNodeFrist(newNode);size++;if (size > capacity) {DNode res = removeLastNode();cache.remove(res.key);size--;}} else {node.value = value;removeNodeToHead(node);}}public int get(int key) {DNode node = cache.get(key);if (node == null) {return -1;}removeNodeToHead(node);return node.value;}public static void main(String[] args) {LFUCache cache = new LFUCache(3);cache.put(2, 2);cache.put(1, 1);System.out.println(cache.get(2));System.out.println(cache.get(1));System.out.println(cache.get(2));cache.put(3, 3);cache.put(4, 4);//1、2元素都有访问次数，放入3后缓存满，加入4时淘汰3System.out.println(cache.get(3));System.out.println(cache.get(2));//System.out.println(cache.get(1));System.out.println(cache.get(4));cache.put(5, 5);//目前2访问2次，1访问一次，4访问一次，由于4的时间比较新，放入5的时候移除1元素。System.out.println("=============================");cache.cache.entrySet().forEach(entry -> {System.out.println(entry.getValue());});}}// cache的容量为：1// cache的容量为：2// cache的容量为：3// cache的容量为：4// cache的容量为：5// cache的容量为：5// cache的容量为：5// cache的容量为：5// cache的容量为：5// cache的容量为：5// cache的容量为：5// =-=-=-=-=-=-=-// map元素:// 7// 8// 9// 10// 11
LinkedHashMap
LinkedHashMap采用数组 + 单身链表的形式，只是在节点Entry中增加了Before和after变量，用于维护双向链表保存LinkedHashMap的存储顺序。这个双向链表提供了两种排序方法，插入顺序（accessOrder为false时）和访问顺序（accessOrder为true时）。
LRU
package cn.com.cninfo.reply;
import java.util.Hashtable;
/**
* @author chenxinwei
* @date 2021/7/23 18:11
**/
public class LFUCache {
class DNode {
DNode prev, next;
int key, value, count;
@Override
public String toString() {
return "DNode key[" + key + "] value[" + value + ']';
}
}
//添加到头部
private void addNodeFrist(DNode node) {
node.next = head.next;
node.prev = head;
head.next = node;
node.next.prev = node;
}
//移除node
private void removeNode(DNode node) {
node.prev.next = node.next;
node.next.prev = head;
}
//将某个Node移到头部
private void removeNodeToHead(DNode node) {
removeNode(node);
addNodeFrist(node);
}
//查找访问频率最低的节点进行移除
private DNode removeLastNode() {
DNode pNode = head.next;
DNode lowVisitNode = head.next;
int lowVisitTime = tail.prev.count;
while (pNode != null && pNode.count > 0) {
if (lowVisitTime >= pNode.count) {
lowVisitTime = pNode.count;
lowVisitNode = pNode;
}
lowVisitNode = lowVisitNode.next;
}
removeNode(lowVisitNode);
return lowVisitNode;
}
private int capacity, size;
private Hashtable<Integer, DNode> cache;
private DNode head, tail;
public LFUCache(int capacity) {
this.capacity = capacity;
this.cache = new Hashtable<>(capacity);
this.size = 0;
head = new DNode();
tail = new DNode();
head.next = tail;
tail.prev = head;
}
public void put(int key, int value) {
DNode node = cache.get(key);
if (node == null) {
DNode newNode = new DNode();
newNode.key = key;
newNode.value = value;
cache.put(key, newNode);
addNodeFrist(newNode);
size++;
if (size > capacity) {
DNode res = removeLastNode();
cache.remove(res.key);
size--;
}
} else {
node.value = value;
removeNodeToHead(node);
}
}
public int get(int key) {
DNode node = cache.get(key);
if (node == null) {
return -1;
}
removeNodeToHead(node);
return node.value;
}
public static void main(String[] args) {
LFUCache cache = new LFUCache(3);
cache.put(2, 2);
cache.put(1, 1);
System.out.println(cache.get(2));
System.out.println(cache.get(1));
System.out.println(cache.get(2));
cache.put(3, 3);
cache.put(4, 4);
//1、2元素都有访问次数，放入3后缓存满，加入4时淘汰3
System.out.println(cache.get(3));
System.out.println(cache.get(2));
//System.out.println(cache.get(1));
System.out.println(cache.get(4));
cache.put(5, 5);
//目前2访问2次，1访问一次，4访问一次，由于4的时间比较新，放入5的时候移除1元素。
System.out.println("=============================");
cache.cache.entrySet().forEach(entry -> {
System.out.println(entry.getValue());
});
}
}
// 2
// 1
// 2
// 3
// 2
// -1
// =============================
// DNode key[3] value[3]
// DNode key[2] value[2]
// DNode key[1] value[1]
若有收获，就点个赞吧
0 人点赞
