手写基于LRU的缓存

前几天看Redis的时候看见了一个LRU缓存,感觉挺有意思的,今天闲着无事就想着手写一个来练练手。不过在开始动手之前,还是做个简单的介绍,关于LRU的一些知识。LRU(least recently used)即最近最少使用,常用语缓存的过期策略。Redis是一个比较常用的缓存中间件,经常被用来存放一些高访问率的数据,但是有的时候数据量过大,就会导致内存溢出,这个时候就需要按照一定的规则或者策略删除掉旧的数据,而LRU过期策略就是其中一种。

设计

接下来我们就来设计一个简单的基于LRU的Key-Value缓存,说到设计首当其冲的就是数据结构。那么选用什么数据结构最合适呢?首先我们要知道我们是用来作为缓存的,那么缓存最多的操作就是读写,除此之外还要有增删操作,那么这个时候仅仅使用数据肯定就不行了,如果只使用链表呢也不行,这个时候就要使用链表和映射结合的方式。

public class day01 {
    public static void main(String[] args) {
        LRUCache<String> lruCache = new LRUCache<String>(3);
        lruCache.cache("A", "a");
        lruCache.cache("B", "b");
        lruCache.cache("C", "c");
        for (String s : lruCache) {
            System.out.print(s + "<-");
        }
        lruCache.get("A");
        System.out.println();
        for (String s : lruCache) {
            System.out.print(s + "<-");
        }
        lruCache.cache("D", "d");
        System.out.println();
        for (String s : lruCache) {
            System.out.print(s + "<-");
        }
    }
    static class LRUCache<T> implements Iterable<T>{
        private final LinkedHashMap<String, T> cache;
        private int MAX;
        public LRUCache(int size) {
            this.cache = new LinkedHashMap<>(size);
            this.MAX = size;
        }
        public void cache(String key, T value) {
            if (cache.size() >= MAX) {
                Map.Entry<String, T> first = cache.entrySet().iterator().next();
                cache.remove(first.getKey());
            } else {
                if (cache.containsKey(key)) {
                    cache.remove(key);
                }
            }
            cache.put(key,value);
        }

        public T get(String key) {
            if (cache.containsKey(key)) {
                T val = cache.get(key);
                cache.remove(key);
                cache.put(key, val);
                return val;
            }
            return null;
        }
        @Override
        public Iterator<T> iterator() {
            Iterator<Map.Entry<String, T>> iterator = cache.entrySet().iterator();
            return new Iterator() {
                @Override
                public boolean hasNext() {
                    return iterator.hasNext();
                }
                @Override
                public T next() {
                    return iterator.next().getValue();
                }
            };
        }
    }
}