`

LRU缓存的实现

多线程GoogleCacheperformancethread 
阅读更多

LinkedHashMap是一个现成的LRU实现。但其缺乏并发机制，并且没有实现满载删除条件(removeEldestEntry)，因此本文认为LinkedHashMap是预留扩展的LRU类。

本文将继承该类进一步实现LRU缓存。

首先，并发使用可重入锁。对于封读锁后是否可写，封写锁后是否可读的问题，这是一个封锁策略。一般而言，读后，若写，会产生脏数据。写后，若读则没有问题。

 

可重入锁之读写锁，封锁顺序测试：

package lock;

import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class LockTest1{
	final static ReadWriteLock rwlock = new ReentrantReadWriteLock();
	final static Lock readLock = rwlock.readLock();
	final static Lock writeLock = rwlock.writeLock();

	public static void main(String[] args) throws InterruptedException {
		System.out.println("test readlock-writelock");
		lockR2W();
		System.out.println("test writelock-readlock");
		lockW2R();
		System.out.println("test readlock-readlock");
		lockRR();
		System.out.println("test writelock-writelock");
		lockWW();
	}

	private static void lockWW() {
		writeLock.lock();
		System.out.println("w lock.");
		try {
			if (writeLock.tryLock(1, TimeUnit.SECONDS))
				System.out.println("w lock.");
			else
				System.out.println("when w lock, cannot w lock again.");
		} catch (InterruptedException e0) {
			e0.printStackTrace();
		}
		try {
			writeLock.unlock();
			System.out.println("w unlock.");
			writeLock.unlock();
			System.out.println("w unlock.");
		} catch (Exception e) {
			//ignore;
		}
	}

	private static void lockRR() {
		readLock.lock();
		System.out.println("r lock.");
		readLock.lock();
		System.out.println("r lock.");
		readLock.unlock();
		System.out.println("r unlock.");
		readLock.unlock();
		System.out.println("r unlock.");
	}

	private static void lockW2R() throws InterruptedException {
		writeLock.lock();
		System.out.println("w lock.");
		if (readLock.tryLock(1, TimeUnit.SECONDS))
			System.out.println("r lock.");
		else
			System.out.println("when w lock, cannot r lock.");
		writeLock.unlock();
		System.out.println("w unlock.");
		readLock.unlock();
		System.out.println("r unlock.");
	}

	private static void lockR2W() {
		readLock.lock();
		System.out.println("r lock.");
		try {
			if (writeLock.tryLock(1, TimeUnit.SECONDS))
				System.out.println("w lock.");
			else
				System.out.println("when r lock, cannot w lock.");
		} catch (InterruptedException e0) {
			e0.printStackTrace();
		}
		try {
			readLock.unlock();
			System.out.println("r unlock.");
			writeLock.unlock();
			System.out.println("w unlock.");
		} catch (Exception e) {
			//ignore;
		}
	}
}

 测试结果：

test readlock-writelock

r lock.
when r lock, cannot w lock.
r unlock.
test writelock-readlock

w lock.
r lock.
w unlock.
r unlock.
test readlock-readlock

r lock.
r lock.
r unlock.
r unlock.
test writelock-writelock

w lock.
w lock.
w unlock.
w unlock.

 

LRU的意义在于最近被访问的数据总是可以最快从缓存中读取到。因此，下面要测试最新数据的位置和缓存已满时数据的处理。

package lru;

import java.util.Iterator;
import java.util.Map.Entry;

public class LRUTest{
	public static void main(String[] args) {
		int maxCapacity = 5;
		OjadbMap<Integer, String> lruMap = new OjadbMap<Integer, String>(maxCapacity);
		for (int i = 0; i < maxCapacity; i++) {
			lruMap.put(i, "data[" + i + "]");
		}
		lruMap.get(3);
		Iterator<Entry<Integer, String>> iter = lruMap.entrySet().iterator();
		while (iter.hasNext()) {
			System.out.println(iter.next().getValue());
		}
		System.out.println();
		lruMap.put(9, "data[ 9 ]");
		Iterator<Entry<Integer, String>> iter1 = lruMap.entrySet().iterator();
		while (iter1.hasNext()) {
			System.out.println(iter1.next().getValue());
		}
		
	}
}

 测试结果：

data[0]
data[1]
data[2]
data[4]
data[3] //最近访问的数据在队尾。

data[1]
data[2]
data[4]
data[3]
data[ 9 ] //最新访问的数据插入队尾(若队满，最老的数据被移除)。

 

本文使用的LRU缓存类：

(参考：这个类是我的一个开源数据库项目中，缓存部分的实现类。

你可以通过访问http://code.google.com/p/ojadb 查看整个项目)

/*******************************************************************************************
 * oJadb is free software: you can redistribute it and/or modify it under 
 * the terms of the GNU General Public License as published by the Free Software Foundation, 
 * either version 3 of the License, or (at your option) any later version.
 * 
 * oJadb is distributed in the hope that it will be useful,but WITHOUT ANY WARRANTY; 
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with this library. 
 * If not, see <http://www.gnu.org/licenses/>.
 * 
 * Author:EricHan
 * Time:2008-8-28
 ******************************************************************************************/
package lru;

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

public class OjadbMap<K, V> extends LinkedHashMap<K, V>{
	private static final long serialVersionUID = -6970580442519842034L;
	private final int maxCapacity;
	private static final float DEFAULT_LOAD_FACTOR = 0.75f;
	//private final Lock lock = new ReentrantLock();
	private final ReadWriteLock rwlock = new ReentrantReadWriteLock();
	private final Lock readLock = rwlock.readLock();
	private final Lock writeLock = rwlock.writeLock();

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

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

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

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

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

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

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

	public Collection<Map.Entry<K, V>> getAll() {
		try {
			readLock.lock();
			return new ArrayList<Map.Entry<K, V>>(super.entrySet());
		} finally {
			readLock.unlock();
		}
	}
}
 
分享到：
| ubuntu 启动菜单
评论
31 楼 yiyidog125 2010-10-20  
想问下为什么要用linkedHashMap　用这个的话每次都是O(n)的操作吧
对一个经常要更新的LRU好吗？
30 楼 sdh5724 2010-09-03  
在线程安全上， 总是有人以为极低概率是的事件是不会发生的。 事实证明， 只要有一个口子做不好， 总是会有机会发生。
29 楼 mht19840918 2010-08-31  
有时间看以看看jcs下的LRUMap。这个是速度最快的。
28 楼 火星来客 2009-12-10  
火星来客 写道


OK，感谢二位！如果可能，请给出重入读锁的失败例子。

多线程操作链表，带来的结果是链表中的顺序。。。。。。乱啊，可能和我们预期的效果完全不同，同步比较保险
27 楼 jiabiao011 2009-12-10  
请好好看看LinkHashMap的说明
26 楼 mikeandmore 2009-12-10  
dennis_zane 写道
貌似我没有说多核单核在抢占上有什么区别，我说的是这个测试在多核上容易出现。

嗯。这个不太好说。

但是都会产生这个问题啊，没区别的。
25 楼 dennis_zane 2009-12-10  
貌似我没有说多核单核在抢占上有什么区别，我说的是这个测试在多核上容易出现。
24 楼 mikeandmore 2009-12-10  
还有，多核的OOE处理器会发生倒序构成的争抢。不过这个明显不足以考虑，因为这个实在太tricky了。

所以，在这个程序中多核，单核都会发生我和某前辈指出过的那个争抢问题，而且相当显而易见。
23 楼 mikeandmore 2009-12-10  
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<div class="quote_title">mikeandmore 写道</div>
<div class="quote_div">
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<div class="quote_title">marshan 写道</div>
<div class="quote_div">
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<p>    尽管讲LRU的maxCapacity设置为1000，然而最后的结果却是maxCapacity的十倍，最大限制形同虚设，如果你将循环次数count设置为Integer.MAX_VALUE，那么很容易跑出个内存溢出。既然这样的代码是放在google code上，我想基于对用户负责的态度，也不应该让这样明显的并发隐患存在于你的系统中吧。可能口气重了点，我想表达的意思是对于并发，不要用“可能、我认为不会”这样的字眼，事实上看起来很小的错误在高并发下都将被放大并显现。</p>
</div>
<p>测试结果：</p>
<p>Current map size:1000<br>我没太懂你要测什么，起初我们在讨论get时，readLock的问题。</p>
<p> </p>
<p>你的表达很中肯，我有的只有敬重和感谢！而且，我的项目或将考虑你们的建议，进行修改。</p>
</div>
<p> </p>
<p>我说的也是不能用读写锁，可能你的机器是单核的吧，那就增大并发看看。在多核机器上很容易出现的。</p>
</div>
<p>和单核多核没关系。并发数小，测试次数少。测试构造不够精巧。</p>
</div>
<p> </p>
<p>单核多核没关系吗？建议你自己找机器试下。</p>
</div>
<p>至少是java来说，其他的green thread的语言不好说。</p>
<p>java基本是native thread的。</p>
<p> </p>
<p>单核争抢发生在切换的时候，多核争抢发生在并发中不需要切换。</p>
<p>所以，都会同样发生争抢，这是显而易见的。</p>
22 楼 dennis_zane 2009-12-10  
<div class="quote_title">mikeandmore 写道</div>
<div class="quote_div">
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<div class="quote_title">marshan 写道</div>
<div class="quote_div">
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<p>    尽管讲LRU的maxCapacity设置为1000，然而最后的结果却是maxCapacity的十倍，最大限制形同虚设，如果你将循环次数count设置为Integer.MAX_VALUE，那么很容易跑出个内存溢出。既然这样的代码是放在google code上，我想基于对用户负责的态度，也不应该让这样明显的并发隐患存在于你的系统中吧。可能口气重了点，我想表达的意思是对于并发，不要用“可能、我认为不会”这样的字眼，事实上看起来很小的错误在高并发下都将被放大并显现。</p>
</div>
<p>测试结果：</p>
<p>Current map size:1000<br>我没太懂你要测什么，起初我们在讨论get时，readLock的问题。</p>
<p> </p>
<p>你的表达很中肯，我有的只有敬重和感谢！而且，我的项目或将考虑你们的建议，进行修改。</p>
</div>
<p> </p>
<p>我说的也是不能用读写锁，可能你的机器是单核的吧，那就增大并发看看。在多核机器上很容易出现的。</p>
</div>
<p>和单核多核没关系。并发数小，测试次数少。测试构造不够精巧。</p>
</div>
<p> </p>
<p>单核多核没关系吗？建议你自己找机器试下。</p>
21 楼 mikeandmore 2009-12-10  
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<div class="quote_title">marshan 写道</div>
<div class="quote_div">
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<p>    尽管讲LRU的maxCapacity设置为1000，然而最后的结果却是maxCapacity的十倍，最大限制形同虚设，如果你将循环次数count设置为Integer.MAX_VALUE，那么很容易跑出个内存溢出。既然这样的代码是放在google code上，我想基于对用户负责的态度，也不应该让这样明显的并发隐患存在于你的系统中吧。可能口气重了点，我想表达的意思是对于并发，不要用“可能、我认为不会”这样的字眼，事实上看起来很小的错误在高并发下都将被放大并显现。</p>
</div>
<p>测试结果：</p>
<p>Current map size:1000<br>我没太懂你要测什么，起初我们在讨论get时，readLock的问题。</p>
<p> </p>
<p>你的表达很中肯，我有的只有敬重和感谢！而且，我的项目或将考虑你们的建议，进行修改。</p>
</div>
<p> </p>
<p>我说的也是不能用读写锁，可能你的机器是单核的吧，那就增大并发看看。在多核机器上很容易出现的。</p>
</div>
<p>和单核多核没关系。并发数小，测试次数少。测试构造不够精巧。</p>
20 楼 dennis_zane 2009-12-10  
<div class="quote_title">marshan 写道</div>
<div class="quote_div">
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<p>    尽管讲LRU的maxCapacity设置为1000，然而最后的结果却是maxCapacity的十倍，最大限制形同虚设，如果你将循环次数count设置为Integer.MAX_VALUE，那么很容易跑出个内存溢出。既然这样的代码是放在google code上，我想基于对用户负责的态度，也不应该让这样明显的并发隐患存在于你的系统中吧。可能口气重了点，我想表达的意思是对于并发，不要用“可能、我认为不会”这样的字眼，事实上看起来很小的错误在高并发下都将被放大并显现。</p>
</div>
<p>测试结果：</p>
<p>Current map size:1000<br>我没太懂你要测什么，起初我们在讨论get时，readLock的问题。</p>
<p> </p>
<p>你的表达很中肯，我有的只有敬重和感谢！而且，我的项目或将考虑你们的建议，进行修改。</p>
</div>
<p> </p>
<p>我说的也是不能用读写锁，可能你的机器是单核的吧，那就增大并发看看。在多核机器上很容易出现的。</p>
19 楼 marshan 2009-12-10  
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<p>    尽管讲LRU的maxCapacity设置为1000，然而最后的结果却是maxCapacity的十倍，最大限制形同虚设，如果你将循环次数count设置为Integer.MAX_VALUE，那么很容易跑出个内存溢出。既然这样的代码是放在google code上，我想基于对用户负责的态度，也不应该让这样明显的并发隐患存在于你的系统中吧。可能口气重了点，我想表达的意思是对于并发，不要用“可能、我认为不会”这样的字眼，事实上看起来很小的错误在高并发下都将被放大并显现。</p>
</div>
<p>测试结果：</p>
<p>Current map size:1000<br>我没太懂你要测什么，起初我们在讨论get时，readLock的问题。</p>
<p> </p>
<p>你的表达很中肯，我有的只有敬重和感谢！而且，我的项目或将考虑你们的建议，进行修改。</p>
18 楼 mikeandmore 2009-12-10  
marshan 写道
你们俩的回复速度惊人。
单纯从缓存角度，synchronized是最好的，但是考虑并发读写上的不同逻辑，当一个线程put时，另一个线程是无法get的。
同一个线程重入get的间隔基本可以保证链表重排完成，而且两次进入该锁的可能性并不高。
技术上存在你们说的问题，但实际上并不太会发生。因此，我不打算做改变。

1 这个东西很难测到的
2 这个东西还是可以测到的。。。见上面的case
17 楼 dennis_zane 2009-12-09  
<div class="quote_title">marshan 写道</div>
<div class="quote_div">
<br>OK，感谢二位！如果可能，请给出重入读锁的失败例子。</div>
<p><br>我想构建并发测试程序是一项基本技能，比如我随手写的一个并发测试：</p>
<p>
</p>
<pre name="code" class="java">package lru;

import java.util.concurrent.CyclicBarrier;

public class LRUMapConcurrentTest {
static int limit = 1000;
static int count = 100000;
static int threadCount = 100;
private final OjadbMap&lt;Integer, Integer&gt; map = new OjadbMap&lt;Integer, Integer&gt;(
1000);

class TestThread implements Runnable {

private final CyclicBarrier barrier;
private final int beginIndex;

public TestThread(int beginIndex, CyclicBarrier barrier) {
super();
this.beginIndex = beginIndex;
this.barrier = barrier;
}

public void run() {
try {
barrier.await();
for (int i = beginIndex; i &lt; beginIndex + count; i++)
map.put(i, i);
for (int i = beginIndex; i &lt; beginIndex + count; i++)
map.get(i);
barrier.await();
} catch (Exception e) {
throw new RuntimeException(e);
}

}
}

public void concurrentTest() {
CyclicBarrier barrier = new CyclicBarrier(threadCount + 1);
for (int i = 0; i &lt; threadCount; i++) {
new Thread(new TestThread(i, barrier)).start();
}
try {
barrier.await();
barrier.await();
} catch (Exception e) {
throw new RuntimeException(e);
}
System.out.println("Current map size:" + map.size());
}

public static void main(String[] args) {
new LRUMapConcurrentTest().concurrentTest();
}
}
</pre>
 
<p>    尽管讲LRU的maxCapacity设置为1000，然而最后的结果却是maxCapacity的十倍，最大限制形同虚设，如果你将循环次数count设置为Integer.MAX_VALUE，那么很容易跑出个内存溢出。既然这样的代码是放在google code上，我想基于对用户负责的态度，也不应该让这样明显的并发隐患存在于你的系统中吧。可能口气重了点，我想表达的意思是对于并发，不要用“可能、我认为不会”这样的字眼，事实上看起来很小的错误在高并发下都将被放大并显现。</p>
<p> </p>
16 楼 dennis_zane 2009-12-09  
marshan 写道
你们俩的回复速度惊人。
单纯从缓存角度，synchronized是最好的，但是考虑并发读写上的不同逻辑，当一个线程put时，另一个线程是无法get的。
同一个线程重入get的间隔基本可以保证链表重排完成，而且两次进入该锁的可能性并不高。
技术上存在你们说的问题，但实际上并不太会发生。因此，我不打算做改变。


不会发生吗？事实上发生的几率相当大，特别是在高并发并且缓存数据急剧增加的情况下。我们的系统吃过苦头，因为这个问题OOM。这本身是不安全的代码，拿出来误导人是很不应该的。
15 楼 marshan 2009-12-09  
你们俩的回复速度惊人。
单纯从缓存角度，synchronized是最好的，但是考虑并发读写上的不同逻辑，当一个线程put时，另一个线程是无法get的。
同一个线程重入get的间隔基本可以保证链表重排完成，而且两次进入该锁的可能性并不高。
技术上存在你们说的问题，但实际上并不太会发生。因此，我不打算做改变。
14 楼 mikeandmore 2009-12-09  
火星来客 写道
mikeandmore 写道

理论上只会升高。不过cache这个东西本身就是越快越好的。

我认为是够用就好，

比如说我做一个cache app，每秒可以接受30w次socket请求，那我这个cache再快也没有用，在这种场景下，我们可以考虑如何降低cpu的消耗，而不是一味的追求快。

总之看场景吧，在速度和cpu的负载之间取一个平衡点


嗯，我不是做这个场景的。嘿嘿。。。
要是数据库的话，这块东西必然是越快越好。。。因为io操作远远比request的数量多。

anyway, tuning is tricky.
13 楼 火星来客 2009-12-09  
mikeandmore 写道

理论上只会升高。不过cache这个东西本身就是越快越好的。

我认为是够用就好，

比如说我做一个cache app，每秒可以接受30w次socket请求，那我这个cache再快也没有用，在这种场景下，我们可以考虑如何降低cpu的消耗，而不是一味的追求快。

总之看场景吧，在速度和cpu的负载之间取一个平衡点
12 楼 mikeandmore 2009-12-09  
火星来客 写道
mikeandmore 写道
火星来客 写道
mikeandmore 写道
原来也是搞链表鸟。。。嗯。。。还是自己写靠谱。。。-,-

于是
我觉得lz的实现有点问题。。。
readlock和readlock互溶

于是会同时发生get，这估计也是lz想要的。
但是看看hashedlinklist的代码
第323行，会开始对lru queue进行访问，要把当前的访问放在queue head。这会发生争抢。造成链表出现一些诡异的现象。

这个也是我用synchronized的原因，get操作会修改链表，用ReentrantLock没问题，但是要用同一把锁做get和put,读写锁用在这里不合适

嗯。对。
而且我觉得这个东西如果用spinlock会好一些。。这么短操作不要陷入内核...

250w/s的操作我想对于一个cache来说应该没有问题了，只是在我的测试中cpu上升到95%，应该是内核互斥命令造成的。不知道用spinlock会不会能降低cpu的消耗

理论上只会升高。不过cache这个东西本身就是越快越好的。
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    c语言实现LRU缓存.zip

    LRU（Least Recently Used）缓存淘汰算法是一种常见的内存管理策略，用于在固定容量的缓存中决定何时替换数据。当缓存满时，最近最少使用的数据将被...通过理解和掌握这些内容，你可以自行编写一个高效的LRU缓存实现。

    lru-cache:带最小堆的 LRU 缓存实现

    描述：这个项目有点像实验，涉及 3 种不同的 LRU 缓存实现。 一个使用最小堆（通常用于优先级队列）而不是 OrderedDict，第二个使用集合包中的内置 OrderedDict，最后一个使用我自己的 OrderedDict 的简单实现。 ...

    php-lrucache:PHP中的LRU缓存实现

    PHP LRU缓存实现介绍WTF 是 LRU 缓存吗？ LRU 代表最近最少使用。 它是一种缓存类型，通常具有固定容量并丢弃最旧的条目。 如果您需要控制缓存内存使用，这将特别有用。 如果您想了解有关 LRU Cache 的更多详细信息...

    LRU 缓存机制.docx

    在Python版本的LRU缓存实现中，类`LRUCache`包括以下关键部分： 1. 初始化方法`__init__`: 接收一个参数`capacity`，表示缓存的最大容量。创建一个字典`cache`用于存储键值对，一个列表`keys`用于存储键的顺序，...

    python-leetcode面试题解之第146题LRU缓存-题解.zip

    下面是一个基于`OrderedDict`的LRU缓存实现： ```python from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): self.cache = OrderedDict() self.capacity = capacity ...

    lrucacheleetcode-LRUCache:python+单元测试中的LRU缓存实现

    单元测试是验证LRU缓存实现正确性的关键步骤。通过编写各种场景的测试用例，如插入、删除、更新和获取数据等，确保在各种情况下缓存都能正确工作。这通常包括边界条件测试，如空缓存、满缓存、已存在的键和不存在的...

    java-leetcode题解之第146题LRU缓存.zip

    以下是简单的LRU缓存实现： ```java import java.util.HashMap; import java.util.LinkedList; import java.util.Map; public class LRUCache, V&gt; implements LRUCache, V&gt; { private int capacity; private Map...

    Go-一个简单高效用于go的LRU缓存包

    在Go语言中，有许多库可以帮助开发者实现LRU缓存，其中"Go-一个简单高效用于go的LRU缓存包"就是一个这样的工具。这个包为Go程序员提供了简单、高效的LRU缓存接口，便于在应用程序中管理和优化数据存储。 在Go语言中...

    Java实现LRU缓存机制：深入解析与高效编码实践

    在Java中实现LRU缓存机制，不仅可以帮助我们更好地理解和应用数据结构，还能在实际开发中提高程序的性能。本文将详细介绍如何在Java中实现LRU缓存机制，包括其原理、实现方式以及编码实践。 LRU缓存机制是一种非常...

    链表（上）：如何实现LRU缓存淘汰算法.pdf

    ### 链表在LRU缓存淘汰算法中的应用...通过上述方法，双向链表成为了实现LRU缓存淘汰算法的理想选择。它不仅提供了高效的插入和删除操作，还能确保数据项的访问顺序符合最近最少使用的策略，从而提高了缓存的整体性能。

    LRU算法 java实现

    以下是一个简单的LRU缓存实现的Java代码框架： ```java class LRUCache, V&gt; { private int capacity; private HashMap, Node&gt; map; private DoublyLinkedList&lt;Node&gt; list; public LRUCache(int capacity) { ...

    python-LRU缓存.zip

    “Python—LRU缓存.zip”是一个压缩文件，其中包含了使用Python实现的最近最少使用（Least Recently Used, LRU）缓存算法的代码和相关文档。LRU缓存算法是一种常用的缓存淘汰策略，它根据数据项最近被使用的时间来...

    LRU算法实现1

    例如，以下是一个简单的LRU缓存实现，使用`LinkedHashMap`的继承方式： ```java public class LRUCache2, V&gt; extends LinkedHashMap, V&gt; { private final int MAX_CACHE_SIZE; public LRUCache2(int cacheSize) ...

    hyperlru用60行代码快速LRU实现

    `hyperlru`是一个高效的LRU缓存实现，它的简洁代码和优秀性能使得它在JavaScript项目中成为一种理想的缓存解决方案。理解和使用`hyperlru`不仅可以提升开发效率，也有助于深入理解LRU缓存机制和数据结构设计。

    Java实现简单LRU缓存算法

    这里的LRUCache类维护了一个双向链表和一个哈希表，用于实现LRU算法。具体实现细节如下： - get方法：首先在哈希表中查找对应的键值对，如果不存在，则返回-1；如果存在，则将对应的节点从双向链表中删除，并将其...

    Asynctask异步加载带图的listview，加入lru缓存机制

    本文将深入探讨如何使用ASyncTask进行异步加载，以及结合LRU缓存策略来优化性能。 首先，我们要理解异步处理的一般方法。在Android中，主线程负责UI更新和用户交互，而耗时操作（如网络请求或数据库操作）应在后台...

    该存储库模拟GEO分布式最近最少使用（LRU）缓存.zip

    1. **LRU缓存实现**：项目会展示如何用编程语言（可能是Java、Python或C++）实现LRU缓存数据结构，包括插入、删除、更新和查找操作。 2. **分布式系统原理**：会涉及一致性哈希、分区策略、复制等分布式系统中的...

    LRU算法--utils工具包

    Guava的`LoadingCache`提供了一种方便的LRU缓存实现，它不仅可以自动管理缓存容量，还能在需要时自动加载新数据。测试代码可能会创建一个`LoadingCache`实例，设置最大容量，然后执行一些put和get操作，验证缓存的...

    LRU_缓存策略_LRU_缓存.zip

    在这个压缩包文件“LRU_缓存策略_LRU_缓存_源码.zip”中，我们预计会找到实现LRU缓存策略的源代码，这对于理解其工作原理和应用非常有帮助。 LRU缓存策略的核心思想是：当缓存满时，优先淘汰最近最少使用的数据。这...

Magicbox
Global site tag (gtag.js) - Google Analytics