阿里面试总结 一
.png)
写了这些还是不够完整，阿里 字节 卷进去加班！奥利给
ThreadLocal
线程变量存放在当前线程变量中，线程上下文中，set将变量添加到threadLocals变量中
Thread类中定义了两个ThreadLocalMap类型变量threadLocals、inheritableThreadLocals用来存储当前操作的ThreadLocal的引用及变量对象，把当前线程的变量和其他的线程的变量之间进行隔离，从而实现了线程的安全性
InheritableThreadLocal类重写get/set方法会对线程的inheritableThreadLocals变量初始化，在对子线程初始化时将子线程的inheritableThreadLocals变量赋值为父线程的inheritableThreadLocals变量值，实现了子线程继承父线程
内存泄漏问题
Thread->ThreadLocalMap->Entry->value，ThreadLocalMap是继承了WeakReference的entry集合，但是线程一直没有remove，threadLocal下次GC将弱引用对象回收，entry对象的key为null，value值却是强引用关系
ThreadLocal每次调用get、set、remove的时候都会直接或者间接的调用expungeStaleEntry方法清除掉key为null的Entry；
主线程执行ThreadLocal.remove()后，子线程中的ThreadLocal并不会被remove()判空，导致线程池中维护的ThreadLocal存储的值一直不变
池化：InheritableThreadLocal子线程使用线程池 更改存储 变量值不变
没找到对应的InheritableThreadLocal 自然改不了：普通的ThreadLocal会让子线程获取不到get值
池化：减少资源对象创建次数
private void init(ThreadGroup g, Runnable target, String name,
long stackSize, AccessControlContext acc,
boolean inheritThreadLocals) {
//省略部分代码
//如果父线程inheritableThreadLocals不为空，则保存下来
if (inheritThreadLocals && parent.inheritableThreadLocals != null)
this.inheritableThreadLocals =
ThreadLocal.createInheritedMap(parent.inheritableThreadLocals);
//省略部分代码
}
注意 使用静态和不使用静态时候
使用静态的InheritableThreadLocal 线程池复用时候不会有问题
ThreadLocal是线程本地变量，每个线程有自己的副本；InheritableThreadLocal具有继承性，在创建子线程时，子线程可以继承父线程的变量副本。
https://www.cnblogs.com/shanheyongmu/p/17922183.html
https://www.cnblogs.com/tiancai/p/17622821.html InheritableThreadLocal详解 - 简书
TransmittableThreadLocal
继承自InheritableThreadLocal，在线程池中传递ThreadLocal变量的值
GitHub - alibaba/transmittable-thread-local: 📌 a missing Java std lib(simple & 0-dependency) for framework/middleware, provide an enhanced InheritableThreadLocal that transmits values between threads even using thread pooling components.
/*
* holder里面存储所有关于TransmittableThreadLocal的引用
*/
public class TransmittableThreadLocal extends InheritableThreadLocal implements TtlCopier {
// 1. 此处的holder是他的主要设计点，后续在构建TtlRunnable
private static InheritableThreadLocal holder =
new InheritableThreadLocal() {
@Override
protected WeakHashMap initialValue() {
return new WeakHashMap();
}
@Override
protected WeakHashMap childValue(WeakHashMap parentValue) {
return new WeakHashMap(parentValue);
}
};
@SuppressWarnings("unchecked")
private void addThisToHolder() {
if (!holder.get().containsKey(this)) {
holder.get().put((TransmittableThreadLocal) this, null); // WeakHashMap supports null value.
}
}
@Override
public final T get() {
T value = super.get();
if (disableIgnoreNullValueSemantics || null != value) addThisToHolder();
return value;
}
/**
* see {@link InheritableThreadLocal#set}
*/
@Override
public final void set(T value) {
if (!disableIgnoreNullValueSemantics && null == value) {
// may set null to remove value
remove();
} else {
super.set(value);
addThisToHolder();
}
}
/**
* see {@link InheritableThreadLocal#remove()}
*/
@Override
public final void remove() {
removeThisFromHolder();
super.remove();
}
private void superRemove() {
super.remove();
}
}
1.继承InheritableThreadLocal，成立个TransmittableThreadLocal类， 该类中有一个hodel变量维护所有的TransmittableThreadLocal引用。
2.在实际submit任务到线程池的时候，需要调用TtlRunnable.get，构建一个任务的包装类。使用装饰者模式，对runnable线程对象进行包装，在初始化这个包装对象的时候，获取主线程里面所有的TransmittableThreadLocal引用，以及里面所有的值，这个值是当前父线程里面的（跟你当时创建这个线程的父线程没有任何关系，注意，这里讲的是线程池的场景）。
3.对数据做规整，根据收集到的captured (这个对象里面存储的都是主线程里面能够获取到TransmittableThreadLocal以及对应的值) 做规整，去掉当前线程里面不需要的，同时将剩余的key和value ，更新到当前线程的ThreadLocal里面。这样就达到了在池化技术里面父子线程传值的安全性
多线程篇-TransmittableThreadLocal解决池化复用线程的传值问题 - 知乎
hashMap1.7与1.8
1.7底层是entry数组+链表
颠倒链表顺序 元素插入前是否需要扩容，扩容后all元素重新计算下位置
头插法：逆序 环形链表死循环
ReentrantLock+Segment+HashEntry
第一次put hash(key)定位segment 未初始化cas赋值
第二次put，hashEntry ReentrantLock.tryLock获取锁，否自旋tryLock 获取锁 超次挂起
1.8node数组+链表+红黑树
保持原链表顺序 元素插入后检查是否扩容
链表长度达到8/元素总数达到64
synchronized+CAS+HashEntry+红黑树
没有初始化initTable
没有hash冲突 cas插入，否 加锁
链表遍历到尾部插入 ，红黑树就是红黑树的结构插入
添加成功addCount统计size是否需要扩容
高低位指针的形式，将低位上的数据移动到原来的位置，高位上的数据移动到【原来的位置+旧数组容量】的位置，避免了rehash
AQS
ConditionObject的await和signal等同Object的wait、notify函数(Synchronized)
五层
如果被请求的共享资源空闲，将当前请求资源的线程设置为有效的工作线程，将共享资源设置为锁定状态；
如果共享资源被占用，需要一定的阻塞等待唤醒机制来保证锁分配。这个机制主要用的是CLH队列（Craig、Landin and Hagersten，是单向链表）的变体实现的，将暂时获取不到锁的线程加入到队列中（AQS是通过将每条请求共享资源的线程封装成一个节点node来实现锁的分配）
理解AQS的原理及应用总结_aqs原理-CSDN博客 这篇阿里P6+的水平了
CountDownLatch和CyclicBarrier
CountDownLatch放行由其他线程控制，一直等待直到线程完成操作
计数器 aqs，countDown减state-1，await 判断state==0 非加入队列阻塞 头节点自旋等待state=0
CyclicBarrier本身控制，线程到达状态 暂停等待其他线程，all线程到达后 继续执行
任务线程调用，线程相互等待，可重用
ReentrantLock加上Condition，await，count -1 ReentrantLock线程安全性，如count不为0，加则condition队列中，如count==0，把节点从condition队列添加至AQS的队列中进行全部唤醒，并且将parties的值重新赋值为count的值（实现复用)
volatile
共享变量：主内存
线程有自己的工作内存
线程间变量的值传递需要主内存
一个线程使用共享变量先判断当前副本变量的状态 无效状态的话 向总线发送read 消息读取变量最新数据 总线贯穿这个变量用到的所有缓存以及主存 读取到的最新数据可能来自主存 也可能来自其他线程
lock指令 本地线程写入内存，其他线程失效
read指令 读取变量最新数据
禁止指令重排
字节码层面：使用volatile修饰变量，在编译后的字节码中为变量添加ACC_VOLATILE标记
JVM层面：JVM规范中有4个内存屏障，LoadLoad/StoreStore/LoadStore/StoreLoad，在读到ACC_VOLATILE标记时会在内存区读写之前都加屏障
操作系统和硬件层面：操作系统执行该程序时，查到有内存屏障，使用lock指令，在指令前后都加lock(屏障)，保证前后不乱序
volatile 指令重排以及为什么禁止指令重排_volatile为什么要禁止重排序-CSDN博客
总线风暴
volatile和cas导致bus总线缓存一致性流量激增
一个变量在多个高速缓存中存在，高速缓存间数据不共享 数据不一致
总线锁定 缓存锁定
MESI：已修改modified 互斥独占exclusive 共享share 无效invalid
1使用共享数据 拷贝到1缓存中 设为E
2也使用共享数据，拷贝到2缓存
1把变量回写到主存，先锁住缓存行，状态=M 向总线发消息告诉其他 在嗅探的cpu 该变量被修改并写会主存，其他CPU 状态S=> I无效，需要时从内存获取
发现缓存地址被改了，无效I
失效：共享变量大于缓存行大小 ，mesi 无法对缓存行加锁
高速缓存：时间局部性(变量被访问 近期may再次被访问)
空间局部性(变量被访问 周围变量可能被近期访问)
缓存行默认64字节
https://blog.51cto.com/u_16213606/7587478
java数据结构
树
前序遍历 ①先访问根节点 ②在访问左节点，接着访问右节点
后序遍历 ①先访问左节点，在访问右节点 ②最后访问根节点
二叉树
一颗非空二叉树的第i层上最多有2^(i-1)个节点
一颗高度为k的二叉树，最多有2^k -1 个节点
满二叉
一颗高度为K 并且具有2^k - 1 个节点
完全二叉树
哈夫曼树
哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树
数据结构——哈夫曼树-CSDN博客
二叉排序树
左小右大
二叉平衡树AVL
左右子树 高度差
