LRU

1、使用LinkedHashMap

LinkedHashMap = HashMap + 双向链表

题目：使用LinkedHashMap实现一个符合LRU算法的数据结构，该结构最多可以缓存6个元素，当元素多余六个时，会自动删除最近最久没有被使用的元素。

import java.util.LinkedHashMap;
import java.util.Map;

public class LRU<K, V> extends LinkedHashMap<K, V> {
    // initialCapacity 初始容量
    // loadFactor 加载因子
    // accessOrder 顺序模式，true对应访问顺序，false对应插入顺序
    public LRU(int initialCapacity, float loadFactor, boolean accessOrder) {
        super(initialCapacity, loadFactor, accessOrder);
    }

    // 重写LinkedHashMap中的removeEldestEntry方法，
    // 当LRU中元素多余6个时，删除最不经常使用的元素
    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        if (size() > 6) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        LRU<Character, Integer> lru = new LRU<>(16, 0.75f, true);
        String s = "abcdefghijkl";
        for (int i = 0; i < s.length(); i++) {
            lru.put(s.charAt(i), i);
        }
        System.out.println("LRU中key为h的Entry的值为：" + lru.get('h'));
        System.out.println("LRU的大小：" + lru.size());
        System.out.println("LRU：" + lru);
    }
}

输出：

LRU中key为h的Entry的值为：7
LRU的大小：6
LRU：{g=6, i=8, j=9, k=10, l=11, h=7}

2、使用双向链表实现LRU

数据结构：哈希表+双向链表，哈希表用来存储节点信息，双向链表用来存储位置信息。链表中每个节点的结构为Node类型，包含所需的键-值信息、该节点的前驱节点、该节点的后继节点。

约定：双向链表的头部是最近访问的节点。这个并不是固定不变的，而是人为约定的。

注意：（1）给双向链表添加头尾的虚拟节点，虚拟节点不包含信息，只起到连接的作用，这样的好处是不用再特殊考虑链表中有数据的第一个节点和最后一个节点，可以把这两个节点也当成普通节点一样对待了。（2）LRU有容量限制，所以在put一个全新的键值时，可以首先考虑剩余容量大小，如果容量已满，先要删除最不常使用的节点（和上面的约定规则相关联）。

例题：LRU缓存机制（LeetCode146）
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

• 获取数据 get(key) ：如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
• 写入数据 put(key, value) ：如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例：

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得关键字 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得关键字 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

代码如下：

// 约定：Node构成的双向链表中，头部是最近使用的，尾部是最不常使用的；
class LRUCache {
    private Map<Integer, Node> dataMap; // 表示key和节点Node的对应关系
    private Node head;
    private Node tail;
    private int size;
    private int capacity;

    private class Node {
        private int key;
        private int value;
        private Node prev;// Node之间构成双向链表
        private Node next;
        public Node() {}
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public LRUCache(int capacity) {
        dataMap = new HashMap<Integer, Node>();
        this.capacity = capacity;
        this.size = 0;
        // 注意：head和tail是虚拟节点，并不指向真实的节点
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        Node target = dataMap.get(key);
        if (target == null) {
            return -1;
        }
        moveToHead(target); // 此操作是O(1)时间复杂度
        return target.value;
    }
    
