LRU cache缓存简单实现

LRU cache

LRU（最近最少使用）是一种常用的缓存淘汰机制。当缓存大小容量到达最大分配容量的时候，就会将缓存中最近访问最少的对象删除掉，以腾出空间给新来的数据。

实现

（1）单线程简单版本

( 来源：力扣（LeetCode）链接：leetcode题目)

　　题目：设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。它应该支持以下操作：获取数据 get 和写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

　　思路：LinkedList + HashMap: LinkedList用来保存key的访问情况，最近访问的key将会放置到链表的最尾端，如果链表大小超过容量，移除链表的第一个节点，同时移除该key在hashmap中对应的键值对。程序如下：

class LRUCache {

    private  HashMap<Integer, Integer> hashMap = null;

    private  LinkedList<Integer> list = null;

    private int capacity;

    public LRUCache(int capacity) {

        hashMap = new HashMap<>(capacity);

        list = new LinkedList<Integer>();

        this.capacity = capacity;

    }

    public int get(int key) {

        if(hashMap.containsKey(key)){

            list.remove((Object)key);

            list.addLast(key);

            return hashMap.get(key);

        }

        return  -1;

    }

    public void put(int key, int value) {

        if(list.contains((Integer)key)){

            list.remove((Integer)key);

            list.addLast((Integer)key);

            hashMap.put(key, value);

            return;

        }

        if(list.size() == capacity){

            Integer v = list.get(0);

            list.remove(0);

            hashMap.remove((Object)v);

        }

        list.addLast(key);

        hashMap.put(key, value);

    }

}

（2）多线程并发版LRU Cache

　与单线程思路类似，将HashMap和LinkedList换成支持线程安全的容器ConcurrentHashMap和ConcurrentLinkedQueue结构。ConcurrentLinkedQueue是一个基于链表，支持先进先出的的队列结构，处理方法同单线程类似，只不过为了保证多线程下的安全问题，我们会使用支持读写分离锁的ReadWiterLock来保证线程安全。它可以实现：

　　1.同一时刻，多个线程同时读取共享资源。

　　2.同一时刻，只允许单个线程进行写操作。

/*

 * 泛型中通配符

 * ？ 表示不确定的 java 类型

 * T (type) 表示具体的一个java类型

 * K V (key value) 分别代表java键值中的Key Value

 * E (element) 代表Element

 */

public class MyLRUCache<K, V> {

    private final int capacity;

    private ConcurrentHashMap<K, V> cacheMap;

    private ConcurrentLinkedQueue<K> keys;

    ReadWriteLock RWLock = new ReentrantReadWriteLock();

    /*

     * 读写锁

     */

    private Lock readLock = RWLock.readLock();

    private Lock writeLock = RWLock.writeLock();

    private ScheduledExecutorService scheduledExecutorService;

    public MyLRUCache(int capacity) {

        this.capacity = capacity;

        cacheMap = new ConcurrentHashMap<>(capacity);

        keys = new ConcurrentLinkedQueue<>();

        scheduledExecutorService = Executors.newScheduledThreadPool(10);

    }

    public boolean put(K key, V value, long expireTime){

        writeLock.lock();

        try {

            //需要注意containsKey和contains方法方法的区别

            if(cacheMap.containsKey(key)){

                keys.remove(key);

                keys.add(key);

                cacheMap.put(key, value);

                return true;

            }

            if(cacheMap.size() == capacity){

                K tmp = keys.poll();

                if( key != null){

                    cacheMap.remove(tmp);

                }

            }

            cacheMap.put(key, value);

            keys.add(key);

            if(expireTime > 0){

                removeAfterExpireTime(key, expireTime);

            }

            return true;

        }finally {

            writeLock.unlock();

        }

    }

    public V get(K key){

        readLock.lock();

        try {

            if(cacheMap.containsKey(key)){

                keys.remove(key);

                keys.add(key);

                return cacheMap.get(key);

            }

            return null;

        }finally {

            readLock.unlock();

        }

    }

    public boolean remove(K key){

        writeLock.lock();

        try {

            if(cacheMap.containsKey(key)){

                cacheMap.remove(key);

                keys.remove(key);

                return true;

            }

            return false;

        }finally {

            writeLock.unlock();

        }

    }

    private void removeAfterExpireTime(K key, long expireTime){

        scheduledExecutorService.schedule(new Runnable() {

            @Override

            public void run() {

                cacheMap.remove(key);

                keys.remove(key);

            }

        }, expireTime, TimeUnit.MILLISECONDS);

    }

    public int size(){

        return cacheMap.size();

    }

}

　　在代码中添加了设置键值对失效的put方法，通过使用一个定时器线程池保证过期键值对的及时清理。测试代码如下：

public class LRUTest {

    public static void main(String[] args) throws InterruptedException {

        /*

        MyLRUCache<String, Integer> myLruCache = new MyLRUCache(100000);

        ExecutorService es = Executors.newFixedThreadPool(10);

        AtomicInteger atomicInteger = new AtomicInteger(1);

        CountDownLatch latch = new CountDownLatch(10);

        long starttime = System.currentTimeMillis();

        for (int i = 0; i < 10; i++) {

            es.submit(new Runnable() {

                @Override

                public void run() {

                    for (int j = 0; j < 100000; j++) {

                        int v = atomicInteger.getAndIncrement();

                        myLruCache.put(Thread.currentThread().getName() + "_" + v, v, 200000);

                    }

                    latch.countDown();

                }

            });

        }

        latch.await();

        long endtime = System.currentTimeMillis();

        es.shutdown();

        System.out.println("Cache size:" + myLruCache.size()); //Cache size:1000000

        System.out.println("Time cost: " + (endtime - starttime));

      */

        MyLRUCache<Integer, String> myLruCache = new MyLRUCache<>( 10);

        myLruCache.put(1, "Java", 1000);

        myLruCache.put(2, "C++", 2000);

        myLruCache.put(3, "Java", 3000);

        System.out.println(myLruCache.size());//3

        Thread.sleep(2200);

        System.out.println(myLruCache.size());//1

    }

}

巴特西

LRU cache缓存简单实现

LRU cache

实现

（1）单线程简单版本

（2）多线程并发版LRU Cache

最新文章

热门文章