简介
LRU (Least Recently Used,最近最少使用)算法是操作系统中一种经典的页面置换算法,这么卷的环境下肯定要会手写拉,这篇就是讲茴字的几种写法。
双向链表
简单来说就一个链表,左端入,清理最右,插入与查询都是O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
| public class LinkListLRUCache {
private LinkedList<Node> cache;
private int capacity;
public LRUCache(int capacity) { this.cache = new LinkedList<>(); this.capacity = capacity; }
public int get(int key) { Iterator<Node> iterator = cache.descendingIterator(); int result = -1; while (iterator.hasNext()) { Node node = iterator.next(); if (node.key == key) { result = node.val; iterator.remove(); put(key, result); break; } } return result; }
public void put(int key, int value) { Iterator<Node> iterator = cache.iterator(); while (iterator.hasNext()) { Node node = iterator.next(); if (node.key == key) { iterator.remove(); break; } }
if (capacity == cache.size()) { cache.removeFirst(); } cache.add(new Node(key, value)); }
class Node { int key; int val;
public Node(int key, int val) { this.key = key; this.val = val; } } }
|
哈希链表
用LinkedHashMap代替LinkedList,插入与查询都是O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
| public class HashLinkListLRUCache {
private LinkedHashMap<Integer, Integer> cache;
private int capacity;
public HashLinkListLRUCache(int capacity) { this.cache = new LinkedHashMap<>(); this.capacity = capacity; }
public int get(int key) { if (!cache.containsKey(key)) return -1;
int val = cache.get(key); cache.remove(key); cache.put(key, val); return val; }
public void put(int key, int value) { if (cache.containsKey(key)) { cache.remove(key); }
if (capacity == cache.size()) { Set<Integer> keySet = cache.keySet(); Iterator<Integer> iterator = keySet.iterator(); cache.remove(iterator.next()); }
cache.put(key, value); }
} ```
当然,也可以重写LinkedHashMap#removeEldestEntry(Map.Entry) ```java import java.util.LinkedHashMap; import java.util.Map;
public class HashLinkListLRUCache {
private Map<Integer, Integer> cache;
public HashLinkListLRUCache(int capacity) { this.cache = new LinkedHashMap<>() { private static final long serialVersionUID = 1L;
@Override protected boolean removeEldestEntry(java.util.Map.Entry<Integer, Integer> eldest) { return size() > capacity; } }; }
public int get(int key) { if (!cache.containsKey(key)) return -1;
int val = cache.get(key); cache.remove(key); cache.put(key, val); return val; }
public void put(int key, int value) { if (cache.containsKey(key)) { cache.remove(key); }
cache.put(key, value); }
}
|
通用一点
改的给阳间一点:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private static final long serialVersionUID = 1L;
private int capacity;
public LRUCache(int capacity) { super(capacity); this.capacity = capacity; }
@Override protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return size() > capacity; }
}
|