Logo

菜单

全站最帅😎
发布于 2022-07-06 / 819 阅读
0
0

Java笔记与实战经验

#面经

算法与数据结构

HashMap底层实现
JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

HashMap 的长度为什么是 2 的幂次方？
当HashMap的容量是2的幂次方时，( n - 1)的2进制都是111..11的形式，在与添加元素的hash值进行位运算时能够充分的散列，使添加的元素能均匀的分布在HashMap的每个位置上，减少hash碰撞。

HashMap线程安全吗？
HashMap线程不安全，多线程操作下 get() 方法会导致死循环。
HashMap多线程下死循环原因

ConcurrentHashMap 底层实现
JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树

ConcurrentHashMap 线程安全实现
在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后 对 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；

ArrayList 和 LinkedList 相同数据情况下谁更加占用内存？

  • 如果数据正好达到 ArrayList 扩容的分界线，则有可能 ArrayList 占用内存更多。
  • 一般情况下，LinkedList 占用的内存会多一些，因为要维护前后两个指针

并发编程

线程池参数

  • corePoolSize：核心线程数定义了最小可以同时运行的线程数量。
  • maximumPoolSize：当队列中存放的任务达到队列容量的时候，当前可以同时运行的线程数量变为最大线程数。
  • workQueue：当新任务来的时候会先判断当前运行的线程数量是否达到核心线程数，如果达到的话，新任务就会被存放在队列中
  • keepAliveTime：当线程池中的线程数量大于 corePoolSize 的时候，如果这时没有新的任务提交，核心线程外的线程不会立即销毁，而是会等待，直到等待的时间超过了 keepAliveTime才会被回收销毁
  • unit：keepAliveTime 参数的时间单位
  • threadFactory：线程工厂，可以对线程进行重命名、是否为守护线程等操作。
  • handler：饱和策略。

线程池的工作流程
image.png

synchronized 和 lock 的区别
- synchronized 加锁和解锁是由 JVM 负责，synchronized 获取锁的过程是阻塞式的，不可中断，可能导致死锁。
- lock 是 jdk 里面 juc 的实现，支持 非阻塞的、支持中断响应、支持超时的获取锁。

AQS 是什么？
AQS 队列同步器，Java中的 ReentrenLock、Stamplock 都是基于 AQS 实现。AQS 使用模板方法，子类只需要继承并 重写对应的钩子方法，例如 tryLock(),tryRelase() 等。

JVM

JVM内存模型
每个线程都有自己的缓存，线程从主存中读取变量到缓存，然后加载到寄存器进行运算，得到结果后写回主存

