…目录

3.JDK中类似LRUCahe的数据结构LinkedHashMap

4.OJ练习

什么是Cache狭义的Cache指的是位于CPU和主存间的快速RAM

通常它不像系统主存那样使用DRAM技术而使用昂贵但较快速的SRAM技术。

用于协调两者数据传输速度差异的结构。

除了CPU与主存之间有Cache

内存与硬盘之间也有Cache乃至在硬盘与网络之间也有某种意义上的Cache──

Cache的容量有限因此当Cache的容量用完后而又有新的内容需要添加进来时

Cache

哈希表查找速度快O(1)双向链表插入和删除的时间复杂度比较快O1

head

3.JDK中类似LRUCahe的数据结构LinkedHashMap

initialCapacity初始容量大小loadFactor

加载因子accessOrder

LinkedHashMap(16,0.75f,false);map.put(1,

a);map.put(2,

LinkedHashMap(16,0.75f,true);map.put(1,

a);map.put(2,

c);map.get(1);map.get(2);System.out.println(map);

输出结果

当accessOrder为true时get方法和put方法都会调用recordAccess方法使得最近使用的Entry移到双向链表的末尾当accessOrder为默认值false时从源码中可以看出recordAccess方法什么也不会做

4.OJ练习

https://leetcode-cn.com/problems/lru-cache/

1get方法存在否-存在需refresh

3refresh:删除放到链表头部/尾部(注意步骤4一定得在步骤1的后面

class

map.get(key);refresh(node);return

node.val;}return

tail.prev;//这里得记录下来不然删了另一个就删不了map.remove(del.key);delete(del);}//放入mapnode

new

DLinkNode(key,value);map.put(key,node);}refresh(node);}//放到链表头部(删除放置)public

void

{delete(node);//删除指定节点node.next

node;node.prev

{/**第3个参数的意思当accessOrder设置为false时会按照插入顺序进行排序当accessOrder为true是会按照访问顺

序也就是插入和访问都会将当前节点放置到尾部尾部代表的是最近访问的数据这和JDK1.6是反过来

的jdk1.6头部是最近访问的。

*/super(capacity,0.75F,true);this.capacity

capacity;

removeEldestEntry(Map.EntryInteger,

Integer

LRUCache(3);//尾插法插入lruCache.put(2,1);lruCache.put(3,1);lruCache.put(4,1);System.out.println(lruCache);//{21,

31,

41}System.out.println(lruCache.get(2));//1

并且放到链表的尾巴System.out.println(lruCache);//{

31,

将n个不同的元素划分成一些不相交的集合开始时每个元素自己都是单元素集合然后按照一定的规律将归于同一组元素的集合合并这个过程需要反复用到查询某个元素归属哪个集合的运算

2)具体例子理解

某公司今年校招全国总共招生10人西安招4人成都招3人武汉招3人10个人来自不同的学校起先互不相识每个学生都是一个独立的小团体现给这些学生进行编号集合树形表示

西安学生小分队s1{0,6,7,8}成都学生小分队s2{1,4,9}武汉学生小分队s3{2,3,5}就相互认识了10个人形成了三个小团体。

假设右三个群主0,1,2担任队长并查集表示

合并1和8

在公司工作一段时间后西安小分队中8号同学与成都小分队1号同学奇迹般的走到了一起两个小圈子的学生相互介绍最后成为了一个小圈子

查找元素属于哪个集合

沿着数组表示树形关系以上一直找到根(即树中中元素为负数的位置)查看两个元素是否属于同一个集合

沿着数组表示的树形关系往上一直找到树的根如果根相同表明在同一个集合否则不在将两个集合归并成一个集合

将一个集合加入另一个集合