美文网首页
LRU数据结构设计与实现

LRU数据结构设计与实现

作者: wuhuaguo丶 | 来源:发表于2019-07-17 03:20 被阅读0次

    LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择距离最近时间最久未使用的页面予以淘汰。其核心思想是“如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小”。
    常见使用场景:内存管理中的页面置换算法、缓存淘汰中的淘汰策略等。
    设计的LRU数据结构需要实现get和set方法
    get(key):若缓存中存在key,返回对应的value,否则返回-1
    set(key,value):若缓存中存在key,替换其value,否则插入key及其value,如果插入时缓存已经满了,应该使用LRU算法把最近最久没有使用的key踢出缓存。
    LRU原理和Redis实现——一个今日头条的面试题
    实现1:使用双向链表+HashMap
    整体设计思路是使用HashMap的key存储key,这样可以做到set和get的时间复杂度都是O(1),而HashMap的Value指向双向链表实现的LRU的Node节点,如图所示:

    class DLinkedNode {
        String key;
        int value;
        DLinkedNode pre;
        DLinkedNode post;
    }
    
    public class LRUCache {
        private Hashtable<String, DLinkedNode> cache = new Hashtable<>();
        private int count;
        private int capacity;
        private DLinkedNode head, tail;
    
        public LRUCache(int capacity) {
            this.count = 0;
            this.capacity = capacity;
    
            head = new DLinkedNode();
            head.pre = null;
    
            tail = new DLinkedNode();
            tail.post = null;
    
            head.post = tail;
            tail.pre = head;
        }
    
        public int get(String key) {
            DLinkedNode node = cache.get(key);
            if (node == null) {
                return -1; // should raise exception here.
            }
    
            // move the accessed node to the head;
            this.moveToHead(node);
    
            return node.value;
        }
    
        public void set(String key, int value) {
            DLinkedNode node = cache.get(key);
    
            if (node == null) {
    
                DLinkedNode newNode = new DLinkedNode();
                newNode.key = key;
                newNode.value = value;
    
                this.cache.put(key, newNode);
                this.addNode(newNode);
    
                ++count;
    
                if (count > capacity) {
                    // pop the tail
                    DLinkedNode tail = this.popTail();
                    this.cache.remove(tail.key);
                    --count;
                }
            } else {
                // update the value.
                node.value = value;
                this.moveToHead(node);
            }
        }
    
        /**
         * Always add the new node right after head;
         */
        private void addNode(DLinkedNode node) {
            node.pre = head;
            node.post = head.post;
    
            head.post.pre = node;
            head.post = node;
        }
    
        /**
         * Remove an existing node from the linked list.
         */
        private void removeNode(DLinkedNode node) {
            DLinkedNode pre = node.pre;
            DLinkedNode post = node.post;
    
            pre.post = post;
            post.pre = pre;
        }
    
        /**
         * Move certain node in between to the head.
         */
        private void moveToHead(DLinkedNode node) {
            this.removeNode(node);
            this.addNode(node);
        }
    
        // pop the current tail.
        private DLinkedNode popTail() {
            DLinkedNode res = tail.pre;
            this.removeNode(res);
            return res;
        }
    }
    

    实现2:直接使用LinkedHashMap

    public class LRU<K, V> {
        /**
         * LinkedHashMap负载因子默认0.75
         */
        private static final float hashLoadFactory = 0.75f;
        private LinkedHashMap<K, V> map;
        private int cacheSize;
    
        /**
         * @param cacheSize
         *            容量
         */
        public LRU(int cacheSize) {
            this.cacheSize = cacheSize;
            int capacity = (int) Math.ceil(cacheSize / hashLoadFactory) + 1;
            //如果accessOrder为true的话,则会把访问过的元素放在链表后面,放置顺序是访问的顺序
            //(LinkedHashMap里面的get方法,当accessOrder为true,会走afterNodeAccess方法将节点移到最后)
            //如果accessOrder为flase的话,则按插入顺序来遍历
            map = new LinkedHashMap<K, V>(capacity, hashLoadFactory, true) {
                private static final long serialVersionUID = -5291175172111746517L;
    
                /*
                 * 当map容量大于LRU的容量时,删除最近最少使用的数据
                 */
                @Override
                protected boolean removeEldestEntry(Entry<K, V> eldest) {
                    return size() > LRU.this.cacheSize;
                }
            };
        }
    
        public synchronized V get(K key) {
            return map.get(key);
        }
    
        public synchronized void put(K key, V value) {
            map.put(key, value);
        }
    
        public synchronized void clear() {
            map.clear();
        }
    
        public synchronized int usedSize() {
            return map.size();
        }
    
        public void print() {
            for (Map.Entry<K, V> entry : map.entrySet()) {
                System.out.print(entry.getValue() + "--");
            }
            System.out.println();
    
        }
    }
    

    LRU算法介绍和在JAVA的实现及源码分析

    相关文章

      网友评论

          本文标题:LRU数据结构设计与实现

          本文链接:https://www.haomeiwen.com/subject/buhflctx.html