数据结构---LRU算法

作者：IT小白 | 2024-05-16 00:18:50

踩

lru算法

LRU算法

哈希链表
自己的JAVA实现

LRU全称Least Recently Used，也就是 最近最少使用的意思，是一种内存管理算法，该算法最早应用于Linux操作系统。

这个算法基于一种假设：长期不被使用的数据，在未来被用到的几率也不大。因此，当数据所占内存达到一定阈值时，我们要移除掉最近最少被使用的数据。

在LRU算法中，使用了哈希链表。

哈希链表

哈希表是由若干个Key-Value组成的。在“逻辑”上，这些Key-Value是无所谓排列顺序的，谁先谁后都一样。

在哈希链表中，这些Key-Value不再是彼此无关的存在，而是被一个链条串了
起来。每一个Key-Value都具有它的前驱Key-Value、后继Key-Value，就像双向
链表中的节点一样。

在这里插入图片描述

原本无序的哈希表就拥有了固定的排列顺序
依靠哈希链表的有序性，我们可以把Key-Value按照最后的使用时间进行排序

将新插入的或者刚被访问的数据插入到链表的最右端
左端就是最近最少被访问的数据

假设这时缓存容量已经达到上限，必须先删除最近最少被访问的数据，那么位于哈希链表最左端的数据就会被删除，然后再把新数据插入最右端的位置。

LinkedHashMap已经实现了哈希链表

自己的JAVA实现

在这里插入图片描述

可以把LRU算法代码的构建类比为后端分层模型:持久层（Dao层）、业务层（Service层）、Servlet层

最底层就是链表
中间层就是用哈希map包装了链表操作(用哈希map的value存链表node)
最上层就是加上了LRU算法逻辑

定义链表节点

