剖析LRU算法及LinkedHashMap源码实现机制

本文主要是介绍剖析LRU算法及LinkedHashMap源码实现机制，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、简述

LRU（Least Recently Used），注意L代表的不是Latest，翻译成中文通常叫：近期最少使用算法、最近最少使用算法。LRU与LFU（Least Frequently Used）、FIFO（First In First Out）是3种常用的缓存算法（页面置换算法）。缓存算法的应用场景有很多，例如操作系统在物理内存不足时触发的磁盘交换、CPU中L1、L2、L3缓存淘汰替换、超市中畅销货品在货架的摆放位置优化等。缓存算法的实现和变种也有很多，这里只针对LRU算法抛砖引玉。

二、算法原理

缓存算法的根本目的，是淘汰掉“最不常用”的元素。LRU算法淘汰的是截止当前缓存区中最久没有被访问过的元素，这意味着“最后一次访问时间”是LRU算法决定是否淘汰元素的唯一标准。

因此，假设我们记录下每个元素最后一次被访问的时间戳，并按照此时间戳早晚进行排序，那么，时间最早的元素应该被淘汰掉（如图1）。所以，将LRU准确地翻译成中文，应该是：距今最久未用淘汰算法。

图1：最后一次访问时间最早的元素首先被淘汰

这里补充一点，LRU算法并不是绝对公平的。举个例子，假如某个元素仅仅在淘汰执行前被访问了1次，在之前的数百万次的请求中从未被访问，按照LRU的算法逻辑，它仍然会留存下来，这其实无法准确描述“是否常用”这一特性。“是否常用”其实在不同的业务场景有不同的定义，大家可以细细体会。

三、LRU的实现机制

依照LRU算法原理，其实现机制并不复杂，仅仅需要根据元素的最后一次访问时间排序即可。但当运用在1个生产环境的缓存系统中时，会面临以下几个工程问题：

在缓存访问频次极高的情况下，时间戳即使精确到纳秒，依然存在大量的相同时间戳，排序无效。若采用递增ID替代时间戳，则存在溢出的风险。
每次进行缓存淘汰时，都需要将缓存区所有元素进行排序。当元素数极多时，缓存系统的性能将急剧下降，CPU耗费极高。
在元素本身占用内存不大的情况下，附加的“时间戳/自增ID”甚至在内存占用上喧宾夺主。

最佳的实现思路是利用链表的有序特性，将缓存元素的“按最后一次访问时间戳排序”巧妙地转换为其在链表中的相对顺序。因为LRU算法关心的并不是元素的绝对访问时间，而是元素被访问的先后顺序。即：元素被命中时，移到链表头。执行淘汰时，从链表尾开始淘汰。因此，LRU算法实现的核心数据结构是：循环链表。

但对于一个<K,V>缓存系统而言，仅有链表结构是不够的。链表虽然解决了缓存淘汰问题，但缓存访问却需要每次都从链表头开始遍历。JDK中的java.util.LinkedHashMap给出了最佳的实现（链表也是Linked这一前缀的由来），同时解决了元素的快速访问与缓存淘汰问题。

四、JDK中LinkedHashMap对LRU的实现源码分析

1、概述

从Oracle的JDK源码的注释中可以看到，从JDK1.4开始，Josh Bloch就提供了LinkedHashMap供开发者使用。LinkedHashMap继承自HashMap，拥有<K,V>结构的同时还提供了缓存淘汰的扩展。

 
Java
  
 1 
2 
3 
  protected   boolean   removeEldestEntry ( Map . Entry < K , V >   eldest )   { 
  return   false ; 
  }

2、LinkedHashMap的使用示例（LRU效果）

Java
  
 1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
 public   static   void   main ( String [ ]   args )   { 
  Map < String ,   String >   map   =   new   LinkedHashMap < String ,   String > ( 16 , 0.75f , true ) ; 
  map . put ( "1" ,   "a" ) ; 
  map . put ( "2" ,   "b" ) ; 
  map . put ( "3" ,   "c" ) ; 
  map . put ( "4" ,   "e" ) ; 
  for   ( Iterator <String>   iterator   =   map . values ( ) . iterator ( ) ;   iterator 
  . hasNext ( ) ; )   { 
  String   name   =   ( String )   iterator . next ( ) ; 
  System . out . print ( name ) ; 
  } 
  } 
 

上面的代码打印结果为：abce，很正常，按照加入的顺序打印

 
 
 
 
 
Java
  
 1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
 public   static   void   main ( String [ ]   args )   { 
  Map < String ,   String >   map   =   new   LinkedHashMap < String ,   String > ( 16 , 0.75f , true ) ; 
  map . put ( "1" ,   "a" ) ; 
  map . put ( "2" ,   "b" ) ; 
  map . put ( "3" ,   "c" ) ; 
  map . put ( "4" ,   "e" ) ; 
  map . get ( "1" ) ; 
  map . get ( "2" ) ; 
  for   ( Iterator <String>   iterator   =   map . values ( ) . iterator ( ) ;   iterator 
  . hasNext ( ) ; )   { 
  String   name   =   ( String )   iterator . next ( ) ; 
  System . out . print ( name ) ; 
  } 
  } 
 

