LRU 算法

栏目: 编程工具 · 发布时间: 5年前

内容简介:LRU 是 Least Recently Used 的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间 t,当须淘汰一个页面时,选择现有页面中其 t 值最大的,即最近最久未使用的页面予以淘汰。-百科本文说的 LRU 主要是指该算法在业务层的缓存算法中的应用,基本的实现逻辑是一样的。算法思想:

LRU 是 Least Recently Used 的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间 t,当须淘汰一个页面时,选择现有页面中其 t 值最大的,即最近最久未使用的页面予以淘汰。-百科

本文说的 LRU 主要是指该算法在业务层的缓存算法中的应用,基本的实现逻辑是一样的。

How ?

算法思想:

  • 1,新数据插入到链表头部。
  • 2,每当缓存命中(即缓存数据被访问),则将数据移到链表头部。
  • 3,当链表满的时候,将链表尾部的数据丢弃。

算法实现

class Node{
    
    public Node(String key,String value){
        this.key = key;
        this.value = value;
    }
    
    public Node pre;
    public Node next;
    public String key;
    public String value;
}

public class LRUCache {
    private Node head;
    private Node end;
    //缓存上限
    private int limit;
    private HashMap map;
    
    public LRUCache(int limit) {
        this.limit = limit;
        map = new HashMap();
    }
    
    public String get(String key) {
        Node node = map.get(key);
        if(node == null) {
            return null;
        }
        //调整node到尾部
        refreshNode(node);
        return node.value;
    }
    
    public void put(String key, String value) {
        Node node = map.get(key);
        if(node == null) {
            //key不存在直接插入
            while(map.size() >= limit) {
                //去除链表内的节点
                String oldKey = removeNode(head);
                //去除map中的缓存
                map.remove(oldKey);
            }
            node = new Node(key, value);
            //链表中加入节点
            addNode(node);
            //map中加入节点
            map.put(key, node);
        } else {
            //更新节点并调整到尾部
            node.value = value;
            refreshNode(node);
        }
    }
    
    private void refreshNode(Node node) {
        //如果访问的是尾节点,无须移动节点
        if(node == end) {
            return;
        }
        //把节点移动到尾部,相当于做一次删除插入操作
        removeNode(node);
        addNode(node);
    }
    
    private String removeNode(Node node) {
        //尾节点
        if(node == end) {
            end = end.pre;
        } else if(node == head) {
        //头结点
            head = head.next;
        } else {
            //中间节点
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        return node.key;
    }
    
    private void addNode(Node node) {
        if(end != null) {
            end.next = node;
            node.pre = end;
            node.next = null;
        }
        end = node;
        if(head == null) {
            head = node;
        }
    }
}

JDK 中的算法实现

通常不需要我们自己专门实现一个此算法的数据结构,使用 JDK 内置的 LinkedHashMap 稍加改造即可。

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int MAX_CACHE_SIZE;
 
    public LRUCache2(int cacheSize) {
        super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
        MAX_CACHE_SIZE = cacheSize;
    }
 
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_CACHE_SIZE;
    }
}

mybatis 中的 LRU 算法实现

/**
 * 最近最少使用缓存
 * 基于 LinkedHashMap 覆盖其 removeEldestEntry 方法实现。
 */
public class LruCache implements Cache {

    private final Cache delegate;
    //额外用了一个map才做lru,但是委托的Cache里面其实也是一个map,这样等于用2倍的内存实现lru功能
    private Map<Object, Object> keyMap;
    private Object eldestKey;

    public LruCache(Cache delegate) {
        this.delegate = delegate;
        setSize(1024);
    }

    @Override
    public String getId() {
        return delegate.getId();
    }

    @Override
    public int getSize() {
        return delegate.getSize();
    }

    public void setSize(final int size) {
        keyMap = new LinkedHashMap<Object, Object>(size, .75F, true) {
            private static final long serialVersionUID = 4267176411845948333L;

            //核心就是覆盖 LinkedHashMap.removeEldestEntry方法,
            //返回true或false告诉 LinkedHashMap要不要删除此最老键值
            //LinkedHashMap内部其实就是每次访问或者插入一个元素都会把元素放到链表末尾,
            //这样不经常访问的键值肯定就在链表开头啦
            @Override
            protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
                boolean tooBig = size() > size;
                if (tooBig) {
                    //这里没辙了,把eldestKey存入实例变量
                    eldestKey = eldest.getKey();
                }
                return tooBig;
            }
        };
    }

    @Override
    public void putObject(Object key, Object value) {
        delegate.putObject(key, value);
        //增加新纪录后,判断是否要将最老元素移除
        cycleKeyList(key);
    }

    @Override
    public Object getObject(Object key) {
        //get的时候调用一下LinkedHashMap.get,让经常访问的值移动到链表末尾
        keyMap.get(key); //touch
        return delegate.getObject(key);
    }

    @Override
    public Object removeObject(Object key) {
        return delegate.removeObject(key);
    }

    @Override
    public void clear() {
        delegate.clear();
        keyMap.clear();
    }

    @Override
    public ReadWriteLock getReadWriteLock() {
        return null;
    }

    private void cycleKeyList(Object key) {
        keyMap.put(key, key);
        //keyMap是linkedhashmap,最老的记录已经被移除了,然后这里我们还需要移除被委托的那个cache的记录
        if (eldestKey != null) {
            delegate.removeObject(eldestKey);
            eldestKey = null;
        }
    }

}

LRU 算法


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

疯长

疯长

[美]肖恩· 阿美拉蒂 / 中信出版集团 / 2018-10 / 45

实现财务回报以及扩大影响力是企业家长期关注和讨论的问题。 为什么有些公司实现了10倍的投资回报,而其他的则勉力支撑?产品类似的公司,为什么有的家喻户晓,有的默默无闻直至退出市场…… 为了了解真相,作者阿美拉蒂在这本书中精选10组对照公司,比如,同为社交平通的Facebook(脸谱网)和Friendster(交友网),同为快餐领域先驱的麦当劳和白色城堡,再比如都在开发电动汽车市场的特斯拉......一起来看看 《疯长》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具