devbox
运维做开发
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LRU算法与LFU算法_lru lfu

作者：运维做开发 | 2024-08-09 01:36:19

赞

踩

lru lfu

LRU算法

LRU是Least Recently Used的缩写，即最近最少使用算法，是操作系统中页面置换算法的一种，由于内存中存放的页数有限，所以将最近没有使用到的算法会移出内存。
LRU原理：
LRU原理如下图所示：
在这里插入图片描述
它会将最近访问的节点放在前面，将最近没有访问的节点放在后面。如果缓存空间满了，就会将最后一个节点删掉，并将新的节点添加到首部。

Java实现
对于链式存储的结构，使用到的集合有ArrayList和LinkedList，而ArrayList底层是基于数组的，对元素的移动花费的时间复杂度较高，所以使用LinkedList，基于链表形式的，并且是双向链表，因为要考虑删除节点。而链表的查找时间复杂度也高，但是可以通过使用hash进行快速定位。所以，LRU算法可以通过双向链表和hash来进行实现。

代码部分
手动实现双向链表：

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    //定义map映射
    private Map<String, Node> map;
    //定义缓存容量
    private int capacity = 8;
    //缓存中当前有一个数据
    private int size = 0;
    //链表的头结点和尾结点
    private Node head, tail;

    //从缓存中读取数据
    public int get(String key) {
        Node node = map.get(key);
        //如果能找到，就将节点移动到链表头部，没有返回-1
        if (node != null) {
            moveToHead(node);
            return node.value;
        }
        return -1;
    }

    //将节点添加到缓存中
    public void put(String key, int value) {
    	if(capacity == 0)   return;
        Node node = map.get(key);
        if (node != null) {
            //如果存在，就将这个点的值进行修改并移到链表头部
            node.value = value;
            moveToHead(node);
            return;
        }

        //如果不存在，先判断空间缓存空间是否足够
        if (size == capacity) {
            map.remove(tail.pre.key);
            deleteNode(tail.pre);
            size -= 1;
        }
        Node newNode = new Node(key, value);
        addToHead(newNode);
        map.put(key, newNode);
        size += 1;
    }

    //将节点移到头结点
    private void moveToHead(Node node) {
        deleteNode(node);
        addToHead(node);
    }

    //将节点添加到头部
    private void addToHead(Node node) {
        node.next = head.next;
        head.next.pre = node;
        node.pre = head;
        head.next = node;
    }

    //删除这个节点
    private void deleteNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        initLinkedList();
        map = new HashMap<>(capacity);
        size = 0;
    }

    //初始化链表
    private void initLinkedList() {
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }

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

    public static class Node {
        public Node pre;
        public Node next;

        public String key;
        public int value;

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

        public Node() {
        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put("key1", 1);
        cache.put("key2", 2);
        System.out.println(cache.get("key2"));//21
        cache.put("key3", 3);
        System.out.println(cache.get("key1"));//32
    }

}

  • 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
  • 109
  • 110
  • 111
  • 112
  • 113

