java LRU算法介绍与用法示例

java LRU算法介绍与用法示例

本文实例讲述了java LRU算法介绍与用法。分享给大家供大家参考，具体如下：

1.前言

在用户使用联网的软件的时候，总会从网络上获取数据，当在一段时间内要多次使用同一个数据的时候，用户不可能每次用的时候都去联网进行请求,既浪费时间又浪费网络

这时就可以将用户请求过的数据进行保存，但不是任意数据都进行保存，这样会造成内存浪费的。LRU算法的思想就可以运用了。

2.LRU简介

LRU是Least Recently Used 近期最少使用算法，它就可以将长时间没有被利用的数据进行删除。

LRU在人们一些情感中也体现的得很好的。当你和一群朋友接触的时候，经常联系的人关系是很好的，若很久没有联系到最后估计都不会再有联系了，也就会是失去这位朋友了。

3.下面通过代码展现LRU算法:

最简单的一种方法是利用LinkHashMap，因为它本身就有一个方法就是在所设置的缓存范围内，去除掉额外的旧数据

public class LRUByHashMap {

/*

* 通过LinkHashMap简单实现LRU算法

*/

/**

* 缓存大小

*/

private int cacheSize;

/**

* 当前缓存数目

*/

private int currentSize;

private LinkedHashMap maps;

public LRUByHashMap(int cacheSize1) {

this.cacheSize = cacheSize1;

maps = new LinkedHashMap() {

/**

*

*/

private static final long serialVersionUID = 1;

// 这里移除旧的缓存数据

@Override

protected boolean removeEldestEntry(java.util.Map.Entry eldest) {

// 当超过缓存数量的时候就将旧的数据移除

return getCurrentSize() > LRUByHashMap.this.cacheSize;

}

};

}

public synchronized int getCurrentSize() {

return maps.size();

}

public synchronized void put(K k, V v) {

if (k == null) {

throw new Error("存入的键值不能为空");

}

maps.put(k, v);

}

public synchronized void remove(K k) {

if (k == null) {

throw new Error("移除的键值不能为空");

}

maps.remove(k);

}

public synchronized void clear() {

maps = null;

}

// 获取集合

public synchronized Collection getCollection() {

if (maps != null) {

return maps.values();

} else {

return null;

}

}

public static void main(String[] args) {

// 测试

LRUByHashMap maps = new LRUByHashMap(

3);

maps.put(1, "1");

maps.put(2, "2");

maps.put(3, "3");

maps.put(4, "4");

maps.put(5, "5");

mahttp://ps.put(6, "6");

Collection

System.out.println("存入缓存中的数据是--->>" + col.toString());

}

}

运行后的效果:

代码明明是put了6个Entry但最后只显示了三个，之间的三个是旧的所以直接被咔嚓掉了

第二种方法是利用双向链表 + HashTable

双向链表的作用是用来记录位置的，而HashTable作为容器来存储数据的

为什么用HashTable不用HashMap呢？

1.HashTable的键和值都不能为null;

2.上面用LinkHashMap实现的LRU，有用到 synchronized , 让线程同步去处理，这样就避免在多线程处理统一数据时造成问题

而HashTable自带同步机制的，所以多线程就能对HashTable进行正确的处理了。

Cache的所都用有位置双连表连接起来，当一个位置被命中之后，就将通过调整链表的指向，将该位置调整到链表头的位置，新加入的Cache直接加到链表 头中。这样，在多次进行Cache操作后，

最近被命中的，就会被向链表头方向移动，而没有命中的，而想链表后面移动，链表尾则表示最近最少使用的 Cache。当需要替换内容时候，链表的最后位置就是最少被命中的位置，我们只需要淘

汰链表最后的部分即可

