文档章节

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

liujiest
 liujiest
发布于 2016/05/06 21:20
字数 473
阅读 62
收藏 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
粉丝 8
博文 75
码字总数 34353
作品 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
LRU缓存介绍与实现 (Java)

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

大白0-0
2015/07/28
0
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缓存淘汰算法」

前几节学习了「链表」、「时间与空间复杂度」的概念,本节将结合「循环链表」、「双向链表」与 「用空间换时间的设计思想」来设计一个很有意思的缓存淘汰策略:LRU缓存淘汰算法。 循环链表的...

AI科技大本营
2018/12/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

ToolBar控件在C#开发APP中的使用方式【附案例源码】——Smobiler移动开发平台

控件说明 底部工具栏控件。 效果演示 其他效果 该界面为仿淘宝UI制作的一个简单的UI模板,源码获取方式请拉至文章末尾。 特色属性 属性 属性说明 Direction(相对布局) 容器主轴方向。 Flex...

amanda112
17分钟前
0
0
模块

AMD是"Asynchronous Module Definition"的缩写,意思就是"异步模块定义"。它采用异步方式加载模块,模块的加载不影响它后面语句的运行。所有依赖这个模块的语句,都定义在一个回调函数中,等...

gtandsn
24分钟前
1
0
代码之外的生存指南,这6本书助你提升软实力

上期盟主向大家推荐了6本技术类书籍,引起了热烈反响。那么,工作之余,还有哪些好书能够为你打开更多的精彩世界呢?本期,多位知名企业的技术大咖将继续为您带来好书推荐,在新的一年里,为...

安卓绿色联盟
27分钟前
3
0
5分钟用Jitpack发布开源库

作者: 菜刀文 Demo:https://github.com/helen-x/JitPackReleaseDemo 项目开发中会用到很多开源库, 他们一般通过Maven/Gradle依赖进来的. 演而优则唱,开发越来越溜以后, 你是否也蠢蠢欲动,想发...

SuShine
33分钟前
2
0
状态码 301 与 302的区别

302重定向只是暂时的重定向,搜索引擎会抓取新的内容而保留旧的地址,因为服务器返回302,所以,搜索搜索引擎认为新的网址是暂时的。 而301重定向是永久的重定向,搜索引擎在抓取新的内容的同...

小草先森
39分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部