//链表节点
    class Node{
        public Node pre;
        public Node next;
        public String key;
        public String value;

        public Node(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

最底层

/**
     * 删除链表中任意位置的节点
     * @param node  要删除的节点
     * @return
     */
    private String removeNode(Node node){
        if(node==head&&node==end){
            //链表只有一个元素，移除唯一的节点
            //头指针和尾指针都置空
            head=null;
            end=null;
        }else if(node==end){
            //移除尾节点
            end = end.pre;//尾指针前移一位
            end.next=null;
        }else if(node==head){
            //移除头节点
            head = head.next;//头指针后移一位
            head.pre = null;
        }else {
            //移除中间节点
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        //将删除节点的key返回
        return node.key;
    }

    /**
     * 尾部插入节点
     * LRU算法每次都只能在尾部插入节点
     * 链表头部表示：最近最少使用的节点
     * @param node  要插入的节点
     */
    private void addNode(Node node){
        if(end!=null){
            //链表有元素，则插入到end指针指向的元素后面
            end.next = node;
            node.pre = end;
            node.next = null;
        }
        //尾指针后移
        //不管之前链表有没有元素，node插入都将是链表最后一个元素
        end=node;
        if(head==null){
            //说明在没插入node之前是空链表
            //插入后只有node一个元素
            //node既是头也是尾
            head=node;
        }
    }

    /**
     * 刷新被访问的节点位置(就是再次访问链表中已经存在的元素,将他们放到链表尾)
     * @param node 被访问的节点
     *             这里Node node都是引用（node就是指针，指向node的指针）
     *             node和end,pre都是引用（指针)
     */
    private void refreshNode(Node node){
        if(node==end){
            //访问的是尾节点，无需移动节点
            return;
        }
        //走到这一步都得把node指向的节点移动到链表尾
        //先删除这个节点
        removeNode(node);
        //在插入到尾部(尾插)
        addNode(node);
    }
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

中间层

//中间层***********

    /**
     * 从哈希map链表中删除key对应的value
     * 注意看传入参数
     * 其实本质就是链表指定位置的删除
     * 在外面套了一层哈希map的皮
     * @param key
     */
    public void remove(String key){
        Node node =hashMap.get(key);
        removeNode(node);//链表中删除
        hashMap.remove(key);//哈希map中删除
    }

    /**
     * 从哈希map链表中添加key对应的value
     *  注意看传入参数
     *  其实本质就是链表尾插
     *  在外面套了一层哈希map的皮
     * @param key
     * @param value
     */
    public void add(String key,String value){
        //新建链表节点
        Node node =new Node(key,value);//value本质保存到node中了
        addNode(node);//链表尾插
        hashMap.put(key,node);//哈希map中添加
    }
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

最上层

/**
     * 将key和value存入哈希map链表中..
     * 注意这里key和value都是String类型
     * 我们定义的：private HashMap<String,Node> hashMap;
     * @param key
     * @param value
     */
    public void put(String key,String value){
        //获取HashMap中对应key值的valus
        //在LRU算法中，如果key对应的value不存在，则在链表末尾插入
        //如果key对应的value存在，则将该元素取出放到链表的末尾
        Node node = hashMap.get(key);

        //如果Key 不存在，则在末尾插入Key-Value
        if(node==null){
            //哈希mao链表超过长度，移除头节点
            if(hashMap.size()>=limit){
                //头节点是最近最少使用的，移除
                String oldKey = removeNode(head);
                hashMap.remove(oldKey);
            }
            add(key,value);
        }else {
            //如果Key 存在，则刷新Key-Value(将其放入链表末尾)
            node.value = value;//更新值
            refreshNode(node);
        }
    }

    public String get(String key){
        Node node = hashMap.get(key);
        //没有存对应的key和value
        if(node==null){
            String a="哈希链表没有 "+key+" 和与之对应的value";
            return a;
        }
        refreshNode(node);//将刚访问的节点放到链表末尾
        return node.value;
    }
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

测试方法：

public static void main(String[] args) {
        myLinkHashMap myLinkHashMap = new myLinkHashMap(4);
        myLinkHashMap.put("1","小红");
        myLinkHashMap.put("2","小明");
        myLinkHashMap.put("3","小强");
        System.out.println(myLinkHashMap.get("2"));
        System.out.println(myLinkHashMap.get("4"));
        myLinkHashMap.put("4","王丽");
        System.out.println(myLinkHashMap.get("4"));
        myLinkHashMap.put("5","小刚");
        System.out.println(myLinkHashMap.get("1"));
    }
1
2
3
4
5
6
7
8
9
10
11
12

在这里插入图片描述
可以看到，最近最少被使用的key="1"被LRU算法删除了。

完整代码：

package practice;

import java.util.HashMap;

public class myLinkHashMap {
    //链表节点
    class Node{
        public Node pre;
        public Node next;
        public String key;
        public String value;

        public Node(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }
    private Node head;//头指针
    private Node end;//尾指针
    private int limit;//最大存储的链表节点数目(缓存存储上限)

    //注意这里的value是Node类型的
    //虽然用HashMap(无序的)存储的,但value是node类型，通过指针就把不同的value串联起来了
    private HashMap<String,Node> hashMap;

    public myLinkHashMap(int limit){
        this.limit = limit;
        hashMap = new HashMap<String,Node>();
    }

    //最底层************
    /**
     * 删除链表中任意位置的节点
     * @param node  要删除的节点
     * @return
     */
    private String removeNode(Node node){
        if(node==head&&node==end){
            //链表只有一个元素，移除唯一的节点
            //头指针和尾指针都置空
            head=null;
            end=null;
        }else if(node==end){
            //移除尾节点
            end = end.pre;//尾指针前移一位
            end.next=null;
        }else if(node==head){
            //移除头节点
            head = head.next;//头指针后移一位
            head.pre = null;
        }else {
            //移除中间节点
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        //将删除节点的key返回
        return node.key;
    }

    /**
     * 尾部插入节点
     * LRU算法每次都只能在尾部插入节点
     * 链表头部表示：最近最少使用的节点
     * @param node  要插入的节点
     */
    private void addNode(Node node){
        if(end!=null){
            //链表有元素，则插入到end指针指向的元素后面
            end.next = node;
            node.pre = end;
            node.next = null;
        }
        //尾指针后移
        //不管之前链表有没有元素，node插入都将是链表最后一个元素
        end=node;
        if(head==null){
            //说明在没插入node之前是空链表
            //插入后只有node一个元素
            //node既是头也是尾
            head=node;
        }
    }

    /**
     * 刷新被访问的节点位置(就是再次访问链表中已经存在的元素,将他们放到链表尾)
     * @param node 被访问的节点
     *             这里Node node都是引用（node就是指针，指向node的指针）
     *             node和end,pre都是引用（指针)
     */
    private void refreshNode(Node node){
        if(node==end){
            //访问的是尾节点，无需移动节点
            return;
        }
        //走到这一步都得把node指向的节点移动到链表尾
        //先删除这个节点
        removeNode(node);
        //在插入到尾部(尾插)
        addNode(node);
    }

    //中间层***********

    /**
     * 从哈希map链表中删除key对应的value
     * 注意看传入参数
     * 其实本质就是链表指定位置的删除
     * 在外面套了一层哈希map的皮
     * @param key
     */
    public void remove(String key){
        Node node =hashMap.get(key);
        removeNode(node);//链表中删除
        hashMap.remove(key);//哈希map中删除
    }

    /**
     * 从哈希map链表中添加key对应的value
     *  注意看传入参数
     *  其实本质就是链表尾插
     *  在外面套了一层哈希map的皮
     * @param key
     * @param value
     */
    public void add(String key,String value){
        //新建链表节点
        Node node =new Node(key,value);//value本质保存到node中了
        addNode(node);//链表尾插
        hashMap.put(key,node);//哈希map中添加
    }

    //最上层****************

    /**
     * 将key和value存入哈希map链表中..
     * 注意这里key和value都是String类型
     * 我们定义的：private HashMap<String,Node> hashMap;
     * @param key
     * @param value
     */
    public void put(String key,String value){
        //获取HashMap中对应key值的valus
        //在LRU算法中，如果key对应的value不存在，则在链表末尾插入
        //如果key对应的value存在，则将该元素取出放到链表的末尾
        Node node = hashMap.get(key);

        //如果Key 不存在，则在末尾插入Key-Value
        if(node==null){
            //哈希mao链表超过长度，移除头节点
            if(hashMap.size()>=limit){
                //头节点是最近最少使用的，移除
                String oldKey = removeNode(head);
                hashMap.remove(oldKey);
            }
            add(key,value);
        }else {
            //如果Key 存在，则刷新Key-Value(将其放入链表末尾)
            node.value = value;//更新值
            refreshNode(node);
        }
    }

    public String get(String key){
        Node node = hashMap.get(key);
        //没有存对应的key和value
        if(node==null){
            String a="哈希链表没有 "+key+" 和与之对应的value";
            return a;
        }
        refreshNode(node);//将刚访问的节点放到链表末尾
        return node.value;
    }

    public static void main(String[] args) {
        myLinkHashMap myLinkHashMap = new myLinkHashMap(4);
        myLinkHashMap.put("1","小红");
        myLinkHashMap.put("2","小明");
        myLinkHashMap.put("3","小强");
        System.out.println(myLinkHashMap.get("2"));
        System.out.println(myLinkHashMap.get("4"));
        myLinkHashMap.put("4","王丽");
        System.out.println(myLinkHashMap.get("4"));
        myLinkHashMap.put("5","小刚");
        System.out.println(myLinkHashMap.get("1"));
    }

}

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/575696