打印结果为：ceab ，可以看出LinkedHashMap构造参数中的“true”启用了其内部的LRU 特性。

3、利用LinkedHashMap的LRU特性，构造固定容量缓存系统

Java
  
 1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
 public   class   FixedSizeCacheMap < K ,   V >   extends   LinkedHashMap < K ,   V >   { 
 private   final   int   fixSize ; 
 public   FixedSizeCacheMap ( int   fixSize )   { 
 super ( fixSize ,   0.75f ,   true ) ; 
 this . fixSize   =   fixSize ; 
 } 
 @Override 
 protected   boolean   removeEldestEntry ( Map . Entry < K ,   V >   eldest )   { 
 return   size ( )   >   fixSize ; 
 } 
 } 
 

说明：上述代码中FixedSizeCahceMap构造参数中的fixSize指定了缓存的最大元素个数。removeEldestEntry方法重写了LinkedHashMap中关于判断是否删除“最久未用元素”的逻辑，“return size() > fixSize”表明，当缓存中的元素数达到fixSize时，将eldest元素淘汰掉。

4、LinkedHashMap实现源码分析

上文提到LinkedHashMap继承自HashMap，其主要目的是充分利用HashMap现有的<K,V>数据结构，在此基础上通过Override一些关键方法，将<K,V>结构与循环链表结构完美结合运用。被Override的几个关键点：

（1）定义链表的节点

 
 
 
 
 
Java
  
 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 
   private   static   class   Entry < K , V >   extends   HashMap . Entry < K , V >   { 
  // 用于记录链表节点的前后节点 
  Entry < K , V >   before ,   after ; 
  Entry ( int   hash ,   K   key ,   V   value ,   HashMap . Entry < K , V >   next )   { 
  super ( hash ,   key ,   value ,   next ) ; 
  } 
  //从链表中摘除本节点 
  private   void   remove ( )   { 
  before . after   =   after ; 
  after . before   =   before ; 
  } 
  //将本节点插入到指定节点的前面 
  private   void   addBefore ( Entry < K , V >   existingEntry )   { 
  after    =   existingEntry ; 
  before   =   existingEntry . before ; 
  before . after   =   this ; 
  after . before   =   this ; 
  } 
         //本节点的元素被命中访问时，将本节点移动到链表头 
  void   recordAccess ( HashMap < K , V >   m )   { 
  LinkedHashMap < K , V >   lm   =   ( LinkedHashMap < K , V > ) m ; 
  if   ( lm . accessOrder )   { 
  lm . modCount ++ ; 
  remove ( ) ; 
  addBefore ( lm . header ) ; 
  } 
  } 
  } 
 

（2）LinkedHashMap初始化时，建立循环链表

Java
  
 1 
2 
3 
4 
 void   init ( )   { 
  header   =   new   Entry <> ( - 1 ,   null ,   null ,   null ) ; 
  header . before   =   header . after   =   header ; 
 } 
 

（3）向缓存中添加元素时的重写

 
 
 
 
 
Java
  
 1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
   void   addEntry ( int   hash ,   K   key ,   V   value ,   int   bucketIndex )   { 
  
          super . addEntry ( hash ,   key ,   value ,   bucketIndex ) ; 
  //每当添加新元素时，判断是否执行LRU淘汰 
  Entry < K , V >   eldest   =   header . after ; 
  if   ( removeEldestEntry ( eldest ) )   { 
  removeEntryForKey ( eldest . key ) ; 
  } 
  } 
  //上述的super.addEntry会调用这里的createEntry，LinkedHashMap将其Override使得Map中存储的Entry都是（1）中定义的新Entry，同时把新元素置于链表头 
  void   createEntry ( int   hash ,   K   key ,   V   value ,   int   bucketIndex )   { 
  HashMap . Entry < K , V >   old   =   table [ bucketIndex ] ; 
  Entry < K , V >   e   =   new   Entry <> ( hash ,   key ,   value ,   old ) ; 
  table [ bucketIndex ]   =   e ; 
  e . addBefore ( header ) ; 
  size ++ ; 
  } 
 

（4）缓存命中时的方法重写

Java
  
 1 
2 
3 
4 
5 
6 
7 
  public   V   get ( Object   key )   { 
  Entry < K , V >   e   =   ( Entry < K , V > ) getEntry ( key ) ; 
  if   ( e   ==   null ) 
  return   null ; 
  e . recordAccess ( this ) ; //参考（1）中Entry定义的recordAccess方法，实际是LRU算法中的节点命中移动到链表头 
  return   e . value ; 
  } 
 