Java基础---手写LRU算法_java手写lru

一. 巧用LinkedHashMap完成LRU算法

package com.xizi.LRU;


import java.util.LinkedHashMap;
import java.util.Map;

//使用LinkedHashMap实现LRU
public class LRU<K,V> extends LinkedHashMap<K, V> implements Map<K, V> {

    private static final long serialVersionUID = 1L;

    public LRU(int initialCapacity, float loadFactor, boolean accessOrder) {
        //直接调用父类的构造方法
        super(initialCapacity, loadFactor, accessOrder);
    }

    //重写LinkedHashMap中的removeEldestEntry方法，当LRU中元素多余6个时，删除最不经常使用的元素
    @Override
    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
        if(size() > 6){
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        LRU<Character, Integer> lru = new LRU<>(16, 0.75f, true);
        String s = "abcdefghijkl";
        for (int i = 0; i < s.length(); i++) {
            lru.put(s.charAt(i), i);
        }
        System.out.println("LRU中key为h的Entry的值为： " + lru.get('h'));
        System.out.println("LRU的大小 ：" + lru.size());
        System.out.println("LRU ：" + lru);
    }
}


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

二. 哈希表 + 双向链表

package com.xizi.LRU;

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

class LRUCache2{
	class Node<K, V>{//双向链表节点
		K key;
		V value;
		Node<K, V> prev;
		Node<K, V> next;
		
		public Node() {
			this.prev = this.next = null;
		}
		public Node(K key, V value) {
			super();
			this.key = key;
			this.value = value;
		}
	}
	
    //新的插入头部，旧的从尾部移除
	class DoublyLinkedList<K, V>{
		Node<K, V> head;
		Node<K, V> tail;
		
		public DoublyLinkedList() {
            //头尾哨兵节点
			this.head = new Node<K, V>();
			this.tail = new Node<K, V>();
			this.head.next = this.tail;
			this.tail.prev = this.head;
		}
		
		public void addHead(Node<K, V> node) {
			node.next = this.head.next;
			node.prev = this.head;
			this.head.next.prev = node;
			this.head.next = node;
		}
		
		public void removeNode(Node<K, V> node) {
			node.prev.next = node.next;
			node.next.prev = node.prev;
			node.prev = null;
			node.next = null;

		}
		
		public Node<K, V> getLast() {
			if(this.tail.prev == this.head)
				return null;
			return this.tail.prev;
		}

	}
	
	private int cacheSize;
	private Map<Integer, Node<Integer, Integer>> map;
	private DoublyLinkedList<Integer, Integer> doublyLinkedList;
	
	
	public LRUCache2(int cacheSize) {
		this.cacheSize = cacheSize;
		map = new HashMap<>();
		doublyLinkedList = new DoublyLinkedList<>();
	}

	public int get(int key) {
		if(!map.containsKey(key)) {
			return -1;
		}
		
		Node<Integer, Integer> node = map.get(key);
        
        //更新节点位置，将节点移置链表头
		doublyLinkedList.removeNode(node);
		doublyLinkedList.addHead(node);
		
		return node.value;
	}
	
	public void put(int key, int value) {
		
		if(map.containsKey(key)) {
			
			Node<Integer, Integer> node = map.get(key);
			node.value = value;
			map.put(key, node);
			
            
			doublyLinkedList.removeNode(node);
			doublyLinkedList.addHead(node);
		}else {
			if(map.size() == cacheSize) {//已达到最大容量了，把旧的移除，让新的进来
				Node<Integer, Integer> lastNode = doublyLinkedList.getLast();
				map.remove(lastNode.key);//node.key主要用处，反向连接map
				doublyLinkedList.removeNode(lastNode);
			}
			
			Node<Integer, Integer> newNode = new Node<>(key, value);
			map.put(key, newNode);
			doublyLinkedList.addHead(newNode);
		}
	}	
}
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