首页  思维导图  详情

温故知新

2025-02-07 23:26:34   0  举报





仅支持查看

AI智能生成

温故知新

架构

作者其他创作

大纲/内容

Java

并发

线程池

线程池各参数含义

corePoolSize -> 该线程池中核心线程数最大值。
在创建完线程池之后，核心线程先不创建，在接到任务之后创建核心线程。
会一直存在于线程池中（除非设置allowCoreThreadTimeOut为true），有任务要执行时，如果核心线程没有被占用，会优先用核心线程执行任务。
maximumPoolSize -> 该线程池中线程总数最大值（核心线程数+非核心线程数）
keepAliveTime -> 非核心线程闲置超时时长
BlockingQueue workQueue -> 线程池中的任务队列
RejectedExecutionHandler handler -> 饱和策略（默认是AbordPolicy）

Java为我们提供的4种线程池

FixedThreadPool：只有核心线程，配合LinkedBlockingQueue使用

CachedThreadPool：全部是非核心线程，且无上限，配合SynchronousQueue使用

SingleThreadExecutor：只有1个核心线程，配合LinkedBlockingQueue使用

ScheduledThreadPool：主要用于定时延时或者定期处理任务，只有核心线程，配合DelayedWorkQueue使用

线程池工作流程

各BlockingQueue子类的区别

LinkedBlockingQueue

SynchronousQueue

ArrayBlockingQueue

PriorityBlockingQueue

线程的各种操作

interrupt()

interrupt()方法会根据thread线程中的run方法里正在运行的代码是否有必须捕获InterruptedException异常的代码，而做出不同操作：

（1）如果正在运行的代码没有必须捕获InterruptedException异常的代码(比如sleep()、wait())，则isInterrupted()返回true，此时可以在isInterrupted的判断中处理中断变化。
（2）如果正在运行的代码有必须捕获InterruptedException异常的代码(比如sleep()、wait())，则会抛出InterruptedException异常，并进行捕获，同时重置isInterrupted为false，此时得在异常捕获中处理中断变化。

https://juejin.cn/post/7158373229201981453?searchId=2024061417283209FCDDD059424C983B47

suspend()、resume()和stop()已过期，不要用。他们会导致线程状态不确定或死锁。

wait()/notify()/notifyAll()

1）使用wait()、notify()和notifyAll()时需要先对调用对象加锁。
2）调用wait()方法后，线程状态由RUNNING变为WAITING，并将当前线程放置到对象的
等待队列。
3）notify()或notifyAll()方法调用后，等待线程依旧不会从wait()返回，需要调用notify()或
notifyAll()的线程释放锁之后，等待线程才有机会从wait()返回。
4）notify()方法将等待队列中的一个等待线程从等待队列中移到同步队列中，而notifyAll()
方法则是将等待队列中所有的线程全部移到同步队列，被移动的线程状态由WAITING变为
BLOCKED。
5）从wait()方法返回的前提是获得了调用对象的锁。

注意：
是调用锁对象的wait/notify

生产者/消费者的经典范式

生产者：
1）获得对象的锁。
2）改变条件。
3）通知所有等待在对象上的线程。

消费者：
1）获取对象的锁。
2）如果条件不满足，那么调用对象的wait()方法，被通知后仍要检查条件。
3）条件满足则执行对应的逻辑。

join()

在线程A中调用线程B的join方法，意思是让A等待B执行完，再继续执行A中的后续操作。
join中调用了wait方法，即在执行当前代码的线程进入WAITING状态。

如何避免死锁

（1）避免一个线程同时获取多个锁。
（2）尝试使用定时锁，使用lock.tryLock（timeout）来替代使用内部锁机制。

对象在内存中的存储布局，如果是Object o = new Object()，则引用o另外占4个字节

CAS

https://www.bilibili.com/video/BV1QB4y1v7Si?p=3&vd_source=e94924c1f8e30e4cf6bb1ad68154c0b6
08:00~15:00

锁的分类

偏向锁：不是一种锁，而是在只有单个线程执行的时候，直接获取锁，而不需要参与锁竞争的一个策略。
轻量级锁：自旋锁，即一直循环等待，不需要放到队列里由操作系统调度。
重量级锁：放到队列中，由系统调度，此过程会切换到内核态。
轻量级锁不一定比重量级锁效率高，要看场景，如果前一个锁住的操作很快执行完，则前者效率高。如果执行慢且尝试获取锁的现成多，则后者效率高，因为自旋和线程切换也会消耗cpu资源。

锁的升级过程：偏向锁->轻量级锁->重量级锁

https://github.com/JsonChao/Awesome-Android-Interview/blob/master/Java%E7%9B%B8%E5%85%B3/Java%E5%B9%B6%E5%8F%91%E9%9D%A2%E8%AF%95%E9%A2%98.md

锁的优缺点对比

锁消除

锁粗化

volatile作用

（1）保证线程间可见性
（2）保证有序性（禁止指令重排序）
但不能保证原子性

可见性

可见性：https://www.bilibili.com/video/BV1QB4y1v7Si/?p=9&vd_source=e94924c1f8e30e4cf6bb1ad68154c0b6

缓存行与有序性：https://www.bilibili.com/video/BV1QB4y1v7Si?p=8&vd_source=e94924c1f8e30e4cf6bb1ad68154c0b6

https://github.com/JsonChao/Awesome-Android-Interview/blob/master/Java%E7%9B%B8%E5%85%B3/Java%E5%B9%B6%E5%8F%91%E9%9D%A2%E8%AF%95%E9%A2%98.md

对象创建过程

DCL（双重检查锁）

其中volatile是为了保证代码的有序性，即防止对象创建过程中【执行构造】和【指向内存】顺序互换

cache line（缓存行）

cpu与主存间传输数据的最小单位，64字节。
缓存行对齐可以避免不相干的数据放入同一个缓存行，导致频繁的线程间同步数据，提升效率。

synchronized

实现过程：
代码中：synchronized关键字
字节码中：monitorenter，monitorexit
运行时：锁的升级过程
汇编中：lock cmpxchg

synchrozied能保证可见性和原子性，不能保证有序性

AQS

基于state来提供获取和释放锁的操作。一个双向队列存放等待获取锁的线程。
state分为独占模式和共享模式，如ReentrantLock为独占，CountDownLatch为共享。
AQS提供并发同步的基本抽象，具体实现由子类重写，比如AQS并不关心state如何获取和改变，都由子类实现。

https://juejin.cn/post/6896278031317663751?searchId=20240531174756F9D667F70B8D97144C97

JUC中的锁

ReentrantLock

ReentrantLock：是一种自旋锁，通过循环调用CAS（compareAndSwap）操作来实现加锁。
--公平锁还是非公平锁；
--Condition实现分组唤醒线程；
--中断获取锁机制，获取锁的过程可以被中断（lockInterruptibly()）。
--获取锁超时机制，可以设置获取锁的超时时间（tryLock()）；

