Created
July 18, 2022 09:40
-
-
Save wuxianggujun/d8f5a0d1cdfeb6c31644d9de1d3568ea to your computer and use it in GitHub Desktop.
以下是基于 双向链表 + HashMap 的 LRU 算法实现,对算法的解释如下: 访问某个节点时,将其从原来的位置删除,并重新插入到链表头部。这样就能保证链表尾部存储的就是最近最久未使用的节点,当节点数量大于缓存最大空间时就淘汰链表尾部的节点。 为了使删除操作时间复杂度为 O(1),就不能采用遍历的方式找到某个节点。HashMap 存储着 Key 到节点的映射,通过 Key 就能以 O(1) 的时间得到节点,然后再以 O(1) 的时间将其从双向队列中删除。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.HashMap; | |
import java.util.Iterator; | |
/** | |
* 以下是基于 双向链表 + HashMap 的 LRU 算法实现,对算法的解释如下: | |
* | |
* 访问某个节点时,将其从原来的位置删除,并重新插入到链表头部。这样就能保证链表尾部存储的就是最近最久未使用的节点,当节点数量大于缓存最大空间时就淘汰链表尾部的节点。 | |
* 为了使删除操作时间复杂度为 O(1),就不能采用遍历的方式找到某个节点。HashMap 存储着 Key 到节点的映射,通过 Key 就能以 O(1) 的时间得到节点,然后再以 O(1) 的时间将其从双向队列中删除。 | |
* @param <K> | |
* @param <V> | |
*/ | |
public class LRU<K, V> implements Iterable<K> { | |
private Node head; | |
private Node tail; | |
private HashMap<K, Node> map; | |
private int maxSize; | |
private class Node { | |
Node pre; | |
Node next; | |
K k; | |
V v; | |
public Node(K k, V v) { | |
this.k = k; | |
this.v = v; | |
} | |
} | |
public LRU(int maxSize) { | |
this.maxSize = maxSize; | |
this.map = new HashMap<>(maxSize * 4 / 3); | |
head = new Node(null, null); | |
tail = new Node(null, null); | |
head.next = tail; | |
tail.pre = head; | |
} | |
public V get(K key) { | |
if (!map.containsKey(key)) { | |
return null; | |
} | |
Node node = map.get(key); | |
unlink(node); | |
appendHead(node); | |
return node.v; | |
} | |
public void put(K key, V value) { | |
if (map.containsKey(key)) { | |
Node node = map.get(key); | |
unlink(node); | |
} | |
Node node = new Node(key, value); | |
map.put(key, node); | |
appendHead(node); | |
if (map.size() > maxSize) { | |
Node toRemove = removeTail(); | |
map.remove(toRemove.k); | |
} | |
} | |
private Node removeTail() { | |
Node node = tail.pre; | |
Node pre = node.pre; | |
tail.pre = pre; | |
pre.next = tail; | |
node.pre = null; | |
node.next = null; | |
return node; | |
} | |
private void appendHead(Node node) { | |
Node next = head.next; | |
node.next = next; | |
next.pre = node; | |
node.pre = head; | |
head.next = node; | |
} | |
private void unlink(Node node) { | |
Node pre = node.pre; | |
Node next = node.next; | |
pre.next = next; | |
next.pre = pre; | |
node.pre = null; | |
node.next = null; | |
} | |
@Override | |
public Iterator<K> iterator() { | |
return new Iterator<K>() { | |
private Node cur = head.next; | |
@Override | |
public boolean hasNext() { | |
return cur != null; | |
} | |
@Override | |
public K next() { | |
Node node = cur; | |
cur = cur.next; | |
return node.k; | |
} | |
}; | |
} | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment