使用LinkedHashMap实现Cache的方法与原理

使用LinkedHashMap实现Cache的方法与原理

基于LinkedHashMap的特性，可以实现一个简单的基于LRU算法的缓存功能。

首先大致介绍一下LinkedHashMap的特点。

通过LinkedHashMap的签名我们可以看出 LinkedHashMap是HashMap的一个子类，它根据自身的特点修改了某些某类的方法

 

在这里八卦一下这个签名，我们可以看到LinkedHashMap继承了HashMap并实现了Map接口。

我们再来看一下HashMap的签名，HashMap继承了AbstractMap 并实现了Map接口，

 

我们再来看一下AbstractMap的签名

 

AbstractMap本身也实现了Map接口

但为什么HashMap和LinkedHashMap还要实现这个接口呢

在*.网站找到了一个类似的帖子，只不过帖子问的是有关于WeakHashMap这个类的，但其道理是一样的

 

 

回复如下

 

大概意思是说只是为了生成javadoc会比较良好，其实在语法上是不需要的。

 

设计原理

LinkedHashMap我们都知道是基于双向链表的，如下图

 

 

 

但LinkedHashMap代源码中我们可以看出，他不仅是一个双向链表，而且是一个环型的双向链表

 

 

 

我们在源码可以看到LinkedHashMap的init方法覆盖了父类的方法

然而在HashMap类中init方法仅仅是一个空实现，为子类提供了一个勾子的作用

 

 

访问顺序

LinkedHashMap提供了两种Key的顺序

<!--[if !supportLists]-->l   <!--[endif]-->访问顺序

<!--[if !supportLists]-->l   <!--[endif]-->插入顺序

LinkedHashMap默认是插入顺序，这点我们在它的构造函数中可以看到

 

 

accessOrder就是访问顺序的意思，默认为false，即使用插入顺序

使用访问顺序的好处是，当我们使用get方法访问元素的时候，在访问过后，LinkedHashMap会将get的元素移到链表的尾部，这样链表的第一个元素总是最早被放入到链表中并且没有被访问过的元素，正好符合我们的LRU原则。

 

通过源码我们可以看到

LinkedHashMap并没有重写父类的put方法，

 

但是LinkedHashMap重新了父类put方法中的子方法addEntry方法

 

 

在addEntry方法中，我们看到了有一段代码，是否删除最老的一个元素。

 

按此推理，我们在实现缓存功能的时候，就需要重写removeEldestEntry方法，在添加元素的时候判断是否超过了缓存定义的容量。

 

按此方法，我在本地实现了一个简单的cache功能，代码如下

 

就这么简单。

 

测试代码如下：

1. 元素大小小于缓存容量

 

 

运行结果

 

2. 元素大小大于缓存容量

 
 

运行结果

 

3. 元素大小大于缓存容量,在缓存容量满之前对缓存数据进行访问

 

运行结果