这里有新鲜出炉的 Java 并发编程示例,程序狗速度看过来!
Java 程序设计语言
java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 程序设计语言和 Java 平台(即 JavaEE(j2ee), JavaME(j2me), JavaSE(j2se))的总称.
这篇文章主要介绍了 java LRU 算法, 简单介绍了 LRU 算法的概念并结合实例形式分析了 LRU 算法的具体使用方法, 需要的朋友可以参考下
本文实例讲述了 java LRU 算法介绍与用法.分享给大家供大家参考,具体如下:
1. 前言
在用户使用联网的软件的时候,总会从网络上获取数据,当在一段时间内要多次使用同一个数据的时候,用户不可能每次用的时候都去联网进行请求, 既浪费时间又浪费网络
这时就可以将用户请求过的数据进行保存,但不是任意数据都进行保存,这样会造成内存浪费的.LRU 算法的思想就可以运用了.
2.LRU 简介
LRU 是 Least Recently Used 近期最少使用算法,它就可以将长时间没有被利用的数据进行删除.
LRU 在人们一些情感中也体现的得很好的.当你和一群朋友接触的时候,经常联系的人关系是很好的,若很久没有联系到最后估计都不会再有联系了,也就会是失去这位朋友了.
3. 下面通过代码展现 LRU 算法:
最简单的一种方法是利用 LinkHashMap,因为它本身就有一个方法就是在所设置的缓存范围内,去除掉额外的旧数据
运行后的效果:
public class LRUByHashMap < K,
V > {
/*
* 通过LinkHashMap简单实现LRU算法
*/
/**
* 缓存大小
*/
private int cacheSize;
/**
* 当前缓存数目
*/
private int currentSize;
private LinkedHashMap < K,
V > maps;
public LRUByHashMap(int cacheSize1) {
this.cacheSize = cacheSize1;
maps = new LinkedHashMap < K,
V > () {
/**
*
*/
private static final long serialVersionUID = 1;
// 这里移除旧的缓存数据
@Override protected boolean removeEldestEntry(java.util.Map.Entry < K, V > 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 < V > getCollection() {
if (maps != null) {
return maps.values();
} else {
return null;
}
}
public static void main(String[] args) {
// 测试
LRUByHashMap < Integer,
String > maps = new LRUByHashMap < Integer,
String > (3);
maps.put(1, "1");
maps.put(2, "2");
maps.put(3, "3");
maps.put(4, "4");
maps.put(5, "5");
maps.put(6, "6");
Collection < String > col = maps.getCollection();
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.当需要替换内容时候,链表的最后位置就是最少被命中的位置,我们只需要淘
汰链表最后的部分即可
希望本文所述对大家 java 程序设计有所帮助.
public class LRUCache {
private int cacheSize;
private Hashtable < Object,
Entry > nodes; //缓存容器
private int currentSize;
private Entry first; //链表头
private Entry last; //链表尾
public LRUCache(int i) {
currentSize = 0;
cacheSize = i;
nodes = new Hashtable < Object,
Entry > (i); //缓存容器
}
/**
* 获取缓存中对象,并把它放在最前面
*/
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;
else 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; //键
}
来源: http://www.phperz.com/article/18/0116/353527.html