LRU算法java实现

逃离我推掉我的手 2022-04-18 01:46 210阅读 0赞

# 1、lru简介 #

LRU是Least Recently Used的缩写，即最近最少使用，常用于页面置换算法，是为虚拟页式存储管理服务的。

即当一个数据最近一段时间没有被访问，未来被访问的概率也很小。当空间被占满后，最先淘汰最近最少使用的数据。

# 2、java简单实现 #

/**
     * @Title: LRU.java
     * @Package com.spring.pro.lru
     * @Description:
     * @author ybwei
     * @date 2018年11月6日 下午2:39:15
     * @version V1.0
     */
    public class LRU<K, V> {
    
    	/**
    	 * LinkedHashMap负载因子默认0.75
    	 */
    	private static final float hashLoadFactory = 0.75f;
    	private LinkedHashMap<K, V> map;
    	private int cacheSize;
    
    	/**
    	 * @param cacheSize 容量
    	 */
    	public LRU(int cacheSize) {
    		this.cacheSize = cacheSize;
    		int capacity = (int) Math.ceil(cacheSize / hashLoadFactory) + 1;
    		map = new LinkedHashMap<K, V>(capacity, hashLoadFactory, true) {
    			private static final long serialVersionUID = -5291175172111746517L;
    
    			/*
    			 * 当map容量大于LRU的容量时，删除最近最少使用的数据
    			 */
    			@Override
    			protected boolean removeEldestEntry(Entry<K, V> eldest) {
    				return size() > LRU.this.cacheSize;
    			}
    		};
    	}
    
    	public synchronized V get(K key) {
    		return map.get(key);
    	}
    
    	public synchronized void put(K key, V value) {
    		map.put(key, value);
    	}
    
    	public synchronized void clear() {
    		map.clear();
    	}
    
    	public synchronized int usedSize() {
    		return map.size();
    	}
    
    	public void print() {
    		for (Map.Entry<K, V> entry : map.entrySet()) {
    			System.out.print(entry.getValue() + "--");
    		}
    		System.out.println();
    	}
    }

HashMap的一个实例有两个影响其性能的参数： 初始容量和负载因子 。 容量是哈希表中的桶数，初始容量只是创建哈希表时的容量。 负载因子是在容量自动增加之前允许哈希表得到满足的度量。 当在散列表中的条目的数量超过了负载因数和电流容量的乘积，哈希表被重新散列 （即，内部数据结构被重建），使得哈希表具有桶的大约两倍。

作为一般规则，默认负载因子（.75）提供了时间和空间成本之间的良好折中。 更高的值会降低空间开销，但会增加查找成本（反映在HashMap类的大部分操作中，包括get和put ）。 在设置其初始容量时，应考虑地图中预期的条目数及其负载因子，以便最小化重新组播操作的数量。 如果初始容量大于最大条目数除以负载因子，则不会发生重新排列操作。

# 3、测试 #

/**   
     * @Title: LRUTest.java 
     * @Package com.spring.pro.lru.test 
     * @Description:  
     * @author ybwei  
     * @date 2018年11月6日 下午4:39:03 
     * @version V1.0   
     */
    public class LRUTest {
    
    	/**
    	 * 
    	 * @author ybwei
    	 */
    	@Test
    	public void LruTest() {
    		LRU<String,Integer> lru=new LRU<>(3);
    		for(int i=0;i<50;i++) {
    			lru.put("aa"+i, i);
    			lru.print();
    		}
    	}
    }