`

LRU算法 java实现

 
阅读更多

最简单的LRU算法实现,就是利用Java的LinkedHashMap,覆写其中的removeEldestEntry(Map.Entry)

 

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.Map;

/**
 * 类说明:利用LinkedHashMap实现简单的缓存, 必须实现removeEldestEntry方法,具体参见JDK文档
 * 
 * 
 * @param
 * @param
 */
public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {
	/**
	 * 
	 */
	private static final long serialVersionUID = -2960999970549803724L;

	private final int maxCapacity;

	private static final float DEFAULT_LOAD_FACTOR = 0.75f;

	private final Lock lock = new ReentrantLock();

	public LRULinkedHashMap(int maxCapacity) {
		super(maxCapacity, DEFAULT_LOAD_FACTOR, true);
		this.maxCapacity = maxCapacity;
	}

	@Override
	protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
		return size() > maxCapacity;
	}

	@Override
	public boolean containsKey(Object key) {
		try {
			lock.lock();
			return super.containsKey(key);
		} finally {
			lock.unlock();
		}
	}

	@Override
	public V get(Object key) {
		try {
			lock.lock();
			return super.get(key);
		} finally {
			lock.unlock();
		}
	}

	@Override
	public V put(K key, V value) {
		try {
			lock.lock();
			return super.put(key, value);
		} finally {
			lock.unlock();
		}
	}

	public int size() {
		try {
			lock.lock();
			return super.size();
		} finally {
			lock.unlock();
		}
	}

	public void clear() {
		try {
			lock.lock();
			super.clear();
		} finally {
			lock.unlock();
		}
	}

	public Collection<Map.Entry<K, V>> getAll() {
		try {
			lock.lock();
			return new ArrayList<Map.Entry<K, V>>(super.entrySet());
		} finally {
			lock.unlock();
		}
	}
}

 

如果你去看LinkedHashMap的源码可知,LRU算法是通过双向链表来实现,当某个位置被命中,通过调整链表的指向将该位置调整到头位置,新加入的内容直接放在链表头,如此一来,最近被命中的内容就向链表头移动,需要替换时,链表最后的位置就是最近最少使用的位置。

    LRU算法还可以通过计数来实现,缓存存储的位置附带一个计数器,当命中时将计数器加1,替换时就查找计数最小的位置并替换,结合访问时间戳来实现。这种算法比较适合缓存数据量较小的场景,显然,遍历查找计数最小位置的时间复杂度为O(n)。我实现了一个,结合了访问时间戳,当最小计数大于MINI_ACESS时(这个参数的调整对命中率有较大影响),就移除最久没有被访问的项:

 

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * 
 * 类说明:当缓存数目不多时,才用缓存计数的传统LRU算法
 * 
 * @param
 * @param
 */
public class LRUCache<K, V> implements Serializable {

    /**
	 * 
	 */
	private static final long serialVersionUID = 2727577376847051556L;

	private static final int DEFAULT_CAPACITY = 100;

	protected Map<K, ValueEntry> map;

	private final ReadWriteLock lock = new ReentrantReadWriteLock();

	private final Lock readLock = lock.readLock();

	private final Lock writeLock = lock.writeLock();

	private volatile int maxCapacity; // 保持可见性

	public static int MINI_ACCESS = 5;

	public LRUCache() {
		this(DEFAULT_CAPACITY);
	}

	public LRUCache(int capacity) {
		if (capacity <= 0)
			throw new RuntimeException("缓存容量不得小于0");
		this.maxCapacity = capacity;
		this.map = new HashMap<K, ValueEntry>(maxCapacity);
	}

	public boolean ContainsKey(K key) {
		try {
			readLock.lock();
			return this.map.containsKey(key);
		} finally {
			readLock.unlock();
		}
	}

	public V put(K key, V value) {
		try {
			writeLock.lock();
			if ((map.size() > maxCapacity - 1) && !map.containsKey(key)) {
				// System.out.println("开始");
				Set<Entry<K, ValueEntry>> entries = this.map.entrySet();
				removeRencentlyLeastAccess(entries);
			}
			ValueEntry new_value = new ValueEntry(value);
			ValueEntry old_value = map.put(key, new_value);
			if (old_value != null) {
				new_value.count = old_value.count;
				return old_value.value;
			} else
				return null;
		} finally {
			writeLock.unlock();
		}
	}

    /**
     * 移除最近最少访问
     */
	protected V removeRencentlyLeastAccess(Set<Map.Entry<K, ValueEntry>> entries) {
		// 最小使用次数
		long least = 0;
		// 访问时间最早
		long earliest = 0;
		K toBeRemovedByCount = null;
		K toBeRemovedByTime = null;
		Iterator<Map.Entry<K, ValueEntry>> it = entries.iterator();
		if (it.hasNext()) {
			Map.Entry<K, ValueEntry> valueEntry = it.next();
			least = valueEntry.getValue().count.get();
			toBeRemovedByCount = valueEntry.getKey();
			earliest = valueEntry.getValue().lastAccess.get();
			toBeRemovedByTime = valueEntry.getKey();
		}
		while (it.hasNext()) {
			Map.Entry<K, ValueEntry> valueEntry = it.next();
			if (valueEntry.getValue().count.get() < least) {
				least = valueEntry.getValue().count.get();
				toBeRemovedByCount = valueEntry.getKey();
			}
			if (valueEntry.getValue().lastAccess.get() < earliest) {
				earliest = valueEntry.getValue().count.get();
				toBeRemovedByTime = valueEntry.getKey();
			}
		}
		// System.out.println("remove:" + toBeRemoved);
		// 如果最少使用次数大于MINI_ACCESS,那么移除访问时间最早的项(也就是最久没有被访问的项)
		if (least > MINI_ACCESS) {
			return map.remove(toBeRemovedByTime).value;
		} else {
			return map.remove(toBeRemovedByCount).value;
		}
	}

	public V get(K key) {
		try {
			readLock.lock();
			V value = null;
			ValueEntry valueEntry = map.get(key);
			if (valueEntry != null) {
				// 更新访问时间戳
				valueEntry.updateLastAccess();
				// 更新访问次数
				valueEntry.count.incrementAndGet();
				value = valueEntry.value;
			}
			return value;
		} finally {
			readLock.unlock();
		}
	}

	public void clear() {
		try {
			writeLock.lock();
			map.clear();
		} finally {
			writeLock.unlock();
		}
	}

	public int size() {
		try {
			readLock.lock();
			return map.size();
		} finally {
			readLock.unlock();
		}
	}

	public long getCount(K key) {
		try {
			readLock.lock();
			ValueEntry valueEntry = map.get(key);
			if (valueEntry != null) {
				return valueEntry.count.get();
			}
			return 0;
		} finally {
			readLock.unlock();
		}
	}

	public Collection<Entry<K, V>> getAll() {
		try {
			readLock.lock();
			Set<K> keys = map.keySet();
			Map<K, V> tmp = new HashMap<K, V>();
			for (K key : keys) {
				tmp.put(key, map.get(key).value);
			}
			return new ArrayList<Entry<K, V>>(tmp.entrySet());
		} finally {
			readLock.unlock();
		}
	}

	class ValueEntry implements Serializable {

		/**
		 * 
		 */
		private static final long serialVersionUID = -7626403101359191860L;

		private V value;

		private AtomicLong count;

		private AtomicLong lastAccess;

		public ValueEntry(V value) {
			this.value = value;
			this.count = new AtomicLong(0);
			lastAccess = new AtomicLong(System.nanoTime());
		}

		public void updateLastAccess() {
			this.lastAccess.set(System.nanoTime());
		}

	}
}

 

 

sdf

分享到:
评论

相关推荐

    Java实现LRU算法.zip

    总的来说,Java实现LRU算法的关键在于利用数据结构特性来跟踪页面的使用频率,通过淘汰最近最少使用的页面来优化内存使用。通过学习和理解LRU算法的实现,我们可以更好地理解和处理内存限制问题,提高系统的性能和...

    LRU算法java实现课程设计大作业

    理解LRU或CLOCK改进算法等置换算法;...按照最多5块的内存分配情况,编程实现所选算法,动态输入访问内存的块号序列,输出置换结果; 测试:输入合法、非法的访问序列数据,检查程序的正确性和健壮性。

    操作系统之LRU算法(java)(csdn)————程序.pdf

    操作系统之LRU算法(Java) LRU(Least Recently Used,最近最少使用)算法是一种常用的页面置换算法,用于操作系统中管理内存页面。该算法的基本思想是:当进程在 CPU 上运行时,如指令中涉及逻辑地址时,操作系统...

    一个LRU算法的实现

    在这个实验设计课程中,我们将探讨LRU算法的原理和实现。 首先,我们需要理解LRU算法的核心思想。假设有一个固定大小的缓存(或内存),当新的数据请求进来而缓存已满时,LRU算法会选择最近最少使用的数据进行替换...

    JAVA实现FIFO、LRU、OPT页面置换算法,有界面

    4. JAVA实现带界面的页面置换算法: 在这个项目中,开发者使用Java编程语言实现了上述三种页面置换算法,并提供了一个图形用户界面(GUI)。用户可以设定页面数量,生成随机页面序列,并在指定的物理块中观察页面...

    实现了LRU算法的缓存

    当缓存满时,LRU算法会优先淘汰最近最少使用的数据。在这个Java实现的LRU缓存中,我们可能会看到以下几个关键知识点: 1. **数据结构的选择**: LRU缓存通常基于哈希表和双向链表实现。哈希表用于快速查找,而双向...

    LRU算法.zip

    LRU(Least Recently Used)算法是一种常用的页面替换算法,用于管理有限的内存资源。...通过深入研究这个LRU算法的实现,你不仅可以掌握LRU算法的工作原理,还能了解到如何在实际项目中应用和优化这种缓存策略。

    LRU.rar_LRU_LRU java_lru.java

    在这个Java实现的LRU算法示例中,我们将深入探讨LRU的核心概念、如何在Java中实现以及可能的应用场景。 1. LRU算法原理: LRU算法的基本思想是:如果一个数据最近被访问过,那么将来被访问的可能性会更高。在内存...

    LRU算法LRU算法LRU算法LRU算法

    在Java中,实现LRU算法可以使用`java.util.LinkedHashMap`类,它内部已经实现了LRU的逻辑。通过设置`accessOrder`参数为`true`,`LinkedHashMap`会按照访问顺序进行排序,从而实现LRU的效果。 总结一下,LRU算法是...

    LRU.rar_LRU_lru 算法_lru算法

    在实际操作中,LRU算法的实现可以采用以下两种方式: 1. **数组+哈希表**:使用固定大小的数组存储数据,哈希表记录数据项的位置。每次访问数据时,先在哈希表中查找,找到则更新其位置并返回,未找到则将新数据...

    操作系统os页面置换算法(java实现)Clock、Lru、Opt、Fifo

    LRU算法基于“最近使用的页面在未来最不可能再次被使用”的假设。它维护一个按照访问时间排序的页面列表,当需要替换页面时,总是选择最近最久未使用的页面。在Java实现中,可以使用数据结构如LinkedHashMap来跟踪...

    操作系统课设-LRU算法的实现 (2).docx

    LRU算法的实现旨在让学生深入理解操作系统的内存管理机制,尤其是虚拟内存的页面替换策略。通过实际编程,加深对理论知识的理解,提升问题解决和编程能力。 2. **设计要求**: - 需要模拟一个简单的内存系统,...

    页面算法模拟(java实现)

    在这个Java实现的项目中,我们将探讨两种主要的页面替换算法:FIFO(先进先出)和LRU(最近最少使用)。这两种算法都是为了解决虚拟存储系统中的缓存问题,即如何决定哪些页面应该被替换到磁盘,以便为新的或已修改...

    操作系统 程实现请求分页存储管理页面Optimal、FIFO、LRU置换算法

    本实验旨在通过实际编程实现请求分页存储管理中的三种页面置换算法:最优置换算法(Optimal)、先进先出置换算法(FIFO)以及最近最少使用置换算法(LRU),帮助学生深入理解和掌握虚拟存储管理的核心概念和技术。...

    Lru.rar_LRU IN java_lru.java_replacement_simulation LRU_页面置换

    总之,`Lru.rar`项目提供了一个用Java实现的LRU页面置换算法实例,通过`Lru.java`类和`www.pudn.com.txt`测试数据,我们可以理解和学习LRU算法的工作原理及其在实际问题中的应用。这种模拟对于理解内存管理、虚拟...

    FIFO与LRU 算法实现(java).rar_FIFO Java_LRU_fifo

    这里,我们将详细讨论这两种算法的原理及其Java实现。 FIFO算法是最简单的缓存替换策略,它基于队列数据结构。当新的数据项进入缓存时,如果缓存已满,最先进入的元素(即队列头部的元素)将被移除以腾出空间。这种...

    基于单链表LRU算法(java)

    基于单链表LRU算法(java)

    缓存淘汰算法之LRU

    LRU 算法的实现简单,但命中时需要遍历链表,找到命中的数据块索引,然后需要将数据移到头部。 4. LRU-K 算法 LRU-K 算法是为了解决 LRU 算法“缓存污染”的问题,其核心思想是将“最近使用过 1 次”的判断标准...

    Java对象缓存系统的实现,实现了LRU算法,并可以进行集群同步

    `LRUCache.java`文件中应包含了实现LRU算法的数据结构,如双向链表结合哈希映射,以及添加、删除和查找操作,确保高效地执行这些操作。 **Java缓存实现** 在`Cache.java`文件中,可能定义了基础的缓存接口或抽象类...

Global site tag (gtag.js) - Google Analytics