江苏龙网

  1. 主页 > 生活百科 > >

Redis：缓存被我写满了，该怎么办？( 二 )

Redis

这里我们的实现为最近访问的放在链表的尾节点，不经常访问的放在链表的头节点
测试一波，输出为链表的正序输出（代码为了简洁没有贴toString方法）
MyLruCache<String, String> myLruCache = new MyLruCache<>(3);// {5 : 5}myLruCache.put("5", "5");// {5 : 5}{3 : 3}myLruCache.put("3", "3");// {5 : 5}{3 : 3}{4 : 4}myLruCache.put("4", "4");// {3 : 3}{4 : 4}{2 : 2}myLruCache.put("2", "2");// {4 : 4}{2 : 2}{3 : 3}myLruCache.get("3");「因为LinkedHashMap的底层实现就是哈希表加双向链表，所以你可以用LinkedHashMap替换HashMap和DoubleList来改写一下上面的类」 。
我来演示一下更骚的操作，只需要重写一个构造函数和removeEldestEntry方法即可 。
使用LinkedHashMap实现LRUpublic class LruCache<K, V> extends LinkedHashMap<K, V> {    private int cacheSize;    public LruCache(int cacheSize) {        /**         * initialCapacity: 初始容量大小         * loadFactor: 负载因子         * accessOrder: false基于插入排序（默认），true基于访问排序         */        super(cacheSize, 0.75f, true);        this.cacheSize = cacheSize;    }    /**     * 当调用put或者putAll方法时会调用如下方法，是否删除最老的数据，默认为false     */    @Override    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {        return size() > cacheSize;    }}注意这个缓存并不是线程安全的，可以调用Collections.synchronizedMap方法返回线程安全的map
LruCache<String, String> lruCache = new LruCache(3);Map<String, String> safeMap = Collections.synchronizedMap(lruCache);Collections.synchronizedMap实现线程安全的方式很简单，只是返回一个代理类 。代理类对Map接口的所有方法加锁
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {    return new SynchronizedMap<>(m);}LFU算法「LRU算法有一个问题，当一个长时间不被访问的key，偶尔被访问一下后，可能会造成一个比这个key访问更频繁的key被淘汰 。」
即LRU算法对key的冷热程度的判断可能不准确 。而LFU算法（Least Frequently Used，最不经常使用）则是按照访问频率来判断key的冷热程度的，每次删除的是一段时间内访问频率较低的数据，比LRU算法更准确 。
使用3个hash表实现lfu算法那么我们应该如何组织数据呢？
为了实现键值的对快速访问，用一个map来保存键值对
private HashMap<K, Integer> keyToFreq;还需要用一个map来保存键的访问频率
private HashMap<K, Integer> keyToFreq;「当然你也可以把值和访问频率封装到一个类中，用一个map来替代上述的2个map」
接下来就是最核心的部分，删除访问频率最低的数据 。

  1. 为了能在O(1)时间复杂度内找到访问频率最低的数据，我们需要一个变量minFreq记录访问最低的频率
  2. 每个访问频率有可能对应多个键 。当空间不够用时，我们要删除最早被访问的数据，所以需要如下数据结构，Map<频率, 有序集合> 。每次内存不够用时，删除有序集合的第一个元素即可 。并且这个有序集合要能快速删除某个key，因为某个key被访问后，需要从这个集合中删除，加入freq+1对应的集合中
  3. 有序集合很多，但是能满足快速删除某个key的只有set，但是set插入数据是无序的 。「幸亏JAVA有LinkedHashSet这个类，链表和集合的结合体，链表不能快速删除元素，但是能保证插入顺序 。集合内部元素无序，但是能快速删除元素，完美」
下面就是具体的实现 。
public class LfuCache<K, V> {    private HashMap<K, V> keyToVal;    private HashMap<K, Integer> keyToFreq;    private HashMap<Integer, LinkedHashSet<K>> freqTokeys;    private int minFreq;    private int capacity;    public LfuCache(int capacity) {        keyToVal = new HashMap<>();        keyToFreq = new HashMap<>();        freqTokeys = new HashMap<>();        this.capacity = capacity;        this.minFreq = 0;    }    public V get(K key) {        V v = keyToVal.get(key);        if (v == null) {            return null;        }        increaseFrey(key);        return v;    }    public void put(K key, V value) {        // get方法里面会增加频次        if (get(key) != null) {            // 重新设置值            keyToVal.put(key, value);            return;        }        // 超出容量，删除频率最低的key        if (keyToVal.size() >= capacity) {            removeMinFreqKey();        }        keyToVal.put(key, value);        keyToFreq.put(key, 1);        // key对应的value存在，返回存在的key        // key对应的value不存在，添加key和value        freqTokeys.putIfAbsent(1, new LinkedHashSet<>());        freqTokeys.get(1).add(key);        this.minFreq = 1;    }    // 删除出现频率最低的key    private void removeMinFreqKey() {        LinkedHashSet<K> keyList = freqTokeys.get(minFreq);        K deleteKey = keyList.iterator().next();        keyList.remove(deleteKey);        if (keyList.isEmpty()) {            // 这里删除元素后不需要重新设置minFreq            // 因为put方法执行完会将minFreq设置为1            freqTokeys.remove(keyList);        }        keyToVal.remove(deleteKey);        keyToFreq.remove(deleteKey);    }    // 增加频率    private void increaseFrey(K key) {        int freq = keyToFreq.get(key);        keyToFreq.put(key, freq + 1);        freqTokeys.get(freq).remove(key);        freqTokeys.putIfAbsent(freq + 1, new LinkedHashSet<>());        freqTokeys.get(freq + 1).add(key);        if (freqTokeys.get(freq).isEmpty()) {            freqTokeys.remove(freq);            // 最小频率的set为空，key被移动到minFreq+1对应的set了            // 所以minFreq也要加1            if (freq == this.minFreq) {                this.minFreq++;            }        }    }}


推荐阅读


上一篇：ps两寸证件照制作教程最新的?ps制作2寸证件照片的步骤

下一篇：优秀程序员必备以下五点能力，你都掌握了吗？