类加载
类加载时机：JVM 虚拟机的实现都是使用的懒加载，需要这个类才去进行加载

  1. 验证阶段：

    • 文件格式验证：验证字节楼是否符合 Class 文件规范，并且能被当前版本的虚拟机处理。
      这阶段的验证是基于二进制字节流进行的，只有通过了这个阶段的验证之后，这段字节流才被允许进人 Java 虚拟机内存的方法区中进行存储
    • 元数据验证：对字节码描述的信息进行语义分析，以保证其描述的信息符合《Java 语言规范》的要求
    • 字节码验证：通过数据流分析和控制流分析，确定程序语义是否合法并符合逻辑。这阶段就要对类的方法体(Class 文件中的 Code 属性)进行校验分析，保证被校验类的方法在运行时不会做出危害虚拟机安全的行为。
    • 符号引用验证：符号引用验证可以看 作是对类自身以外（常量池中的各种符号引用）的各类信息进行匹配性校验，符号引用验证的主要目的是确保解析行为能正常执行。
    • 验证总结： 验证阶段对于虚拟机的类加载机制来说，是一个非常重要的、 但却不是必须要执行的阶段，因为验证阶段只有通过或者不通过的差别，只要通过了验证， 其后就对程序运行期没有任何影响了。如果程序运行的全部代码(包括自己编写的、第三方包中的、从外部加载的、动态生成的等所有代码)都已经被反复 使用和验证过，在生产环境的实施阶段就可以考虑使用-Xverify:none 参数来关闭大部分的类验证措施，以缩短虚拟机类加载的时间。

  2. 准备阶段
    准备阶段是正式为类变量分配内存并设置类变量初始值的阶段

    • 类变量分配（不包括实例变量）
    • 基本类型设置初始值

  3. 解析阶段
    解析阶段是 JVM 将常量池内的符号引用替换为直接引用的过程。解析动作主要针对类或接口、字段、类方法、接口方法、方法类型、方法句柄和调用限定符 7 类符号引用进行。
    符号引用就是一组符号来描述目标，可以是任何字面量。直接引用就是直接指向目标的指针、相对偏移量或一个间接定位到目标的句柄 （符号引用类比一个人的电话号码，而直接引用就类比和你面对面的这个人）

  4. 初始化阶段
    初始化主要是对一个 class 中的 static{}语句进行操作，执行了 clinit 方法的过程，是类加载的最后一步，这一步 JVM 才开始真正执行类中定义的 Java 程序代码(字节码)。

    1）遇到 new、getstatic、putstatic 或 invokestatic 这 4 条字节码指令时，如果类没有进行过初始化，则需要先触发其初始化。生成这 4 条指令的最常见的 Java 代码场景是：
    —使用 new 关键字实例化对象的时候。
    —读取或设置一个类的静态字段（被 final 修饰、已在编译期把结果放入常量池的静态字段除外）的时候
    —调用一个类的静态方法的时候。

    2）使用 java.lang.reflect 包的方法对类进行反射调用的时候，如果类没有进行过初始化，则需要先触发其初始化。

    3）当初始化一个类的时候，如果发现其父类还没有进行过初始化，则需要先触发其父类的初始化。

    4）当虚拟机启动时，用户需要指定一个要执行的主类（包含 main（）方法的那个类），虚拟机会先初始化这个主类。

    5）当使用 JDK 1.7 的动态语言支持时，如果一个 java.lang.invoke.MethodHandle 实例最后的解析结果 REF_getStatic、REF_putStatic、REF_invokeStatic 的方法 句柄，并且这个方法句柄所对应的类没有进行过初始化，则需要先触发其初始化。

    6）当一个接口中定义了 JDK1.8 新加入的默认方法（被 default 关键字修饰的接口方法）时，如果这个接口的实现类发生了初始化，那该接口要在其之前 被初始化。

可达性分析
以 “GC Roots” 的对象作为起始点，从这些节点开始向下搜索，搜索所走过的路径称为引用链（Reference Chain），当一个对象到 GC Roots 没有任何引用链相连时，则证明此对象是不可用的。 作为 GC Roots 的对象包括下面几种（重点是前面 4 种）：虚拟机栈（栈帧中的本地变量表）中引用的对象；各个线程调用方法堆栈中使用到的参数、局部变量、临时变量等
1）方法区中类静态属性引用的对象；java 类的引用类型静态变量。
2）方法区中常量引用的对象；比如：字符串常量池里的引用。
3）本地方法栈中 JNI（即一般说的 Native 方法）引用的对象。
4）JVM 的内部引用（class 对象、异常对象 NullPointException、OutofMemoryError，系统类加载器）。（非重点）
5）所有被同步锁(synchronized 关键)持有的对象。（非重点）
6）JVM 内部的 JMXBean、JVMTI 中注册的回调、本地代码缓存等（非重点）
7）JVM 实现中的“临时性”对象，跨代引用的对象（在使用分代模型回收只回收部分代的对象，这个后续会细讲，先大致了解概念）（非重点）

垃圾回收算法
1）复制算法：
将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再把已使 用过的内存空间一次清理掉，常用于新生代。内存移动是必须实打实的移动（复制），所以对应的引用(直接指针)需要调整

2）标记-整理算法：
首先标记出所有需要回收的对象，在标记完成后，后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向一端移动，然后直接清理掉边界以外的内存。标记整理算法 没有内存碎片，但是因为涉及到内存数据的移动，所以 效率偏低。同时对象移动不单单会加重系统负担，且需要全程暂停用户线程，同时所有引用对象的地方都需要更新（直接指针需要调整）