    public void put(int key, int value) {
        Node target = dataMap.get(key);
        if (target != null) {
            target.value = value;
            moveToHead(target);
        } else { // 这个key不存在的话
            target = new Node(key, value);
            if (size == capacity) {
                int delKey = tail.prev.key;
                removeNode(tail.prev);
                dataMap.remove(delKey);
                size--;
            }
            addFirst(target);
            dataMap.put(key, target);
            size++;
        }
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addFirst(node);
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addFirst(Node node) {
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

例题总结：

1. 使用的数据结构：哈希表+双向链表，哈希表用来存储节点（数据），双向链表用来存储位置信息。
2. 哈希表的键值对中，键是给出的key，值是节点信息，节点Node是内部类，注意这里必须要存储节点，从而保证从链表中删除一个节点的时间复杂度为O(1)。
3. 这里约定：最近访问过的（get、put）节点放在双向链表的头部，所以尾部的节点就是最不经常使用的节点。
4. 具体实现的过程中，head和tail是虚拟节点，不指向真正的节点，便于链表的穿针引线。

LFU

LFU，即最不经常使用页面置换算法，是一种根据页面访问次数来淘汰节点的内存置换算法。

底层结构

LFU的具体实现由两种链表组成，分别是次数链表和元素链表。首先访问次数构成一个链表，然后同一个访问次数下面可能包含多个元素，这些元素也是通过双向链表串联在该访问次数下面。示例如下：

解释：

• 两种访问操作：put(key)和get(key)，对应的链表的操作如下：
  • 如果这个key不存在，put操作会将这个key加到次数为1的次数链表节点（如果不存在需先建立）下面的元素链表的尾部，get操作直接返回null；
  • 如果这个key存在，put操作和get操作会将这个key先从原先的元素链表中删除，然后移到次数加一的次数链表节点（如果不存在需先建立）下面的元素链表的尾部。
• 如果次数链表节点下面没有元素了，那么该节点就要被删除了。
• 如何删除相同次数下面的元素链表节点？大家都是相同的访问次数，那肯定是删除最先被访问的，就是该元素链表节点下面的元素链表的头部。

代码实现

题目：实现LFU中的set和get方法，要求：两个方法的时间复杂度都是O(1)。

import java.util.HashMap;

public class LFUCache {
    private class Node {
        private Integer key;
        private Integer value;
        private Integer times;
        private Node up;
        private Node down; // Node节点之间构成双向链表

        public Node(int key, int value, int times) {
            this.key = key;
            this.value = value;
            this.times = times;
        }
    }

    // NodeList是次数链表节点，NodeList节点之间构成双向链表
    // NodeList节点里面包含了该次数对应的所有Node节点
    private class NodeList {
        private Node head;
        private Node tail;
        private NodeList last;
        private NodeList next;

        public NodeList(Node node) {
            this.head = node;
            this.tail = node;
        }

        // 约定：新来的Node节点加入到Node双向链表的尾部
        public void addNodeToTail(Node node) {
            node.up = tail;
            tail.down = node;
            tail = node;
        }

        public boolean isEmpty() {
            return head == null;
        }

        public void deleteNode(Node node) {
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                if (node == head) {
                    head = head.down;
                    head.up = null;
                } else if (node == tail) {
                    tail = tail.up;
                    tail.down = null;
                } else {
                    node.up.down = node.down;
                    node.down.up = node.up;
                }
            }
            node.up = null;
            node.down = null;
        }
    }

    private int capacity;
    private int size;
    private HashMap<Integer, Node> records; // 记录 key 到 Node的映射关系
    private HashMap<Node, NodeList> heads; // 记录 Node 到 次数链表节点的映射关系
    private NodeList headList; // 次数链表的头部

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        records = new HashMap<>();
        heads = new HashMap<>();
        headList = null;
    }

    /**
     * 功能：设置某个key对应的值
     * 思路：首先是否包含这个key，如果包含，更新对应的节点的值和位置信息；
     * 如果不包含，肯定要新建一个节点，需要判断容量是否已满，以及判断次数链表头部是否为1次。
     * @param key
     * @param value
     */
    public void set(int key, int value) {
        if (records.containsKey(key)) {
            Node node = records.get(key);
            node.value = value;
            node.times++;
            NodeList oldNodeList = heads.get(node);
            move(node, oldNodeList); // 更新新的Node节点的位置信息
        } else {
            if (size == capacity) {
                // 删除次数最少且最近没有访问的Node节点
                // headList是次数链表的头部，是访问次数最少的
                // headList里面的Node链表，头部是最近没有访问的Node节点
                Node delNode = headList.head;
                headList.deleteNode(delNode);
                // 删除节点之后验证是否要删除NodeList
                deleteNodeList(headList);
                records.remove(delNode.key);
                heads.remove(delNode);
                size--;
            }
            Node newNode = new Node(key, value, 1);
            // 初始状态，此时还没有任何节点
            if (headList == null) {
                headList = new NodeList(newNode);
            } else {
                if (headList.head.times.equals(newNode.times)) {
                    headList.addNodeToTail(newNode);
                } else {
                    // 新建次数为1的次数链表节点，并且更换头部headList
                    NodeList newList = new NodeList(newNode);
                    newList.next = headList;
                    headList.last = newList;
                    headList = newList;
                }
            }
            // 更新映射关系
            records.put(key, newNode);
            heads.put(newNode, headList);
            size++;
        }
    }

    /**
     * 获取某个key对应的值
     * @param key
     * @return
     */
    public int get(int key) {
        if (!records.containsKey(key)) {
            return -1;
        }
        Node node = records.get(key);
        // 更新这个Node的访问次数和位置信息
        node.times++;
        NodeList oldNodeList = heads.get(node);
        move(node, oldNodeList);
        return node.value;
    }

    /**
     * 功能：如果NodeList里面的Node链表为空，需要将该NodeList删除
     * @param nodeList
     * @return
     */
    private boolean deleteNodeList(NodeList nodeList) {
        if (nodeList.isEmpty()) {
            if (nodeList == headList) {
                headList = headList.next;
                nodeList.next = null;
                if (headList != null) {
                    headList.last = null;
                }
            } else {
                nodeList.last.next = nodeList.next;
                if (nodeList.next != null) {
                    nodeList.next.last = nodeList.last;
                }
            }
            return true;
        }
        return false;
    }

    /**
     * 功能：将Node从旧的次数链表节点移动到新的次数链表节点中
     * @param node
     * @param oldNodeList
     */
    private void move(Node node, NodeList oldNodeList) {
        oldNodeList.deleteNode(node);
        // 从旧的NodeList中删除Node之后，Node将要被放置的新的位置的前一个NodeList
        // 问号表达式主要是区分了oldNodeList是否被删除了
        NodeList preNodeList = deleteNodeList(oldNodeList) ? oldNodeList.last : oldNodeList;
        NodeList nextNodeList = preNodeList.next;
        if (nextNodeList == null) {
            NodeList newNodeList = new NodeList(node);
            if (preNodeList != null) {
                preNodeList.next = newNodeList;
            }
            newNodeList.last = preNodeList;
            if (headList == null) {
                headList = newNodeList;
            }
            heads.put(node, newNodeList);
        } else {
            if (nextNodeList.head.times.equals(node.times)) {
                nextNodeList.addNodeToTail(node);
                heads.put(node, nextNodeList);
            } else {
                NodeList newNodeList = new NodeList(node);
                if (preNodeList != null) {
                    preNodeList.next = newNodeList;
                }
                newNodeList.last = preNodeList;
                newNodeList.next = nextNodeList;
                nextNodeList.last = newNodeList;
                if (headList == nextNodeList) {
                    headList = newNodeList;
                }
                heads.put(node, newNodeList);
            }
        }
    }
}

参考资料：左老师算法进阶课程

最后

以上就是眼睛大百褶裙为你收集整理的LRU和LFU的底层原理和代码实现LRULFU的全部内容，希望文章能够帮你解决LRU和LFU的底层原理和代码实现LRULFU所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。