Skip to content

Commit c89b3e8

Browse files
author
liuxun
committed
实现LRU缓存
1 parent 04ee124 commit c89b3e8

3 files changed

Lines changed: 243 additions & 0 deletions

File tree

‎src/main/java/com/algorithm/study/demo/LRUCache/LRULinkedMap.java‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package com.algorithm.study.demo.LRUCache;
2+
3+
import java.util.ArrayList;
4+
import java.util.Collection;
5+
import java.util.LinkedHashMap;
6+
import java.util.Map;
7+
8+
/**
9+
* LinkedHashMap实现LRU缓存
10+
* @Author: liuxun
11+
* @CreateDate: 2018/7/12 下午8:42
12+
* @Version: 1.0
13+
*/
14+
public class LRULinkedMap<K,V> {
15+
/**
16+
* 最大缓存大小
17+
*/
18+
private int cacheSize;
19+
private LinkedHashMap<K,V> cacheMap ;
20+
public LRULinkedMap(int cacheSize) {
21+
this.cacheSize = cacheSize;
22+
cacheMap = new LinkedHashMap(16,0.75F,true){
23+
@Override
24+
protected boolean removeEldestEntry(Map.Entry eldest) {
25+
if (cacheSize + 1 == cacheMap.size()){
26+
return true ;
27+
}else {
28+
return false ;
29+
}
30+
}
31+
};
32+
}
33+
public void put(K key,V value){
34+
cacheMap.put(key,value) ;
35+
}
36+
public V get(K key){
37+
return cacheMap.get(key) ;
38+
}
39+
public Collection<Map.Entry<K, V>> getAll() {
40+
return new ArrayList<Map.Entry<K, V>>(cacheMap.entrySet());
41+
}
42+
public static void main(String[] args) {
43+
LRULinkedMap<String,Integer> map = new LRULinkedMap(4) ;
44+
map.put("1",1);
45+
map.put("2",2);
46+
map.put("3",3);
47+
map.put("4",4);
48+
map.put("5",5);
49+
for (Map.Entry<String, Integer> e : map.getAll()){
50+
System.out.print(e.getKey() + " : " + e.getValue() + "\t");
51+
}
52+
}
53+
}

‎src/main/java/com/algorithm/study/demo/LRUCache/LRUMap.java‎

