2024.05.14
Java
HashCode的扰动算法
(hashcode ^ (hash() »>16))&n-1=下标
&n-1=%n
比如十进制126，对10^n数求余数，不用计算，直接拿个位十位26
二进制同理，对2^n求余数，对该数-1后则是前n-1位全1，再做&运算获得数（例如16-1=01111，再做&运算可拿到前4位的1的数量，就是%n的结果）
那么为什么要^以及为什么»>16呢
hashcode是32位二进制数，前面提到&1111，只会保留前4位的hashcode特征，后面全浪费了，所以通过»>16拿到后半部分的特征，通过^异或操作，前面有后面没有的特征保留，其他去掉，保留高位+地位的hash特征，会让得到的下标更均匀
2024.05.09
Java
@Autowired @Resources @Inject区别
@Autowired Spring包里的，默认byType，找不到再byName，通过@Qualified指定name，注入失败可以通过require属性让他不报错
@Resources是JSR标准的，默认byName，找不到byType，通过name或type参数控制
@Inject是JSR标准的，在Spring里和@Autowired一样，但是没有require参数，找不到会报错
这三个都可以用在filed，setter和constructor上
MySQL
is null会用到索引吗，会的，用不到是因为回表范围太大，例如null字段只有一个，查询 is not null会查到 除了这一个以外的所有行，回表范围大于总数据20%，所以直接全表扫描
2024.05.06
数据库
B树和B+树
B+树与B树的设计主要用于提高I/O速度，也就是读取磁盘的速度。无论是记录查询还是索引查询主要受限于硬盘的I/O速度，查询I/O次数越少，速度越快，所以就产生了B树。B树中每个节点都可以存放表的行记录数据，每个节点的读取可以视为一次I/O读取，树的高度表示最多的I/O次数，在相同数量的总记录个数下，每个节点的记录个数越多，高度越低，查询所需的I/O次数越少；假设，硬盘一次I/O数据为8K，数据用4字节建立，理论上一个节点最多可以放2000个记录，2000 × 2000 × 2000 = 8000000000，80亿行的数据只需3次I/O（理论值），可想而知，B树做为数据查询效率有多高。
为了进一步提高磁盘的访问效率，就产生了B+树，B+树与B树最大的不同是内部结点不保存记录数据，只保存关键字，用于查找，所有记录数据都保存在叶子结点中。由于每个非叶子节点只存放关键字，这样节点中能存放的关键字数量就更多，每个节点的扇出数就越大，树的结构就更加矮小，访问磁盘的次数就更少。
2024.05.03
操作系统‼️
内存管理方式（连续和离散两种方式）
连续方式：分区管理内存
单一分区
最早用户内存只有单一个区，只能运行一个程序，DOS系统用此方式管理，方便但是完全浪费cpu资源
多个分区
为了适应多道批处理系统，给内存分了多个固定的区，每个程序独占一个区，这种方式有内碎片，因为用不完
动态分区
每个程序动态分区，要多少给多少为一个区，但是随着运行会有外碎片产生
离散方式：页式管理内存
将物理内存分为多个物理页（块），将程序也分为相同大小的多个逻辑页，将这些逻辑页离散的分配给不同的物理页上去对应，这样一个程序会被离散的分配在内存，通过页表来查询逻辑页到物理页的映射
页表内有页号（隐含，类似下标）、物理页号（块号），是否在物理内存中的判定，页表存储在PCB程序控制块内，每个进程都有自己的页表。
程序在运行中，将逻辑地址拆开获得页号和页内偏移量（只要页面大小是2^n次方，则可以利用进制，将逻辑地址拆开快速获得页号和页内偏移量，例如十进制，页面大小100，那么第零页是000～099，第一页是100～199，可以通过第三位快速拿到页号，前两位快速拿到页内偏移量），MMU拿到逻辑地址去页表中查询物理地址，先通过页表寄存器中的页表长度查看是否越界（防止进程访问到非本进程的页号，保证进程间隔离性），再通过页表起始地址算出查询页表项的位置（类似下标），查询到物理页号地址后，通过物理页号+页内偏移量直接拼接可得到实际物理地址
快表（空间换时间）
因为要查页表，页表连续存储于内存中，cpu查一次速度不快，所以根据局部性原则（空间局部性代表这个页号还有可能会被访问，时间局部性表示这段时间可能还会访问相同的页号），只需要将热点页表项存储与TLB中即可，MMU翻译时先查TLB，查不到再内存并回写缓存
多级页表（时间换空间）
因为页表的页号是隐含的，我们是通过起始地址+页号*页表项大小这种方式去查询页表，这种方式必须保证页表是连续内存（跟数组一样），在内存很大时，页就会有很多，页号就很大，页表就要很长。单级页表会占用很大一部分连续内存，与离散分配思想相悖。于是我们将单级页表拆开，离散的放到不同的页中，再用一个顶级页表去记录映射。
逻辑地址翻译时，要从逻辑地址拆出一级页号，二级页号，页内偏移量，从顶级页表查询二级页表，再用二级页号查询到实际的物理页号
多级页表还可以将不常用的离散页表放到外存（局部性原理+虚拟内存），查询时只有顶级页表和常用二级页表在内存中。
离散方式：段式管理内存
由用户将程序分为多个段，每个段的长度是不一定的，操作系统将这些段离散的分配在内存中，通过段表处理映射关系，段表中有段号（隐含），段长（与页表不同，段长不一定，由编程者决定），基址（物理地址）
逻辑地址翻译为物理地址时，逻辑地址会被拆开为段号和段内偏移量，首先由段表寄存器查询段号是否越界，如果不越界根据段表起始地址+段号*段表项长度算出段表项位置，随后检查段内地址有没有超过段长（与页表不同）。最后将基址+段内偏移量即可得到物理地址
段与页式存储不同的地方：
页式存储是方便系统离散分配内存所用，对用户不可见，用户不知道程序是否被分页，页长固定的
段式存储是方便编程者编程用的，对用户可见，用户知道程序有几个段，段长是根据程序决定的
离散方式：段页式管理内存
由于段内是连续的，如果段太长会导致连续内存太多，违背离散分配的思想，于是段页式分配思路将程序分为一个个段，再将连续的段内分为一个个页，将连续的段离散的分配在内存当中，通过段表+页表维护映射。
不同点：
段表与段式管理的段表不同，段表分为段号（隐含），页表长度（段可能分为多个页），页表地址组成，页表则跟页式管理相同，逻辑地址会分为段号，页号，页内偏移量，MMU翻译时，会先查检查段表越界，然后找到段表项，再检查页号是否超过页表长度，未超过则找到对应页表，根据页号查询到物理页号，最后物理页号+页内偏移量得到物理地址。
虚拟内存：请求分页
由于局部性原理，程序的许多内存短时间都不需要访问，所以我们可以将这些不经常被访问到的内存放入外存，等用到的时候再换回内存，这就是虚拟内存
有了虚拟内存我们有几个好处
1.运行程序时只需要将程序的一部分放入内存，运行不到的先放到外存
2.程序运行时，不会一直保留在内存中，用不到的会换到外存
3.虚拟内存用逻辑的方式扩充了内存，在物理内存不变的情况下增大了实际可使用的内存
实现：
页表增加字段，状态位（是否在物理内存），外存地址，修改位（如果没修改可以不覆盖外存），指标（页面置换算法判断用）
页面置换算法：OPT（理想型）、FIFO（不符合局部性原理）、LRU（实现难度大，需要硬件）、CLOCK（均衡，扫描最近没有使用过的）
2024.05.02
Java
垃圾回收：
YoungGC Eden满
FullGC 老年代剩余空间小于平均晋升空间
CMS 老年代空间占整空间45%
G1 Mix GC 整堆使用超过45%
从头梳理一遍G1‼️
分为两种GC，YoungGC MixGC Young回收所有Eden+S0，MixGC回收所有Young+一部分Old，根据Region优先级选择，优先级是标记结束后会清点Region存活对象，存活对象越多，复制时间越长，回收优先级越低。
G1默认将堆分为2048个Region，每个Region的大小最小为1M，最大为32M，如果没有手动设定大小，会根据(xms+xmx)/2/2048计算每个Region的大小，计算出的结果往2的n次幂靠近。
CardTable和Rset解决跨代引用（O->O O->N)问题，例如老引新，新没有直接连接GCRoot，为了避免在YoungGC再去扫老年代所以查询Rset即可知道N对象是垃圾还是被O引用。CardTable每个元素指代Region的512Byte。
YoungGC：
初始标记阶段
标记所有GCRoot直接相连的对象，将其置为灰色，放入扫描stack，注意如果是CMS则会将所有Young当作Root，扫描所有和年轻代直接相连的老年代，所以G1比CMS初始标记阶段要快
并发标记阶段
此阶段开启写屏障，记录SATB和DirtyCard
当用户线程断开引用时，将old写入SATBQueue（线程私有）防止出现三色标记漏标问题，当用户线程连接另一个引用时，如果不在一个Region，并且发出引用的是老年代，将CardTable置为dirty，并将cardIndex写入DirtyCardQueue（用户私有），这两个queue写满后都会分别写入他们自己相对应的全局queue，让第三方线程后期处理，防止线程并发严重，因为用户线程修改引用是十分频繁的，直接修改会影响性能。
补充Rset的修改：当全局DirtyCardQueue达到某些程度时（白（不清理）绿（单个refine线程）黄（全部refine线程）红（全部refine线程+用户线程））会notify refine线程修改Rset。首先会遍历cardIndex指向的堆内存区域，因为一个card 512字节一定包含很多对象，遍历这些对象，查看他们的引用跟自己是不是不在一个区域(所以会记录下O->O和O->N)，如果不在一个区域，则将对面的Rset修改。
再标记阶段
此阶段将SATB队列中所有未标记的改变引用全部标记完成，如果是CMS，会从根节点（所有Young）重新扫描，看漏标的是否是浮动垃圾，由于要重新扫描Young区，所以CMS比较慢，但是再标记阶段的浮动垃圾比G1少，G1只需要将引用断开的地方全部置为灰（保持老的存活形态，所以叫原始快照），包括新添加（next到top区域）的所有对象置为黑即可，所以G1很快，但是浮动垃圾多，属于空间换时间的思路
清理阶段
该阶段会清点Region中存活对象的数量，用来计算Region的优先级
复制阶段
将GCRoot直连的对象全部复制到新Region，并将它们的非老年代属性引用压到一个栈里，再去查Rset，将老年代直接引用的对象复制，属性也压栈。随后将栈里的对象也复制到新Region中。最后重构Rset，清理空间
MixGC：
MixGC紧接着在YoungGC后，默认如果堆空间大于45%即开始MixGC
初始标记阶段
将刚刚YoungGC后复制到新S区的节点作为根节点，扫描所有与老年代直接相连的引用
并发标记阶段
与Young类似，依然是SATB+DirtyCard记录所有漏标
再标记阶段
清理SATB标记漏标引用
清理阶段
清点存活对象数量，计算Region优先级
复制阶段
根据Region优先级选择一些合适的old region，先复制根，再查Rset找O->O的直接引用复制
2024.05.01
JAVA
CAS底层：
native方法，不由java实现，在unsafe.cpp文件中最终调用的是cmpxchg汇编指令
但这个指令并不是原子性的，实际上在运行之前有LOCK_IF_MP的判断，如果是MP（多处理器），就LOCK锁定总线，保证后面的cmpxchg是原子操作
volatile
可见性+防止指令重排
可见性：缓存一致性协议，经过volatile修饰过的变量，在缓存中被修改后会被嗅探到，将其他线程的缓存失效，使其被迫从主存中再次查询保证可见性
防止指令重排：原理为内存屏障，有loadload，loadstore，storestore，storeload四种读写屏障，jvm在volatile变量前后加入读写屏障（loadload读loadstore，storestore写storeload），保证前面volatile做的操作后面一定可见。
屏障的解读，如loadstore volatile写，意为在volatile写之前，他之前的读指令必须执行完成（对后面的写可见）
G1
CardTable+Rset 解决跨域引用（老引新）性能问题 防止YoungGC时对老年代进行整堆扫描
SATB解决并发标记时三色标记的漏标问题 CMS通过写屏障+增量标记实现 再标记阶段要重新扫描根节点去查询dirtycard（增量标记）到底可不可达 速度比SATB慢但浮动垃圾更少
SATB只需要遍历快照节点和他的子节点 更快但浮动垃圾多
SATBQueue 每个线程都有 队列满后加入全局队列集合 让另一个线程处理再标记
DirtyCardQueue 解决Rset并发标记问题 Queue的元素到一定数量会有第三方线程开始写Rset
2024.04.30
Java
零拷贝
mmap（FileChannel.map()）或者sendFile（transferTo）
一个共享用户和内核缓冲区，另一个直接拷贝内核缓冲区到另一个缓冲区，不回到用户态缓冲区
复习栈内存空间：
程序计数器+本地方法栈+虚拟机栈（操作数栈、局部变量表、返回地址、动态链接）
复习堆内存空间
对象（对象头（markword+类指针）+对象数据+对齐字节）
复习方法区空间：
类元信息+运行时常量池（字面量和符号引用）（例如方法的直接引用池）
类加载器
双亲委派机制，自底向上查询是否加载，自上而下尝试加载，为了保护同一个应用不加载相同全限定性类名的类
tomcat打破此机制
因为不同Web应用有可能有相同的全限定性类名比如User但实现完全不同，但必须要加载，所以每个Web应用有自己的WebAppClassLoader，每次优先加载自己目录下的类
但每个Web相同的引用比如Spring，没必要都重复加载，于是将相同的共享类用ShareClassLoader加载
Tomcat自己的类要和别的隔离开，所以用CatalinaClassLoader加载
Tomcat自己的与Web共享类就用CommonClassLoader加载
类加载器在加载类的时候，他的依赖类也要由这个加载类加载，但是JDBC或者Spring用户实现类这种情况，BootStrapClassLoader和ShareClassLoader是无法加载DriverManager和用户业务类的，于是让线程上下文类加载，tomcat中threadContextClassLoader设置为WebAppClassLoader
这种情况只打破了类和依赖类需要同一个类加载器加载的规则，没有打破自顶向上和自顶向下规则。
happens-before
HashMap系列复习
首先hashtable，直接synchronized锁全部对象
1.7HashMap 头插法
1.8HashMap改尾插法，为了解决并发时HashMap的reHash()导致循环链表问题
1.7ConcurrentHashMap Segment锁，继承了ReentrantLock，每一个Segment就是一个ReentrantLock，默认是16个Segment，初始化后就不能扩，每个Segment内的数组可以扩，跟HashMap一致，超过阈值就扩容两倍
1.8ConcurrentHashMap使用Node节点，使用CAS+自旋或者Synchronized保证线程安全，空就CAS自旋，不空就Synchronized替换，锁的粒度更小，不发生hash冲突就不会竞争
复习偏向锁轻量级锁重量级锁，只有重量级锁有自旋，轻量级没有
2024.04.29
Spring
复习循环依赖
事务传播 https://mp.weixin.qq.com/s?__biz=Mzg2OTA0Njk0OA==&mid=2247486668&idx=2&sn=0381e8c836442f46bdc5367170234abb&chksm=cea24307f9d5ca11c96943b3ccfa1fc70dc97dd87d9c540388581f8fe6d805ff548dff5f6b5b&token=1776990505&lang=zh_CN&poc_token=HALvBGejMB_pOhtvzSOg0frevYpD9zk68Mc7TLX5
IOC原理与实现
原理：控制反转，DI依赖注入，经过配置后交给Spring生成Bean
实现：Bean由容器控制，容器是Map，三级缓存
Bean的生命周期
模版模式：
必须是抽象类，例如AbstractPlatformTransactionManager，
模版方法必须为final（算法骨架，不能重写），例如commit()
模版方法调用的抽象方法可以重写，例如doRollback()
循环依赖问题->三级缓存‼️
一级缓存（完整成品）
二级缓存（半成品（有代理就是代理，没代理就是普通）
三级缓存（Lambda表达式，获得正确的二级缓存value）
如果没有二级缓存，那么无法区分半成品和成品，需要两个map区分开
如果没有三级缓存，那么如果有代理对象A，在依赖注入B的时候，A代理对象还没有生成，系统会将错误的原始对象赋给B
那么如果我不要三级缓存，就将半成品对象放入二级缓存中，有代理就放代理，没代理放原始。这样则会彻底打破生命周期，所有的代理对象都会在实例化完成放入二级缓存。三级缓存在这里的另一个意义就是可以推迟打破生命周期的时机，如果没有循环依赖问题的出现，A会正常的在初始化完成后再创建代理对象，也就是说，三级缓存的一个重要原因就是只有在循环依赖和动态代理对象共同出现时，才会打破生命周期。
推迟的原理就是Lambda表达式（函数式接口）
2024.04.27
Java
ZGC、G1
Linux‼️
select(),poll(),epoll()
(select()优点：减少系统调用【同poll】，缺点 bitmap最大1024，bitmap置位会破坏fdset需要重新创建）
（poll()优点：使用fd数组，置位不会破坏原有数组，可复用，缺点【同select()】：需要多次拷贝fd，每次发回来需要O（N）判断，但比NIO不需要多次系统调用）
（epoll()优点：事件驱动IO多路复用，epoll_create()开辟红黑树内核内存区域，fd送入红黑树(epoll_ctl(add)只需一次拷贝，epoll_wait()直接取有事件的fd，不需要遍历，缺点：还是需要程序调用实际事件）
BIO,NIO,IO多路复用,AIO
strace -ff -o 追踪系统调用
/proc/pid/task线程
/proc/pid/fd 文件描述符（网络连接，读写等）
2024.04.26
Java
Happens-Before条件
LockSupport.park()方法阻塞线程，unpark(thread)唤醒，CAS自旋可用
Condition 与lock混用，await()放锁阻塞,signal()唤醒指定线程
Lock和Synchronized区别
MySQL
Next-Key-Lock的所有情况判断
https://coder1024.blog.csdn.net/article/details/131766686?spm=1001.2101.3001.6650.4&utm_medium=distribute.wap_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-4-131766686-blog-114342620.237%5Ev3%5Ewap_relevant_t0_download&depth_1-utm_source=distribute.wap_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-4-131766686-blog-114342620.237%5Ev3%5Ewap_relevant_t0_download
计算机网络
HTTP粘包半包解决方法
算法
归并排序、快速排序、冒泡排序、选择排序、插入排序
2024.04.25
Java
ThreadLocalMap启发式清理（i,n，i每次移动1位，n每次»>1位，没清理到n到0结束，清理到从len重新开始)
清理后 size>阈值（len2/3) 就rehash rehash（size>阈值3/4就扩容（*2））
Spring
Bean生命周期
找到配置->反射实例化->设置属性->调用实现的aware接口（beanName，classLoader，beanFactory）->BeanPostProcessor前置处理->调用实现的initializing的afterPropertiesSet()->执行init-method方法->beanPostProcessor后置处理->destroy方法()->destroy-method方法
事务传播级别
事务隔离级别
IOC DI
MyBatis
${}和#{}的区别
Mybatis原理（JDK动态代理拦截dao接口方法，从map<String,MapperStatment>里找到mapperstatment）
WEB
JWT
SpringMVC
原理
核心DS
DS->MappingHandler->AdapterHandler->Handler–>ViewResolver->浏览器
MySQL
复习索引以及索引失效（不符合最左匹配前缀（联合），select * where的范围过大，order by全表比回表快，in的范围过大，%在左边范围过大，or两头有一个没索引，用了函数计算）
SpringBoot
自动配置类原理（META-INF/Spring.factories读全限定类名->@ConditionOnXX判断加载时机->@ConfigurationProperties(prefix=“xxx”)加载Application.yaml配置信息
2024.04.24
MySQL
redo log，undo log，bin log
Redis
zset跳表 与b+和红黑区别
RDB+AOF持久化
主从同步 sync（RDB+缓冲区） psync部分同步（主从offset+主服务器id+主积压缓冲区）
缓存一致性（更新服务器+重试删缓存）
Java
ThreadLocalMap原理（扩容 清理 底层结构）
2024.04.23
操作系统
进程线程（死锁 条件 如何解决 进程通信）
内存管理（页表 tlb 多级页表）
MySQL
MVCC和读写锁如何解决事务并发问题
事务隔离等级
Redis
数据结构
