技术标签: 死磕 Java 死磕 Java Core
大家好,我是大明哥
个人网站:https://www.topjava.cn/
LRU,即 Least Recently Use ,直译为 “最近最少使用”。它是根据数据的历史访问记录来进行数据淘汰的,淘汰掉最先访问的数据,其核心思想是 如果数据最近被访问过,那么将来被访问的几率也会更加高。
要实现 LRU,需要做到两点:
实现的方案有多种,这里小编主要介绍两种:
利用 LinkedHashMap 的原因就在于 LinkedHashMap 是有序的,默认情况下是按照元素的添加顺序存储的,也可以调整为根据访问顺序来调整内部顺序(设置参数 accessOrder 进行调整),即最近读取的数据放在最前面,我们就是利用 LinkedHashMap 的这个特性来实现 LRU。先来一个简单的例子吧:
public static void main(String[] args){
Map<String,String> map = new LinkedHashMap(10,0.75f,true);
map.put("1","a");
map.put("2","b");
map.put("3","c");
map.put("4","d");
System.out.println("原始顺序为:");
for(Iterator<Map.Entry<String,String>> it = map.entrySet().iterator();it.hasNext();){
System.out.print(it.next().getKey() + " ");
}
System.out.println();
map.get("2");
System.out.println("访问 4 之后的顺序为:");
for(Iterator<Map.Entry<String,String>> it = map.entrySet().iterator();it.hasNext();){
System.out.print(it.next().getKey() + " ");
}
}
运行结果:
原始顺序为:
1 2 3 4
访问 4 之后的顺序为:
1 3 4 2
更多关于 LinkedHashMap,请看这篇文章:图解集合6:LinkedHashMap
LinkedHashMap 实现 LRU 有两种方式,一种是继承 LinkedHashMap,一种是利用组合的方式,下面分别演示这两种情况。
采用继承的方式实现起来是非常简单的,因为 LinkedHashMap 本身就已经具备了 LRU 的特性,我们只需要实现一点:当容器中元素个数超过我们设定的容量后,删除第一个元素即可。同时由于 LinkedHashMap 本身不具备线程安全,我们需要确保他线程安全,这个也很简单,重写 LinkedHashMap 的 get()
和 put()
方法即可,或者使用 Collections.synchronizedMap() 方法也可以。实现如下:
public class LRUCacheLinkedHashMap<K,V> extends LinkedHashMap<K,V> {
/**
* 定一缓存容量
*/
private int capacity;
LRUCacheLinkedHashMap(int capacity){
// AccessOrder = true
super(capacity,0.75f,true);
this.capacity = capacity;
}
/**
* 实现LRU的关键方法,如果 map 里面的元素个数大于了缓存最大容量,则删除链表的顶端元素
*
* @param eldest
* @return
*/
@Override
public boolean removeEldestEntry(Map.Entry<K, V> eldest){
System.out.println(eldest.getKey() + "=" + eldest.getValue());
return size()>capacity;
}
@Override
public synchronized V get(Object key) {
return super.get(key);
}
@Override
public synchronized V put(K key, V value) {
return super.put(key, value);
}
}
验证
public static void main(String[] args){
LRUCacheLinkedHashMap cache = new LRUCacheLinkedHashMap(5);
cache.put("1","a");
cache.put("2","b");
cache.put("3","c");
cache.put("4","d");
cache.put("5","e");
System.out.println("插入 5 个元素后的顺序");
printlnCache(cache);
// 插入第 6 个元素
cache.put("6","e");
System.out.println("插入第 6 个元素后的顺序");
printlnCache(cache);
// 访问 第 3 个元素
cache.get("3");
System.out.println("访问元素 3 后的顺序");
printlnCache(cache);
}
private static void printlnCache(LRUCacheLinkedHashMap cacheMap){
for(Iterator<Map.Entry<String,String>> it = cacheMap.entrySet().iterator(); it.hasNext();){
System.out.print(it.next().getKey() + " ");
}
System.out.println();
}
运行结果:
插入 5 个元素后的顺序
1 2 3 4 5
插入第 6 个元素后的顺序
2 3 4 5 6
访问元素 3 后的顺序
2 4 5 6 3
运行结果完全符合我们的预期
使用组合的方式可能会更加优雅些,但是由于没有实现 Map 接口,所以就不能使用 Collections.synchronizedMap()
方式来保证线程安全性了,所以需要在每个方法处增加 synchronized 来确保线程安全。实现方式如下:
public class LRUCache<K,V> {
private int capacity;
private Map<K,V> cacheMap;
public LRUCache(int capacity){
this.capacity = capacity;
cacheMap = new LinkedHashMap<>(capacity,0.75f,true);
}
public synchronized void put(K k,V v){
cacheMap.put(k,v);
// 移除第一个元素
if(cacheMap.size() > capacity){
K first = this.keyIterator().next();
cacheMap.remove(first);
}
}
public synchronized V get(K k){
return cacheMap.get(k);
}
public Iterator<K> keyIterator(){
return cacheMap.keySet().iterator();
}
}
验证:
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(5);
lruCache.put("1","a");
lruCache.put("2","b");
lruCache.put("3","c");
lruCache.put("4","d");
lruCache.put("5","e");
System.out.println("插入 5 个元素后的顺序");
println(lruCache);
// 插入第 6 个元素
lruCache.put("6","e");
System.out.println("插入 第 6 个元素后的顺序");
println(lruCache);
// 访问 第 3 个元素
lruCache.get("3");
System.out.println("访问元素 3 后的顺序");
println(lruCache);
}
private static void println(LRUCache lruCache){
for(Iterator it = lruCache.keyIterator(); it.hasNext();){
System.out.print(it.next() + " ");
}
System.out.println();
}
运行结果如下:
插入 5 个元素后的顺序
1 2 3 4 5
插入 第 6 个元素后的顺序
2 3 4 5 6
访问元素 3 后的顺序
2 4 5 6 3
组合的方式也显得非常简单,有两点需要注意:
removeEldestEntry()
,如下: cacheMap = new LinkedHashMap<K,V>(capacity,0.75f,true){
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size()>capacity;
}
};
我们想想,在不利用现存数据结构的条件(如 LinkedHashMap)如何实现一个 LRU 呢?缓存部分容易实现,我们都知道利用 HashMap 即可,但是如何实现缓存容量不足时丢弃最不常用的数据的功能?
public class LinkedLRUCache<K,V> {
private int capacity;
private Map<K,LRUNode> map;
private LRUNode head;
private LRUNode tail;
LinkedLRUCache(int capacity){
this.capacity = capacity;
this.map = new HashMap<>();
}
public synchronized void put(K k,V v){
LRUNode node = map.get(k);
// 存在该 key,将节点的设置为 head
if(node != null){
node.value = v;
remove(node,false);
}else{
/**
* 该节点不存在
* 1、将该节点加入缓存
* 2、设置该节点为 head
* 3、判断是否超出容量
*/
node = new LRUNode(k,v);
if(map.size() >= capacity){
//删除 tail 节点
remove(tail,true);
}
map.put(k,node);
setHead(node);
}
// 设置当前节点为首节点
setHead(node);
}
public Object get(String key) {
LRUNode node = map.get(key);
if (node != null) {
// 将刚操作的元素放到head
remove(node, false);
setHead(node);
return node.value;
}
return null;
}
/**
* 设置头结点
*
* @param node
*/
private void setHead(LRUNode node) {
if(head != null){
node.next = head;
head.prev = node;
}
head = node;
if(tail == null){
tail = node;
}
}
/**
* 从链表中删除此Node
*
* @param node
* @param flag 为 true 就删除该节点的 key
*/
private void remove(LRUNode node,boolean flag) {
if (node.prev != null) {
node.prev.next = node.next;
} else {
head = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
} else {
tail = node.prev;
}
node.next = null;
node.prev = null;
if (flag) {
map.remove(node.key);
}
}
private Iterator iterator(){
return map.keySet().iterator();
}
private class LRUNode<K,V> {
/**
* cache 的 key
*/
private K key;
/**
* cache 的 value
*/
private V value;
private LRUNode next;
private LRUNode prev;
LRUNode(K key, V value) {
this.key = key;
this.value = value;
}
}
}
验证
public static void main(String[] args){
LRUCache lruCache = new LRUCache(5);
lruCache.put("1","a");
lruCache.put("2","b");
lruCache.put("3","c");
lruCache.put("4","d");
lruCache.put("5","e");
System.out.println("插入 5 个元素");
println(lruCache);
System.out.println("插入 3 元素");
lruCache.put("3","c");
println(lruCache);
System.out.println("插入第 6 个元素");
lruCache.put("6","f");
println(lruCache);
System.out.println("访问 4 元素");
lruCache.get("4");
println(lruCache);
}
private static void println(LRUCache lruCache){
Iterator iterator = lruCache.keyIterator();
while (iterator.hasNext()){
System.out.print(iterator.next() + " ");
}
System.out.println();
}
执行结果:
插入 5 个元素
1 2 3 4 5
插入 3 元素
1 2 4 5 3
插入第 6 个元素
2 4 5 3 6
访问 4 元素
2 5 3 6 4
文章浏览阅读752次。MockJs可以生成随机数据,拦截 Ajax 请求。Mock.js 的语法规范包括两部分:- 数据模板定义规范(Data Template Definition,DTD)- 数据占位符定义规范(Data Placeholder Definition,DPD)Mock.mock( rURL, function( options ) )当拦截到匹配 rurl 的请求时,函数 function(options) 将被执行,并把执行结果作为响应数据返回。_react axios mock
文章浏览阅读1.1w次。吴恩达十年前首次推出的课程,收获了480万学习者。2022年课程团队对其进更新升级,广泛地介绍了现代机器学习,包括监督学习、无监督学习、以及硅谷AI创新最佳实践。_吴恩达2022 机器学习课程介绍
文章浏览阅读1.1k次。Taro Hooks 实现手机短信验证码const [safePhoneInfo, setSafePhoneInfo] = useState({})const [originalData, setOriginalData] = useState({})const [countDownInfo, setCountDownInfo] = useState({ icode: '', code_ts: '获取验证码', show_btn: true, toast: false,_实现 发送验证码hooks
文章浏览阅读377次。理解Java中的对象内存解析和方法参数传递机制对于Java初学者而言是非常重要的。这不仅有助于编写更高效的代码,而且还能避免在程序设计中出现一些常见的错误。
文章浏览阅读2.6k次,点赞4次,收藏7次。示例说明假设有一个程序,需要接受文字信息并生成学生档案,信息的形式为:"Name:ABC", "Age:20", "Wight:73","Address:Dalian", "Interest:football"程序解析上述信息后,形成以下形式的数据:根据本应用的要求,姓名,年龄和体重三项为必填项,地址和兴趣为可选项。 sizeof...运算符参考前一篇文章的做法,代..._c++11 sizeof...
文章浏览阅读619次。问题所在:是这样的,我使用ajax调用了一串json数据,使用字符串拼接的方法动态插入div容器.结果css并没有对动态插入的内容加css样式.代码描述:css使用的内联,在head部分, jquery使用外联,在body后.我尝试过:$(function(){}) //入口函数加载window.onload = function(){} //原生dom加载(function(){})() ..._ajax异步添加html后样式失效
文章浏览阅读334次,点赞4次,收藏7次。对于网站的设计,要保证主界面的整洁有序,能够抓住人的眼球,不会产生视觉疲劳,更重要的是,带给人容易操作的直观感受,这样才能留住用户去进行使用,增加三分热度的延续期。操作可行性也就是系统的可用性,一个系统的操作是否容易决定着这个系统的使用度,在系统的操作方面的设计我都是采取简洁易懂的方式,操作的整个菜单界面整齐有序,所有的功能都有序的排列,不会出现重叠或者需要转换的现象,用户想要哪方面的操作都可以直接进行操作,所以该系统任何人都可以进行操作,不需要有相关专业的技术这样用户在操作起来就容易很多。
文章浏览阅读2.8k次。查看文档:德邦文档链接【新】下单服务接口融合了标准类的散客电子面单,快递电子面单,零担电子面单所有的下单接口;该接口提供的服务:(1)快递电子面单,零担电子面单和散客电子面单下单,并支持预埋单号或者同步获取运单号;(2)轨迹订阅一切..._调试德邦下单接口
文章浏览阅读4.3k次,点赞3次,收藏10次。一、创建数据库1、创建测试人员统计表CREATE TABLE `daily_test_bug` ( `id` int(11) NOT NULL AUTO_INCREMENT, `user_name` varchar(50) DEFAULT NULL COMMENT '开发账号', `test_name` varchar(20) DEFAULT NULL, `project_name` varchar(100) DEFAULT NULL COMMENT '项目名称', `Itera..._jira问题统计分析
文章浏览阅读857次。树莓派Raspberry Zero W (无外接屏幕)登陆遇到的问题及解决办法SSH远程登陆1. IP端口扫描软件扫描不到树莓派的IP地址2. 输入有卡顿,或者不显示输入字符串口登陆1. 无法输入**第一种:软件终端只有一个绿光标在闪,没有任何字****第二种:出现了加载时的输出和登陆的提示,光标在用户名那里闪动,但无法输入**2. 字体都是白色SSH远程登陆前置条件:sd卡已经烧录了操作系统,且配好了ssh文件和wpa_supplicant.conf文件启动顺序:给树莓派供电,等待几分钟。_zerow无显示器登录系统
文章浏览阅读5.2k次,点赞2次,收藏31次。当需要批量处理EXCEL文件时,手动处理太耗时间且可能出错,由于电脑上有Matlab,因此尝试了使用Matlab进行EXCEL文件的编辑,效果很好因此在这里向大家分享简单的使用方法。通过matlab自带的几个基本函数,对于excel文件进行批量处理,提高了办公效率,未来也会分享一些工作中使用到的实用代码。..._matlab实现excel修改
文章浏览阅读3w次,点赞53次,收藏204次。认识Flask-SQLAlchemyFlask-SQLAlchemy 是一个为 Flask 应用增加 SQLAlchemy 支持的扩展。它致力于简化在 Flask 中 SQLAlchemy 的使用。SQLAlchemy 是目前python中最强大的 ORM框架, 功能全面, 使用简单。ORM优缺点优点有语法提示, 省去自己拼写SQL,保证SQL语法的正确性orm提供方言功能(dialect, 可以转换为多种数据库的语法), 减少学习成本防止sql注入攻击搭配数据迁移, 更新数据库方便_flask_sqlalchemy