Created
September 11, 2017 06:34
-
-
Save yunnysunny/3c45223313b9f5fbc698407cebf5816b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class LRUCache { | |
/** | |
* 链表节点 | |
* @author Administrator | |
* | |
*/ | |
class CacheNode { | |
CacheNode prev;//前一节点 | |
CacheNode next;//后一节点 | |
Object value;//值 | |
Object key;//键 | |
CacheNode() { | |
} | |
} | |
public LRUCache(int i) { | |
currentSize = 0; | |
cacheSize = i; | |
nodes = new Hashtable(i);//缓存容器 | |
} | |
/** | |
* 获取缓存中对象 | |
* @param key | |
* @return | |
*/ | |
public Object get(Object key) { | |
CacheNode node = (CacheNode) nodes.get(key); | |
if (node != null) { | |
moveToHead(node); | |
return node.value; | |
} else { | |
return null; | |
} | |
} | |
/** | |
* 添加缓存 | |
* @param key | |
* @param value | |
*/ | |
public void put(Object key, Object value) { | |
CacheNode node = (CacheNode) nodes.get(key); | |
if (node == null) { | |
//缓存容器是否已经超过大小. | |
if (currentSize >= cacheSize) { | |
if (last != null)//将最少使用的删除 | |
nodes.remove(last.key); | |
removeLast(); | |
} else { | |
currentSize++; | |
} | |
node = new CacheNode(); | |
} | |
node.value = value; | |
node.key = key; | |
//将最新使用的节点放到链表头,表示最新使用的. | |
moveToHead(node); | |
nodes.put(key, node); | |
} | |
/** | |
* 将缓存删除 | |
* @param key | |
* @return | |
*/ | |
public Object remove(Object key) { | |
CacheNode node = (CacheNode) nodes.get(key); | |
if (node != null) { | |
if (node.prev != null) { | |
node.prev.next = node.next; | |
} | |
if (node.next != null) { | |
node.next.prev = node.prev; | |
} | |
if (last == node) | |
last = node.prev; | |
if (first == node) | |
first = node.next; | |
} | |
return node; | |
} | |
public void clear() { | |
first = null; | |
last = null; | |
} | |
/** | |
* 删除链表尾部节点 | |
* 表示 删除最少使用的缓存对象 | |
*/ | |
private void removeLast() { | |
//链表尾不为空,则将链表尾指向null. 删除连表尾(删除最少使用的缓存对象) | |
if (last != null) { | |
if (last.prev != null) | |
last.prev.next = null; | |
else | |
first = null; | |
last = last.prev; | |
} | |
} | |
/** | |
* 移动到链表头,表示这个节点是最新使用过的 | |
* @param node | |
*/ | |
private void moveToHead(CacheNode node) { | |
if (node == first) | |
return; | |
if (node.prev != null) | |
node.prev.next = node.next; | |
if (node.next != null) | |
node.next.prev = node.prev; | |
if (last == node) | |
last = node.prev; | |
if (first != null) { | |
node.next = first; | |
first.prev = node; | |
} | |
first = node; | |
node.prev = null; | |
if (last == null) | |
last = first; | |
} | |
private int cacheSize; | |
private Hashtable nodes;//缓存容器 | |
private int currentSize; | |
private CacheNode first;//链表头 | |
private CacheNode last;//链表尾 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment