伟大的车尔尼

伟大的车尔尼

关注
发信
关注(28)粉丝(399)

哈希表题目：LFU 缓存

题目

标题和出处

标题：LFU 缓存

出处：460. LFU 缓存

难度

9 级

题目描述

要求

请你为最不经常使用（LFU）缓存设计并实现数据结构。

实现 LFUCache \texttt{LFUCache} LFUCache 类：

  • LFUCache(int   capacity) \texttt{LFUCache(int capacity)} LFUCache(int capacity) 用数据结构的容量 capacity \texttt{capacity} capacity 初始化对象。
  • int   get(int   key) \texttt{int get(int key)} int get(int key) 如果关键字 key \texttt{key} key 存在于缓存中，则获取关键字的值，否则返回 -1 \texttt{-1} -1。
  • void   put(int   key,   int   value) \texttt{void put(int key, int value)} void put(int key, int value) 如果关键字 key \texttt{key} key 已存在，则变更其值；如果关键字不存在，请插入键值对。当缓存达到其容量 capacity \texttt{capacity} capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个关键字具有相同使用频率）时，应该移除最近最久未使用的关键字。

为了确定最不常使用的关键字，为缓存中的每个关键字维护一个使用计数器。使用计数最小的关键字是最久未使用的关键字。

当一个关键字首次插入到缓存中时，它的使用计数器被设置为 1 \texttt{1} 1（由于 put \texttt{put} put 操作）。对缓存中的关键字执行 get \texttt{get} get 或 put \texttt{put} put 操作，使用计数器的值将会递增。

函数 get \texttt{get} get 和 put \texttt{put} put 必须以 O(1) \texttt{O(1)} O(1) 的平均时间复杂度运行。

示例

示例 1：

