调度访问后的节点需要移动到链表尾部 。
完整代码import java.util.HashMap;/** * @Auther: Xianglei * @Company: * @Date: 2020/6/27 14:52 * @Version 1.0 */public class XLRUCache<K, V> { private int size; // 存储K和Node节点的映射 Node中会存放KV private HashMap<K, Node> map; private Node head; private Node tail; XLRUCache(int size) { this.size = size; map = new HashMap<>(); } /** * 添加元素 * 1.元素存在，将元素移动到队尾 * 2.不存在，判断链表是否满 。 * 如果满，则删除队首元素，放入队尾元素，删除更新哈希表 * 如果不满，放入队尾元素，更新哈希表 */ public void put(K key, V value) { Node node = map.get(key); if (node != null) { //更新值 node.v = value; moveNodeToTail(node); } else { Node newNode = new Node(key, value); //链表满，需要删除首节点 if (map.size() == size) { Node delHead = removeHead(); map.remove(delHead.k); } addLast(newNode); map.put(key, newNode); } } public V get(K key) { Node node = map.get(key); if (node != null) { moveNodeToTail(node); return node.v; } return null; } public void addLast(Node newNode) { if (newNode == null) { return; } if (head == null) { head = newNode; tail = newNode; } else { tail.next = newNode; newNode.pre = tail; tail = newNode; } } public void moveNodeToTail(Node node) { if (tail == node) { return; } if (head == node) { head = node.next; head.pre = null; } else { node.pre.next = node.next; node.next.pre = node.pre; } node.pre = tail; node.next = null; tail.next = node; tail = node; } public Node removeHead() { if (head == null) { return null; } Node res = head; if (head == tail) { head = null; tail = null; } else { head = res.next; head.pre = null; res.next = null; } return res; } /** * 定义双向链表 */ class Node { K k; V v; Node pre; Node next; Node(K k, V v) { this.k = k; this.v = v; } }}
推荐阅读
- 一致性哈希算法的介绍与实现
- 春茶到底贵在哪儿,真正都匀毛尖春茶去哪儿了
- MySQL中一条SQL到底是如何执行的？
- 隔夜白菜到底能不能吃
- 《机器学习算法的几大分类》
- 茶烟到底对身体有害吗,吃砖茶上火吗
- 川茶到底有多热,川茶集团复工后工人选茶间隔3米以上
- 最大熵强化学习算法SAC
- Python量化工具之“k线波幅加速”算法跟踪止盈，仅需一行代码
- 红茶到底要不要加糖？[红茶]