ReentrantReadWriteLock

CountDownLatch

CyclicBarrier

Semaphore

类加载

双亲委托

先从当前加载器缓存中找，如果没有再委托给父加载器，如果到最顶层仍未找到，则开始加载。如果加载失败，则委托给子加载器，直到最顶层如果还加载失败，则抛出ClassNotFound异常。如果要保持双亲委托逻辑，则重写findClass，如果要破坏此逻辑，则重写loadClass。

Android类加载器的继承关系

类加载在代码中的执行过程

判断两个类相等的三个条件：来自同一个.class文件，同一个JVM，由同一个ClassLoader加载。
如果想保持双亲委托机制，则重写findClass，如果想破坏双亲委托，则重写loadClass
自定义ClassLoader：https://blog.csdn.net/is_zhoufeng/article/details/26602689

类的加载过程生命周期？
https://blog.csdn.net/sinat_19650093/article/details/50939132

JVM内存结构

虚拟机栈：存放局部变量表，方法返回地址等信息
本地方法栈：
程序计数器：当前代码执行位置
方法区：类信息，静态变量，常量
堆：对象实例和数组

垃圾回收

https://www.cnblogs.com/xiaoxi/p/6486852.html
https://www.bilibili.com/video/BV1xq4y1d7VT/?spm_id_from=333.337.search-card.all.click&vd_source=e94924c1f8e30e4cf6bb1ad68154c0b6

GC root

(1). 虚拟机栈（栈帧中的局部变量区，也叫做局部变量表）中引用的对象。

(2). 方法区中的类静态属性引用的对象。

(3). 方法区中常量引用的对象。

(4). 本地方法栈中JNI(Native方法)引用的对象。

GC收集算法

复制算法一般用于分代收集法的新生代中，因为新生代对象存活率低，复制成本低，没有碎片。但空间利用率只有一半；
标记清除法一般用于分代收集法中的老年代，内存碎片化严重；
标记整理法一般用于分代收集法的老年代中，因为老年代对象存活率高，没有额外空间进行分配担保。对象移动更新导致效率低；

分代收集

什么情况内存栈溢出？

无限递归调用方法

new一个对象的过程

对象会不会分配在栈中？

当一个对象不会逃逸时，则栈上分配
https://mp.weixin.qq.com/s/t4ykXwJ7PbLY3K3JSOw-0A
https://mp.weixin.qq.com/s/rGxzpeAY40WDXDmIJKXicw

引用类型

强：不会被回收
软：内存不够时被回收。用作缓存。
弱：被垃圾回收期发现即被回收
虚：用来管理堆外内存（直接内存）

虚引用的使用场景

equals与hasCode

下面是使用hashCode()与equals()的相关规定：
（1）如果两个对象相等（即用 equals 比较返回 true），则 hashcode 一定也是相同的;
（2）两个对象有相同的 hashcode 值，它们也不一定是相等的（不同的对象也可能产生相同的
hashcode，概率性问题）;
（3）equals 方法被覆盖过，则 hashCode 方法也必须被覆盖。

为什么必须要重写 hashcode 方法？其实就是为了保证同一个对象，保证在 equals 相同的情况下
hashcode 值必定相同，如果重写了 equals 而未重写 hashcode 方法，可能就会出现两个没有关系的
对象 equals 相同的（因为 equals 都是根据对象的特征进行重写的），但 hashcode 确不相同的。

集合

HashMap

https://blog.csdn.net/duan19920101/article/details/51579136
1.7版本：https://blog.csdn.net/carson_ho/article/details/79373026
1.8版本：https://blog.csdn.net/carson_ho/article/details/79373134

红黑树

为什么使用红黑树？
如果使用链表，当数据太大时，复杂度为O(n)，而二叉树是O(logN)。
又因为AVL树平衡条件苛刻（最大高度与最小高度之差不能大于1），频繁旋转树也会有额外开销，
所以采用红黑树（平衡条件是最大路径节点数小于最短路径的两倍）。

CurrentHashMap

其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap，相对而言，ConcurrentHashMap只是增加了同步的操作来控制并发，从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树。
1.数据结构：取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。2.保证线程安全机制：JDK1.7采用segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。3.锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。4.链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。

CopyOnWriteArrayList

CopyOnWriteArrayList这是一个ArrayList的线程安全的变体，CopyOnWriteArrayList 底层实现添加的原理是先copy出一个容器(可以简称副本)，再往新的容器里添加这个新的数据，最后把新的容器的引用地址赋值给了之前那个旧的的容器地址，但是在添加这个数据的期间，其他线程如果要去读取数据，仍然是读取到旧的容器里的数据。如果你需要在多线程环境下进行读操作远远多于写操作，并且对实时性要求不高，可以考虑使用。

反射

1.反射为啥慢？
因为反射中的native代码无法被jvm优化。

动态代理

https://www.bilibili.com/video/BV1tY411Z799?p=5&spm_id_from=pageDriver&vd_source=e94924c1f8e30e4cf6bb1ad68154c0b6

https://juejin.cn/post/6844903744954433544

原理图

注解

泛型

extends和super

桥方法：为了保证接口和类的实现关系

序列化

transient

Parcelable与Serializable

设计模式

单例

DCL方式

静态内部类的方式
好处：静态内部类与外部类，没有绑定关系，只有第一次调用getInstance时才会实例化SingletonCase2对象，
延迟了对象的创建，并且静态初始化可以由JVM保证线程安全。

设计原则

S.O.L.I.D

单一职责、开闭、里氏代换、接口隔离、依赖倒转
https://juejin.cn/post/6844903461172051982?searchId=20240617105953C3D8CC5FE05FA3121BF9

各种内部类

深拷贝&浅拷贝

异常体系

String

https://github.com/Omooo/Android_QA/blob/master/Answer.md#java_advance_14

HTTP与HTTPS

三次握手与四次挥手

https://www.cnblogs.com/lhy-qingqiu/p/16727388.html

为什么三次握手？
需要三次握手才能确认双方的接收与发送能力是否都正常。

为什么四次挥手？
当服务端收到FIN报文时，很可能并不会立即关闭SOCKET，所以只能先回复一个ACK报文，告诉客户端，“你发的FIN报文我收到了”。只有等到我服务端所有的报文都发送完了，我才能发送FIN报文，因此不能一起发送。故需要四次挥手。

HTTPS的流程

1.客户端发送请求到服务端；
2.服务端将数字证书发给客户端；
2.1.服务端自己的pub key和其他信息做hash计算，生成消息摘要；
2.2.用CA机构的pri key对消息摘要加密，生成数字签名；
2.3.pub key和其他信息+数字签名放到一起，形成数字证书，传给客户端；
3.客户端拿到数字证书校验是否被篡改；
3.1.拿到数字证书中保存的服务端的pub key和其他信息，用同样的hash算法生成消息摘要；
3.2.再用CA机构的pub key对数字签名解密，还原生成签名前的摘要；
3.3.将两个消息摘要作比较，如果相同则验证通过，如果不同，做出风险提示；
4.客户端验证通过后，生成自己的对称加密秘钥；
5.客户端用服务端传来的pub key将自己生成的秘钥加密，传给服务端；
6.服务端用自己的pri key解密，拿到客户端的对称加密秘钥；
7.之后的通信过程，都用对称秘钥加密。

什么是JIT（即时编译）？

https://www.bilibili.com/video/BV1Y8411R7DC/?spm_id_from=333.337.search-card.all.click&vd_source=e94924c1f8e30e4cf6bb1ad68154c0b6

32位与64位的区别

Android

Activity与Fragment生命周期

https://blog.csdn.net/flueky/article/details/51581346

Activity与Fragment之间传参

Activity启动模式

Standard：标准模式，也是默认模式。每次启动都会创建一个全新的实例。
SingleTop：栈顶复用模式。这种模式下如果Activity位于栈顶，不会新建实例。onNewIntent会
被调用，接收新的请求信息，不会再调用用onCreate和onStart。
SingleTask：栈内复用模式。如果栈内有实例，则复用，并会将该实例之上的Activity全部清除。
SingleInstance：系统会为它创建一个单独的任务栈，并且这个实例独立运行在一个 task中，这
个task只有这个实例，不允许有别的Activity 存在（可以理解为手机内只有一个）。

SingleTask需要配合taskAffinity使用，否则无效

https://blog.csdn.net/w1142203475/article/details/134975029

Service启动与生命周期

IntentService

内部是HandlerThread在子线程发一个消息，在消息中执行onHandleIntent()

View绘制流程

View的测量与布局

https://www.bilibili.com/video/BV1YK4y1G7US?p=5&vd_source=e94924c1f8e30e4cf6bb1ad68154c0b6

Android屏幕刷新机制

invalidate与postInvalidate

requestLayout与invalidate

getMeasuredWidth与getWidth的区别

前者是在onMeasure执行完就有值

后者是onLayout执行后，通过getRight() - getLeft()计算出来的

View事件分发

https://juejin.cn/post/6922300686638153736?searchId=20240523153120CE5BE9286A2F841F4AC1

如果View.OnTouchListener#onTouch返回true，则View#onTouchEvent不会被执行，
且因为View.OnClickListener#onClick在onTouchEvent中被调用，所以onClick也不会被执行

进程间通信

Binder的通信过程

参考资料

https://juejin.cn/post/6844903589635162126?searchId=202405271010533E2E4CF0624D3A37072E

mmap原理

UI的创建与刷新流程

https://www.processon.com/view/link/6655d1f4d8de3304a029098a

Activity、Window、DecorView、ViewRootImpl关系

https://juejin.cn/post/6844903974294781965?searchId=202405231628136D097950CDEB557864C9

attach：创建PhoneWindow
onCreate&setContentView：window.setContentView-》创建DecorView-》DecorView.setWindow
onResume：wm.addView(decor)-》创建ViewRootImpl-》root.setView(decor)-》requestLayout-》scheduleTraversals-》mWindowSession.addToDisplay

scheduleTraversals流程

为什么子线程不能更新UI？

子线程可以更新UI，只不过更新的操作要和添加window在同一个线程中才行。
另外1，子线程是可以显示toast、dialog、popupWindow，自定义window，要在子线程前后加prepare()和loop()，保证IPC通信后回调到当前线程。
另外2，在onCreate和首次onResume时期是可以更新UI的，因为添加window是在onResume之后执行。

Activity启动过程

普通Activity

关键API：
Instrumentation：具有跟踪Activity生命周期的能力，用于测试框架中代码检测
ActivityThread：管理应用进程中主线程的执行，调度和执行AMS请求的关于activity，broadcast等操作
ApplicationThread：用于IPC过程中，AMS调用App进程
H：用于将binder线程的切换到主线程执行消息

AMS：system_server进程中Activity管理服务。
通过ActivityStarter、ActivityStack、ActivityStackSupervisor 对 Activity任务、activity栈、Activity记录管理。

根Activity

根activity的启动前需要创建应用进程，然后走到ActivityThread的main方法，开启主线程循环，初始化并绑定Application、赋值IApplicationThread，最后真正的启动过程和普通Activity是一致的。

https://juejin.cn/post/6847902222294990862

App启动过程

ThreadLocal

Handler工作原理

发送和处理消息代码流程

当没有新消息时，MessageQueue#next()会阻塞。
如果子线程在不使用Handler时应该调用Looper#quit()退出。quit()的作用是先唤醒阻塞的线程，
然后mQuitting设为true，这时再调用MessageQueue#next()会返回null，而Looper#loop()判断了如果msg=null则直接return。

Message#obtain()使用了享元模式进行内存复用。
因为message频繁被使用，为了防止频繁创建和回收导致内存碎片化，进而防止OOM。

同步屏障：
next()取消息时，遇到msg.target=null则视为屏障（消息屏障也是一个消息，只不过target为null），然后遍历找到msg.isAsynchronous()为true的消息优先执行。postSyncBarrier()与removeSyncBarrier()为设置和移除同步屏障。可以参考ViewRootImpl#scheduleTraversals()的过程。

HandlerThread

优点：方便获取子线程的Looper，并解决获取Looper的线程安全问题。

关键代码

RecyclerView优化

共享对象池RecyclerView#setRecycledViewPool(mSharedPool)

避免在循环内创建对象导致GC

Prefetch

插值器与估值器

插值器，Interpolator，根据时间流逝的百分比计算出属性改变的百分比，
或者说是计算动画从开始到结束的过程中，属性值的变化规律。
估值器，Evaluator，根据插值器算出的fraction，动画初始值和结束值，
设置动画的具体属性值，fraction即为Interpolator#getInterpolation的返回值。
https://blog.csdn.net/carson_ho/article/details/72863901

AOT的优点

ART虚拟机的垃圾回收

Parcelable 与 Serializable

（1）Serializable 使用 I/O 读写存储在硬盘上，而 Parcelable 是直接在内存中读写。
（2）Serializable 会使用反射，序列化和反序列化过程需要大量 I/O 操作， Parcelable 自已实现封送和
解封（marshalled &unmarshalled）操作不需要用反射。

MVP & MVVM & MVI

MVC

缺点：
Activity同时负责View与Controller层，Model层与View层存在耦合

MVP

优点：V和P的职责更加清晰
缺点：接口太多，View和Presenter相互持有

MVVM
View层：Activity/Fragment
ViewModel层：Jetpack ViewModel + Jetpack LivaData
Model层：Repository仓库，本地持久性数据和服务端数据

优点：ViewModel不持有View的引用，数据驱动，单一可信源，生命周期感知
缺点：
多数据流： View 与 ViewModel 的交互分散，缺少唯一修改源，不易于追踪；
LiveData 膨胀：复杂的页面需要定义多个 MutableLiveData，并且都需要暴露为不可变的 LiveData。

Lifecycle

目的/本质/好处：
“Lifecycle 本质是实现生命周期组件管理代码修改的一致性”，
“Lifecycle 可让第三方组件在自己内部监听和响应页面生命周期事件”，

关键API：
LifecycleOwner（getLIfecycle）、
LifecycleObserver（用注解监听生命周期，如@OnLifecycleEvent(Lifecycle.Event.ON_CREATE)）、
LIfecycle（addObserver、getCurrentState、Event、State，LifecycleRegistry是Lifecycle的具体实现）
ReportFragment（利用Fragment获取Activity的生命周期，然后调用dispatch处理事件）

LiveData

好处：
数据单一可信源，数据更新对生命周期感知能力

关键API：
LiveData（observe、setValue、dispatchValue、considerNotify、removeObserver会移除LifecycleOwner和Observer，也会移除LifecycleOwner的观察者）
ObserverWrapper（activeStateChanged）（将Observer包了一层）
LIfecycleBoundObserver（onStateChnaged）（继承自ObserverWrapper和LifecycleEventObserver，调用observe时将LifecycleOwner与Observer绑定）

ViewModel

好处：
不持有UI层的引用，生命周期比UI层长
屏幕旋转重建后，ViewModel对象会继续留存

DataBinding

本质：
终态数据与 UI控件的绑定

好处：
1、无需多处调用控件，原本调用的地方只需要set数据即可
2、无需手动判空
3、完全不用写模板代码 findViewById
4、引入DataBinding后，原本的 UI 逻辑无需改动，只需设置终态数据

DataBinding提供的双向绑定，是用来完善Jetpack MVVM 的工具，其本身在业界又非常具有争议性。
掌握本篇内容，已经是Google推荐的开发架构，就已经实现 MVVM 模式。在Google官方的应用架构指南中也同样丝毫没有提到 DataBinding。

ViewBinding

只能解决findviewbyid，不能解决view判空

总之，ViewBinding 是一款适用于 Kotlin 语境的 UI 框架，如你坚持留在 Java 或是 MVVM 开发模式，那么 DataBinding 才是你不二之选。

https://juejin.cn/post/6893870636733890574

https://juejin.cn/post/6923859213403979789

MVVM的数据倒灌问题？

LiveData本身被设计为粘性的，而在Activity与Fragment页面通信场景下，有人会使用SharedViewModel+LiveData的方式，
此时用于通信的ViewModel生命周期长于Fragment，当Fragment销毁重建并监听时，
LiveData会判断自身version大于observer的lastVersion，从而立刻将上次的旧数据发给observer，此为“数据倒灌”

参考：https://xiaozhuanlan.com/topic/6719328450

MVI

Intent 就是在提示你，将原先命令式的函数调用转换成一个事件数据，用响应式编程的方式进行事件到状态的变换，
并且还得保证界面状态有唯一可信数据源，这样界面的刷新就形成了一条单向数据流。

个人理解：Intent就是将MVVM中函数方式调用改为事件数据，就是数据流的进流数据，UIState就是出流数据

所以只要满足“响应式编程”、“单向数据流”、“唯一可信数据源”这三个原则的都可以称之为 MVI。不管使用的是 ViewModel 还是 Presenter。
MVI 关心的不是具体的界面状态持有者，而是整个更新界面数据链路的流动方式和方向。

所以 MVI 和 MVP, MVVM 不同，它关心的不是具体的界面状态持有者，而是整个更新界面的数据链路流动方式和方向。

https://juejin.cn/post/7087717477246369805?searchId=20240613153636D5B3FDB551EEDC01B010

https://juejin.cn/post/7177619630050000954?searchId=202406141510186DDFB114F5A7A889FE8B

https://juejin.cn/post/7022624191723601928?searchId=202409120024143757487F2A9EA0C43845

示例代码：
https://cloud.tencent.com/developer/article/1934805

响应式编程

响应式编程是一种面向数据流和变化传播的声明式编程范式 “数据流”和“变化传播”是相互解释的：有数据流动，就意味着变化会从上游传播到下游。变化从上游传播到下游，就形成了数据流。

“声明式”意思是定义流上数据变换的逻辑并不是立刻执行，只有当数据流流动起来之后才会执行。

插码框架

ASM灵活，但使用难度高

gradle8.0弃用Transform后的替代方案：AsmClassVistorFactory

https://juejin.cn/post/7105925343680135198

https://cloud.tencent.com/developer/article/1951722

aspectj使用简单，但会产生中间代码影响性能

NDK

JNI

插件化

（1）调用插件apk中的代码：DexClassLoader+反射
（2）调用插件apk中的activity：容器Activity占坑+PlugActivity（容器Activity转发来自系统的生命周期回调至插件PlugActivity，同时转发来自插件PlugActivity的API调用至系统）
（3）调用插件apk中的资源：

参考资料：https://juejin.cn/post/6973888932572315678?searchId=2024061809055341E276216A93F895D0D4

热修复

性能调优

OOM

相关资料：
https://juejin.cn/post/7368372944584130601?searchId=20240626152054E517B791992F284F1B9E#heading-8
https://juejin.cn/post/7074762489736478757?searchId=20240626152054E517B791992F284F1B9E

内存指标概念
adb shell dumpsys meminfo

排查方法：
（1）根据用户行为流操作页面，看是否复现
（2）如果能复现，可以直接dump内存快照进行分析，看是否有内存占用高的对象
（3）如果不能复现，使用Memory Profiler观察是否有内存抖动或内存骤增
（4）如果有抖动则看代码是否有频繁创建对象，如在循环中，onDraw等绘制方法
（5）如果怀疑有泄露则退出怀疑页面手动gc两次，看内存是否有降低，然后dump hprof
（6）使用mat分析引用关系，看怀疑的页面是否有泄漏

优化内存的目的：
1）、防止应用发生OOM。
2）、降低应用由于内存过大被LMK机制杀死的概率。
3）、避免不合理使用内存导致GC次数增多，从而导致应用发生卡顿。

内存抖动

原因：
1）、频繁创建对象，导致内存不足及碎片（不连续）。
2）、不连续的内存片无法被分配，导致OOM。

排查方法：
一般使用 Memory Profiler （表现为频繁GC、内存曲线呈锯齿状）结合代码排查即可找到内存抖动出现的地方。
通常的技巧就是着重查看循环或频繁被调用的地方。

如何避免：
1、字符串使用加号拼接
1）、使用StringBuilder替代。
2）、初始化时设置容量，减少StringBuilder的扩容。

2、资源复用
1）、使用全局缓存池，以重用频繁申请和释放的对象。
2）、注意结束使用后，需要手动释放对象池中的对象。

3、减少不合理的对象创建
1）、ondraw、getView 中创建的对象尽量进行复用。
2）、避免在循环中不断创建局部变量。

4、使用合理的数据结构
1）、使用 SparseArray类族、ArrayMap 来替代 HashMap。

