文档章节

LRU缓存算法-基于双链表实现

liujiest
 liujiest
发布于 2016/05/06 21:20
字数 473
阅读 50
收藏 1

代码

import java.util.Hashtable;

public class DoubleLinkLRU {

	public static void main(String[] args) {
		DoubleLinkLRU lru = new DoubleLinkLRU(3);
		lru.put("1", "1");
		lru.put("2", "2");
		lru.put("3", "3");
		lru.printAll();
		lru.put("4", "4");
		lru.printAll();
		String node = (String) lru.get("3");
		System.out.println("访问:" + node);
		lru.printAll();
	}

	/**
	 * 链表节点
	 * 
	 * @author Administrator
	 *
	 */
	class CacheNode {
		CacheNode prev;// 前一节点
		CacheNode next;// 后一节点
		Object value;// 值
		Object key;// 键

		CacheNode() {
		}
	}

	// 构造函数
	public DoubleLinkLRU(int size) {
		currentSize = 0;
		cacheSize = size;
		nodes = new Hashtable<Object, Object>(size);// 缓存容器
	}

	/**
	 * 获取缓存中对象
	 * 
	 * @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;
	}

	public void printAll() {
		CacheNode node = first;
		System.out.println("当前容器:");
		while (node != null) {
			System.out.println(node.key + ":" + node.value);
			node = node.next;
		}
	}

	private int cacheSize;
	private Hashtable<Object, Object> nodes;// 缓存容器
	private int currentSize;
	private CacheNode first;// 链表头
	private CacheNode last;// 链表尾
}


© 著作权归作者所有

共有 人打赏支持
liujiest
粉丝 7
博文 66
码字总数 28338
作品 0
杭州
程序员
LRU 缓存置换算法

1.LRU 1.1. 原理 LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。 1.2. 实现 最...

满小茂
2016/01/13
477
0
LRU-最近最少使用算法

LRU是Least Recently Used 近期最少使用算法 1.1. 原理 LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来...

zh_iOS
2016/11/03
41
0
cache 的设计与实现

本文整理自一下两篇博客:http://my.oschina.net/ScottYang/blog/298727 http://my.oschina.net/u/866190/blog/188712 Cache简介: Cache(高速缓存), 一个在计算机中几乎随时接触的概念。C...

peiquan
2014/09/26
0
0
LRU缓存介绍与实现 (Java)

我们平时总会有一个电话本记录所有朋友的电话,但是,如果有朋友经常联系,那些朋友的电话号码不用翻电话本我们也能记住,但是,如果长时间没有联系了,要再次联系那位朋友的时候,我们又不得...

大白0-0
2015/07/28
0
0
linux2.6.28内核对页面置换算法的改进--代码

最新的linux2.6.28内核的一个重大改进就是对内存回收算法进行了修改,以往的内核中保持了active和inactive两个链表用来实现 lru算法,这个方式一直工作的很好,但是粒度过于粗糙,另外,每次...

晨曦之光
2012/04/10
453
0

没有更多内容

加载失败,请刷新页面

加载更多

【大福利】极客时间专栏返现二维码大汇总

我已经购买了如下专栏,大家通过我的二维码你可以获得一定额度的返现! 然后,再给大家来个福利,只要你通过我的二维码购买,并且关注了【飞鱼说编程】公众号,可以加我微信或者私聊我,我再...

飞鱼说编程
今天
1
0
Spring5对比Spring3.2源码之容器的基本实现

最近看了《Spring源码深度解析》,该书是基于Spring3.2版本的,其中关于第二章容器的基本实现部分,目前spring5的实现方式已有较大改变。 Spring3.2的实现: public void testSimpleLoad(){...

Ilike_Java
今天
1
0
【王阳明心学语录】-001

1.“破山中贼易,破心中贼难。” 2.“夫万事万物之理不外于吾心。” 3.“心即理也。”“心外无理,心外无物,心外无事。” 4.“人心之得其正者即道心;道心之失其正者即人心。” 5.“无...

卯金刀GG
今天
2
0
OSChina 周三乱弹 —— 我们无法成为野兽

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ _刚刚好: 霸王洗发水这波很骚 手机党少年们想听歌,请使劲儿戳(这里) hahahahahahh @嘻酱:居然忘了喝水。 让你喝可乐的话, 你准忘不了...

小小编辑
今天
11
0
vm GC 日志 配置及查看

-XX:+PrintGCDetails 打印 gc 日志 -XX:+PrintTenuringDistribution 监控晋升分布 -XX:+PrintGCTimeStamps 包含时间戳 -XX:+printGCDateStamps 包含时间 -Xloggc:<filename> 可以将数据保存为......

Canaan_
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部