一道数据结构题

LRU和LFU

LRU作为常用的缓存策略,LFU也是一种缓存策略。两者的代码实现均可采用LinkedHashSet(map)或双向链表来实现。

LRU

LinkedHashSet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class LRUCache {


    static class Node {

        Integer k, v;


        Node(Integer _k, Integer _v) {
            k = _k;
            v = _v;
        }
    }

    Map<Integer, Node> map = new HashMap<>();
    LinkedHashSet<Node> set = new LinkedHashSet<>();

    int capacity;
    int count;

    public LRUCache(int _capacity) {
        capacity = _capacity;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        set.remove(node);
        set.add(node);
        return map.get(key).v;
    }

    public void put(int key, int value) {
        Node newNode = new Node(key, value);
        if (map.containsKey(key)) {
            var oldNode = map.get(key);
            set.remove(oldNode);
            set.add(newNode);
            map.put(key, newNode);
        } else {
            if (count < capacity) {
                set.add(newNode);
                map.put(key, newNode);
                count++;
            } else {
                var obsoleteNode = set.iterator().next();
                set.remove(obsoleteNode);
                map.remove(obsoleteNode.k);
                set.add(newNode);
                map.put(key, newNode);
            }
        }
    }
}

DoublyList

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
class LRUCache {


    static class Node<K, V> {
        Node<K, V> pre;
        Node<K, V> next;
        K k;
        V v;

        Node(K k, V v) {
            this.k = k;
            this.v = v;
        }
    }

    static class DoublyList {


        Node<Integer, Integer> head, tail;

        DoublyList() {
            head = new Node<>(-1, -1);
            tail = new Node<>(-1, -1);
            head.next = tail;
            tail.pre = head;
        }

        void addLast(Node<Integer, Integer> node) {
            var p = tail.pre;
            node.next = tail;
            tail.pre = node;
            node.pre = p;
            p.next = node;
        }

        Node<Integer, Integer> removeFirst() {
            var ret = head.next;
            var nxt = ret.next;
            nxt.pre = head;
            head.next = nxt;
            return ret;
        }

        void remove(Node<Integer, Integer> node) {
            var pre = node.pre;
            var nxt = node.next;
            pre.next = nxt;
            nxt.pre = pre;
        }

    }


    Map<Integer, Node<Integer, Integer>> map;

    int capacity;

    DoublyList doublyList;

    int count;

    public LRUCache(int capacity) {
        map = new HashMap<>();
        this.capacity = capacity;
        doublyList = new DoublyList();
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        var node = map.get(key);
        doublyList.remove(node);
        doublyList.addLast(node);
        return node.v;
    }

    public void put(int key, int value) {
        Node<Integer, Integer> newNode = new Node<>(key, value);
        if (map.containsKey(key)) {
            var oldNode = map.get(key);
            doublyList.remove(oldNode);
            doublyList.addLast(newNode);
            map.put(key, newNode);
        } else {
            if (count < capacity) {
                doublyList.addLast(newNode);
                map.put(key, newNode);
                count++;
            } else {
                var obsolete = doublyList.removeFirst();
                map.remove(obsolete.k);
                doublyList.addLast(newNode);
                map.put(key, newNode);
            }
        }
    }
}

LFU

LinkedHashSet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class LFUCache {


    static class Node<K, V> {
        Node<K, V> next;
        Node<K, V> pre;

        K k;

        V v;

        int freq;

        Node(K _k, V _v) {
            k = _k;
            v = _v;
            freq = 1;
        }

    }

    Map<Integer, Node<Integer, Integer>> map = new HashMap<>();

    Map<Integer, LinkedHashSet<Node<Integer, Integer>>> Freq = new HashMap<>();

    int cap;

    int cnt;

    int minFreq;

    public LFUCache(int capacity) {
        cap = capacity;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        flush(key);
        return map.get(key).v;
    }

    public void put(int key, int value) {
        if (!map.containsKey(key)) {
            Node<Integer, Integer> node = new Node<>(key, value);
            if (cnt < cap) cnt++;
            else removeOne();
            map.put(key, node);
            Freq.computeIfAbsent(1, e -> new LinkedHashSet<>()).add(node);
            minFreq = 1;
        } else {
            Node<Integer, Integer> integerIntegerNode = map.get(key);
            integerIntegerNode.v = value;
            flush(key);
        }
    }

    private void flush(int key) {
        var node = map.get(key);
        var freq = node.freq;
        var set = Freq.get(freq);
        set.remove(node);
        if (set.isEmpty() && minFreq == freq) minFreq++;
        node.freq++;
        Freq.computeIfAbsent(node.freq, e -> new LinkedHashSet<>()).add(node);
    }

    private void removeOne() {
        LinkedHashSet<Node<Integer, Integer>> nodes = Freq.get(minFreq);
        Node<Integer, Integer> next = nodes.iterator().next();
        nodes.remove(next);
        map.remove(next.k);
    }


}

DoublyList

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
class LFUCache {


    static class Node<K, V> {
        Node<K, V> next;
        Node<K, V> pre;
        K k;
        V v;
        int freq;

        Node(K _k, V _v) {
            k = _k;
            v = _v;
            freq = 1;
        }
    }


    static class DoublyList {

        Node<Integer, Integer> head, tail;

        DoublyList() {
            head = new Node<>(-1, -1);
            tail = new Node<>(-1, -1);
            head.next = tail;
            tail.pre = head;
        }

        boolean isEmpty() {
            return head.next == tail;
        }

        Node<Integer, Integer> removeFirst() {
            var node = head.next;
            var nNode = node.next;
            head.next = nNode;
            nNode.pre = head;
            return node;
        }

        void remove(Node<Integer, Integer> node) {
            var pNode = node.pre;
            var nNode = node.next;
            pNode.next = nNode;
            nNode.pre = pNode;
        }

        void add(Node<Integer, Integer> node) {
            var lastNode = tail.pre;
            lastNode.next = node;
            node.pre = lastNode;
            node.next = tail;
            tail.pre = node;
        }
    }


    Map<Integer, Node<Integer, Integer>> map = new HashMap<>();

    Map<Integer, DoublyList> Freq = new HashMap<>();

    int cap;

    int cnt;

    int minFreq;

    public LFUCache(int capacity) {
        cap = capacity;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        flush(key);
        return map.get(key).v;
    }

    public void put(int key, int value) {
        if (!map.containsKey(key)) {
            Node<Integer, Integer> node = new Node<>(key, value);
            if (cnt < cap) cnt++;
            else removeOne();
            map.put(key, node);
            Freq.computeIfAbsent(1, e -> new DoublyList()).add(node);
            minFreq = 1;
        } else {
            map.get(key).v = value;
            flush(key);
        }
    }

    private void flush(int key) {
        var node = map.get(key);
        var f = node.freq;
        var list = Freq.get(f);
        list.remove(node);
        if (list.isEmpty() && f == minFreq) minFreq++;
        node.freq++;
        Freq.computeIfAbsent(node.freq, e -> new DoublyList()).add(node);
    }

    private void removeOne() {
        var list = Freq.get(minFreq);
        Node<Integer, Integer> node = list.removeFirst();
        map.remove(node.k);
    }
}
算法
#杂项
一道数据结构题
http://example.com/2023/09/25/一道数据结构题/
作者
ykexc
发布于
2023年9月25日
许可协议