调用LinkedList API进行实现

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LRUCache {
    //定义map映射
    private Map<String, Node> map;
    //定义缓存容量
    private int capacity = 8;

    private LinkedList<Node> list = new LinkedList<>();

    //从缓存中读取数据
    public int get(String key) {
        Node node = map.get(key);
        //如果能找到，就将节点移动到链表头部，没有返回-1
        if (node != null) {
            list.remove(node);
            list.addFirst(node);
            return node.value;
        }
        return -1;
    }

    //将节点添加到缓存中
    public void put(String key, int value) {
        if(capacity == 0)   return;
        Node node = map.get(key);
        if (node != null) {
            //如果存在，就将这个点的值进行修改并移到链表头部
            node.value = value;
            list.remove(node);
            list.addFirst(node);
            return;
        }

        //如果不存在，先判断空间缓存空间是否足够
        if (list.size() == capacity) {
            //如果存在，要将map和LinkedList中的删掉
            map.remove(list.getLast().key);
            list.removeLast();
        }
        Node newNode = new Node(key, value);
        map.put(key, newNode);
        list.addFirst(newNode);
    }


    public LRUCache(int capacity) {
        this.capacity = capacity;
        //也是定义map的容量，其实这一步没必要
        map = new HashMap<>(capacity);
    }


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

    public static class Node {
        public String key;
        public int value;

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

        public Node() {
        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put("key1",1);
        cache.put("key2",2);
        System.out.println(cache.get("key2"));  //21
        cache.put("key3",3);
        System.out.println(cache.get("key1"));  //32
    }

}

  • 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

LFU算法

LFU是 Least Frequently Used 的缩写，即最近最少访问频率，也是操作系统中页面调换算法的一种，将最近使用频率最小，并且很长时间没使用的页面调出内存。

LFU原理
在这里插入图片描述
其中，一个map存储频率和节点的集合之间的关系，即 freq - list，另一个map存储key - node 之间的关系。从key - node 中读到节点，然后去 freq - list 中将节点添加到对应的list集合中

代码部分
由于对每一个频率都要创建一个链表来存储，所以这里直接使用 Java 中的 API 进行实现

package cache;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LFUCache {

    private Map<String,Node> key_node;
    private Map<Integer, LinkedList<Node>> freq_list;
    private int capacity = 2;

    private int minFreq = 1;


    public int get(String key){
        //如果不包含这个数，返回-1
        if(!key_node.containsKey(key))  return -1;
        Node node = key_node.get(key);
        //获得节点的频率
        int freq = node.freq;
        //当前节点频率加1
        node.freq += 1;
        //从对应的集合中删除节点
        freq_list.get(freq).remove(node);
        //如果删除完节点为0，删除集合
        if(freq_list.get(freq).size() == 0){
            freq_list.remove(freq);
            if(freq == minFreq){
                minFreq += 1;
            }
        }
        LinkedList<Node> list = freq_list.getOrDefault(freq + 1, new LinkedList<Node>());
        list.addFirst(node);
        freq_list.put(freq + 1, list);
        return node.value;
    }


    public void put(String key,int value){
        if(capacity == 0)   return ;
        Node node = key_node.get(key);
        if(node != null){
            //获取当前节点的频率
            int freq = node.freq;
            node.freq += 1;
            node.value = value;
            //从对应的频率节点的集合中删除节点
            freq_list.get(freq).remove(node);
            //如果集合中没有了元素，就将集合删除
            if(freq_list.get(freq).size() == 0){
                freq_list.remove(freq);
                //如果删除的是最小的频次，就让最小的频次加1
                if(freq == minFreq){
                    minFreq += 1;
                }
            }
            //将节点移动到下一个频率的节点集合中
            LinkedList<Node> list = freq_list.getOrDefault(freq + 1, new LinkedList<Node>());
            list.offerFirst(node);
            freq_list.put(freq + 1, list);
            key_node.put(key, node);
        }else {
            Node newNode = new Node(key,value,1);
            //如果缓存容量已经满了，需要将使用频率最低并且长时间没使用的数据删除
            if(key_node.size() == capacity){
                Node lastNode = freq_list.get(minFreq).pollLast();
                key_node.remove(lastNode.key);
                if(freq_list.get(minFreq).size() == 0){
                    freq_list.remove(minFreq);
                }
            }
            //将新的节点添加到集合中
            key_node.put(key,newNode);
            LinkedList<Node> list = freq_list.getOrDefault(1, new LinkedList<Node>());
            list.offerFirst(newNode);
            freq_list.put(1,list);
            minFreq = 1;
        }
    }

    public LFUCache(int capacity) {
        this.capacity = capacity;
        key_node = new HashMap<>();
        freq_list = new HashMap<>();
    }

    public LFUCache() {
        key_node = new HashMap<>();
        freq_list = new HashMap<>();
    }

    public static class Node{
        public String key;
        public int value;
        public int freq;

        public Node() {
        }

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

    public static void main(String[] args) {
        LFUCache cache = new LFUCache(2);
        cache.put("key1",1);    //1
        cache.put("key2",2);    //21
        cache.put("key3",3);    //32
        System.out.println(cache.get("key1"));
        System.out.println(cache.get("key2"));
        System.out.println(cache.get("key3"));
        cache.put("key1",1);    //13
        System.out.println(cache.get("key1"));
        System.out.println(cache.get("key2"));
        System.out.println(cache.get("key3"));
        cache.put("key2",2);    //21
        cache.put("key1",1);    //12
    }
}


  • 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
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/运维做开发/article/detail/950798
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号