用HashMap+LinkedList进行实现。
- LinkedList表尾存储的是最新被访问的元素
- 当缓存数量超过容量时，选择删除最近最久未被访问的元素删除，以腾出空间
相关方法——增删改查
public void put(K k,V v)
public void remove(K k)
public V get(K k)
一、HashMap+LinkedList
/**
* HashMap和LinkedList构造LRUCache
* <p>Description: </p>
* @author 杨丽金
* @date 2018-9-15
* @version 1.0
*/
public class LRUCache<K,V> {
// 指定容量缓存数据
private int capacity;
Map<K,V> map;
LinkedList<K> list;// 维护访问顺序
public LRUCache(int capacity){
this.capacity=capacity;
map=new HashMap<K,V>();
list=new LinkedList<K>();
}
/**
* 添加、修改元素
* @param k
* @param v
*/
public void put(K k,V v){
map.put(k,v);
// 修改list
if(list.contains(k)){
list.remove(k);
list.add(k);
}else{
list.add(k);
if(map.size()>capacity){
// 容量超了
K oldKey=list.getFirst();
list.removeFirst();
map.remove(oldKey);
}
}
}
/**
* 删除元素
* @param k
*/
public void remove(K k){
map.remove(k);
list.remove(k);
}
/**
* 获取元素
* @param k
* @return
*/
public V get(K k){
if(map.containsKey(k)){
list.remove(k);
list.add(k);
return map.get(k);
}else{
return null;
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int capacity=scan.nextInt();
LRUCache<Integer, String> cache=new LRUCache<>(capacity);
while(scan.hasNext()){
// 操作
String op=scan.next();
if("add".equals(op)){
int key=scan.nextInt();
String value=scan.next();
cache.put(key, value);
}else if ("delete".equals(op)){
int key=scan.nextInt();
cache.remove(key);
}else if("update".equals(op)){
int key=scan.nextInt();
String value=scan.next();
cache.put(key, value);
}else if("get".equals(op)){
int key=scan.nextInt();
cache.get(key);
}
System.out.println(cache.list.toString());
}
}
}
二、HashMap+自己实现的LinkedList
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class LRUCache2<K,V> {
class Node{
Node prev;
K data;
Node next;
public Node(Node prev,K data,Node next){
this.prev=prev;
this.data=data;
this.next=next;
}
}
// 缓存容量
int capacity;
Map<K,V> map;
// 自己实现双向链表
Node first;
Node last;
public LRUCache2(int capacity){
this.capacity=capacity;
map=new HashMap<K,V>();
first=null;
last=null;
}
/**
* 从缓存中添加元素/修改元素
* @param k
* @param v
*/
public void put(K k,V v){
// 1,
map.put(k, v);
// 2,
if(listContains(k)){
// 说明是修改
listRemove(k);
listAdd(k);// 添加到链表尾部
}else{
// 说明时添加
listAdd(k);
K oldKey=first.data;
if(map.size()>capacity){
// 将链表头元素删除
listRemove(first.data);
map.remove(oldKey);
}
}
}
/**
* 向链表的表尾部添加元素
* @param k
*/
private void listAdd(K k) {
Node l=last;
Node newNode=new Node(l,k,null);
if(l!=null){
l.next=newNode;
}else{
first=newNode;
}
last=newNode;
}
/**
* 从链表中删除元素
* @param k
*/
private void listRemove(K k) {
Node f=first;
// 先找到，然后删除
if(k==null){
while(f!=null){
if(f.data==null){
// 找到，删除
unLink(f);
return;
}
f=f.next;
}
}else{
while(f!=null){
if(k.equals(f.data)){
// 找到，删除
unLink(f);
return;
}
f=f.next;
}
}
}
/**
* 将节点从链表上删除下去
* @param f
*/
private void unLink(Node f) {
Node prev=f.prev;
Node next=f.next;
if(prev!=null){
prev.next=next;
}else{
first=next;
}
if(next!=null){
next.prev=prev;
}else{
last=prev;
}
f=null;
}
/**
* 双向链表中是否包含该元素
* @param k
* @return
*/
private boolean listContains(K k) {
Node f=first;
if(k==null){
// 遍历整个链表
while(f!=null){
if(f.data==null){
return true;
}
f=f.next;
}
}else{
while(f!=null){
if(k.equals(f.data)){
return true;
}
f=f.next;
}
}
return false;
}
/**
* 从缓存中删除元素
* @param k
*/
public void remove(K k){
map.remove(k);
listRemove(k);
}
/**
* 从缓存中得到元素
* @param k
* @return
*/
public V get(K k){
if(map.containsKey(k)){
// 修改list
listRemove(k);
listAdd(k);
return map.get(k);
}else{
return null;
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int capacity=scan.nextInt();
LRUCache<Integer, String> cache=new LRUCache<>(capacity);
while(scan.hasNext()){
// 操作
String op=scan.next();
if("add".equals(op)){
int key=scan.nextInt();
String value=scan.next();
cache.put(key, value);
}else if ("delete".equals(op)){
int key=scan.nextInt();
cache.remove(key);
}else if("update".equals(op)){
int key=scan.nextInt();
String value=scan.next();
cache.put(key, value);
}else if("get".equals(op)){
int key=scan.nextInt();
cache.get(key);
}
System.out.println(cache.list.toString());
}
}
}
