当前位置: IT大杂烩 > Ubuntu  > LRUCache 详解

LRUCache 详解

www.someabcd.com  网友分享于:Jun 8, 2018 5:52:50 PM

标签:lru算法   lrucache   lru   最少被访问   

LRU的基本概念:

    LRU是Least Recently Used的缩写,近期最少使用算法。

Java 实现LRUCache

  1、基于LRU的基本概念,为了达到按近期最少使用排序,可以选择HashMap的子类
 LinkedHashMap来作为LRUCache的存储容器。
  2、LinkedHashMap的原理:
  a、 对于LinkedHashMap而言,它继承与HashMap、底层使用哈希表与双向链表来保存所有元素。其基本操作与父类HashMap相似,它通过重写父类相关的方法,来实现自己的链接列表特性。HashMap是单链表,LinkedHashMap是双向链表
  b、存储:LinkedHashMap并未重写父类HashMap的put方法,而是重写了父类HashMap的put方法调用的子方法void recordAccess(HashMap m)   ,void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex),提供了自己特有的双向链接列表的实现。
  c、读取:LinkedHashMap重写了父类HashMap的get方法,实际在调用父类getEntry()方法取得查找的元素后,再判断当排序模式accessOrder为true时,记录访问顺序,将最新访问的元素添加到双向链表的表头,并从原来的位置删除。由于的链表的增加、删除操作是常量级的,故并不会带来性能的损失。

LRUCache的简单实现

package com.knowledgeStudy.lrucache;
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.Map;
/**
 * 固定大小 的LRUCache<br>
 * 线程安全
 **/
public class LRUCache<K, V> {
    private static final float factor = 0.75f;//扩容因子
    private Map<K, V> map; //数据存储容器
    private int cacheSize;//缓存大小
    public LRUCache(int cacheSize) {
        this.cacheSize = cacheSize;
        int capacity = (int) Math.ceil(cacheSize / factor) + 1;
        map = new LinkedHashMap<K, V>(capacity, factor, true) {
            private static final long serialVersionUID = 1L;
            /**
             * 重写LinkedHashMap的removeEldestEntry()固定table中链表的长度
             **/
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                boolean todel = size() > LRUCache.this.cacheSize;
                return todel;
            }
        };
    }
    /**
     * 根据key获取value
     *
     * @param key
     * @return value
     **/
    public synchronized V get(K key) {
        return map.get(key);
    }
    /**
     * put一个key-value
     *
     * @param key
     *            value
     **/
    public synchronized void put(K key, V value) {
        map.put(key, value);
    }
    /**
     * 根据key来删除一个缓存
     *
     * @param key
     **/
    public synchronized void remove(K key) {
        map.remove(key);
    }
    /**
     * 清空缓存
     **/
    public synchronized void clear() {
        map.clear();
    }
    /**
     * 已经使用缓存的大小
     **/
    public synchronized int cacheSize() {
        return map.size();
    }
    /**
     * 获取缓存中所有的键值对
     **/
    public synchronized Collection<Map.Entry<K, V>> getAll() {
        return new ArrayList<Map.Entry<K, V>>(map.entrySet());
    }
}



LRUCache 详解

标签:lru算法   lrucache   lru   最少被访问   

发布此文章仅为传递网友分享,不代表本站观点,若侵权请联系我们删除,本站将不对此承担任何责任。
Copyright ©2018  IT大杂烩  版权所有  京ICP备11030978号-1 网站地图