3）标记-清除算法：
算法分为 “标记” 和 “清除” 两个阶段：首先扫描所有对象标记出需要回收的对象，在标记完成后扫描回收所有被标记的对象，所以需要扫描两遍。 回收效率略低，如果大部分对象是朝生夕死，那么回收效率降低，因为需要大量标记对象和回收对象，对比复制回收效率要低。 它的主要问题，标记清除之后会产生大量不连续的内存碎片，空间碎片太多可能会导致以后在程序运行过程中需要分配较大对象时，无法找到足够的连续内存而不得不提前触发另一次垃圾回收动作。回收的时候如果需要回收的对象越多，需要做的标记和清除的工作越多，所以标记清除算法适用于老年代
image.png

对象分配策略
1）栈上分配：

如果方法的对象没有逃逸分析（在方法外部没有引用），那么对象就会在栈上面分配。
2）对象优先在 Eden 区分配：

大多数情况下，对象在新生代 Eden 区中分配。当 Eden 区没有足够空间分配时，虚拟机将发起一次 Minor GC。

3）大对象直接进入老年代
大对象就是指需要大量连续内存空间的 Java 对象。在 Java 虚拟机中要避免大对象的原因是：在分配空间时，它容易导致内存明明还有不少空间时就提前触发垃圾收集，以获取足够的连续空间才能分配给它们。 而当复制对象时，大对象就意味着高额的内存复制开销。HotSpot 虚拟机提供了-XX:PretenureSizeThreshold 参数（只对 Serial 和 ParNew 两款收集器有效），指定大于该设置值的对象直接在老年代分配。这样做的目的就是避免在 Eden 区及两个 Survivor 区之间来回复制，产生大量的内存复制操作

4）长期存活对象进入老年代
如果对象在 Eden 出生并经过第一次 Minor GC 后仍然存活，并且能被 Survivor 容纳的话，将被移动到 Survivor 空间中，并将对象年龄设为 1，对象在 Survivor 区中每熬过一次 Minor GC，年龄就增加 1，当它的年龄增加到一定程度(并发的垃圾回收器默认为 15),CMS 是 6 时，就会被晋升到老年代中。 -XX:MaxTenuringThreshold 调整

5）对象年龄动态判定
为了能更好地适应不同程序的内存状况，虚拟机并不是永远地要求对象的年龄必须达到了 MaxTenuringThreshold 才能晋升老年代，如果在 Survivor 空间中 相同年龄所有对象大小的总和大于 Survivor 空间的一半，年龄大于或等于该年龄的对象就可以直接进入老年代，无须等到 MaxTenuringThreshold 中要求的 年龄

6）空间分配担保
在发生 Minor GC 之前，虚拟机会先检查老年代最大可用的连续空间是否大于新生代所有对象总空间，如果这个条件成立，那么 Minor GC 可以确保是安全 的。如果不成立，则虚拟机会查看 HandlePromotionFailure 设置值是否允许担保失败。如果允许，那么会继续检查老年代最大可用的连续空间是否大于历 次晋升到老年代对象的平均大小，如果大于，将尝试着进行一次 Minor GC，尽管这次 Minor GC 是有风险的，如果担保失败则会进行一次 Full GC；如果小 于，或者 HandlePromotionFailure 设置不允许冒险，那这时也要改为进行一次 Full GC。

7）本地线程分配缓冲(TLAB)
每个线程在 Java 堆中预先分配一小块私有内存，也就是本地线程分配缓冲（Thread Local Allocation Buffer,TLAB），JVM 在线程初始化时，同时也会申请一块指定大小的内存，只给当前线程使用，这样每个线程都单独拥有一个 Buffer，如果 需要分配内存，就在自己的 Buffer 上分配，这样就不存在竞争的情况，可以大大提升分配效率，当 Buffer 容量不够的时候，再重新从 Eden 区域申请一块继续使用。

