算法之LRU和LFU算法

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
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;

public class LRUCache<K, V> {
    //存储的单位元素
    class CacheNode{
        Object key;
        Object value;
        CacheNode pre;//用于构造双向链表
        CacheNode next;
        public CacheNode(Object key，Object value){
            this.key = key;
            this.value = value;
        }
        public CacheNode(){
        }
    }
    private int currentCacheSize;//当前容量
    private int CacheCapcity;//最大容量
    private HashMap<K,CacheNode> caches;
    private CacheNode first;//指向链表头结点
    private CacheNode last;//指向链表尾节点

    public LRUCache(int size){
        currentCacheSize = 0;
        this.CacheCapcity = size;
        caches = new HashMap<K,CacheNode>(size);
    }
    //添加新的节点时，放入链表头部
    public void put(K k,V v){
        CacheNode node = caches.get(k);
        if(node == null){
            if(caches.size() >= CacheCapcity){
                removeLast();
                caches.remove(last.key);
            }
            node = new CacheNode(k,v);
            caches.put(k, node);
            InsetToFirst(node);
        }else{
            moveToFirst(node);
        }
        currentCacheSize = caches.size();
    }
    //访问某个元素
    public Object  get(K k){
        CacheNode node = caches.get(k);
        if(node == null){
            return null;
        }
        moveToFirst(node);
        return node.value;
    }
    //将链表中的某个元素移到链表头部
    private void moveToFirst(CacheNode node){
        CacheNode prenode = node.pre;
        CacheNode nextnode = node.next;
        if(prenode == null && nextnode == null){
            return;
        }else if(nextnode == null){
            InsetToFirst(node);
            return;
        }else if(prenode == null){
            return;
        }else{
            prenode.next = nextnode;
            nextnode.pre = prenode;
            InsetToFirst(node);
        }
    }
    //插入某个元素到链表头部
    private void InsetToFirst(CacheNode node){
        if(first == null || last == null){
            first = node;
            last = node;
        }else{
        node.next = first;
        first.pre = node;
        }
    }
    //删除某个尾节点元素
    private void removeLast(){
        if(last != null){
            last = last.pre;
            if(last == null){
                first = null;
            }else{
                last.next = null;
            }
        }
    }
     //清空所有元素
    public void clear(){
        first = null;
        last = null;
        caches.clear();
    }
    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        CacheNode node = first;
        while(node != null){
            sb.append(String.format("%s:%s ", node.key,node.value));
            node = node.next;
        }

        return sb.toString();
    }
    public static void main(String[] args) {
        LRUCache<Integer,String> lru = new LRUCache<Integer,String>(3);

        lru.put(1, "a");    // 1:a
        System.out.println(lru.toString());
        lru.put(2, "b");    // 2:b 1:a 
        System.out.println(lru.toString());
        lru.put(3, "c");    // 3:c 2:b 1:a 
        System.out.println(lru.toString());
        lru.put(4, "d");    // 4:d 3:c 2:b  
        System.out.println(lru.toString());
    }
}