引子:
我们平时总会有一个电话本记录所有朋友的电话,但是,如果有朋友经常联系,那些朋友的电话号码不用翻电话本我们也能记住,但是,如果长时间没有联系了,要再次联系那位朋友的时候,我们又不得不求助电话本,但是,通过电话本查找还是很费时间的。但是,我们大脑能够记住的东西是一定的,我们只能记住自己最熟悉的,而长时间不熟悉的自然就忘记了。
其实,计算机也用到了同样的一个概念,我们用缓存来存放以前读取的数据,而不是直接丢掉,这样,再次读取的时候,可以直接在缓存里面取,而不用再重新查找一遍,这样系统的反应能力会有很大提高。但是,当我们读取的个数特别大的时候,我们不可能把所有已经读取的数据都放在缓存里,毕竟内存大小是一定的,我们一般把最近常读取的放在缓存里(相当于我们把最近联系的朋友的姓名和电话放在大脑里一样)。现在,我们就来研究这样一种缓存机制。
LRU缓存:
LRU缓存利用了这样的一种思想。LRU是Least Recently Used 的缩写,翻译过来就是“最近最少使用”,也就是说,LRU缓存把最近最少使用的数据移除,让给最新读取的数据。而往往最常读取的,也是读取次数最多的,所以,利用LRU缓存,我们能够提高系统的performance.
实现:
要实现LRU缓存,我们首先要用到一个类 LinkedHashMap。 用这个类有两大好处:一是它本身已经实现了按照访问顺序的存储,也就是说,最近读取的会放在最前面,最最不常读取的会放在最后(当然,它也可以实现按照插入顺序存储)。第二,LinkedHashMap本身有一个方法用于判断是否需要移除最不常读取的数,但是,原始方法默认不需要移除(这是,LinkedHashMap相当于一个linkedlist),所以,我们需要override这样一个方法,使得当缓存里存放的数据个数超过规定个数后,就把最不常用的移除掉。LinkedHashMap的API写得很清楚,推荐大家可以先读一下。
要基于LinkedHashMap来实现LRU缓存,我们可以选择inheritance, 也可以选择 delegation, 我更喜欢delegation。基于delegation的实现已经有人写出来了,而且写得很漂亮,我就不班门弄斧了。代码如下:
- import java.util.LinkedHashMap;
- import java.util.Collection;
- import java.util.Map;
- import java.util.ArrayList;
- /**
- * An LRU cache, based on <code>LinkedHashMap</code>.
- *
- * <p>
- * This cache has a fixed maximum number of elements (<code>cacheSize</code>).
- * If the cache is full and another entry is added, the LRU (least recently used) entry is dropped.
- *
- * <p>
- * This class is thread-safe. All methods of this class are synchronized.
- *
- * <p>
- * Author: Christian d'Heureuse, Inventec Informatik AG, Zurich, Switzerland<br>
- * Multi-licensed: EPL / LGPL / GPL / AL / BSD.
- */
- public class LRUCache<K,V> {
- private static final float hashTableLoadFactor = 0.75f;
- private LinkedHashMap<K,V> map;
- private int cacheSize;
- /**
- * Creates a new LRU cache.
- * @param cacheSize the maximum number of entries that will be kept in this cache.
- */
- public LRUCache (int cacheSize) {
- this.cacheSize = cacheSize;
- int hashTableCapacity = (int)Math.ceil(cacheSize / hashTableLoadFactor) + 1;
- map = new LinkedHashMap<K,V>(hashTableCapacity, hashTableLoadFactor, true) {
- // (an anonymous inner class)
- private static final long serialVersionUID = 1;
- @Override protected boolean removeEldestEntry (Map.Entry<K,V> eldest) {
- return size() > LRUCache.this.cacheSize; }}; }
- /**
- * Retrieves an entry from the cache.<br>
- * The retrieved entry becomes the MRU (most recently used) entry.
- * @param key the key whose associated value is to be returned.
- * @return the value associated to this key, or null if no value with this key exists in the cache.
- */
- public synchronized V get (K key) {
- return map.get(key); }
- /**
- * Adds an entry to this cache.
- * The new entry becomes the MRU (most recently used) entry.
- * If an entry with the specified key already exists in the cache, it is replaced by the new entry.
- * If the cache is full, the LRU (least recently used) entry is removed from the cache.
- * @param key the key with which the specified value is to be associated.
- * @param value a value to be associated with the specified key.
- */
- public synchronized void put (K key, V value) {
- map.put (key, value); }
- /**
- * Clears the cache.
- */
- public synchronized void clear() {
- map.clear(); }
- /**
- * Returns the number of used entries in the cache.
- * @return the number of entries currently in the cache.
- */
- public synchronized int usedEntries() {
- return map.size(); }
- /**
- * Returns a <code>Collection</code> that contains a copy of all cache entries.
- * @return a <code>Collection</code> with a copy of the cache content.
- */
- public synchronized Collection<Map.Entry<K,V>> getAll() {
- return new ArrayList<Map.Entry<K,V>>(map.entrySet()); }
- } // end class LRUCache
- ------------------------------------------------------------------------------------------
- // Test routine for the LRUCache class.
- public static void main (String[] args) {
- LRUCache<String,String> c = new LRUCache<String, String>(3);
- c.put ("1", "one"); // 1
- c.put ("2", "two"); // 2 1
- c.put ("3", "three"); // 3 2 1
- c.put ("4", "four"); // 4 3 2
- if (c.get("2") == null) throw new Error(); // 2 4 3
- c.put ("5", "five"); // 5 2 4
- c.put ("4", "second four"); // 4 5 2
- // Verify cache content.
- if (c.usedEntries() != 3) throw new Error();
- if (!c.get("4").equals("second four")) throw new Error();
- if (!c.get("5").equals("five")) throw new Error();
- if (!c.get("2").equals("two")) throw new Error();
- // List cache content.
- for (Map.Entry<String, String> e : c.getAll())
- System.out.println (e.getKey() + " : " + e.getValue()); }
import java.util.LinkedHashMap; import java.util.Collection; import java.util.Map; import java.util.ArrayList; /** * An LRU cache, based on <code>LinkedHashMap</code>. * * <p> * This cache has a fixed maximum number of elements (<code>cacheSize</code>). * If the cache is full and another entry is added, the LRU (least recently used) entry is dropped. * * <p> * This class is thread-safe. All methods of this class are synchronized. * * <p> * Author: Christian d'Heureuse, Inventec Informatik AG, Zurich, Switzerland<br> * Multi-licensed: EPL / LGPL / GPL / AL / BSD. */ public class LRUCache<K,V> { private static final float hashTableLoadFactor = 0.75f; private LinkedHashMap<K,V> map; private int cacheSize; /** * Creates a new LRU cache. * @param cacheSize the maximum number of entries that will be kept in this cache. */ public LRUCache (int cacheSize) { this.cacheSize = cacheSize; int hashTableCapacity = (int)Math.ceil(cacheSize / hashTableLoadFactor) + 1; map = new LinkedHashMap<K,V>(hashTableCapacity, hashTableLoadFactor, true) { // (an anonymous inner class) private static final long serialVersionUID = 1; @Override protected boolean removeEldestEntry (Map.Entry<K,V> eldest) { return size() > LRUCache.this.cacheSize; }}; } /** * Retrieves an entry from the cache.<br> * The retrieved entry becomes the MRU (most recently used) entry. * @param key the key whose associated value is to be returned. * @return the value associated to this key, or null if no value with this key exists in the cache. */ public synchronized V get (K key) { return map.get(key); } /** * Adds an entry to this cache. * The new entry becomes the MRU (most recently used) entry. * If an entry with the specified key already exists in the cache, it is replaced by the new entry. * If the cache is full, the LRU (least recently used) entry is removed from the cache. * @param key the key with which the specified value is to be associated. * @param value a value to be associated with the specified key. */ public synchronized void put (K key, V value) { map.put (key, value); } /** * Clears the cache. */ public synchronized void clear() { map.clear(); } /** * Returns the number of used entries in the cache. * @return the number of entries currently in the cache. */ public synchronized int usedEntries() { return map.size(); } /** * Returns a <code>Collection</code> that contains a copy of all cache entries. * @return a <code>Collection</code> with a copy of the cache content. */ public synchronized Collection<Map.Entry<K,V>> getAll() { return new ArrayList<Map.Entry<K,V>>(map.entrySet()); } } // end class LRUCache ------------------------------------------------------------------------------------------ // Test routine for the LRUCache class. public static void main (String[] args) { LRUCache<String,String> c = new LRUCache<String, String>(3); c.put ("1", "one"); // 1 c.put ("2", "two"); // 2 1 c.put ("3", "three"); // 3 2 1 c.put ("4", "four"); // 4 3 2 if (c.get("2") == null) throw new Error(); // 2 4 3 c.put ("5", "five"); // 5 2 4 c.put ("4", "second four"); // 4 5 2 // Verify cache content. if (c.usedEntries() != 3) throw new Error(); if (!c.get("4").equals("second four")) throw new Error(); if (!c.get("5").equals("five")) throw new Error(); if (!c.get("2").equals("two")) throw new Error(); // List cache content. for (Map.Entry<String, String> e : c.getAll()) System.out.println (e.getKey() + " : " + e.getValue()); }
代码出自:http://www.source-code.biz/snippets/java/6.htm
在博客 http://gogole.iteye.com/blog/692103 里,作者使用的是双链表 + hashtable 的方式实现的。如果在面试题里考到如何实现LRU,考官一般会要求使用双链表 + hashtable 的方式。 所以,我把原文的部分内容摘抄如下:
双链表 + hashtable实现原理:
将Cache的所有位置都用双连表连接起来,当一个位置被命中之后,就将通过调整链表的指向,将该位置调整到链表头的位置,新加入的Cache直接加到链表头中。这样,在多次进行Cache操作后,最近被命中的,就会被向链表头方向移动,而没有命中的,而想链表后面移动,链表尾则表示最近最少使用的Cache。当需要替换内容时候,链表的最后位置就是最少被命中的位置,我们只需要淘汰链表最后的部分即可。
- public class LRUCache {
- private int cacheSize;
- private Hashtable<Object, Entry> nodes;//缓存容器
- private int currentSize;
- private Entry first;//链表头
- private Entry last;//链表尾
- public LRUCache(int i) {
- currentSize = 0;
- cacheSize = i;
- nodes = new Hashtable<Object, Entry>(i);//缓存容器
- }
- /**
- * 获取缓存中对象,并把它放在最前面
- */
- public Entry get(Object key) {
- Entry node = nodes.get(key);
- if (node != null) {
- moveToHead(node);
- return node;
- } else {
- return null;
- }
- }
- /**
- * 添加 entry到hashtable, 并把entry
- */
- public void put(Object key, Object value) {
- //先查看hashtable是否存在该entry, 如果存在,则只更新其value
- Entry node = nodes.get(key);
- if (node == null) {
- //缓存容器是否已经超过大小.
- if (currentSize >= cacheSize) {
- nodes.remove(last.key);
- removeLast();
- } else {
- currentSize++;
- }
- node = new Entry();
- }
- node.value = value;
- //将最新使用的节点放到链表头,表示最新使用的.
- moveToHead(node);
- nodes.put(key, node);
- }
- /**
- * 将entry删除, 注意:删除操作只有在cache满了才会被执行
- */
- public void remove(Object key) {
- Entry node = nodes.get(key);
- //在链表中删除
- if (node != null) {
- if (node.prev != null) {
- node.prev.next = node.next;
- }
- if (node.next != null) {
- node.next.prev = node.prev;
- }
- if (last == node)
- last = node.prev;
- if (first == node)
- first = node.next;
- }
- //在hashtable中删除
- nodes.remove(key);
- }
- /**
- * 删除链表尾部节点,即使用最后 使用的entry
- */
- private void removeLast() {
- //链表尾不为空,则将链表尾指向null. 删除连表尾(删除最少使用的缓存对象)
- if (last != null) {
- if (last.prev != null)
- last.prev.next = null;
- else
- first = null;
- last = last.prev;
- }
- }
- /**
- * 移动到链表头,表示这个节点是最新使用过的
- */
- private void moveToHead(Entry node) {
- if (node == first)
- return;
- if (node.prev != null)
- node.prev.next = node.next;
- if (node.next != null)
- node.next.prev = node.prev;
- if (last == node)
- last = node.prev;
- if (first != null) {
- node.next = first;
- first.prev = node;
- }
- first = node;
- node.prev = null;
- if (last == null)
- last = first;
- }
- /*
- * 清空缓存
- */
- public void clear() {
- first = null;
- last = null;
- currentSize = 0;
- }
- }
- class Entry {
- Entry prev;//前一节点
- Entry next;//后一节点
- Object value;//值
- Object key;//键
- }
public class LRUCache { private int cacheSize; private Hashtable<Object, Entry> nodes;//缓存容器 private int currentSize; private Entry first;//链表头 private Entry last;//链表尾 public LRUCache(int i) { currentSize = 0; cacheSize = i; nodes = new Hashtable<Object, Entry>(i);//缓存容器 } /** * 获取缓存中对象,并把它放在最前面 */ public Entry get(Object key) { Entry node = nodes.get(key); if (node != null) { moveToHead(node); return node; } else { return null; } } /** * 添加 entry到hashtable, 并把entry */ public void put(Object key, Object value) { //先查看hashtable是否存在该entry, 如果存在,则只更新其value Entry node = nodes.get(key); if (node == null) { //缓存容器是否已经超过大小. if (currentSize >= cacheSize) { nodes.remove(last.key); removeLast(); } else { currentSize++; } node = new Entry(); } node.value = value; //将最新使用的节点放到链表头,表示最新使用的. moveToHead(node); nodes.put(key, node); } /** * 将entry删除, 注意:删除操作只有在cache满了才会被执行 */ public void remove(Object key) { Entry node = nodes.get(key); //在链表中删除 if (node != null) { if (node.prev != null) { node.prev.next = node.next; } if (node.next != null) { node.next.prev = node.prev; } if (last == node) last = node.prev; if (first == node) first = node.next; } //在hashtable中删除 nodes.remove(key); } /** * 删除链表尾部节点,即使用最后 使用的entry */ private void removeLast() { //链表尾不为空,则将链表尾指向null. 删除连表尾(删除最少使用的缓存对象) if (last != null) { if (last.prev != null) last.prev.next = null; else first = null; last = last.prev; } } /** * 移动到链表头,表示这个节点是最新使用过的 */ private void moveToHead(Entry node) { if (node == first) return; if (node.prev != null) node.prev.next = node.next; if (node.next != null) node.next.prev = node.prev; if (last == node) last = node.prev; if (first != null) { node.next = first; first.prev = node; } first = node; node.prev = null; if (last == null) last = first; } /* * 清空缓存 */ public void clear() { first = null; last = null; currentSize = 0; } } class Entry { Entry prev;//前一节点 Entry next;//后一节点 Object value;//值 Object key;//键 }
相关推荐
LRU 缓存机制(java代码).docx
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算法删除、获取缓存值等功能。 复制到本地项目的时候,记得改包路径哦~
主要介绍了Java实现简单LRU缓存机制的方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
缓存淘汰算法之LRU
这里的LRUCache类维护了一个双向链表和一个哈希表,用于实现LRU算法。具体实现细节如下: - get方法:首先在哈希表中查找对应的键值对,如果不存在,则返回-1;如果存在,则将对应的节点从双向链表中删除,并将其...
Android提供了LRUCache类,可以方便的使用它来实现LRU算法的缓存。Java提供了LinkedHashMap,可以用该类很方便的实现LRU算法,Java的LRULinkedHashMap是直接继承了LinkedHashMap,进行了极少的改动后可以实现LRU...
主要介绍了详解Java实现LRU缓存,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
主要介绍了Java实现LRU缓存的实例详解的相关资料,这里提供实例帮助大家理解掌握这部分内容,需要的朋友可以参考下
Android提供了LRUCache类,可以方便的使用它来实现LRU算法的缓存。Java提供了LinkedHashMap,可以用该类很方便的实现LRU算法,Java的LRULinkedHashMap就是直接继承了LinkedHashMap,进行了极少的改动后就可以实现LRU...
LRU缓存HashMap+双向链表实现,java版本,导入即用
用Java写的一个Cache,内部实现了LRU算法~
LRU缓存 Java 中最近最少使用 (LRU) 缓存。 测试 mvn test ------------------------------------------------------- T E S T S ------------------------------------------------------- Running ...
缓存——LRU Java 缓存描述快速 灵活 高效的内存 LRU Java 缓存 该存储库包含的来源。 巴拉克。 示例用法: Cache< String> fileContentCache = new Cache<> (key - > readFileContent( new File (key)),...
主要介绍了浅谈Java如何实现一个基于LRU时间复杂度为O(1)的缓存,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
1.2.3 java.util.regex的使用... 6 1.3 实战正则表达式... 8 第2章 程序最优化.... 14 2.1 空间与时间... 14 2.1.1 空间与时间的概念和度量... 14 2.1.2 空间与时间的背反... 15 2.1.3 以空间换时间... 15 2.2 字典...
缓存 在 Java 中实现 LRU 缓存
NULL 博文链接:https://jimi68.iteye.com/blog/440892