文档章节

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

liujiest
 liujiest
发布于 2016/05/06 21:20
字数 473
阅读 47
收藏 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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JS三元运算示例

1. topFlag=topFlag ==0?1:0; 等于 if(topFlag=00){ topFlag=1; }else if(topFlag == 1){ topFlag=0; } 2. 5>3?alert('5大'):alert('3大'); 即 if(5>3){alert('5大')}else{alert('3大')}; 注......

森火
今天
0
0
利用Slf4j的MDC跟踪方法调用链

why? 一个web项目通常提供很多URL访问地址, 项目一般都是分层处理,例如Controller——>Service——>DAO。 如果想根据日志查看用户一次请求都走了哪些方法(多数是查错误)。 如果系统是多人...

杨春炼
今天
7
0
Maven介绍及安装

Maven介绍及安装 以下内容是本人早期学习时的笔记,可能比较详实繁琐,现在复习一下Maven,顺便将内容抛出来,供大家一起学习进步。 一、Maven简介 Maven是Apache旗下的一款项目管理工具,是...

星汉
今天
0
0
小程序Aes解密

主要步骤: 1、下载AES源码(JS版) 2、在小程序中新建一个公共的文件夹,把AES源码拷贝进去(注意:需要暴露接口 module.exports = CryptoJS;) 3、添加一个用于加密解密的公共JS,可取名为...

Mr_Tea伯奕
今天
0
0
Go实现文件传输(基本传输可用)

发送端 package mainimport ("fmt""os""net""io")func SendFile(path string, connect net.Conn){file, oerr :=os.Open(path)if oerr !=nil{fmt.Println("Open", oerr)......

CHONGCHEN
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部