LRU算法详解-创新互联

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值大的，即最近最少使用的页面予以淘汰。

LRU是一种常见的缓存管理算法，在一些常见的技术中，都有应用，如redis的缓存淘汰策略，mysql的数据缓存页等。

通常意义上讲，有两种实现方式，一种是基于访问顺序，一种是基于读取顺序的，接下来基于LinkedHashMap，对这两种实现方式进行Demo编写。

• 实现

public class LocalCache{

    private int capacity = 16;

    private LinkedHashMapcache;

    public LocalCache(int capacity) {
        this.capacity = capacity;
        cache = new LinkedHashMap<>(capacity);
    }

    public LocalCache() {
        cache = new LinkedHashMap<>(capacity);
    }

    public V get(K key) {
        if (!cache.containsKey(key)) {
            return null;
        }

        V value = cache.get(key);
        cache.remove(key);
        cache.put(key, value);
        return value;
    }

    public void set(K key, V value) {
        if (cache.containsKey(key)) {
            cache.remove(key);
        }

        if (cache.size() == capacity) {
            SetkeySet = cache.keySet();
            Iteratoriterator = keySet.iterator();
            cache.remove(iterator.next());
        }
        cache.put(key, value);
    }

    @Override
    public String toString() {
        StringBuilder cacheStr = new StringBuilder();
        cache.forEach((k, v) ->cacheStr.append(k).append(":").append(v).append("\t"));
        return cacheStr.toString();
    }
}

• 测试

public class CacheTest {

    public static void main(String[] args) {
        LocalCachelocalCache = new LocalCache<>(5);
        localCache.set("A", "a");
        localCache.set("B", "b");
        localCache.set("C", "c");
        localCache.set("D", "d");
        localCache.set("E", "e");
        localCache.set("F", "f");
        localCache.get("D");
        System.out.println(localCache);
    }
}

• 输出

B:b    C:c    E:e    F:f    D:d

• 实现

public class LocalCacheextends LinkedHashMap{

    private int capacity = 16;

    public LocalCache() {
        super(16);
    }

    public LocalCache(int capacity) {
        super(capacity);
        this.capacity = capacity;
    }

    @Override
    public boolean removeEldestEntry(Map.Entryeldest) {
        return super.size() >capacity;
    }

    @Override
    public String toString() {
        return super.toString();
    }

}

• 测试

public class CacheTest {

    public static void main(String[] args) {
        LocalCachecache = new LocalCache<>(3);
        cache.put("1", "1");
        cache.put("2", "2");
        cache.put("3", "3");
        cache.put("4", "4");
        System.out.println(cache);
        cache.get("3");
        System.out.println(cache);
    }
}

• 输出

{2=2, 3=3, 4=4}
{2=2, 3=3, 4=4}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