内存泄露

排查方法：使用LeakCanary，然后用mat分析泄露对象

泄露情形总结：
1、避免内类持有外类引用（每个内类都有一个this$0指向外类）
（1）使用静态内部类
（2）Activity退出时断掉内外类引用关系，如Handler#removeCallbackAndMessages、通过反射将Runnable匿名内部类this$0置空
2、能用Application context的地方就不要用Activity context
3、WebView所在Activity设置为独立进程，在onDestroy中退出进程
4、列表 item 被回收时注意释放图片的引用
5、使用 ViewStub 进行占位

我做了哪些事情？

图片优化

（1）统一图片库
（2）解决lottie内存问题，弃用lottie
（3）收敛操作Bitmap的API，使用统一的封装
（4）超大图监控
（5）资源图片管理（控制包体获得的顺带收益）

计划做Bitmap线上监控：
1）、首先，在接口层将所有创建出来的 Bitmap 放入一个 WeakHashMap 中，并记录创建 Bitmap 的数据、堆栈等信息。
2）、然后，每隔一定时间查看 WeakHashMap 中有哪些 Bitmap 仍然存活来判断是否出现 Bitmap 滥用或泄漏。
3）、最后，如果发生了 Bitmap 滥用或泄露，则将相关的数据与堆栈等信息打印出来或上报至 APM 后台。

还能做哪些事情？

内存监控

采集内存快照：触顶采集和OOM时采集
裁剪：去除字符串内容，Bitmap像素信息等数据，然后做空字符回填
自动分析：如图所示

参考资料：
https://juejin.cn/post/7052286163884703780?searchId=20240701111941893CB031A18E610D3D7C

线程监控

线上dump堆快照，日志回捞

ANR

ANR原理

为什么会出现ANR？

ANR超时时长

1、ANR发生前流程：以BroadcastReceiver为例，系统发送广播给接受者时，会设置一个超时时间，消息到App进程的binder线程中，以message的形式入队等待执行，执行后通知AMS取消超时监控，如果在超时时间内没有通知AMS，则AMS会触发ANR。
2、ANR发生后流程：
（1）过滤场景，排除正在dump、关机、crash、进程被kill等因素；
（2）收集与ANR相关的所有进程，包括父进程、与App交互的系统进程、CPU占用率较高的进程等；
（3）统计各进程信息，如虚拟机信息、线程状态、堆栈；（一次dump最多20s，否则放弃dump剩余的进程）

ANR影响因素分类：
1、系统负载正常，但是应用内部主线程消息过多或耗时严重。
2、系统或应用内部其它线程或资源负载过高，主线程调度被严重抢占。

参考资料：
https://mp.weixin.qq.com/s?__biz=MzI1MzYzMjE0MQ==&mid=2247488116&idx=1&sn=fdf80fa52c57a3360ad1999da2a9656b&chksm=e9d0d996dea750807aadc62d7ed442948ad197607afb9409dd5a296b16fb3d5243f9224b5763&token=569762407&lang=zh_CN#rd

如何监控发生了ANR？

1、主线程 watchdog

2、监听 SIGNALQUIT 信号（Matrix和xCrash都在用的方案）

方案说明：
1、发生 ANR 的进程一定会收到 SIGQUIT 信号；但是收到 SIGQUIT 信号的进程并不一定发生了 ANR。
所以收到SIGQUIT后可以根据进程是否加了NOT_RESPONDING标识来判断自己的进程是否发生ANR。

2、进程处于 NOT_RESPONDING 的状态可以确认该进程发生了 ANR。但是发生ANR的进程并不一定会被设置为 NOT_RESPONDING 状态。
有以下来两种特殊情况：
（1）后台 ANR（SilentAnr）会被直接杀死。
（2）闪退ANR（部分厂商修改了ANR流程，如VIVO、OPPO），不弹窗，直接闪退。

3、通过判断主线程是否阻塞，进一步判断自己的进程是否发生ANR，从而提升准确率。具体方法是：
通过反射拿到MessageQueue中的下一个Message，msg.when是入队时间，与当前时间的差值如果很大，就表示主线程阻塞。

参考资料：
https://mp.weixin.qq.com/s/qQAPg0PwefYhScdN5bBPnA

如何获取Trace文件？

hook 系统与 App 的边界，从而通过 socket 拿到系统 dump 好的 ANR Trace 内容。

参考资料：
https://mp.weixin.qq.com/s/qQAPg0PwefYhScdN5bBPnA

如何分析ANR日志？

1、先看ANR时间和dump时间间隔，如果间隔太长就没意义了。
2、如果主线程堆栈是nativePollOnce，说明主线程空闲，正在等待新消息。应该排查CPU和内存。
3、主线程阻塞：如果主线程处于blocked、waiting、timewaiting三种状态中，说明主线程阻塞导致。常见因锁而 ANR 的场景是 SharePreference 写入。
4、CPU被抢占：如果CPU过高，则看过高的进程是否为自己的App进程。
5、内存问题：看发生ANR的时间附近是否有onTrimMemory的日志，可能是内存问题。
6、系统服务超时导致的ANR：日志会包含BinderProxy.transactNative关键字，可进一步查看是调用哪个服务出现的问题。

参考资料：
https://mp.weixin.qq.com/s/qQAPg0PwefYhScdN5bBPnA

https://mp.weixin.qq.com/s/qQAPg0PwefYhScdN5bBPnA

但是有时候，拿到的ANR Trace并不能把真正的ANR原因给分析出来，需要使用类似字节开发的Raster工具进行分析。
Raster 主要是能知道主线程的消息调度在过去、现在、将来的具体情况，配合线程 CheckTime 感知线程调度能力，要比单单分析 ANR Trace要方便很多。

分析思路：
https://juejin.cn/post/6942665216781975582?searchId=20240607190656B56EFBA1A325C7B4EACB#heading-21

实例剖析：
https://juejin.cn/post/6945267342671052807

ANR技术文章

https://juejin.cn/user/1838039172387262/posts

看CPU、找关键词（held、hold、lock、waiting、timeout等）

冷启

使用CPU Profiler和SysTrace分析启动耗时

https://juejin.cn/post/7354233812593246248#heading-31

我做了哪些事情？

启动时长上报到APM（attachBaseContext到onWindowFocusChanged）

（1）统一启动项任务接口，通过插码打点监控每个启动项耗时
（2）能异步的就异步，不能异步的延迟或按需初始化

还可以做哪些？

依靠ContentProvider初始化的组件或三方库改为按需加载

SplashActivity与MainActivity合并（好处是减少一次启动页面，且可以利用开屏时间异步加载view）

参考资料：
https://mp.weixin.qq.com/s?__biz=MzI1MzYzMjE0MQ==&mid=2247491335&idx=1&sn=e3eabd9253ab2f83925af974db3f3072&scene=21#wechat_redirect
https://juejin.cn/post/7080065015197204511

包体

我做了哪些事情？

图片资源管理