Lines changed: 171 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,171 @@
1+
package com.algorithm.study.demo.LRUCache;
2+
3+
import java.util.HashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* LRU缓存链表实现思路
8+
* 每次写入数据时将数据放入链表头结点。
9+
* 使用数据时候将数据移动到头结点。
10+
* 缓存数量超过阈值时移除链表尾部数据。
11+
* @Author: liuxun
12+
* @CreateDate: 2018/7/12 下午6:05
13+
* @Version: 1.0
14+
*/
15+
public class LRUMap<K,V> {
16+
private final Map<K, V> cacheMap = new HashMap<>();
17+
/**
18+
* 最大缓存大小
19+
*/
20+
private int cacheSize;
21+
/**
22+
* 节点大小
23+
*/
24+
private int nodeCount;
25+
/**
26+
* 头结点
27+
*/
28+
private Node<K, V> header;
29+
/**
30+
* 尾结点
31+
*/
32+
private Node<K, V> tailer;
33+
public LRUMap(int cacheSize) {
34+
this.cacheSize = cacheSize;
35+
this.header=null;
36+
this.tailer=null;
37+
}
38+
public void put(K key, V value) {
39+
cacheMap.put(key, value);
40+
//双向链表中添加结点
41+
addNode(key, value);
42+
}
43+
public V get(K key){
44+
Node<K, V> node = getNode(key);
45+
//移动到头结点
46+
moveToHead(node) ;
47+
return cacheMap.get(key);
48+
}
49+
private void moveToHead(Node<K,V> node){
50+
//如果是最后的一个节点
51+
if (node.next == null){
52+
node.tail.next=null;
53+
tailer=node.tail;
54+
nodeCount -- ;
55+
}
56+
//如果是本来就是头节点 不作处理
57+
if (node.tail == null){
58+
return ;
59+
}
60+
//如果处于中间节点
61+
if (node.tail != null && node.next != null){
62+
//它的上一节点指向它的下一节点 也就删除当前节点
63+
node.tail.next=node.next;
64+
nodeCount -- ;
65+
}
66+
//最后在头部增加当前节点
67+
//注意这里需要重新 new 一个对象，不然原本的node 还有着下面的引用，会造成内存溢出。
68+
node = new Node<>(node.getKey(),node.getValue()) ;
69+
addHead(node) ;
70+
}
71+
/**
72+
* 链表查询 效率较低
73+
* @param key
74+
* @return
75+
*/
76+
private Node<K,V> getNode(K key){
77+
Node<K,V> node = header ;
78+
while (node != null){
79+
if (node.getKey().equals(key)){
80+
return node ;
81+
}
82+
node = node.next ;
83+
}
84+
return null ;
85+
}
86+
/**
87+
* 写入头结点
88+
* @param key
89+
* @param value
90+
*/
91+
private void addNode(K key, V value) {
92+
Node<K, V> node = new Node<>(key, value);
93+
//容量满了删除最后一个
94+
if (cacheSize == nodeCount) {
95+
//删除尾结点
96+
delTail();
97+
}
98+
//写入头结点
99+
addHead(node);
100+
}
101+
/**
102+
* 添加头结点
103+
*
104+
* @param node
105+
*/
106+
private void addHead(Node<K, V> node) {
107+
if (header==null){
108+
tailer=node;
109+
}else{
110+
header.tail=node;
111+
node.next=header;
112+
}
113+
header=node;
114+
nodeCount++;
115+
}
116+
private void delTail() {
117+
//把尾结点从缓存中删除
118+
cacheMap.remove(tailer.getKey());
119+
tailer.tail.next=null;
120+
tailer=tailer.tail;
121+
nodeCount--;
122+
}
123+
private class Node<K, V> {
124+
private K key;
125+
private V value;
126+
Node<K, V> tail;
127+
Node<K, V> next;
128+
public Node(K key, V value) {
129+
this.key = key;
130+
this.value = value;
131+
}
132+
public Node() {
133+
}
134+
public K getKey() {
135+
return key;
136+
}
137+
public void setKey(K key) {
138+
this.key = key;
139+
}
140+
public V getValue() {
141+
return value;
142+
}
143+
public void setValue(V value) {
144+
this.value = value;
145+
}
146+
}
147+
@Override
148+
public String toString() {
149+
StringBuilder sb = new StringBuilder() ;
150+
Node<K,V> node = header ;
151+
while (node != null){
152+
if (node.getKey()!=null){
153+
sb.append(node.getKey()).append(":")
154+
.append(node.getValue())
155+
.append("-->");
156+
}
157+
node = node.next ;
158+
}
159+
return sb.toString();
160+
}
161+
public static void main(String[] args) {
162+
LRUMap<String,String> lruMap=new LRUMap<>(3);
163+
lruMap.put("1","1");
164+
lruMap.put("2","2");
165+
lruMap.put("3","3");
166+
lruMap.get("1");
167+
lruMap.put("4","4");
168+
System.out.println(lruMap.toString());
169+
}
170+
171+
}

‎src/main/java/com/algorithm/study/demo/datastructure/linear/TwoLinkList.java‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
package com.algorithm.study.demo.datastructure.linear;
22

3+
import com.algorithm.study.demo.LRUCache.LRUMap;
4+
35
/**
46
* 双向链表实现
57
* Created by liuxun on 2017/6/19.
@@ -145,4 +147,21 @@ private void checkPositionIndex(int index) {
145147
public int size(){
146148
return size;
147149
}
150+
@Override
151+
public String toString() {
152+
StringBuilder sb = new StringBuilder() ;
153+
Node node= first ;
154+
while (node != null){
155+
sb.append(node.element)
156+
.append("-->") ;
157+
node = node.next ;
158+
}
159+
return sb.toString();
160+
}
161+
public static void main(String[] args) {
162+
TwoLinkList<String> twoLinkList=new TwoLinkList<>();
163+
// twoLinkList.add("1");
164+
// twoLinkList.add("2");
165+
System.out.println(twoLinkList.toString());
166+
}
148167
}

0 commit comments

Comments
 (0)