package com.amg.util;
import java.util.HashMap;
import java.util.Map;
/**
* 面试官叫你手写一份lru算法实现
*
* 这里的LRUCache类维护了一个双向链表和一个哈希表,用于实现LRU算法。具体实现细节如下:
*
* - get方法:首先在哈希表中查找对应的键值对,如果不存在,则返回-1;如果存在,则将对应的节点从双向链表中删除,并将其添加到链表头部。最后返回节点的值。
*
* - put方法:首先在哈希表中查找对应的键值对,如果存在,则将该节点的值更新,并将其从双向链表中删除并添加到链表头部;如果不存在,则判断当前链表是否已满(达到容量上限),
* 如果是,则删除链表尾部的节点并在哈希表中删除对应的键值对;然后创建一个新的节点,并将其添加到链表头部和哈希表中。
*
* - addNode方法:将新节点添加到链表头部。
*
* - removeNode方法:从链表中删除指定节点。
*
* - Node类:表示双向链表中的节点,包含了键值对、前驱节点和后继节点。
*
* 另外,需要注意哈希表和双向链表的一致性维护。在put方法中,当新建节点或者更新节点时,都需要更新哈希表中的键值对,并将节点添加到链表头部;同样,在删除节点时,也需要从哈希表中删除对应的键值对。
*
* @author Amg
* @date 2023/5/20 10:44
*/
public class LRUCache {
private int capacity; // 缓存容量
private Map<Integer, Node> map = new HashMap<>(); // 哈希表用于存储缓存数据
private Node head; // 双向链表头指针
private Node tail; // 双向链表尾指针
public LRUCache(int capacity) {
this.capacity = capacity;
}
// 获取缓存数据
public int get(int key) {
Node node = map.get(key); // 从哈希表中获取节点
if (node == null) { // 如果节点不存在,返回-1
return -1;
}
if (node != head) { // 如果节点不在头部,将其移动到头部
removeNode(node); // 首先从链表中删除节点
addNode(node); // 然后将该节点添加到头部
}
return node.value; // 返回节点的值
}
// 存储缓存数据
public void put(int key, int value) {
Node node = map.get(key); // 从哈希表中获取节点
if (node != null) { // 如果节点已经存在,更新其值并将其移动到头部
node.value = value; // 更新节点的值
removeNode(node); // 首先从链表中删除节点
addNode(node); // 然后将该节点添加到头部
} else { // 如果节点不存在,创建新节点并将其添加到头部
if (map.size() >= capacity) { // 如果缓存已满,删除尾部节点
map.remove(tail.key); // 首先从哈希表中删除节点
removeNode(tail); // 然后从链表中删除节点
}
Node newNode = new Node(); // 创建新节点
newNode.key = key; // 添加键值对
newNode.value = value;
map.put(key, newNode); // 将新节点添加到哈希表中
addNode(newNode); // 将新节点添加到头部
}
}
// 将节点添加到头部
private void addNode(Node node) {
if (head == null) { // 如果链表为空,将头指针和尾指针都指向新节点
head = node;
tail = node;
} else {
node.next = head; // 将新节点的后继指针指向原来的头节点
head.prev = node; // 将原来的头节点的前驱指针指向新节点
head = node; // 更新头指针
}
}
// 将节点从链表中删除
private void removeNode(Node node) {
if (node == head && node == tail) { // 如果链表只有一个节点
head = null;
tail = null;
} else if (node == head) { // 如果节点在头部
head = node.next;
head.prev = null;
} else if (node == tail) { // 如果节点在尾部
tail = node.prev;
tail.next = null;
} else { // 如果节点在中间
node.prev.next = node.next;
node.next.prev = node.prev;
}
}
// 双向链表的节点类
private static class Node {
int key; // 节点的键
int value; // 节点的值
Node prev; // 前驱节点
Node next; // 后继节点
}
}
没有合适的资源?快使用搜索试试~ 我知道了~
Java实现简单LRU缓存算法
共1个文件
java:1个
需积分: 2 0 下载量 122 浏览量
2023-05-20
10:47:35
上传
评论
收藏 2KB ZIP 举报
温馨提示
这里的LRUCache类维护了一个双向链表和一个哈希表,用于实现LRU算法。具体实现细节如下: - get方法:首先在哈希表中查找对应的键值对,如果不存在,则返回-1;如果存在,则将对应的节点从双向链表中删除,并将其添加到链表头部。最后返回节点的值。 - put方法:首先在哈希表中查找对应的键值对,如果存在,则将该节点的值更新,并将其从双向链表中删除并添加到链表头部;如果不存在,则判断当前链表是否已满(达到容量上限),如果是,则删除链表尾部的节点并在哈希表中删除对应的键值对;然后创建一个新的节点,并将其添加到链表头部和哈希表中。 - addNode方法:将新节点添加到链表头部。 - removeNode方法:从链表中删除指定节点。 - Node类:表示双向链表中的节点,包含了键值对、前驱节点和后继节点。 另外,需要注意哈希表和双向链表的一致性维护。在put方法中,当新建节点或者更新节点时,都需要更新哈希表中的键值对,并将节点添加到链表头部;同样,在删除节点时,也需要从哈希表中删除对应的键值对。
资源推荐
资源详情
资源评论
收起资源包目录
LRUCache.zip (1个子文件)
LRUCache.java 4KB
共 1 条
- 1
资源评论
码农Amg
- 粉丝: 8
- 资源: 13
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功