使用LinkedHashMap实现LRU(缓存淘汰算法)

LRU算法简介

LRU（Least Recently Used），即最近最少被使用的意思。

LRU算法的设计原则就是：如果一个数据在最近一段时间没有被访问到，那么在将来一段时间它被访问到的几率也很小。也就是说，当有限的存储空间存满数据时，应该将最久没有被访问到的数据删除，为存储新的数据腾出空间。

LRU算法的实现方式

1. 使用数组实现
   使用一个数组来存储数据，可以为数组的每个元素对象添加一个计数器或者时间戳之类的东西，每次为数组插入新的元素时，先把数组中原来存在的元素中的时间戳增加，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。

2. 使用单向链表实现
   利用一个链表来实现，每次新插入数据的时候将新数据插到链表的头部；每次缓存命中（即数据被访问），则将数据移到链表头部；那么当链表满的时候，就将链表尾部的数据丢弃。

   对于第一种方法，需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n)。对于第二种方法，链表在定位数据的时候时间复杂度为O(n)。所以在一般使用链表+HashMap实现LRU算法。

3. 利用链表+HashMap。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表尾部，如果不存在，则新建一个节点，放到链表尾部，若缓存满了，则把链表最第一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表尾部，否则返回-1。这样一来在链表头部的节点就是最近最近最少被访问的数据项。

使用LinkedHashMap实现LRU算法

LinkedHashMap底层就是用的HashMap加双链表实现的，而且本身已经实现了按照访问顺序的存储。此外，LinkedHashMap中本身就实现了一个方法removeEldestEntry用于判断是否需要移除最不常读取的数，方法默认是直接返回false，不会移除元素，所以需要重写该方法。即当缓存满后就移除最不常用的数据。

package com.loong.lru;

import java.util.LinkedHashMap;
import java.util.Map;

public class LruCache<K,V> {
	
	//负载因子
	private static float LOADFACTOR = 0.75f;
	//缓存容量
	private int cacheSize;
	//链表HashMap
	private LinkedHashMap<K,V> map;
	
	public LruCache(int cacheSize) {
		this.cacheSize = cacheSize;
		//匿名实现类，重写removeEldestEntry方法
		this.map = new LinkedHashMap<K,V>(cacheSize, LOADFACTOR, true){
			private static final long serialVersionUID = 1L;
			@Override
			protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
				return super.size() > LruCache.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 size() {
		return map.size();
	}
	
	public void forEach() {
		for(Map.Entry<K, V> entry : map.entrySet()) {
			System.out.println(entry);
		}
	}
	
	//测试算法效果
	public static void main(String[] args) {
		LruCache<String, Integer> lru = new LruCache<String, Integer>(3);
		lru.put("k1", 1);
		lru.put("k2", 2);
		lru.put("k3", 3);
		lru.forEach();
		lru.put("k4", 4);
		System.out.println("淘汰头部元素k1");
		lru.forEach();
		lru.get("k2");
		lru.put("k5", 5);
		System.out.println("k2被命中已到尾部，淘汰头部k3");
		lru.forEach();
		
	}
}

当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。

使用LinkedHashMap实现LRU(缓存淘汰算法)

原文：https://www.cnblogs.com/codeloong/p/14825581.html