转自：http://www.iteye.com/topic/692103
原理：将Cache的所有位置都用双连表连接起来，当一个位置被命中之后，就将通过调整链表的指向，将该位置调整到链表头的位置，新加入的Cache直接加到链表头中。
这样，在多次进行Cache操作后，最近被命中的，就会被向链表头方向移动，而没有命中的，而想链表后面移动，链表尾则表示最近最少使用的Cache。
当需要替换内容时候，链表的最后位置就是最少被命中的位置，我们只需要淘汰链表最后的部分即可。 帅！
import java.util.Hashtable;
/*
* 来源于： http://www.iteye.com/topic/692103
* */
public class LRU {
private int cacheSize;
private Hashtable nodes;//缓存容器
private int currentSize;
private CacheNode first;//链表头
private CacheNode last;//链表尾
class CacheNode {
CacheNode prev;//前一节点
CacheNode next;//后一节点
Object value;//值
int key;//键
CacheNode() {
}
}
public LRU(int i) {
currentSize = 0;
cacheSize = i;
nodes = new Hashtable(i);//缓存容器
}
//获取缓存中对象
public Object get(int key) {
CacheNode node = (CacheNode) nodes.get(key);
if (node != null) {
moveToHead(node);
System.out.println("get lurcache:" + key);
System.out.println("move lurcache:" + key + " to head");
return node.value;
} else {
return null;
}
}
// 添加缓存
public void put(int key, Object value) {
CacheNode node = (CacheNode) nodes.get(key);
if (node == null) {
System.out.println("insert into lurcache:" + key);
//缓存容器是否已经超过大小.
if (currentSize >= cacheSize) {
System.out.println("缓存不够了，需要移除最后一个 ");
if (last != null)//将最少使用的删除
{
System.out.println("========================");
nodes.remove(last.key);
}
removeLast();
} else {
currentSize++;
System.out.println("缓存大小为：" + currentSize);
}
node = new CacheNode();
}
node.value = value;
node.key = key;
//将最新使用的节点放到链表头，表示最新使用的.
moveToHead(node);
nodes.put(key, node);
}
//将缓存删除
public Object remove(int 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() {
System.out.println("移除中...");
//链表尾不为空,则将链表尾指向null. 删除连表尾（删除最少使用的缓存对象）
if (last != null) {
if (last.prev != null)
last.prev.next = null;
else
first = null;
last = last.prev;
}
}
//移动到链表头，表示这个节点是最新使用过的
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;
}
public void print_list()
{
CacheNode temp = first;
while(temp != last)
{
System.out.print(temp.key + " ");
temp = temp.next;
}
System.out.println("\n");
}
public static void main(String [] args)
{
LRU lrucache = new LRU(10);
CacheNode node1 = lrucache.new CacheNode();
lrucache.put(1, node1);
CacheNode node2 = lrucache.new CacheNode();
lrucache.put(2, node2);
CacheNode node3 = lrucache.new CacheNode();
lrucache.put(3, node3);
CacheNode node4 = lrucache.new CacheNode();
lrucache.put(4, node4);
CacheNode node5 = lrucache.new CacheNode();
lrucache.put(5, node5);
CacheNode node6 = lrucache.new CacheNode();
lrucache.put(6, node6);
CacheNode node7 = lrucache.new CacheNode();
lrucache.put(7, node7);
CacheNode node8 = lrucache.new CacheNode();
lrucache.put(8, node8);
CacheNode node9 = lrucache.new CacheNode();
lrucache.put(9, node9);
CacheNode node10 = lrucache.new CacheNode();
lrucache.put(10, node10);
CacheNode node11 = lrucache.new CacheNode();
lrucache.put(11, node11);
lrucache.print_list();
CacheNode node12 = lrucache.new CacheNode();
lrucache.put(12, node12);
lrucache.print_list();
lrucache.get(10);
lrucache.get(10);
lrucache.print_list();
lrucache.get(3);
lrucache.get(3);
lrucache.print_list();
}
}
最后加一个锁的并发访问吧，对于读锁与写锁的问题，加了写锁之后，就不能在添加读锁了，读锁之后还可以加写锁 。。
没什么用，但是害怕丢了
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
public class LockTest1{
final static ReadWriteLock rwlock = new ReentrantReadWriteLock();
final static Lock readLock = rwlock.readLock();
final static Lock writeLock = rwlock.writeLock();
public static void main(String[] args) throws InterruptedException {
System.out.println("test readlock-writelock");
lockR2W();
System.out.println("test writelock-readlock");
lockW2R();
System.out.println("test readlock-readlock");
lockRR();
System.out.println("test writelock-writelock");
lockWW();
}
private static void lockWW() {
writeLock.lock();
System.out.println("w lock.");
try {
if (writeLock.tryLock(1, TimeUnit.SECONDS))
System.out.println("w lock.");
else
System.out.println("when w lock, cannot w lock again.");
} catch (InterruptedException e0) {
e0.printStackTrace();
}
try {
writeLock.unlock();
System.out.println("w unlock.");
writeLock.unlock();
System.out.println("w unlock.");
} catch (Exception e) {
//ignore;
}
}
private static void lockRR() {
readLock.lock();
System.out.println("r lock.");
readLock.lock();
System.out.println("r lock.");
readLock.unlock();
System.out.println("r unlock.");
readLock.unlock();
System.out.println("r unlock.");
}
private static void lockW2R() throws InterruptedException {
writeLock.lock();
System.out.println("w lock.");
if (readLock.tryLock(1, TimeUnit.SECONDS))
System.out.println("r lock.");
else
System.out.println("when w lock, cannot r lock.");
writeLock.unlock();
System.out.println("w unlock.");
readLock.unlock();
System.out.println("r unlock.");
}
private static void lockR2W() {
readLock.lock();
System.out.println("r lock.");
try {
if (writeLock.tryLock(1, TimeUnit.SECONDS))
System.out.println("w lock.");
else
System.out.println("when r lock, cannot w lock.");
} catch (InterruptedException e0) {
e0.printStackTrace();
}
try {
readLock.unlock();
System.out.println("r unlock.");
writeLock.unlock();
System.out.println("w unlock.");
} catch (Exception e) {
//ignore;
}
}
}