输入：
["LFUCache",   "put",   "put",   "get",   "put",   "get",   "get",   "put",   "get",   "get",   "get"] \texttt{["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]} ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2],   [1,   1],   [2,   2],   [1],   [3,   3],   [2],   [3],   [4,   4],   [1],   [3],   [4]] \texttt{[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]} [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输出：
[null,   null,   null,   1,   null,   -1,   3,   null,   -1,   3,   4] \texttt{[null, null, null, 1, null, -1, 3, null, -1, 3, 4]} [null, null, null, 1, null, -1, 3, null, -1, 3, 4]
解释：
// cnt(x) \texttt{cnt(x)} cnt(x) 表示关键字 x \texttt{x} x 的使用计数
// cache=[] \texttt{cache=[]} cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的）
LFUCache   lfu   =   new   LFUCache(2); \texttt{LFUCache lfu = new LFUCache(2);} LFUCache lfu = new LFUCache(2);
lfu.put(1,   1); \texttt{lfu.put(1, 1);} lfu.put(1, 1); // cache=[1,_],   cnt(1)=1 \texttt{cache=[1,\_], cnt(1)=1} cache=[1,_], cnt(1)=1
lfu.put(2,   2); \texttt{lfu.put(2, 2);} lfu.put(2, 2); // cache=[2,1],   cnt(2)=1,   cnt(1)=1 \texttt{cache=[2,1], cnt(2)=1, cnt(1)=1} cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1); \texttt{lfu.get(1);} lfu.get(1); // 返回 1 \texttt{1} 1， cache=[1,2],   cnt(2)=1,   cnt(1)=2 \texttt{cache=[1,2], cnt(2)=1, cnt(1)=2} cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3,   3); \texttt{lfu.put(3, 3);} lfu.put(3, 3); // 去除关键字 2 \texttt{2} 2，因为 cnt(2)=1 \texttt{cnt(2)=1} cnt(2)=1，使用计数最小， cache=[3,1],   cnt(3)=1,   cnt(1)=2 \texttt{cache=[3,1], cnt(3)=1, cnt(1)=2} cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2); \texttt{lfu.get(2);} lfu.get(2); // 返回 -1 \texttt{-1} -1（未找到）
lfu.get(3); \texttt{lfu.get(3);} lfu.get(3); // 返回 3 \texttt{3} 3， cache=[3,1],   cnt(3)=2,   cnt(1)=2 \texttt{cache=[3,1], cnt(3)=2, cnt(1)=2} cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4,   4); \texttt{lfu.put(4, 4);} lfu.put(4, 4); // 去除关键字 1 \texttt{1} 1， 1 \texttt{1} 1 和 3 \texttt{3} 3 的 cnt \texttt{cnt} cnt 相同，但 1 \texttt{1} 1 最久未使用， cache=[4,3],   cnt(4)=1,   cnt(3)=2 \texttt{cache=[4,3], cnt(4)=1, cnt(3)=2} cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1); \texttt{lfu.get(1);} lfu.get(1); // 返回 -1 \texttt{-1} -1（未找到）
lfu.get(3); \texttt{lfu.get(3);} lfu.get(3); // 返回 3 \texttt{3} 3， cache=[3,4],   cnt(4)=1,   cnt(3)=3 \texttt{cache=[3,4], cnt(4)=1, cnt(3)=3} cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4); \texttt{lfu.get(4);} lfu.get(4); // 返回 4 \texttt{4} 4， cache=[4,3],   cnt(4)=2,   cnt(3)=3 \texttt{cache=[4,3], cnt(4)=2, cnt(3)=3} cache=[4,3], cnt(4)=2, cnt(3)=3

数据范围

  • 0 ≤ capacity ≤ 10 4 \texttt{0} \le \texttt{capacity} \le \texttt{10}^\texttt{4} 0≤capacity≤104
  • 0 ≤ key ≤ 10 5 \texttt{0} \le \texttt{key} \le \texttt{10}^\texttt{5} 0≤key≤105
  • 0 ≤ value ≤ 10 9 \texttt{0} \le \texttt{value} \le \texttt{10}^\texttt{9} 0≤value≤109
  • 最多调用 2 × 10 5 \texttt{2} \times \texttt{10}^\texttt{5} 2×105 次 get \texttt{get} get 和 put \texttt{put} put

前言

这道题是「LRU 缓存」的进阶，实现 LFU 缓存的方法和实现 LRU 缓存的方法相似，都是使用哈希表和双向链表。但是 LFU 缓存需要记录关键字的使用计数，因此情况更加复杂，需要使用两个哈希表记录，并对每个使用计数维护一个双向链表。

解法

思路和算法

实现 LFU 缓存需要使用哈希表和双向链表。双向链表中的每个结点存储键值对、该结点的使用计数以及该结点的前一个结点和后一个结点，结点顺序为从头结点到尾结点依次按照最近访问时间降序排列。两个哈希表中，关键字结点哈希表存储每个关键字对应的的结点，计数链表哈希表存储每个计数对应的双向链表。

为了便于操作，每个双向链表需要维护伪头结点和伪尾结点，链表的实际头结点为伪头结点的后一个结点，链表的实际尾结点为伪尾结点的前一个结点（只有当链表不为空时才存在实际头结点和实际尾结点）。初始时，伪头结点和伪尾结点相邻。

在 LFU 缓存中插入新的关键字时，如果缓存达到容量则需要首先移除使用计数最低的关键字，然后插入新的关键字，因此除了维护容量和两个哈希表之外，还需要维护最低使用计数。

构造方法中，将容量初始化为参数值，将最低使用计数初始化为 0 0 0，将两个哈希表初始化。

由于当容量为 0 0 0 时，缓存中不能存入任何关键字，因此 get \textit{get} get 操作返回 − 1 -1 −1， put \textit{put} put 操作直接返回。以下对于 get \textit{get} get 操作和 put \textit{put} put 操作的说明只考虑容量大于 0 0 0 的情况。

对于 get \textit{get} get 操作，做法如下。

  • 如果关键字结点哈希表中存在关键字 key \textit{key} key，则在关键字结点哈希表中得到 key \textit{key} key 对应的结点，更新该结点的状态，返回结点的值。

  • 如果关键字结点哈希表中不存在关键字 key \textit{key} key，返回 − 1 -1 −1。

由于 get \textit{get} get 操作只是根据关键字 key \textit{key} key 从缓存中得到对应的值，虽然改变了关键字的使用计数和顺序，但是并没有添加新的关键字，因此关键字的数量不变，不会出现关键字数量超过容量的情况，不需要移除最不经常使用的关键字。

对于 put \textit{put} put 操作，首先判断关键字节点哈希表中是否存在关键字 key \textit{key} key。如果存在关键字 key \textit{key} key 则关键字的数量不变，不需要移除最不经常使用的关键字。如果不存在关键字 key \textit{key} key 则关键字的数量增加 1 1 1 个，如果在 put \textit{put} put 操作之前，关键字的数量已经达到容量，则需要移除最不经常使用的关键字。

移除最不经常使用的关键字的做法是：在计数链表哈希表中得到最低使用计数对应的双向链表，将该双向链表的实际尾结点（伪尾结点的前一个结点）从双向链表中删除，将实际尾结点的关键字从关键字结点哈希表中删除。

分析了移除最不经常使用的关键字的做法之后，可以得到 put \textit{put} put 操作的完整做法。

  • 如果关键字结点哈希表中存在关键字 key \textit{key} key，则在关键字结点哈希表中得到 key \textit{key} key 对应的结点，将该结点的值设为 value \textit{value} value，并更新该结点的状态。

  • 如果关键字结点哈希表中不存在关键字 key \textit{key} key，则需要执行两步操作，第一步是判断缓存容量是否已满并在容量已满的情况下移除最不经常使用的关键字，第二步是将新的键值对添加到缓存中。

    1. 如果关键字的数量已经达到容量，则需要移除最不经常使用的关键字；如果关键字的数量小于容量，则不移除任何关键字。

    2. 根据 key \textit{key} key 和 value \textit{value} value 创建结点，由于新结点的使用计数是 1 1 1，因此将最低使用计数设为 1 1 1，在关键字结点哈希表中添加 key \textit{key} key 和该结点的对应关系，在计数链表哈希表中得到计数 1 1 1 对应的双向链表并将该结点添加到双向链表的头部。

在 get \textit{get} get 和 put \textit{put} put 操作中，如果关键字结点哈希表中存在关键字 key \textit{key} key，则在得到对应的结点之后，都需要更新该结点的状态。更新结点状态的具体做法如下。

  1. 将结点的使用计数加 1 1 1，更新前的使用计数为原计数，更新后的使用计数为新计数。

  2. 在计数链表哈希表中得到原计数对应的双向链表，将结点从双向链表中删除。

  3. 在计数链表哈希表中得到新计数对应的双向链表，将结点添加到双向链表的头部。

  4. 上述操作之后，如果在计数链表哈希表中最低使用计数对应的双向链表为空，则该次更新操作将唯一的最低使用计数的关键字的使用计数加 1 1 1，因此将最低使用计数加 1 1 1。

由于每次 get \textit{get} get 操作和 put \textit{put} put 操作都是对哈希表和双向链表的操作，哈希表操作和在链表中添加和删除结点操作的时间都是 O ( 1 ) O(1) O(1)，因此 get \textit{get} get 操作和 put \textit{put} put 操作的时间复杂度都是 O ( 1 ) O(1) O(1)。

代码

class LFUCache {
    private class Node {
        private int key;
        private int value;
        private int count;
        private Node prev;
        private Node next;

        public Node() {
            this(-1, -1);
        }

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            count = 1;
            prev = null;
            next = null;
        }

        public int getKey() {
            return key;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public int getCount() {
            return count;
        }

        public void increaseCount() {
            count++;
        }

        public Node getPrev() {
            return prev;
        }

        public void setPrev(Node prev) {
            this.prev = prev;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }

    private class DoublyLinkedList {
        private Node pseudoHead;
        private Node pseudoTail;
        private int size;

        public DoublyLinkedList() {
            pseudoHead = new Node();
            pseudoTail = new Node();
            pseudoHead.setNext(pseudoTail);
            pseudoTail.setPrev(pseudoHead);
            size = 0;
        }

        public void addNode(Node node) {
            Node nextNode = pseudoHead.getNext();
            node.setNext(nextNode);
            nextNode.setPrev(node);
            pseudoHead.setNext(node);
            node.setPrev(pseudoHead);
            size++;
        }

        public void removeNode(Node node) {
            Node prev = node.getPrev(), next = node.getNext();
            prev.setNext(next);
            next.setPrev(prev);
            size--;
        }

        public Node getTail() {
            return pseudoTail.getPrev();
        }

        public boolean isEmpty() {
            return size == 0;
        }
    }

    private int capacity;
    private int minCount;
    private Map<Integer, Node> keyNodeMap;
    private Map<Integer, DoublyLinkedList> countListMap;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        minCount = 0;
        keyNodeMap = new HashMap<Integer, Node>();
        countListMap = new HashMap<Integer, DoublyLinkedList>();
    }

    public int get(int key) {
        if (capacity == 0) {
            return -1;
        }
        if (keyNodeMap.containsKey(key)) {
            Node node = keyNodeMap.get(key);
            update(node);
            return node.getValue();
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        if (keyNodeMap.containsKey(key)) {
            Node node = keyNodeMap.get(key);
            node.setValue(value);
            update(node);
        } else {
            if (keyNodeMap.size() == capacity) {
                DoublyLinkedList minCountList = countListMap.get(minCount);
                Node tail = minCountList.getTail();
                minCountList.removeNode(tail);
                keyNodeMap.remove(tail.getKey());
            }
            minCount = 1;
            Node node = new Node(key, value);
            keyNodeMap.put(key, node);
            countListMap.putIfAbsent(1, new DoublyLinkedList());
            DoublyLinkedList list = countListMap.get(1);
            list.addNode(node);
        }
    }

    private void update(Node node) {
        int prevCount = node.getCount();
        node.increaseCount();
        int currCount = node.getCount();
        DoublyLinkedList prevList = countListMap.get(prevCount);
        prevList.removeNode(node);
        countListMap.putIfAbsent(currCount, new DoublyLinkedList());
        DoublyLinkedList currList = countListMap.get(currCount);
        currList.addNode(node);
        if (countListMap.get(minCount).isEmpty()) {
            minCount++;
        }
    }
}

复杂度分析

  • 时间复杂度：构造方法和各项操作的时间复杂度都是 O ( 1 ) O(1) O(1)。

  • 空间复杂度： O ( capacity ) O(\textit{capacity}) O(capacity)，其中 capacity \textit{capacity} capacity 是 LFU 缓存的容量。每次 get \textit{get} get 和 put \textit{put} put 操作过程中和操作结束之后，哈希表中的键值对数量和双向链表中的结点数量（不包括伪头结点和伪尾结点）不会超过 capacity \textit{capacity} capacity。

06-01 21:56
Powered by LMLPHP ©2024 伟大的车尔尼 0.005790