public class LRUCache {

private int cacheSize;

private Hashtable

private int currentSize;

private Entry first;//链表头

private Entry last;//链表尾

public LRUCache(int i) {

currentSize = 0;

cacheSize = i;

nodes = new Hashtable

}

/**

* 获取缓存中对象,并把它放在最前面

*/

public Entry get(Object key) {

Entry node = nodes.get(key);

if (node != null) {

moveToHead(node);

return node;

} else {

return null;

}

}

/**

* 添加 entry到hashtable, 并把entry

*/

public void put(Object key, Object value) {

//先查看hashtable是否存在该entry, 如果存在，则只更新其value

Entry node = nodes.get(key);

if (node == null) {

//缓存容器是否已经超过大小.

if (currentSize >= cacheSize) {

nodes.remove(last.key);

removeLast();

} else {

currentSize++;

}

node = new Entry();

}

node.value = value;

//将最新使用的节点放到链表头，表示最新使用的.

node.key = key

moveToHead(node);

nodes.put(key, node);

}

/**

* 将entry删除, 注意：删除操作只有在cache满了才会被执行

*/

public void remove(Object key) {

Entry node = 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;

}

//在hashtable中删除

nodes.remove(key);

}

/**

* 删除链表尾部节点，即使用最后 使用的entry

*/

private void removeLast() {

//链表尾不为空,则将链表尾指向null. 删除连表尾（删除最少使用的缓存对象）

if (last != null) {

if (last.prev != null)

last.prev.next = null;

elhttp://se

first = null;

last = last.prev;

}

}

/**

* 移动到链表头，表示这个节点是最新使用过的

*/

private void moveToHead(Entry 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 clear() {

first = null;

last = null;

currentSize = 0;

}

}

class Entry {

Entry prev;//前一节点

Entry next;//后一节点

Object value;//值

Object key;//键

}

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

System.out.println("存入缓存中的数据是--->>" + col.toString());

}

}

运行后的效果:

代码明明是put了6个Entry但最后只显示了三个，之间的三个是旧的所以直接被咔嚓掉了

第二种方法是利用双向链表 + HashTable

双向链表的作用是用来记录位置的，而HashTable作为容器来存储数据的

为什么用HashTable不用HashMap呢？

1.HashTable的键和值都不能为null;

2.上面用LinkHashMap实现的LRU，有用到 synchronized , 让线程同步去处理，这样就避免在多线程处理统一数据时造成问题

而HashTable自带同步机制的，所以多线程就能对HashTable进行正确的处理了。

Cache的所都用有位置双连表连接起来，当一个位置被命中之后，就将通过调整链表的指向，将该位置调整到链表头的位置，新加入的Cache直接加到链表 头中。这样，在多次进行Cache操作后，

最近被命中的，就会被向链表头方向移动，而没有命中的，而想链表后面移动，链表尾则表示最近最少使用的 Cache。当需要替换内容时候，链表的最后位置就是最少被命中的位置，我们只需要淘

汰链表最后的部分即可

public class LRUCache {

private int cacheSize;

private Hashtable

private int currentSize;

private Entry first;//链表头

private Entry last;//链表尾

public LRUCache(int i) {

currentSize = 0;

cacheSize = i;

nodes = new Hashtable

}

/**

* 获取缓存中对象,并把它放在最前面

*/

public Entry get(Object key) {

Entry node = nodes.get(key);

if (node != null) {

moveToHead(node);

return node;

} else {

return null;

}

}

/**

* 添加 entry到hashtable, 并把entry

*/

public void put(Object key, Object value) {

//先查看hashtable是否存在该entry, 如果存在，则只更新其value

Entry node = nodes.get(key);

if (node == null) {

//缓存容器是否已经超过大小.

if (currentSize >= cacheSize) {

nodes.remove(last.key);

removeLast();

} else {

currentSize++;

}

node = new Entry();

}

node.value = value;

//将最新使用的节点放到链表头，表示最新使用的.

node.key = key

moveToHead(node);

nodes.put(key, node);

}

/**

* 将entry删除, 注意：删除操作只有在cache满了才会被执行

*/

public void remove(Object key) {

Entry node = 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;

}

//在hashtable中删除

nodes.remove(key);

}

/**

* 删除链表尾部节点，即使用最后 使用的entry

*/

private void removeLast() {

//链表尾不为空,则将链表尾指向null. 删除连表尾（删除最少使用的缓存对象）

if (last != null) {

if (last.prev != null)

last.prev.next = null;

elhttp://se

first = null;

last = last.prev;

}

}

/**

* 移动到链表头，表示这个节点是最新使用过的

*/

private void moveToHead(Entry 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 clear() {

first = null;

last = null;

currentSize = 0;

}

}

class Entry {

Entry prev;//前一节点

Entry next;//后一节点

Object value;//值

Object key;//键

}

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。