R文件内联

https://blog.csdn.net/qijingwang/article/details/134753516

https://blog.csdn.net/a1018875550/article/details/128125908

为什么module/aar中的没有R.id没有被内联（不是final）？
因为module/aar在开发过程中使用的R文件是假的，只是让你能编译过去，真正的资源id需要打包时分配。

为什么不能编译module/aar时分配确切内存地址？
如果编译module/aar时分配资源id，那么App整体编译时可能导致资源id冲突。

新增组件监控

卡顿

替换Looper的printer，计算msg.target.dispatchMessage前后打印日志的时间差

BlockCanary

通过Choreographer#postFrameCallback检测帧率，每次执行doFrame会回调callback

ArgusAPM、LogMonitor

慢函数插码

Matrix

网络

工具

mat

常规的排查方法：
1）、首先，找到当前 Activity，在 Histogram 中选择其 List Objects 中的 with incoming reference（哪些引用引向了我）。
2）、然后，选择当前的一个 Path to GC Roots/Merge to GC Roots 的 exclude All 弱软虚引用。
3）、最后，找到的泄漏对象在左下角下会有一个小圆圈。

参考资料：
https://juejin.cn/post/6844903492604133383?searchId=20240607152354DFEBDA46B22F759D30D8
https://juejin.cn/post/6844904099998089230#heading-42

CPU profiler

systrace

traceview

一些面试题

https://juejin.cn/post/7267737437953720359?searchId=2024071211435674B34CC5799956247CF4

Kotlin

内置类型

基本类型

数组

集合

kotlin集合的包名类名与java不同，使用类型别名与java进行了映射

函数

函数的类型，Foo被称做bar方法的receiver

函数的引用

类型初步

类和接口

接口只用于定义行为，不能保存状态

kotlin的property等于java中的backing field+getter+setter

扩展方法

类型的安全转换

表达式

常量和变量

常量的定义

val是只读变量，不是常量

分支表达式

when

转为赋值表达式

try/catch

运算符

== equals()
+ plus()
[] get()
in contains()
> compareTo()
() invoke()

中缀表达式：
2 to 3 2.to(3)

Lambda表达式

函数进阶

内联函数

内联高阶函数的return

禁用non-local return

crossinline：当一个 lambda 表达式被标记为crossinline时，在这个 lambda 表达式内部不能使用非局部返回（即不能直接使用return来跳出包含这个 lambda 的函数）。
这对于确保高阶函数的逻辑完整性非常有用，特别是当高阶函数需要对传入的 lambda 表达式进行一些额外的操作之后再调用它。

noinline：有时候，我们可能不想让某个函数类型参数被内联，例如当我们需要将这个函数参数存储起来以便在以后的某个时间点调用它时。

几个有用的高阶函数

let

any?.let {}, 判空情况使用，返回计算结果

with

with(any) { this } ，返回计算结果

run

let + with的效果

also

also 和 let 函数类似，唯一的区别就是 also 函数的返回值是调用对象本身

apply

apply 函数和 run 函数很像，但是 apply 最后返回的是调用对象本身

集合变换与序列

asSequence是懒汉模式

饿汉模式

map是把每个元素映射成新的元素
flatMap是把每个元素映射成一个集合，然后再把所有集合拼接成一个新的集合

SAM转换

Java的SAM转换

Kotlin的SAM转换

Kotlin的匿名内部类

类型进阶

类的构造器

不推荐副构造器，推荐主构造器+默认参数的方式

类与成员的可见性

注意protected只能修饰成员

类属性的延迟初始化

lateinit

lazy

代理（委托）

接口委托：对象 X 代替当前类 A 实现接口 B 的方法。
通过这个 by 关键字，就可以自动将接口里的方法委托给一个对象，从而可以帮我们省略很多接口方法适配的模板代码。

属性委托：对象 X 代替属性 A 实现getter/setter

object关键字

匿名内部类

单例

缺点：
不能传参数、不能懒加载，相当于Java中的饿汉式单例

伴生对象

非伴生对象的写法，类中嵌套一个object

伴生对象的写法

数据类data class的特点：不能被继承，主构造函数，解构，Component

密封类与枚举类的区别

注意：密封类是抽象的，构造器私有，子类只能在同一个文件中（子类可数）

泛型

java与kotlin泛型对比，注意：java没有声明式型变

泛型作为参数的时候，用 in，泛型作为返回值的时候，用 out。

表达式思维

类型系统

Any、Any?、Object

Any与Any?没有继承关系，但可以将Any看做是Any?的子类型，Any?可以看做是所有类型的根类型，Object可以看做是Any?

Unit

类似java中的void，当Unit作为返回值类型时，可以不写return

Nothing

所有类型的底类型

Unit?、Nothing?

没什么使用场景

不可变思维

1、尽可能使用条件表达式消灭 var

2、使用数据类来存储数据，消灭数据类的可变性

3、尽可能对外暴露只读集合

4、只读集合底层不一定是不可变的，要警惕 Java 代码中的只读集合访问行为

5、val 并不意味着绝对的不可变

空安全四维

第一个准则：警惕 Kotlin 与外界的交互。这里主要分为两大类，第一种是：Kotlin 与其他语言的交互，比如和 Java 交互；第二种是：Kotlin 与外界环境的交互，比如 JSON 解析。

第二个准则：绝不使用非空断言“!!.”

第三个准则：尽可能使用非空类型。借助 lateinit、懒加载

协程

什么是协程？

协程，可以理解为更加轻量的线程，成千上万个协程可以同时运行在一个线程当中；
协程，其实是运行在线程当中的轻量的 Task；
协程，不会与特定的线程绑定，它可以在不同的线程之间灵活切换。
协程，通过挂起和恢复的能力，实现了“非阻塞”。

有栈与无栈：用调用栈保存挂起状态，用对象或闭包保存挂起点状态（Kotlin用Continuation保存）。

对称与非对称：非对称协程在被调用协程挂起之后控制总是会转移到调用者协程。

协程与线程的区别？

协程是语言运行时级别的，CPU对协程是无感知的

线程是操作系统CPU级别的

阻塞与挂起的区别？

阻塞是阻塞整个线程，当前线程的后续代码都无法执行

挂起只是挂起当前协程的执行流程，不影响当前线程中其他协程或代码的执行

协程的基本要素

CoroutineContext

协程上下文就是个数据结构

ContinuationInterceptor

拦截resume操作，切换线程

Continuation

挂起函数编译时会在后面自动加一个Continuation参数completion

有N个挂起点的协程，会执行N+2次resume

Continuation执行示意

拦截Continuation示意

协程挂起恢复的要点

协程的启动模式

子主题

协程的调度器

调度器本质就是拦截器

Default适用于CPU密集型任务，IO适用于IO密集型任务
IO调度器多了一个无限队列，防止IO操作时CPU空转确又创建了太多线程

三种启动协程的方式：launch、runBlocking、async

不要在生产环境当中使用 runBlocking

