`

How to set up a simple LRU cache using LinkedHash

阅读更多
How to set up a simple LRU cache using LinkedHashMap

Caches

Caches are a simple way to improve the performance of an application that reads data from a "slow" source such as files on disk or rows of data from a database table, but may need to re-read the same data multiple times. The idea is simple: instead of discarding the data after using it, keep it in memory so that it doesn't have to be re-read later.

For example, a simple way to organize this for files might be to create a HashMap that maps the file names to objects containing the file data. When your application needs a particular file it first checks the map to see if it already has the data; if it doesn't, it reads the file and places it in the map in case it needs it again later.

LRU caches

The problem with this simple method is that your application could use a vast amount of memory. Once read in, a file is in the cache for the lifetime of the application whether or not it is ever used again. For an application such as a server that is intended to stay up and running for weeks or months at a time, this is probably not acceptable.

What's needed is a cache that automatically discards entries that haven't been accessed for some time so as to limit the amount of space being used. Such as cache is called an LRU Cache. LRU stands for "Least Recently Used", which refers to the policy of removing the oldest, or least-recently used entries to make space for new data.

LRU caches have a maximum number of data items that they will hold and these items are usually arranged in a list. When an item is added to the cache, and every time it is accessed after that, it is automatically moved to the head of the list. If the cache is full and a slot is required for a new item, the cache makes room by discarding the entry at the tail of the list - the least-recently used item.

The java.util.LinkedHashMap class

LinkedHashMap is a subclass of java.util.HashMap that adds a couple of useful features. One is that by default the iteration order reflects the order that entries are added to the map, rather than the rather haphazard order of a HashMap.

The other feature - the one we're interested in here - is that LinkedHashMap has an option to use access-order instead of insertion order, and includes a way to remove the least-recently accessed entries automatically. This makes it well suited for creating LRU caches.

Creating a cache class

The simplest way to create a cache using LinkedHashMap is to extend it. Here is an example:
public class Cache extends
    LinkedHashMap
{
  private final int capacity;

  public Cache(int capacity)
  {
    super(capacity + 1, 1.1f, true);
    this.capacity = capacity;
  }

  protected boolean removeEldestEntry(Entry eldest)
  {
    return size() > capacity;
  }
}

Note that the constructor takes as an argument the maximum number of entries we want a Cache object to hold. The superclass constructor has three arguments: the initial capacity of the map, the load factor, and a boolean argument that tells the LinkedHashMap constructor to keep entries in access order instead of the default insertion order. (See the java.util.HashMap API documentation for a description of the initial capacity and load factor.) In this case we set the initial capacity to be one more than our required cache size - this is because new entries are added before any are removed, so for example if we want to hold 100 entries the cache will actually contain 101 for an instant when new data is added. Setting the load factor to 1.1 ensures that the rehashing mechanism of the underlying HashMap class isn't triggered - this isn't a vital point but helps a little with efficiency at run-time.

The removeEldestEntry() method overrides a default implementation in LinkedHashMap and is where we determine the policy for removing the oldest entry. In this case, we return true when the cache has more entries than our defined capacity.

Using the cache

Using the cache is simple - just use a suitable key to access the cache; if the data is in the cache we can read it from there. If it's not there we pull it from the slow medium and add it to the cache so that it's in place if needed later:
    Cache cache = new Cache(100);
    // ...

    String filename = "file.txt";
    String filedata = (String) cache
        .get(filename);
    if (filedata == null)
    {
      // Read filedata from file system here...
      cache.put(filename, filedata);
    }

How does it perform?

Our basic implementation should work just fine but we may need to know how effective it is in a given application. One measure of how well a cache is performing is Hit Rate, which tells us how many cache accesses are "hits" - that is, how many times the required data was found in the cache for a given number of accesses. Hit rate is usually expressed as a percentage - a hit rate above 80% is usually pretty good.

We can add a few things to our Cache class to make it possible to monitor performance so that we can tune the cache by setting an optimum size. We need a counter for the number of accesses and another for the number of hits. We will need getter methods to allow us to retrieve those values after the cache has been running for a time, and finally we must override the get() method to update the counts. Here is our Cache class complete with these new members:
public class Cache extends
    LinkedHashMap
{
  private final int capacity;
  private long accessCount = 0;
  private long hitCount = 0;

  public Cache(int capacity)
  {
    super(capacity + 1, 1.1f, true);
    this.capacity = capacity;
  }

  public Object get(Object key)
  {
    accessCount++;
    if (containsKey(key))
    {
      hitCount++;
    }
    Object value = super.get(key);
    return value;
  }

  protected boolean removeEldestEntry(Entry eldest)
  {
    return size() > capacity;
  }

  public long getAccessCount()
  {
    return accessCount;
  }

  public long getHitCount()
  {
    return hitCount;
  }
}

One point to note is that calls to the containsKey() method don't update the access counts; we may want to override that method also, so that the hit rate isn't skewed by code such as this:
    if (cache.containsKey(filename))
    {
      filedata = (String) cache
          .get(filename);
    }
    else
    {
      // Read filedata from file system here...
      cache.put(filename, filedata);
}
分享到:
评论

相关推荐

    算法面试通关40讲完整课件 57-58 LRU Cache

    算法面试通关40讲完整课件 57-58 LRU Cache 算法面试通关40讲完整课件 57-58 LRU Cache 算法面试通关40讲完整课件 57-58 LRU Cache 算法面试通关40讲完整课件 57-58 LRU Cache 算法面试通关40讲完整课件 57-58 LRU ...

    最近最少使用cache,提取leveldb的lru cache部分,增加过期时间,过期失效

    提取google开源软件leveldb的lru cache部分,独立出来,并增加过期时间,过期失效,可独立使用。仅供参考。

    Android性能优化一 : 1.The Magic of LRU Cache (100 Days of Google Dev)

    谷歌官方视频

    LRU更新Cache

    是计算机体系结构试验程序,用LRU算法更新Cache

    Lru Cache java代码

    LruCache的java代码实现,是从android代码中抽取出来的

    LRU Cache的简单C++实现

     LRU Cache是一个Cache的置换算法,含义是“近少使用”,把满足“近少使用”的数据从Cache中剔除出去,并且保证Cache中第一个数据是近刚刚访问的,因为这样的数据更有可能被接下来的程序所访问。  LRU的应用比较...

    LRU-update-Cache-.zip_LRU cache

    LRU置换算法是选择最近最久未使用的页面予以置换。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来经历的时间T,当须淘汰一个页面时,选择现有页面中T值最大的,即最近最久没有访问的页面。这是...

    java 缓存 cache lru 实例

    java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例

    backports.functools_lru_cache

    在发布的Python 3.3中的functools.lru_cache的反向。 用法 考虑使用此技术导入“ lru_cache”函数: try: from functools import lru_cache except ImportError: from backports.functools_lru_cache import lru_...

    backports.functools_lru_cache-1.5.tar

    python源码安装包backports.functools_lru_cache-1.5.tar 解压后python setup.py install 进行安装

    javalruleetcode-LRU_cache:LRU_cache

    LRU_cache (Leetcode 146) 设计和实现最近最少使用 (LRU) 缓存的数据结构。 它应该支持以下操作:get 和 set。 get(key) – 如果键存在于缓存中,则获取键的值(将始终为正),否则返回 -1。 set(key, value) – ...

    LRU-cache:用JS实现的LRU缓存

    #LRU缓存通过Node JS中的链接列表和哈希映射实现要运行,请先将存储库克隆到桌面git clone https://github.com/Teaflavored/LRU-cache然后导航到LRU-cache文件夹并运行node testingLRUCache.js

    PyPI 官网下载 | backports.functools_lru_cache-1.3.tar.gz

    资源来自pypi官网。 资源全名:backports.functools_lru_cache-1.3.tar.gz

    erlang lru cache module

    NULL 博文链接:https://erlangdisplay.iteye.com/blog/315483

    lru-cache-node:具有最近使用策略的节点的照明快速缓存管理器

    lru-cache-node 具有最近使用策略的节点的照明快速缓存管理器。 具有LRU策略的节点的超快速缓存。 缓存将继续添加值,直到达到maxSize为止。 之后,它将开始从缓存中弹出最近最少使用/访问的值,以便设置新值。 支持...

    lru-cache-js:使用双链表和映射实现 LRU Cache,读写时间复杂度为 O(1)

    LRU缓存使用的数据结构使用双向链表实现的队列。 队列的最大大小将等于...执行 npm i lru-cache-js-map const LRUCache = require('lru-cache-js-map');var cache = new LRUCache(100);for(var i=0; i < 100; i++){

    LRU-Cache:通过Node.js实现LRU缓存

    const lru = require ( 'LRU-Cache' ) ; 。放 capacity -列表容量,不允许0,默认值:1000 maxAge节点将在maxAge ms内自行销毁 const cache = new lru ( { capacity : 100 } ) ; cache . set ( 'test_key' , 123 ) ...

    lrucacheleetcode-lru_cache:lru_cache

    lru缓存leetcode LRU缓存 受启发的简单 LRU 缓存实现 发展 建造 ./gradlew build 测试 ./gradlew test 使用示例 LRUCache< String , String > cache = new LRUCache<> ( 2 /* capacity */ ); cache . put( " ...

    node-lru-cache

    var LRU = require ( "lru-cache" ) , options = { max : 500 , length : function ( n , key ) { return n * 2 + key . length } , dispose : function ( key , n ) { n . close ( ) } , maxAge : 1000 * 60 *...

    ARM高速缓存(Cache)Verilog代码 包含ISE工程

    Cache替换策略: LRU I_Cache的工作就是在cpu需要指令时将指令从主存中搬进I_Cache,再传给CPU,而D_Cache在解决数据读外,还要注意数据写入的问题。本工程可以与arm.v 中的arm 核协同工作,主存使用dram_ctrl_sim。

Global site tag (gtag.js) - Google Analytics