大厂常见面试题LRU算法实现

• 要实现put和get的O(1)时间复杂度

• 最近最少/最久使用问题

• 将最近最少使用的数据淘汰

• LRU缓存是操作系统常见的页面缓存淘汰机制

• 实现方式：哈希表 + 双向链表

  • 哈希表用于存储数据，主要用于实现存取操作put和get的O(1)时间复杂度
  • 双向链表用于记录最近最少使用、最近最久未使用情况，主要是为了实现记录和删除记录操作的O(1)时间复杂度
    • 选择自定义实现双向链表，而不使用自带的双向链表
      • 自定义链表能更好的管控和访问每个节点数据

  

public class LRUCache {
  // 缓存的最大容量， 存储元素大于这个大小的时候将被优化删除掉
	private int capacity = 0;
  // map，主要用于存储已存储过的数据，以实现访问和添加的O(1)时间复杂度
	private Map<Integer, Node<Integer, Integer>> map = new HashMap<>();
  // 链表的虚拟头结点
	private Node<Integer, Integer> first;
  // 链表的虚拟尾节点
	private Node<Integer, Integer> last;
	
	
	public LRUCache(int capacity) {
		this.capacity = capacity;
		this.first = new Node<>();
		this.last = new Node<>();
		first.next = last;
		last.prev = first;
  }
    
    public int get(int key) {
      // 通过map获取，能实现O(1)时间复杂度
    	Node<Integer, Integer> node = map.get(key);
      // 如果不存在，则直接返回-1
    	if (node == null) return -1;
    	
      // 如果存在，则更新节点位置到头部
    	int v = node.value;
      removeNode(node);
      addAfterFirst(node);
      return v;
    }
    
    public void put(int key, int value) {
    	Node<Integer, Integer> node = map.get(key);
    	if (node != null) {
        // 如果已经存在此节点
        // 就移除当前节点，并在后续通过addAfterFirst方法更新新的元素
    		node.value = value;
    		removeNode(node);
    	} else {
        // 如果不存在此节点，则是新数据
    		if (map.size() == capacity) {
            // 如果当前存储数据已满，则移除链表中最后一个数据
        		removeNode(map.remove(last.prev.key));
        	}
        	
          // map中添加新的数据
        	node = new Node<>(key, value);
        	map.put(key, node);
    	}
    	
      // 添加新的数据到链表头
    	addAfterFirst(node);
    }
    
    // 删除节点
    private void removeNode(Node<Integer, Integer> node) {
    	node.prev.next = node.next;
    	node.next.prev = node.prev;
    }
    
    // 在头部添加节点
    private void addAfterFirst(Node<Integer, Integer> node) {
    	node.next = first.next;
    	first.next.prev = node;
    	node.prev = first;
    	first.next = node;
    }
    
    
    // 自定义链表的节点类
    private class Node<K, V> {
    	public K key;
    	public V value;
    	public Node<K, V> prev;
    	public Node<K, V> next;
    	
    	public Node(K key, V value) {
    		this.key = key;
    		this.value = value;
    	}
    	
    	public 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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85