lruCache

package demo.base.cache;

/**
 * LRU 缓存。你需要继承这个抽象类来实现 LRU 缓存。
 *
 * @param <K> 数据 key
 * @param <V> 数据 value
 */
public abstract class LruCache<K, V> implements Storage<K, V> {
    // 缓存容量
    protected final int capacity;

    // 低速存储，所有的数据都可以从这里读到
    protected final Storage<K, V> lowSpeedStorage;

    public LruCache(int capacity, Storage<K, V> lowSpeedStorage) {
        this.capacity = capacity;
        this.lowSpeedStorage = lowSpeedStorage;
    }
}

myLruCache

package demo.base.cache;

import java.util.*;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * 待优化：双向链表 + 哈希表实现O(1)复杂度操作
 * => LRU-K,LRU-2Q解决LRU-1的缓存污染问题（大量一次性最近访问数据）
 *
 * @author gx
 * @create 2019-08-29 17:22
 */
public class MyLruCache<K, V> extends LruCache<K, V> {
    /*
    链表存储数据key, 最近使用的key排在尾部, 存储不够时优先从头部清除
     */
    private List<K> keys = new LinkedList<>();
    private Map<K, V> cache = new HashMap<>(capacity);
    private Lock keyLock = new ReentrantLock(false);

    public MyLruCache(int capacity, Storage<K, V> lowSpeedStorage) {
        super(capacity, lowSpeedStorage);
    }

    public List<K> getKeys() {
        return keys;
    }

    @Override
    public V get(K key) {
        return getValue(key);
    }

    private V getValue(K key) {
        V v = cache.get(key);

        if (v == null) {
            //从低速缓存(磁盘...)获取数据
            v = lowSpeedStorage.get(key);

            if (v == null) return null;

            keyLock.lock();
            try {
                //需要保证容量判断与删除、添加操作的连续性
                if (keys.size() >= capacity) remove();

                add(key, v);
            } finally {
                keyLock.unlock();
            }

            return v;
        }

        keyLock.lock();
        try {
            //并行执行环境keys.get(keys.size() - 1)有越界或索引偏移风险(remove，add)
            if (key != keys.get(keys.size() - 1)) move(key);
        } finally {
            keyLock.unlock();
        }

        return v;
    }

    // 瓶颈: LinkedList remove object 是O(n)复杂度
    // 改进: 可以通过记录达到一定访问次数再移动，来降低性能损耗
    private void move(K key) {
        keys.remove(key);
        keys.add(key);
    }

    private void add(K key, V value) {
        cache.put(key, value);
        keys.add(key);
    }

    private void remove() {
        K remove = keys.remove(0);
        cache.remove(remove);
    }

    public static void main(String[] args) {
        StorageImpl<String, String> storage = new StorageImpl<>(8);
        storage.put("a", "1");
        storage.put("b", "2");
        storage.put("c", "3");
        storage.put("d", "4");
        storage.put("e", "5");
        storage.put("f", "6");

        MyLruCache<String, String> cache = new MyLruCache<>(4, storage);
        cache.get("a");
        cache.get("b");
        cache.get("c");
        cache.get("d");
        cache.get("c");

        for (String key : cache.getKeys()) {
            System.out.println(key);
        }
    }
}

MyLruCacheV2

package demo.base.cache;

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * 基于支持访问顺序的LinkedHashMap实现
 *
 * @author gx
 * @create 2019-09-16 11:19
 */
public class MyLruCacheV2<K, V> extends LruCache<K, V> {
    private LinkedHashMap<K, V> cache;
    private Lock keyLock = new ReentrantLock(false);

    public MyLruCacheV2(int capacity, Storage<K, V> lowSpeedStorage) {
        super(capacity, lowSpeedStorage);
        cache = new InnerLinkedHashMap<>(capacity, 0.75f, true);
    }

    public Set<K> getKeys(){
        return cache.keySet();
    }

    @Override
    public V get(K key) {
        return getVal(key);
    }

    private V getVal(K key) {
        V val;
        keyLock.lock();
        try {
            val = cache.get(key);
        } finally {
            keyLock.unlock();
        }

        if (val == null) {
            V v = lowSpeedStorage.get(key);
            if (v == null) {
                return null;
            }

            keyLock.lock();
            try {
                cache.put(key, v);
            } finally {
                keyLock.unlock();
            }
            return v;
        }
        return val;
    }

    final class InnerLinkedHashMap<A, B> extends LinkedHashMap<A, B> {

        InnerLinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
            super(initialCapacity, loadFactor, accessOrder);
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<A, B> eldest) {
            return this.size() > capacity;
        }
    }

    public static void main(String[] args) {
        StorageImpl<String, String> storage = new StorageImpl<>(8);
        storage.put("a", "1");
        storage.put("b", "2");
        storage.put("c", "3");
        storage.put("d", "4");
        storage.put("e", "5");
        storage.put("f", "6");

        MyLruCacheV2<String, String> cache = new MyLruCacheV2<>(4, storage);
        cache.get("a");
        cache.get("d");
        cache.get("c");
        cache.get("d");

        for (String key : cache.getKeys()) {
            System.out.println(key);
        }
    }
}

storage

package demo.base.cache;

/**
 * KV 存储抽象
 */
public interface Storage<K,V> {
    /**
     * 根据提供的 key 来访问数据
     * @param key 数据 key
     * @return 数据 value
     */
    V get(K key);
}

StorageImpl

package demo.base.cache;

import java.util.HashMap;

/**
 * @author gx
 * @create 2019-09-16 10:09
 */
public class StorageImpl<K, V> implements Storage<K, V> {
    private HashMap<K, V> cache;

    public StorageImpl(int capacity) {
        // 初始容量
        cache = new HashMap<>(capacity);
    }

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

    public void put(K key, V value) {
        cache.put(key, value);
    }
}