CoroutineScope.async有返回值

suspend

挂起函数在线程间切换。比如“val user = getUserInfo()”，其中“=”左边的代码运行在主线程，而“=”右边的代码运行在 IO 线程。

挂起函数的本质，就是带有泛型参数的Callback，只是这个 CallBack 换了个名字，叫做 Continuation。
这个“从挂起函数转换成 CallBack 函数”的过程，被叫做是 CPS 转换（Continuation-Passing-Style Transformation）

挂起函数反编译后的代码

Continuation在kotlin中的定义

当程序运行 getUserInfo() 这个挂起函数的时候，它的“Continuation”则是下图红框的代码：

挂起函数，只能在协程当中被调用，或者是被其他挂起函数调用。

虽然“协程和挂起函数”都可以调用“挂起函数”，但是协程的 Lambda，也是挂起函数。
所以，它们本质上都是因为“挂起函数可以调用挂起函数”。

Job

LAZY模式不会马上启动协程，调用job.start()后才会启动

Job 的生命周期

job.join()与job.invokeOnCompletion()

job.join() 其实是一个“挂起函数”，它的作用是：挂起当前的程序执行流程，等待 job 当中的协程任务执行完毕，再恢复当前的程序执行流程。

如何理解“Job 是协程的句柄”这句话呢？

Job 和协程的关系，就有点像“遥控器和空调的关系”。
（1）空调遥控器可以监测空调的运行状态；Job 也可以监测协程的运行状态；
（2）空调遥控器可以操控空调的运行状态，Job 也可以简单操控协程的运行状态。

Deferred

Deferred是继承自 Job 的一个接口，它并没有在 Job 的基础上扩展出很多其他功能，最重要的就是 await() 这个方法，await可以拿到协程的执行结果。

await() 是一个挂起函数，这也就意味着，这个方法拥有挂起和恢复的能力。
如果当前的 Deferred 任务还没执行完毕，那么，await() 就会挂起当前的协程执行流程，等待 Deferred 任务执行完毕，再恢复执行后面的代码。

结构化并发

结构化并发就是带有结构和层级的并发。

只有当childJob全部执行完毕，parentJob 才算是执行完毕了。

Context

很多类都是 CoroutineContext。比如 Job、Deferred、Dispatcher、ContinuationInterceptor、CoroutineName、CoroutineExceptionHandler。
所以都支持操作符重载，比如“Job() + mySingleDispatcher+CoroutineName(“MyFirstCoroutine!”)”。

CoroutineScope本质上也是 CoroutineContext 的一层简单封装。它的核心能力都是源自于 CoroutineContext。

Channel

Channel的分类

Channel的关闭

Channel的迭代

读取数据时要使用resumeEach或for循环，不要使用receive

Channel 是“热”的。不管有没有接收方，发送方都会工作。

Flow

三种创建Flow的方式

emit：发送数据
filter、map、take：中间操作符，对数据进行处理
collect：终止操作符，返回最终数据
Flow.toList()、List.asFlow()：Flow和集合相互转换
onStart、onCompletion：生命周期操作符

flowOn：切换flowOn上游操作（flow{}、map{}、filter{}）的线程

launchIn：切换下游的线程

Flow 被认为是“冷”的原因，就是因为只有调用终止操作符之后，Flow 才会开始工作。

通过上面的运行结果，我们可以发现，Flow 一次只会处理一条数据。
虽然它也是 Flow“冷”的一种表现，但这个特性准确来说是“懒”。

Flow与Channel对比

flow中的emit是非线程安全的，如果要切线程发消息，则使用channelFlow

背压

待学习的内容

merge{}
callbackFlow{}
trySend()
awaitClose()
filterIsInstance
flatMapConcat
MutableSharedFlow

相关代码：
https://juejin.cn/post/7087718088681979934#heading-13

算法
https://www.hello-algo.com/

递归

从本质上看，递归体现了“将问题分解为更小子问题”的思维范式，这种分治策略至关重要。

从算法角度看，搜索、排序、回溯、分治、动态规划等许多重要算法策略直接或间接地应用了这种思维方式。
从数据结构角度看，递归天然适合处理链表、树和图的相关问题，因为它们非常适合用分治思想进行分析。

尾递归：
如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或解释器优化，使其在空间效率上与迭代相当。这种情况被称为尾递归（tail recursion）。

普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下文。
尾递归：递归调用是函数返回前的最后一个操作，这意味着函数返回到上一层级后，无须继续执行其他操作，因此系统无须保存上一层函数的上下文。

迭代与递归的对比

堆

堆的概念

堆（heap）是一种满足特定条件的完全二叉树，主要可分为两种类型

小顶堆（min heap）：任意节点的值其子节点的值。
大顶堆（max heap）：任意节点的值其子节点的值。

堆的表示与存储

堆通常用于实现优先队列，大顶堆相当于元素按从大到小的顺序出队的优先队列。从使用角度来看，我们可以将“优先队列”和“堆”看作等价的数据结构。

搜索

二分查找

二分查找插入点

无重复元素

数组包含target，插入点的索引就是该 target 的索引

数组不存在target，插入点为i

有重复元素

二分查找边界

查找左边界

哈希优化策略

线性查找：以时间换空间

哈希查找：以空间换时间

排序

选择排序

开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。

冒泡排序

通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样，因此得名冒泡排序。

插入排序

我们在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。

快速排序

快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，
而大于基准数的元素移到其右侧。

（1）选取数组最左端元素作为基准数，初始化两个指针 i 和 j 分别指向数组的两端。
（2）设置一个循环，在每轮中使用 i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素。
（3）循环执行步骤 2，直到 i 和 j 相遇时停止，最后将基准数交换至两个子数组的分界线。

回溯算法

回溯算法（backtracking algorithm）是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止。

回溯算法通常采用“深度优先搜索”来遍历解空间。

动态规划

LruCache原理

HashMap + 双向链表
https://www.bilibili.com/video/BV15Y4y1574Q/?spm_id_from=333.788&vd_source=e94924c1f8e30e4cf6bb1ad68154c0b6

排序算法

时间复杂度

单链表反转？

链表成环的判断？

二叉树从根结点到指定节点的路径？

LeetCode

两数之和

用HashMap，key是值，value是索引

链表

链表两数相加

注意处理进位的情况：连续两次进位、最后一次相加进位

合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/

链表反转

86. 分隔链表

https://leetcode.cn/problems/partition-list/description/

返回两个无环链表相交的第一个节点

思路：
判断两个链表是否相交，判断最后一个节点是否相等即可。
找出两个链表第一个相交的节点？长链表先走一定的步数（长链表长度减去短链表长度），然后两个链表一起走，第一个相等的节点就是结果

25. K 个一组翻转链表

https://leetcode.cn/problems/reverse-nodes-in-k-group/description/

138. 随机链表的复制

思路：
新链表的每个节点追加到旧链表每个节点的next节点上，让random节点指向正确位置，然后做新旧链表分离。

