Yinde's Blog

Talk is cheap. Show me the code.

目录
LRU 缓存算法
/  

LRU 缓存算法

缓存的主要目的就是提高访问速度,当我们需要从某个容器中获取一个元素的时候,将会优先从缓存中获取,如果缓存中正好存在,那么我们就可以直接取走这个元素,并且称之为成功命中。

所以缓存算法的主要目的就是定制一种策略,让命中率能够最大化。更好的利用计算机中不同存储介质速度不同的特性。

主要的缓存算法有两种 LRU 最久未用淘汰 以及 LFU 最少使用淘汰

LRU 一段时间内 上一次命中时间最长的元素将被淘汰

LFU 一段时间内 命中次数最少的元素将被淘汰

这个算法比较简单,我这里就直接上代码了

实现


package  tech.yinode.demo;

  

import  java.util.*;

  

import  tech.yinode.demo.Print;

  

class  Storage  {

static  class  Cache  {

static  class  CacheItem  {

public  String  key;

public  int  count;

public  String  val;

  

CacheItem(String  key, int  count, String  val)  {

this.key  = key;

this.count  = count;

this.val  = val;

}

}

  

private  PriorityQueue<CacheItem>  LFUQueue  =  new  PriorityQueue<CacheItem>(11,  new  Comparator<CacheItem>() {

@Override

public  int compare(CacheItem  o1, CacheItem  o2)  {

return  o1.count  -  o2.count;

}

});

private  HashMap<String,  CacheItem>  cacheSpace  =  new  HashMap<String,  CacheItem>();

private  int  cacheMaxSize  =  2;

  

public  void put(String  key, String  val)  {

//缓存空间不足 需要先进行清除

if (cacheSpace.size() > cacheMaxSize) {

Print.println("缓存空间不足 删除频率最低的元素");

CacheItem  item  =  LFUQueue.poll();

cacheSpace.remove(item.key);

}

CacheItem  newItem  =  new  CacheItem(key, 0, val);

LFUQueue.add(newItem);

cacheSpace.put(key, newItem);

}

  

public  String get(String  key)  {

CacheItem  item  =  cacheSpace.get(key);

  

// 命中失败

if (item ==  null) {

Print.println(key +  ": 命中失败");

return  null;

}

  

Print.println(key +  ": 命中成功");

  

// 更新该元素的访问频率

LFUQueue.remove(item);

item.count++;

LFUQueue.add(item);

  

return  item.val;

}

}

  

// 高速缓存

private  Cache  cache  =  new  Cache();

// 模拟磁盘

private  HashMap<String,  String>  disk  =  new  HashMap<String,  String>();

  

public  void put(String  key, String  val)  {

disk.put(key, val);

cache.put(key, val);

}

  

public  String get(String  key)  {

String  cacheValue  =  cache.get(key);

// 命中失败

if (cacheValue ==  null) {

return  disk.get(key);

}

return cacheValue;

}

}

  

class  Index  {

  

public  static  void main(String[] args)  throws  Exception  {

Storage  data  =  new  Storage();

data.put("a", "1");

data.get("a");

data.get("a");

data.get("a");

data.put("b", "1");

data.get("b");

data.put("c", "1");

data.put("d", "1");

try {

data.get("a");

data.get("b");

data.get("c");

data.get("d");

} catch (NullPointerException  e) {

Print.println("404");

}

}

}


标题:LRU 缓存算法
作者:zhangzhengyi12
地址:https://blog.yinode.tech/articles/2019/09/06/1567751007304.html

评论