LRU 缓存

要点：双向链表+hashmap，第三遍了，还是不太能顺利写完

class LRUCache {
    //最近最少
    //使用了放在最前面，超出size从后面开始删除
    //不是，环形链表
    //找到node， 放在前面， 删除
    //双向链表+hashmap
    public class ListNode{
        int val;
        int key;
        ListNode pre;
        ListNode next;

        ListNode(int key, int val){
            this.key = key;
            this.val = val;
        }
    }

    Map<Integer, ListNode> map;
    ListNode dummy;
    int capacity;
    

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        dummy = new ListNode(0,0);
        dummy.next = dummy;
        dummy.pre = dummy;
        
    }
    
    public int get(int key) {
        ListNode node = map.get(key);
        if(node != null){
            getNode(node);
            return node.val;
        }else{
            return -1;
        }
        
    }
    
    public void put(int key, int value) {
        ListNode node = map.get(key);
        if(node != null){
            node.val = value;
            getNode(node);
        }else{
            ListNode tempnode = new ListNode(key, value);
            map.put(key, tempnode);
            toFirst(tempnode);
        }

        while(map.size() > capacity){
            ListNode last = dummy.pre;
            map.remove(last.key, last);
            remove(last);
        }
        
    }

    public void getNode(ListNode node){
        remove(node);
        toFirst(node);
    }

    public void remove(ListNode node){
        node.next.pre = node.pre;
        node.pre.next = node.next;
    }


    public void toFirst(ListNode node){
        node.pre = dummy;
        node.next = dummy.next;
        node.next.pre = node;
        node.pre.next = node;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

随机知识

GC算法与G1、CMS核心对比 学习笔记

一、GC存活判定算法

1. 引用计数法（JVM不采用）

原理：对象每多一个引用，计数器+1；引用失效，计数器-1；计数为0则回收。

核心缺陷（面试必背）：

• 无法解决循环引用问题：两个对象互相引用，计数器永不为0，导致内存泄漏。

• 额外内存开销：每个对象需要单独存储计数器。

• 并发场景下引用计数增减需要加锁，性能低下。

2. 可达性分析算法（HotSpot JVM 主流）

原理：以 GC Roots 为起始链路遍历内存，可达对象存活，不可达对象判定为垃圾、等待回收。

常用 GC Roots：

• 虚拟机栈（栈帧局部变量）引用的对象

• 本地方法栈 Native 引用的对象

• 方法区中静态变量、常量引用的对象

• Synchronized 锁持有对象

• JVM 系统内部引用（Class对象、系统异常、类加载器等）

二、四大基础GC算法（原理+优缺点+场景）

手绘背诵版对比表（核心考点）

算法	执行流程	优点	缺点	适用场景
引用计数	引用+1/释放-1，计数为0回收	即时回收、无STW、逻辑简单	循环引用无法回收、有开销、并发低效	JVM堆不使用
标记-清除	1.标记存活对象；2.统一清除垃圾	无需移动对象、无复制开销	产生大量内存碎片、大对象分配容易OOM	老年代、CMS底层算法
标记-复制	内存分两块，存活对象复制到空闲区，清空原区域	无内存碎片、内存分配快、STW短	内存利用率仅50%、存活对象多的时候复制开销大	新生代 Minor GC
标记-整理	1.标记存活对象；2.向内存一端压缩移动、清空尾部垃圾	无内存碎片、内存利用率100%	需要移动对象、STW停顿时间最长	老年代 Serial Old / Parallel Old

三、CMS 与 G1 核心区别（重点）

1. 底层本质

• CMS：基于 标记-清除，传统整体分代堆（新生代、老年代连续内存）

• G1：基于 分区标记+局部整理，堆被切分为多个等大小 Region，逻辑分代、物理不分代

2. 关键差异汇总

• 内存碎片：CMS 大量碎片；G1 局部压缩，几乎无碎片

• 停顿控制：CMS 停顿不可预测；G1 支持 MaxGCPauseMillis 可控延迟

• 回收范围：CMS 每次扫描整个老年代；G1 只回收垃圾最多的 Region（收益优先）

• 大对象支持：CMS 无专门区域，极易产生碎片；G1 有 Humongous 大对象分区

• 并发失败：CMS 大堆高并发极易并发失败、退化为单线程Full GC；G1 概率极低

• Full GC 性能：CMS 单线程整理、停顿极长；G1 多线程并行整理、速度更快

四、简答题标准答案：为什么 G1 更适合大堆？

（可直接背诵、打字提交、面试口述）

第一，解决内存碎片问题。CMS 基于标记清除，不整理内存，大堆长期运行会积累大量碎片，分配大对象时找不到连续空间，频繁触发Full GC；而 G1 以Region为单位局部回收并压缩，从根源避免内存碎片，适合超大堆长期稳定运行。

第二，GC停顿可控。CMS 必须扫描完整老年代，堆越大GC耗时越长，停顿完全不可控；G1 采用分区回收策略，每次只选择垃圾收益最高的部分Region回收，不用扫描整堆，同时支持自定义最大停顿时间，大堆场景延迟稳定。

第三，避免并发失败雪崩。CMS 并发阶段需要预留堆内存存放新对象，大堆高并发场景极易耗尽预留空间，触发并发失败，退化为单线程串行Full GC，造成长时间卡顿；G1 内存分配更灵活，大幅降低并发失败概率。

第四，适配超大对象。G1 专门设计Humongous Region存储大对象，独立回收、不产生碎片；CMS 大对象直接进入老年代，会严重加剧碎片问题，导致大堆服务频繁GC卡顿。

第五，Full GC 性能更强。CMS Full GC为单线程执行，大堆下停顿可达分钟级；G1 采用多线程并行整理，Full GC耗时大幅缩短，故障影响更小。

五、极简口述版（录音背诵专用）

G1相比CMS更适合大堆，核心有四点：一是G1局部压缩无内存碎片，CMS标记清除碎片严重；二是G1分区回收、停顿可控，CMS整堆扫描、延迟不可控；三是G1有专门大对象分区，适配超大对象，CMS大对象极易造成内存碎片；四是大并发下CMS容易并发失败、单线程Full GC卡顿严重，而G1并发更稳定、Full GC多线程速度更快。

碎碎念：后续会更新每天学习的八股和算法  题，开始准备秋招的第43/44天。努力连续更新100天！以后每天就按，秋招项目【java +agent】，科研，必做项目，算法，八股，锻炼身体来总结。

总结：团建+干实习杂活

1.算法面试150  83/150  1h

2.秋招项目，【java 项目】，【修改，2h】，

【agent 项目 】，【修改，1h】，两个应该都是跑通了，准备开背！

3.科研要跑一下，2-3h，慢慢有点头绪了

4.检测项目，

6.背八股，

7.锻炼身体，无

反思：一切都会更好，相信自己，相信自己有解决问题的能力