原文链接:http://quentinXXZ.iteye.com/blog/2176345
1、Cache
Cache对于代码系统的加速与优化具有极大的作用,对于码农来说是一个很熟悉的概念。可以说,你在内存中new 了一个一段空间(比方说数组,list)存放一些冗余的结果数据,并利用这些数据完成了以空间换时间的优化目的,你就已经使用了cache。
有服务级的缓存框架,如memcache, redis等。其实,很多时候,我们在自己同一个服务内,或者单个进程内也需要缓存,例如,lucene就对搜索做了缓存,而无须依赖外界。那么,我们如何实现我们自己的缓存?还要带自动失效的,最好还是LRU(Least Recently Used)。
当你思考怎么去实现,你可能会想得很远。为了LRU,需要把刚使用的数据存入栈,或者纪录每个数据最近使用的时间,再来的定时扫描失效的线程….其实,java本身就已经为我们提供了LRU Cache很好的实现,即LinkedHashMap。
2、LinkedHashMap分析
很多没有去细究过其内部实现的人,只是将其当作一个普通的hashMap来对待。LinkedHashMap是一个双向链表,加上hashTable的实现。表现出来与普通HashMap的一个区别就是LinkedHashMap会记录存入其中的数据的顺序,并能按顺取出。
为了实现,一个hash表,自然应该先申请在一片连续的内存空间上。当需要存入数据的时候,根据相应的hash值存入。而LinkedHashMap在这个基础上,为每个entry设置了before与after属性,形了一个双向链表,记录了他们put进入的前后顺序。
不仅如此,当get每个元素后,它就会通过afterNodeAccess方法来调整链表的指向:
void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.Entry<K,V> last; if (accessOrder && (last = tail) != e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.after = null; if (b == null) head = a; else b.after = a; if (a != null) a.before = b; else last = b; if (last == null) head = p; else { p.before = last; last.after = p; } tail = p; ++modCount; } }
上述代码将Node e移至了双向链表的未尾。而在方法afterNodeInsertion中,只要满足条件,便移除最老的数据,即链表的head。
void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry<K,V> first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } }
可见,当你为linkedHashMap设置有限空间的时候,自然便完成了LRU Cache的效果。当然还有一个前提,你必须重写一个方法removeEldestEntry,返回true。表示空间已满时,删除最老的。
@Override public boolean removeEldestEntry(Map.Entry<K, V> eldest){ return size()>capacity; }
3、线程安全的LRU Cache
如此,我们就获得了一个LRU缓存利器,满足了我们大多场景下的需求。但还有一个问题,它不是线程安全的。在多线程的情况下,你有可能需要对某些Cache做同步处理。这时候,你再找,可以看到java有ConcurrentHashMap的实现,但并不存在ConcurrentLinkedHashMap这样的类。
当然这个问题也不大,我们可以对再有的LinkedHashMap,再作封装,对get,put, 之类的方法加上同步操作。
目前,我们所用的处理,是直接采和google提供的guava包,这里面就提供了我们想要的ConcurrentLinkedHashMap。这样就可以很方便地实现一个线程安全。具体代码如下:
import java.util.Set; import com.googlecode.concurrentlinkedhashmap.Weighers; import com.googlecode.concurrentlinkedhashmap.ConcurrentLinkedHashMap; public class ConcurrentLRUCache<K, V> { public static final int DEFAULT_CONCURENCY_LEVEL = 32; private final ConcurrentLinkedHashMap<K, V> map; public ConcurrentLRUCache(int capacity) { this(capacity, DEFAULT_CONCURENCY_LEVEL); } public ConcurrentLRUCache(int capacity, int concurrency) { map = new ConcurrentLinkedHashMap.Builder<K, V>().weigher(Weighers.<V> singleton()) .initialCapacity(capacity).maximumWeightedCapacity(capacity) .concurrencyLevel(concurrency).build(); } public void put(K key, V value) { map.put(key, value); } public V get(K key) { V v = map.get(key); return v; } public V getInternal(K key) { return map.get(key); } public void remove(K key) { map.remove(key); } public long getCapacity() { return map.capacity(); } public void updateCapacity(int capacity) { map.setCapacity(capacity); } public int getSize() { return map.size(); } public void clear() { map.clear(); } public Set<K> getKeySet() { return map.keySet(); } }
原文链接:http://quentinXXZ.iteye.com/blog/2176345
相关推荐
主要介绍了详解Java实现LRU缓存,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
主要介绍了Java实现LRU缓存的实例详解的相关资料,这里提供实例帮助大家理解掌握这部分内容,需要的朋友可以参考下
主要介绍了Java实现简单LRU缓存机制的方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
这里的LRUCache类维护了一个双向链表和一个哈希表,用于实现LRU算法。具体实现细节如下: - get方法:首先在哈希表中查找对应的键值对,如果不存在,则返回-1;如果存在,则将对应的节点从双向链表中删除,并将其...
java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例
Java利用ConcurrentHashMap实现本地缓存demo; 基本功能有缓存有效期、缓存最大数、缓存存入记录、清理线程、过期算法删除缓存、LRU算法删除、获取缓存值等功能。 复制到本地项目的时候,记得改包路径哦~
Android提供了LRUCache类,可以方便的使用它来实现LRU算法的缓存。Java提供了LinkedHashMap,可以用该类很方便的实现LRU算法,Java的LRULinkedHashMap是直接继承了LinkedHashMap,进行了极少的改动后可以实现LRU...
主要介绍了浅谈Java如何实现一个基于LRU时间复杂度为O(1)的缓存,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
缓存 在 Java 中实现 LRU 缓存
Android提供了LRUCache类,可以方便的使用它来实现LRU算法的缓存。Java提供了LinkedHashMap,可以用该类很方便的实现LRU算法,Java的LRULinkedHashMap就是直接继承了LinkedHashMap,进行了极少的改动后就可以实现LRU...
LRU 缓存机制(java代码).docx
LRU缓存HashMap+双向链表实现,java版本,导入即用
LRU缓存 Java 中最近最少使用 (LRU) 缓存。 测试 mvn test ------------------------------------------------------- T E S T S ------------------------------------------------------- Running ...
缓存淘汰算法之LRU
缓存——LRU Java 缓存描述快速 灵活 高效的内存 LRU Java 缓存 该存储库包含的来源。 巴拉克。 示例用法: Cache< String> fileContentCache = new Cache<> (key - > readFileContent( new File (key)),...
用Java写的一个Cache,内部实现了LRU算法~
缓存 LeetCode 问题 146 LRU Cache in Java 我很喜欢这个问题。 我在康奈尔大学的第一个 CS 课程涉及队列和其他数据结构。 对于其中一个课堂项目,我们必须开发基于队列的模拟。 在工作中,我开发了广泛的队列库。 ...
NULL 博文链接:https://jimi68.iteye.com/blog/440892