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

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。下面看下java实现LRU缓存淘汰算法的方法，一起看看吧

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

如何实现LRU缓存淘汰算法
场景：

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

代码如下：

				?

									import java.util.*;

									public class LRUCache {

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

									    Map<String, String> values;//缓存

									    Set<String> 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.containsKey(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<String, String> getValues() {

									        return values;

									    }

									    public Set<String> 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:"+lruCache.getValues());

									//a将被淘汰

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

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

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