当前访客身份:游客 [ 登录  | 注册加入尚学堂]
直播

我来了!

拥有积分:3896
尚学堂雄起!!威武。。。

博客分类

笔记中心

课题中心

提问中心

答题中心

解答题中心

用LinkedHashMap实现LRU Cache

我来了! 发表于 2年前 (2014-09-24 13:19:18)  |  评论(0)  |  阅读次数(354)| 0 人收藏此文章,   我要收藏   

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

LinkedHashMap提供特殊的构造方法来创建链接哈希映射,该哈希映射的迭代顺序就是最后访问其条目的顺序,从近期访问最少到近期访问最多的顺序(访问顺序)。这种映射很适合构建 LRU 缓存。调用put或get方法将会访问相应的条目(假定调用完成后它还存在)。putAll方法以指定映射的条目集合迭代器提供的键-值映射关系的顺序,为指定映射的每个映射关系生成一个条目访问。任何其他方法均不生成条目访问。特别是,collection 视图上的操作 影响底层映射的迭代顺序。

可以重写 removeEldestEntry(Map.Entry) 方法来实施策略,以便在将新映射关系添加到映射时自动移除旧的映射关系。

此类提供所有可选的Map操作,并且允许 null 元素。与HashMap一样,它可以为基本操作(add、contains和remove)提供稳定的性能,假定哈希函数将元素正确分布到桶中。由于增加了维护链接列表的开支,其性能很可能比HashMap稍逊一筹,不过这一点例外:LinkedHashMap的 collection 视图迭代所需时间与映射的大小 成比例。HashMap迭代时间很可能开支较大,因为它所需要的时间与其容量 成比例。

链接的哈希映射具有两个影响其性能的参数:初始容量加载因子。它们的定义与HashMap极其相似。要注意,为初始容量选择非常高的值对此类的影响比对HashMap要小,因为此类的迭代时间不受容量的影响。 


<span style="font-size:18px;">import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache extends LinkedHashMap<Integer, Integer> {
  private int capacity;

  public LRUCache(int capacity) {
    super(capacity, 0.75f, true);
    this.capacity = capacity;
  }
  //重写父类get,为null时范围-1
  public Integer get(Object key) {
    Integer v = super.get(key);
    if (v != null)
      return v;
    else
      return -1;
  }
  //重写父类方法,当超过缓存容量时,就删除最久没有访问的的
  public boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
    return size() > capacity;
  }

  public void set(int key, int value) {
    super.put(key, value);
  }
}</span>



分享到:0
关注微信,跟着我们扩展技术视野。每天推送IT新技术文章,每周聚焦一门新技术。微信二维码如下:
微信公众账号:尚学堂(微信号:bjsxt-java)
北京总部地址:北京市海淀区西三旗桥东建材城西路85号神州科技园B座三层尚学堂 咨询电话:400-009-1906 010-56233821
Copyright 2007-2015 北京尚学堂科技有限公司 京ICP备13018289号-1 京公网安备11010802015183