https://leetcode.cn/problems/copy-list-with-random-pointer/

234. 回文链表

思路：
1、借助栈，先遍历一遍放入栈，然后再遍历一次每个元素跟出栈元素对比，如果都相同则返回true
2、
（1）使用快慢指针找到中点；
（2）然后逆序中点右侧的链表；
（3）分别从左右两侧向中点移动指针，每次两端节点值相同，则为回文链表，当两侧值不同时跳出；
（4）还原被逆序的那部分链表；

https://leetcode.cn/problems/palindrome-linked-list/description/

142. 环形链表 II

https://leetcode.cn/problems/linked-list-cycle-ii/description/

思路：
（1）使用快慢指针，S指针每次一步，F指针每次两步
（2）它们一定会在环上相遇
（3）相遇后S指针继续每次一步，F指针从头节点开始每次一步
（4）再相遇时必是入环节点

数据结构

155. 最小栈

https://leetcode.cn/problems/min-stack/description/

设计有setAll功能的哈希表

思路：
（0）声明变量globalTime表示时间戳，setAllValue表示setAll的值，setAllValueTime表示setAll的时间戳
（1）value采用int数组，0位置是真正的value，1位置是时间戳
（2）当put一个元素时，记录当前时间戳put(key, int[]{value, globalTime})，然后globalTime++
（3）当调用setAll时，为setAllValue和setAllValueTime赋值，然后globalTime++
（4）获取元素时，如果元素时间戳小于setAllValueTime，说明是setAllValue之前设置的值，则返回setAllValue
（5）反之，说明是setAllValue之后设置的值，则返回元素自身的值

146. LRU 缓存

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

思路：
哈希表+双向链表，哈希表是为了查找是O(1)，双向链表是为了删除和移动是O(1)
如果是单向链表，删除和移动结点是需要访问前驱元素的，而访问前驱元素就要遍历，所以单向链表的删除和移动是需要的时间复杂度是o(n),但是如果使用双向链表，通过pre就可以访问前边的元素

380. O(1) 时间插入、删除和获取随机元素

https://leetcode.cn/problems/insert-delete-getrandom-o1/description/

思路：
哈希表+ArrayList。
哈希表key为值，value为数组下标。delete时用最后一个元素补上并更新哈希表下标

895. 最大频率栈

https://leetcode.cn/problems/maximum-frequency-stack/description/

子主题

432. 全 O(1) 的数据结构

https://leetcode.cn/problems/all-oone-data-structure/description/

二叉树

102. 二叉树的层序遍历

https://leetcode.cn/problems/binary-tree-level-order-traversal/description/

思路：
（1）使用数组充当队列，L是左下标，R是右下标，初始都为0，添加元素时R++，取出元素时L++
（2）两个循环，第一个是while(L < R)，当L小于R时说明队列中还有数据，第二个循环是遍历二叉树中的每一层，每层遍历size次，有左加左，有右加右，size是链表长度（R减去L）

103. 二叉树的锯齿形层序遍历

思路1：
跟《102. 二叉树的层序遍历》差不多，只是有个锯齿逆序收集元素的逻辑
思路二：
先收集，再每隔一层反转

https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/

662. 二叉树最大宽度

https://leetcode.cn/problems/maximum-width-of-binary-tree/description/

思路：
（1）设根节点编号为n（n从1开始），则左子结点编号为2*n，右子节点编号为2*n+1
（2）最大宽度就是：每层的最右节点编号 - 最左节点编号 + 1
（3）也是一层一层遍历，用数组模拟队列做广度优先遍历，再用另一个数组存放每个节点的编号，两个数组存和取要同步进行

104. 二叉树的最大深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

递归思路

111. 二叉树的最小深度

https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/

297. 二叉树的序列化与反序列化（前序）

https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/description/

序列化

反序列化

注意：只有前序和后序遍历才能完成序列化，中序无法做到，因为中序可能存在多种树结构序列化结果相同的情况

二叉树的序列化与反序列化（按层）

思路：
还是队列那个逻辑

105. 从前序与中序遍历序列构造二叉树

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

思路：
（1）头节点必是前序的L1位置
（2）然后根据从中序里找到头节点，位置记作k
（3）则中序中L2到K-1就是左子树
（4）前序中的L1+1往后（K-L2个节点就是左子树）
（5）如此递归

958. 二叉树的完全性检验

https://leetcode.cn/problems/check-completeness-of-a-binary-tree/description/

思路：
1、如果某个节点有右无左，则不满足完全性
2、广度遍历，如果遇到空节点后仍有非空节点，则不满足完全性

求完全二叉树节点数，要求复杂度小于O(n)

思路：
（1）先算出高度H（一直数左节点就行）
（2）判断右子树高度是否达到H
（3）如果达到H，说明左子树是满二叉树，则通过公式为2的H次方减1算左树节点，再算右树节点
（4）如果没达到H，说明右树是高度为H-1的满二叉树，根据公式计算右树节点数，再算左树节点数
（5）如此递归

算法讲解037【必备】二叉树高频题目-下-不含树型dp

https://www.bilibili.com/video/BV1194y16727/?spm_id_from=333.999.0.0&vd_source=e94924c1f8e30e4cf6bb1ad68154c0b6

递归

返回字符串的所有子序列，去重

每个字符要或不要的所有组合情况

方法一

方法二

90. 子集 II（组合）

https://leetcode.cn/problems/subsets-ii/description/

思路：
（1）先排序
（2）按相同元素分组，如[2, 2, 2, 3]，每次要0个到j-1个2，然后调后续数组的递归

46. 全排列

https://leetcode.cn/problems/permutations/description/

最大公约数、最小公倍数

滑动窗口

209. 长度最小的子数组

https://leetcode.cn/problems/minimum-size-subarray-sum/description/

3. 无重复字符的最长子串

https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

134. 加油站

https://leetcode.cn/problems/gas-station/description/

开源库原理

leakcanary

（1）监听activity销毁事件，发生销毁时，将activity放入弱引用，并指定一个queue，当弱引用被回收时，会加入这个queue中。
（2）在App空闲状态执行一个message，检查activity是否被回收。
（3）如果被回收则结束，如果未被回收则手动触发一次gc。
（4）手动触发后，如果队列中仍然没有activity的弱引用，则发生了内存泄露，接下来dump堆内存快照进行分析和通知用户。

arouter

主要分为四部分：
注解、API、apt、Gradle插件

注解：定义路由
apt：根据注解生成路由表的类
gradle插件：生成路由表注册代码
api：路由导航、拦截器、工具类等

mmkv

优势：
（1）效率高，使用mmap，将内存映射到磁盘
（2）使用protobuf协议，空间占用小
（3）增量更新（sp是全量更新）

https://juejin.cn/post/6930168094983716877?searchId=20240618090236734E95C54E39459118CD

koom

rxjava

okhttp

eventbus

gilde

https://juejin.cn/post/6844903986412126216