1+ // 146. LRU 缓存
2+
3+
4+ /**
5+ * Your LRUCache object will be instantiated and called as such:
6+ * LRUCache obj = new LRUCache(capacity);
7+ * int param_1 = obj.get(key);
8+ * obj.put(key,value);
9+ */
10+
11+
12+ /*
13+ 1、LRU：最近最久未使用，缓存淘汰算法
14+ 2、LinkedHashMap 哈希链表 = 双向链表 + 哈希表
15+ 1）哈希表：查找快，但是无序
16+ 2）链表：有序，插入、删除快，但是查找慢
17+ */
18+
19+
20+ // 使用Java的API LinkedHashMap
21+ class LRUCache extends LinkedHashMap <Integer , Integer > {
22+
23+ private int capacity ;
24+
25+ public LRUCache (int capacity ) {
26+ super (capacity , 0.75F , true );
27+ this .capacity = capacity ;
28+ }
29+
30+ public int get (int key ) {
31+ return super .getOrDefault (key , -1 );
32+ }
33+
34+ public void put (int key , int value ) {
35+ super .put (key , value );
36+ }
37+
38+ // 删除最近最久未使用节点
39+ @ Override
40+ protected boolean removeEldestEntry (Map .Entry <Integer , Integer > entry ) {
41+ return size () > capacity ;
42+ }
43+ }
44+
45+
46+ /*
47+ LRUCache类，即手动实现哈希链表、缓存淘汰机制：
48+ 1、定义 双向链表节点内部类，包含 公有成员变量“键、值、前驱节点、后驱节点”、构造方法
49+ 2、定义 私有成员变量“HashMap缓存、链表大小、链表容量、链表头尾哨兵节点”
50+ 3、定义 公有构造方法，初始化成员变量
51+ 4、定义 私有方法，处理链表节点，添加节点到头部、删除节点、移动节点到头部、删除尾部节点
52+ 5、实现获取节点值
53+ 1）根据key从缓存中获取节点
54+ 2）如果节点不存在，返回-1
55+ 3）如果节点存在，当前被使用了，移动节点到头部
56+ 6、实现存入节点
57+ 1）根据key从缓存中获取节点
58+ 2）如果节点不存在
59+ ① 创建节点、添加节点到缓存、添加节点到头部、链表大小加1
60+ ② 判断链表大小是否超过链表容量，超过则 删除尾部节点、删除该节点缓存、链表大小减1
61+ 3）如果节点存在，更新节点值、移动节点到头部
62+ */
63+ class LRUCache {
64+ // 内部类，双向链表节点
65+ class DoubleLinkedNode {
66+ int key ;
67+ int value ;
68+ DoubleLinkedNode prev ;
69+ DoubleLinkedNode next ;
70+
71+ public DoubleLinkedNode () {}
72+
73+ public DoubleLinkedNode (int key , int value ) {
74+ this .key = key ;
75+ this .value = value ;
76+ }
77+ }
78+
79+ private Map <Integer , DoubleLinkedNode > cache = new HashMap <>(); // 缓存
80+ private int size ; // 大小
81+ private int capacity ; // 容量
82+ private DoubleLinkedNode head , tail ; // 头尾哨兵节点
83+
84+ public LRUCache (int capacity ) {
85+ this .size = 0 ;
86+ this .capacity = capacity ;
87+ this .head = new DoubleLinkedNode ();
88+ this .tail = new DoubleLinkedNode ();
89+ this .head .next = this .tail ;
90+ this .tail .prev = this .head ;
91+ }
92+
93+ // 获取节点值
94+ public int get (int key ) {
95+ DoubleLinkedNode node = cache .get (key );
96+ if (node == null ) {
97+ return -1 ;
98+ }
99+ moveToHead (node );
100+ return node .value ;
101+ }
102+
103+ // 存入节点
104+ public void put (int key , int value ) {
105+ DoubleLinkedNode node = cache .get (key );
106+ if (node == null ) {
107+ DoubleLinkedNode newNode = new DoubleLinkedNode (key , value );
108+ cache .put (key , newNode );
109+ addToHead (newNode );
110+ this .size ++;
111+ if (this .size > this .capacity ) {
112+ DoubleLinkedNode tailNode = removeTail ();
113+ cache .remove (tailNode .key );
114+ this .size --;
115+ }
116+ } else {
117+ node .value = value ;
118+ moveToHead (node );
119+ }
120+ }
121+
122+ // 添加节点到头部
123+ private void addToHead (DoubleLinkedNode node ) {
124+ node .prev = this .head ;
125+ node .next = this .head .next ;
126+ this .head .next .prev = node ;
127+ this .head .next = node ;
128+ }
129+
130+ // 删除节点
131+ private void removeNode (DoubleLinkedNode node ) {
132+ node .prev .next = node .next ;
133+ node .next .prev = node .prev ;
134+ }
135+
136+ // 移动节点到头部：删除节点、添加节点到头部
137+ private void moveToHead (DoubleLinkedNode node ) {
138+ removeNode (node );
139+ addToHead (node );
140+ }
141+
142+ // 删除尾部节点
143+ private DoubleLinkedNode removeTail () {
144+ DoubleLinkedNode node = this .tail .prev ;
145+ removeNode (node );
146+ return node ;
147+ }
148+ }
0 commit comments