java实现LRU缓存淘汰算法的方法

java实现LRU缓存淘汰算法的方法

LRU算法：最近最少使用淘汰算法（Least Recently Used）。LRU是淘汰最长时间没有被使用的缓存（即使该缓存被访问的次数最多）。

如何实现LRU缓存淘汰算法

场景：

我们现在有这么个真实场景，我在爬取某个网站时，控制该网站的代理IP并发数，太多会搞垮对方网站的对吧，要蹲号子的呢。这里我需要维护一个代理IP代理池，而且这些IP肯定不是一直都很稳定的，但是又不能取一个就丢一个，这样太浪费资源。所以我会将这些IP缓存起来，进行按需提取，采用LRU最近最少使用的策略去管理代理IP。

代码如下：

import java.util.*;

http://public class LRUCache {

int cap;//最大缓存的数量

Map values;//缓存

Set position;//缓存的key,按照存入的顺序存储

public LRUCache(int cap) {

this.cap = cap;

values = new HashMap<>(cap);

position = new LinkedHashSet<>(cap);

}

/**

* 从缓存中获取值，缓存中没有则返回null

*/

public String get(String key) {

String value = null;

if (values.chttp://ontainsKey(key)) {

value = values.get(key);

position.remove(key);

position.add(key);

}

return value;

}

/**

* 将值放入缓存中

*/

public void put(String key, String value) {

if (position.size() == cap) {

//若达到缓存上限则将距今最久的缓存删除

String firstKey = position.iterator().next();

position.remove(firstKey);

values.remove(firstKey);

}

position.add(key);

values.put(key, value);

}

public Map getValues() {

return values;

}

public Set getPosition() {

return position;

}

}

测试：

LRUCache lruCache = new LRUCache(4);

lruCache.put("a","a");

lruCache.put("b","b");

lruCache.put("c","c");

lruCache.put("d","d");

System.out.println("position:"+lruCache.getPosition());

System.out.println("values:"+lruhttp://Cache.getValues());

//a将被淘汰

lruCache.put("e","e");

System.out.println("position:"+lruCache.getPosition());

System.out.println("values:"+lruCache.getValues());

输出：

position:[a, b, c, d]

values:{a=a, b=b, c=c, d=d}

position:[b, c, d, e]

values:{b=b, c=c, d=d, e=e}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。