Skip to content

Commit e5825d1

Browse files
crossoverJiecrossoverJie
authored
Merge pull request crossoverJie#25 from crossoverJie/dev
LRU cache
2 parents 805ebc2 + 1d970e3 commit e5825d1

File tree

7 files changed

+441
-6
lines changed

7 files changed

+441
-6
lines changed

‎MD/spring/spring-bean-lifecycle.md

+1
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
## Spring Bean 生命周期
22

33

4+
### 前言
45

56
Spring Bean 的生命周期在整个 Spring 中占有很重要的位置，掌握这些可以加深对 Spring 的理解。
67

‎src/main/java/com/crossoverjie/actual/AbstractMap.java renamed to ‎src/main/java/com/crossoverjie/actual/LRUAbstractMap.java

+4-4
Original file line numberDiff line numberDiff line change
@@ -24,9 +24,9 @@
2424
* Date: 02/02/2018 20:47
2525
* @since JDK 1.8
2626
*/
27-
public class AbstractMap extends java.util.AbstractMap {
27+
public class LRUAbstractMap extends java.util.AbstractMap {
2828

29-
private final static Logger LOGGER = LoggerFactory.getLogger(AbstractMap.class);
29+
private final static Logger LOGGER = LoggerFactory.getLogger(LRUAbstractMap.class);
3030

3131
/**
3232
* 检查是否超期线程
@@ -74,7 +74,7 @@ public class AbstractMap extends java.util.AbstractMap {
7474
private volatile AtomicInteger size ;
7575

7676

77-
public AbstractMap() {
77+
public LRUAbstractMap() {
7878

7979

8080
arraySize = DEFAULT_ARRAY_SIZE;
@@ -310,7 +310,7 @@ public String toString() {
310310

311311

312312
/**
313-
* 摘抄自 HashMap 的 hash 实现
313+
* copy HashMap 的 hash 实现
314314
* @param key
315315
* @return
316316
*/

‎src/main/java/com/crossoverjie/actual/LRULinkedMap.java

+53
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package com.crossoverjie.actual;
2+
3+
import java.util.ArrayList;
4+
import java.util.Collection;
5+
import java.util.LinkedHashMap;
6+
import java.util.Map;
7+
8+
/**
9+
* Function:
10+
*
11+
* @author crossoverJie
12+
* Date: 05/04/2018 12:04
13+
* @since JDK 1.8
14+
*/
15+
public class LRULinkedMap<K,V> {
16+
17+
18+
/**
19+
* 最大缓存大小
20+
*/
21+
private int cacheSize;
22+
23+
private LinkedHashMap<K,V> cacheMap ;
24+
25+
26+
public LRULinkedMap(int cacheSize) {
27+
this.cacheSize = cacheSize;
28+
29+
cacheMap = new LinkedHashMap(16,0.75F,true){
30+
@Override
31+
protected boolean removeEldestEntry(Map.Entry eldest) {
32+
if (cacheSize + 1 == cacheMap.size()){
33+
return true ;
34+
}else {
35+
return false ;
36+
}
37+
}
38+
};
39+
}
40+
41+
public void put(K key,V value){
42+
cacheMap.put(key,value) ;
43+
}
44+
45+
public V get(K key){
46+
return cacheMap.get(key) ;
47+
}
48+
49+
50+
public Collection<Map.Entry<K, V>> getAll() {
51+
return new ArrayList<Map.Entry<K, V>>(cacheMap.entrySet());
52+
}
53+
}

‎src/main/java/com/crossoverjie/actual/LRUMap.java

+226
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,226 @@
1+
package com.crossoverjie.actual;
2+
3+
import java.util.HashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* Function:
8+
*
9+
* @author crossoverJie
10+
* Date: 03/04/2018 00:08
11+
* @since JDK 1.8
12+
*/
13+
public class LRUMap<K, V> {
14+
private final Map<K, V> cacheMap = new HashMap<>();
15+
16+
/**
17+
* 最大缓存大小
18+
*/
19+
private int cacheSize;
20+
21+
/**
22+
* 节点大小
23+
*/
24+
private int nodeCount;
25+
26+
27+
/**
28+
* 头结点
29+
*/
30+
private Node<K, V> header;
31+
32+
/**
33+
* 尾结点
34+
*/
35+
private Node<K, V> tailer;
36+
37+
public LRUMap(int cacheSize) {
38+
this.cacheSize = cacheSize;
39+
//头结点的下一个结点为空
40+
header = new Node<>();
41+
header.next = null;
42+
43+
//尾结点的上一个结点为空
44+
tailer = new Node<>();
45+
tailer.tail = null;
46+
47+
//双向链表 头结点的上结点指向尾结点
48+
header.tail = tailer;
49+
50+
//尾结点的下结点指向头结点
51+
tailer.next = header;
52+
53+
54+
}
55+
56+
public void put(K key, V value) {
57+
cacheMap.put(key, value);
58+
59+
//双向链表中添加结点
60+
addNode(key, value);
61+
}
62+
63+
public V get(K key){
64+
65+
Node<K, V> node = getNode(key);
66+
67+
//移动到头结点
68+
moveToHead(node) ;
69+
70+
return cacheMap.get(key);
71+
}
72+
73+
private void moveToHead(Node<K,V> node){
74+
75+
//如果是最后的一个节点
76+
if (node.tail == null){
77+
node.next.tail = null ;
78+
tailer = node.next ;
79+
nodeCount -- ;
80+
}
81+
82+
//如果是本来就是头节点 不作处理
83+
if (node.next == null){
84+
return ;
85+
}
86+
87+
//如果处于中间节点
88+
if (node.tail != null && node.next != null){
89+
//它的上一节点指向它的下一节点 也就删除当前节点
90+
node.tail.next = node.next ;
91+
nodeCount -- ;
92+
}
93+
94+
//最后在头部增加当前节点
95+
//注意这里需要重新 new 一个对象，不然原本的node 还有着下面的引用，会造成内存溢出。
96+
node = new Node<>(node.getKey(),node.getValue()) ;
97+
addHead(node) ;
98+
99+
}
100+
101+
/**
102+
* 链表查询 效率较低
103+
* @param key
104+
* @return
105+
*/
106+
private Node<K,V> getNode(K key){
107+
Node<K,V> node = tailer ;
108+
while (node != null){
109+
110+
if (node.getKey().equals(key)){
111+
return node ;
112+
}
113+
114+
node = node.next ;
115+
}
116+
117+
return null ;
118+
}
119+
120+
121+
/**
122+
* 写入头结点
123+
* @param key
124+
* @param value
125+
*/
126+
private void addNode(K key, V value) {
127+
128+
Node<K, V> node = new Node<>(key, value);
129+
130+
//容量满了删除最后一个
131+
if (cacheSize == nodeCount) {
132+
//删除尾结点
133+
delTail();
134+
135+
//写入头结点
136+
addHead(node);
137+
} else {
138+
addHead(node);
139+
140+
}
141+
142+
143+
}
144+
145+
146+
/**
147+
* 添加头结点
148+
*
149+
* @param node
150+
*/
151+
private void addHead(Node<K, V> node) {
152+
153+
//写入头结点
154+
header.next = node;
155+
node.tail = header;
156+
header = node;
157+
nodeCount++;
158+
159+
//如果写入的数据大于2个 就将初始化的头尾结点删除
160+
if (nodeCount == 2) {
161+
tailer.next.next.tail = null;
162+
tailer = tailer.next.next;
163+
}
164+
165+
}
166+
167+
private void delTail() {
168+
//把尾结点从缓存中删除
169+
cacheMap.remove(tailer.getKey());
170+
171+
//删除尾结点
172+
tailer.next.tail = null;
173+
tailer = tailer.next;
174+
175+
nodeCount--;
176+
177+
}
178+
179+
private class Node<K, V> {
180+
private K key;
181+
private V value;
182+
Node<K, V> tail;
183+
Node<K, V> next;
184+
185+
public Node(K key, V value) {
186+
this.key = key;
187+
this.value = value;
188+
}
189+
190+
public Node() {
191+
}
192+
193+
public K getKey() {
194+
return key;
195+
}
196+
197+
public void setKey(K key) {
198+
this.key = key;
199+
}
200+
201+
public V getValue() {
202+
return value;
203+
}
204+
205+
public void setValue(V value) {
206+
this.value = value;
207+
}
208+
209+
}
210+
211+
@Override
212+
public String toString() {
213+
StringBuilder sb = new StringBuilder() ;
214+
Node<K,V> node = tailer ;
215+
while (node != null){
216+
sb.append(node.getKey()).append(":")
217+
.append(node.getValue())
218+
.append("-->") ;
219+
220+
node = node.next ;
221+
}
222+
223+
224+
return sb.toString();
225+
}
226+
}

‎src/test/java/com/crossoverjie/actual/AbstractMapTest.java

+2-2
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,7 @@ public class AbstractMapTest {
1010

1111
@Test
1212
public void test(){
13-
AbstractMap map = new AbstractMap() ;
13+
LRUAbstractMap map = new LRUAbstractMap() ;
1414
map.put(1,1) ;
1515
map.put(2,2) ;
1616

@@ -22,7 +22,7 @@ public void test(){
2222
}
2323

2424
public static void main(String[] args) {
25-
AbstractMap map = new AbstractMap() ;
25+
LRUAbstractMap map = new LRUAbstractMap() ;
2626
map.put(1,1) ;
2727
map.put(2,2) ;
2828

0 commit comments

Comments
 (0)