GuavaCache学习笔记一：自定义LRU算法的缓存实现

一枝花算不算浪漫

发布于 2018-12-24 10:25:06

8350

发布于 2018-12-24 10:25:06

文章被收录于专栏：一枝花算不算浪漫的专栏

前言

今天在看GuavaCache缓存相关的源码，这里想到先自己手动实现一个LRU算法。于是乎便想到LinkedHashMap和LinkedList+HashMap, 这里仅仅是作为简单的复习一下。

LRU

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

代码实现原理

LinkedList + HashMap： LinkedList其实是一个双向链表，我们可以通过get和put来设置最近请求key的位置，然后hashMap去存储数据 LinkedHashMap：LinkedHashMap是继承自HashMap，只不过Map中的Node节点改为了双向节点，双向节点可以维护添加的顺序，在LinkedHashMap的构造函数中有一个accessOrder，当设置为true后，put和get会自动维护最近请求的位置到last。

LinkedList+HashMap代码实现

LRUCache接口：

/**
 * @Description:
 * @Author: wangmeng
 * @Date: 2018/12/8-10:49
 */
public class LinkedListLRUTest {
    public static void main(String[] args) {
        LRUCache<String, String> cache = new LinkedListLRUCache<>(3);
        cache.put("1", "1");
        cache.put("2", "2");
        cache.put("3", "3");
        System.out.println(cache);

        cache.put("4", "4");
        System.out.println(cache);

        System.out.println(cache.get("2"));
        System.out.println(cache);
    }
}

LinkedList实现：

/**
 * @Description:使用LinkedList+HashMap来实现LRU算法
 * @Author: wangmeng
 * @Date: 2018/12/8-10:41
 */
public class LinkedListLRUCache<K, V> implements LRUCache<K, V> {

    private final int limit;
    private final LinkedList<K> keys = new LinkedList<>();
    private final Map<K, V> cache = Maps.newHashMap();

    public LinkedListLRUCache(int limit) {
        this.limit = limit;
    }

    @Override
    public void put(K key, V value) {
        Preconditions.checkNotNull(key);
        Preconditions.checkNotNull(value);
        if (keys.size() >= limit) {
            K oldesKey = keys.removeFirst();
            cache.remove(oldesKey);
        }

        keys.addLast(key);
        cache.put(key, value);
    }

    @Override
    public V get(K key) {
        boolean exist = keys.remove(key);
        if (!exist) {
            return null;
        }

        keys.addLast(key);
        return cache.get(key);
    }

    @Override
    public void remove(K key) {

        boolean exist = keys.remove(key);
        if (exist) {
            keys.remove(key);
            cache.remove(key);
        }
    }

    @Override
    public int size() {
        return keys.size();
    }

    @Override
    public void clear() {
        keys.clear();
        cache.clear();
    }

    @Override
    public int limit() {
        return this.limit;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (K key : keys) {
            builder.append(key).append("=").append(cache.get(key)).append(";");
        }
        return builder.toString();
    }
}

LinkedList测试类：

/**
 * @Description:
 * @Author: wangmeng
 * @Date: 2018/12/8-10:49
 */
public class LinkedListLRUTest {
    public static void main(String[] args) {
        LRUCache<String, String> cache = new LinkedListLRUCache<>(3);
        cache.put("1", "1");
        cache.put("2", "2");
        cache.put("3", "3");
        System.out.println(cache);

        cache.put("4", "4");
        System.out.println(cache);

        System.out.println(cache.get("2"));
        System.out.println(cache);
    }
}

LinkedList测试类返回值：

1=1;2=2;3=3;
2=2;3=3;4=4;
2
3=3;4=4;2=2;

LinkedHashMap实现

/**
 * @Description: 不是一个线程安全的类，这里是使用LinkedHashMap来做LRU算法
 * @Author: wangmeng
 * @Date: 2018/12/8-10:14
 */
public class LinkedHashLRUCache<K, V> implements LRUCache<K, V> {

    private static class InternalLRUCache<K, V> extends LinkedHashMap<K, V> {

        final private int limit;
        private InternalLRUCache(int limit) {
            super(16, 0.75f, true);
            this.limit = limit ;
        }

        //实现remove元素的方法，这个是重写了LinkedHashMap中的方法。因为在HashMap的putVal会调用afterNodeInsertion(), 而这个方法会判断removeEldestEntry方法。
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > limit;
        }
    }


    private final int limit;
    //使用组合关系优于继承，这里只对外暴漏LRUCache中的方法
    private final InternalLRUCache<K, V> internalLRUCache;
    public LinkedHashLRUCache(int limit) {
        Preconditions.checkArgument(limit > 0, "The limit big than zero.");
        this.limit = limit;
        this.internalLRUCache = new InternalLRUCache(limit);

    }

    @Override
    public void put(K key, V value) {
        this.internalLRUCache.put(key, value);
    }

    @Override
    public V get(K key) {
        return this.internalLRUCache.get(key);
    }

    @Override
    public void remove(K key) {
        this.internalLRUCache.remove(key);
    }

    @Override
    public int size() {
        return this.internalLRUCache.size();
    }

    @Override
    public void clear() {
        this.internalLRUCache.clear();
    }

    @Override
    public int limit() {
        return this.limit;
    }

    @Override
    public String toString() {
        return internalLRUCache.toString();
    }
}

LinkedHashMap测试类：

/**
 * @Description:
 * @Author: wangmeng
 * @Date: 2018/12/8-10:30
 */
public class LinkedHashLRUTest {
    public static void main(String[] args) {
        LRUCache<String, String> cache = new LinkedHashLRUCache<>(3);
        cache.put("1", "1");
        cache.put("2", "2");
        cache.put("3", "3");
        System.out.println(cache);

        cache.put("4", "4");
        System.out.println(cache);

        System.out.println(cache.get("2"));
        System.out.println(cache);
    }
}

LinkedHashMap测试结果：

{1=1, 2=2, 3=3}
{2=2, 3=3, 4=4}
2
{3=3, 4=4, 2=2}

来自为知笔记(Wiz)

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-12-08 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度