JVM 对象内存分配
1）指针碰撞：
如果堆内存是绝对规整的，一边是正在占用的内存，另外一边是空闲的内存，中间是一个分界点的指示器，那分配内存就只需要将指示器往空闲内存那一边挪动一段与对象大小相等的距离，这种方式叫做 指针碰撞

2）空闲列表：
如果堆内存不是规整的，已使用的内存和未使用的内存相互交错，那么 指针碰撞 这种方式就不再适用了。虚拟机必须维护一个内存列表，记录哪些内存是可用的，在分配的时候从列表中找到一块足够大的空间对象划分给对象实例，并更新内存列表记录，这种分配方式叫做 空闲列表

3）并发安全问题
通过CAS机制来解决分配原子性
image.png

4）分配缓冲机制-TLAB
每个线程在 Java 堆中预先分配一小块私有内存，也就是本地线程分配缓冲（Thread Local Allocation Buffer,TLAB），JVM 在线程初始化时，同时也会申请一块指定大小的内存，只给当前线程使用，这样每个线程都单独拥有一个 Buffer，如果 需要分配内存，就在自己的 Buffer 上分配，这样就不存在竞争的情况，可以大大提升分配效率，当 Buffer 容量不够的时候，再重新从 Eden 区域申请一块继续使用。

数据库

MySQL B 树和 B+树的区别
B+树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树
image.png

1）B 树非叶子节点保存节点和数据，B+树的非叶子节点不保存数据，数据保存在叶子节点中；所以 B+ 树的层高更低，显得更加矮胖，实际查找时磁盘 IO 数量更少。

2）B树的查找要只要匹配到元素，就不用管在什么位置，B+树查找必须匹配到叶子节点，所以B+树查找更稳定；

3）对于范围查找到说，B树要从头到尾查找，而B+树只需要在一定的范围内的叶子节点中查找就可以；

4）B+树的叶子节点通过指针连接，从左到右顺序排列；

5）B+树的非叶子节点与叶子节点冗余；

哪些列适合建立索引？怎样选择索引最合适？

1）离散程度|混乱程度 高的列建立索引

2）join 列建立索引

3）包含在 ORDER BY、GROUP BY、DISTINCT 中的字段

4）where 从句中的列建立索引

5）尽量建立联合索引，不要对表中的每一列都建立索引。建立联合索引的时候，遵循一下规则：
数据离散性高的列放在左侧：离散性越高，索引片的范围就越窄，扫描的数据就越少，实际io次数越少
字段长度小的列放在左侧：MySql内存页大小16k，字段长度越小，单个内存页的记录就越多，对应B+树的层高就越低（显得矮胖），实际对应io次数就越少。
使用最频繁的列放在左侧

6）针对较长文本字段，建议使用 前缀索引，前缀的长度选择多少合适呢？还是根据离散程度来确定，计算的sql如下：

SELECT
	count(DISTINCT LEFT ( NAME, 5 )) / count(*) rate5,
	count(DISTINCT LEFT ( NAME, 6 )) / count(*) rate6,
	count(DISTINCT LEFT ( NAME, 7 )) / count(*) rate7,
	count(DISTINCT LEFT ( NAME, 8 )) / count(*) rate8,
	count(DISTINCT LEFT ( NAME, 9 )) / count(*) rate9,
	count(DISTINCT LEFT ( NAME, 10 )) / count(*) rate10
FROM
	student_1;

image.png
如上图所示，前缀为6-8的时候建立前缀索引最好。

6）排除不需要的查询字段，尽量保证覆盖索引，避免回表。

7）总结：尽量达成三星索引
一星：所有等值谓词的列，是组合索引的开头的列，可以把索引片缩得很窄。
二星：在满足一星的情况下，当查询需要排序（group by、 order by）。如果查询所需的顺序与索引是一致的（索引本身是有序的）
三星：在满足了二星的情况下，如果索引中所包含了这个查询所需的所有列（包括 where 子句 和 select 子句中所需的列，也就是覆盖索引

安装 pytorch-gpu，op...
Redis 开发注意事项

评论