欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-10 19:14:52
...

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

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

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

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


使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 

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

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


使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 

我们再来看一下AbstractMap的签名


使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 

AbstractMap本身也实现了Map接口

但为什么HashMapLinkedHashMap还要实现这个接口呢

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


使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 

 

回复如下


使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 

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

 

设计原理

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

 


使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 

 

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

 


使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 
使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 

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

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


使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 

 

访问顺序

LinkedHashMap提供了两种Key的顺序

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

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

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

 


使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 

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

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


使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 

通过源码我们可以看到

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


使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 

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

 


使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 

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

 

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

 

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


使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 

就这么简单。

 

测试代码如下:

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


使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 

 

运行结果


使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 

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



使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 
 

运行结果


使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 

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


使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 

运行结果

 

使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
 

  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 9.9 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 14.8 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 7 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 283 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 78.9 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 6.5 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 12.8 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 42 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 33.3 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 8.9 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 34.6 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 70.5 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 70 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 101.5 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 78.7 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 66.2 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 78.6 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 172 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 78.6 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 79.1 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 80.2 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 101.9 KB
  • 使用LinkedHashMap实现Cache的方法与原理
            
    
    博客分类: JAVA javaLinkedHashMapcache缓存LRU 
  • 大小: 174.7 KB