2021春招实习-Java语法和底层原理

第一部分：Java的语法和数据结构的底层细节

1.0 Java的循环

Java的循环方式有for使用下标循环，for-each循环，while循环和迭代器循环
- 使用下标和while完成循环是最常见的方式，对于数组或者collection都通用
- for-each循环是Java1.5之后带来的语法糖，可以用一个变量来遍历该类型的一个可迭代的结构，比如数组和集合
- iterator是一些结构提供的一个迭代器，可以用hasNext来判断是否到了末尾，并依次进行迭代
在Collection框架的数据结构下，如果使用for-each对一个容器进行遍历，那么在编译之后这一段for循环在class文件中会被优化成迭代器的形式
- 也就是说for-each语句是通过迭代器实现的 #### 1.0.1 for-each循环的坑
for-each循环是通过迭代器实现的，而Collection又一个fail-fast机制，如果有多个线程对同一个集合的内容进行操作的话就可能产生fail-fast，比如当一个线程A通过Iterator去遍历集合的时候，如果这个集合的内容被其他的线程改变了，那么迭代器访问集合的时候会抛出异常
迭代器工作在一个独立的线程中，并且拥有一个mutex锁，通过访问一个单向的索引链表来遍历所有的元素，如果原本的collection中的元素数量发生变化，索引表并不会同步这一变化，因此可能造成对象的遗失。比如遍历一个集合的时候如果remove了元素可能就会发生异常。
- 也就是说迭代器工作的过程中不允许被迭代的对象发生改变。 #### 1.0.2 效率问题
一般来说如果是可以随机访问的结构，比如说数组，那么直接食用for循环的效率将高于for-each循环，反过来如果只能进行顺序访问，比如链表，那么for-each循环的效率就会更高。 ### 1.1 Java的STL(Collection)
Java标准库中提供的常用数据结构和算法的模版有Vector，Stack，Queue，List，Set，Map等等，其中List，Set和Map又是Java的Collection大框架下的
以下是我在用Java刷Leetcode的过程中碰到的一些常见Collection的总结

1.1.1 List

List是一个继承了Collection的接口，底下有具体实现的类ArrayList和LinkedList，一般创建List对象的时候都需要用ArrayList或者LinkedList来具体实现，添加元素用add，获取元素用get
1
2
3
List<Integer> list = new ArrayList<>();
list.add(1);
System.out.println(list.get(0));
ArrayList和LinkedList的区别在于底层实现方式的不同，从名字中就可以看出一个是用数组实现的，一个是用链表实现的，值得注意的是LinkedList的底层是一个双向链表
- 相比于ArrayList，LinkedList的增删更快，而插入更慢，因此更具实际操作的需要可以确定具体选用哪种List的具体实现来提高代码的性能
- Vector和ArrayList一样，都是通过数组实现的，但是Vector是线程安全的 #### 1.1.2 Vector
Vector是一类动态数组，和ArrayList比较类似，用在事先不知道数组的大小，或者只是需要一个可以改变大小的数组的情况
- Vector也是实现了List的接口
Vector添加元素用add方法或者addElement，获取元素用elementAt方法 #### 1.1.3 Stack与Queue
Java提供的实现了栈和队列的数据结构，实际上都是一种List接口的具体实现，其中Stack是Vector的一个子类，提供了push，pop和peek等方法
LinkedList类实现了Queue接口，因此可以用LinkedList来创建一个队列，队列提供了offer和add方法在末尾插入元素，同时提供了poll方法移除队列首部的元素
1
2
3
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
int a = queue.poll();

1.2 HashMap的底层实现

1.2.1 基本结构

总体原则：先扩容，再变树，先数组，后链表
Java的HashMap实现了自Map抽象类，用数组+链表+红黑树来实现，数组用于存储元素的内容，链表用于解决hash时产生的冲突
- 如果链表长度大于阈值8但是当前数组长度小于树化的阈值64就会进行扩容，每次扩大两倍，如果数组的长度大于树化阈值64，链表就转变成红黑树
- 默认的初始容量是16，负载因子默认是0.75，当Map的当前容量大于总容量*负载因子的时候就要进行扩容的操作，并且扩容成原来的两倍

1.2.2 HashMap和HashTable的区别

HashTable没有树化操作，只有数组+链表
- HashTable在扩容的时候是2n+1的规则，而且初始的默认容量是11
在hash发生冲突的时候，hashmap使用尾插法插入链表，而table使用头插法插入链表
map是线程不安全的，而table用了synchronized关键字，所以是线程安全的

1.2.3 ConcurrentHashMap

通过synchronized关键字和CAS操作实现线程安全，如果插入的槽没有数据则使用CAS如果插入的槽有数据那么就可以通过synchronized关键字锁住链表的头节点从而实现效率和线程安全

1.2.4 冲突解决和具体实现

hash产生冲突的时候常见的处理办法有开放定址法(比如使用线性探测和平方探测)，也有rehash的办法和链地址法，hashmap采用的是链地址的方法，也就是数组+链表的方法
hashmap的主体是一个entry数组，每个entry是一个key-value对，如果定位到的数组位置没有链表，那么就很简单只需要一次寻址就查到了，如果包含链表那么就说明这个位置产生了hash冲突，链表上的点都对应着同一个hash函数值，那么就需要遍历链表进行插入删除等操作
处于性能的考虑，hashmap的链表出现的越少越好。

1.3 HashSet和TreeSet

这是Java的collection框架下Set接口的两种具体实现，所有的Set都是不包含重复元素的 #### 1.3.1 HashSet
HashSet底层是通过hash表来实现的，存储的元素是无序的，并且是不同步的，需要外部保持线程之间的同步问题，集合中元素的值允许事null，而通过构造函数可以知道，HashSet的底层是通过HashMap来实现的
HashSet实际上就是一个阉割了一些功能的HashMap
LinkedHashSet在HashSet的基础之上保留了插入的顺序 #### 1.3.2 TreeSet
TreeSet中的元素是有序存放的，因此必须要是可比较大小的元素才可以在TreeSet中存储，换句话说就是需要实现Comparable接口
TreeSet中的元素是不重复并且排好序的，默认采用升序排列，也可以进行自定义的排序。

1.4 并发与多线程

Java实现多线程并发的方式有三种：
- 实现runnable接口
- 继承Thread类
- 实现Callable接口
Java中的线程有New，Runnable,Blocked,Waiting,Timed-Waiting和Terminated等多种状态
实现Java的并发编程需要关注线程之间的同步和死锁，而同步往往可以 #### 1.4.1 synchronized关键字
synchronized方法可以修饰变量、方法和类
- synchronized解决的是执行控制的问题，当有线程在使用一个synchronized的方法的时候，会阻止其他线程调用这个方法，等该调用结束之后才允许下一个线程调用
- 使用synchronized修饰的东西无法并发执行

1.4.2 volatile关键字

Volatile关键字解决的是内存可见性的问题，会使得所有对volatile变量的读写都会直接刷到主存，即保证了变量的可见性。这样就能满足一些对变量可见性有要求而对读取顺序没有要求的需求
volatile就是标记一个变量存储在主内存中，堆该类型变量的每次读操作都会直接从计算机的主存中读取，而不是从CPU中读取 #### 1.4.3 二者的区别
volatile本质是在告诉JVM当前变量在寄存器（工作内存）中的值是不确定的，需要从主存中读取； synchronized则是锁定当前变量，只有当前线程可以访问该变量，其他线程被阻塞住
volatile仅能使用在变量级别；synchronized则可以使用在变量、方法、和类级别的
volatile仅能实现变量的修改可见性，不能保证原子性；而synchronized则可以保证变量的修改可见性和原子性
volatile不会造成线程的阻塞；synchronized可能会造成线程的阻塞
volatile标记的变量不会被编译器优化；synchronized标记的变量可以被编译器优化

第二部分：JVM相关

2.1 JVM垃圾回收机制 GC

2.1.1 常见的回收判断算法

要回收首先需要使用算法来判断对象是否可以回收

引用计数算法：记录每个对象被引用的次数，如果引用的次数为0就说明需要回收内存但事实上Java用的并不是这种策略，可以用下面一段代码来说明

public class refGC {
    public Object instance = null;
    private static final int _1MB = 1024;
    private byte[] bigMem = new byte[2 * _1MB];
    public static void main() {
        refGC a = new refGC(), b = new refGC();
        a.instance = b;
        b.instance = a;
        a = null;
        b = null;
    }
}

这段代码中虽然AB互相引用了，但是事实上还是作为垃圾被回收了，说明Java使用的并不是引用计数的策略

可达性分析算法：Java中使用的方法：GC-root
- 用一个对象作为GC-Roots，每次垃圾回收层root开始向下搜索，搜索的路径称为引用链
- 如果一个对象和root之间没有任何引用链，那么就需要进行回收
- Java语言中可以作为root的对象包括
  - 虚拟机栈中应用的对象
  - 方法区类静态属性引用的对象
  - 方法区常量引用的对象
  - 本地方法栈中本地方法引用的对象
- 对象被回收的时候，可以用finalize方法进行“自救”
引用的多种类型
- 强引用，只要强引用还存在，就不能把对象作为垃圾来回收，new出来的就是强引用
- 软引用：用来描述一些还有用但是并非必须的对象，软引用的关联的对象在系统将要发生内存溢出的异常之前，会对它们进行二次回收，之后还不行再抛出OOM异常
- 弱引用：描述非必须的对象，引用的强度比软引用还要弱，垃圾回收的时候一定会回收掉只有弱引用的对象
- 虚引用：最弱的引用，基本没啥用

2.1.2 垃圾回收算法

标记-清除算法：
- 先标记出有哪些垃圾需要回收，再进行回收——先标记再回收
- 问题是效率太低了，并且会在回收之后产生大量的不连续内存
复制算法：
- 将内存分成两块，一次只使用其中一块，需要垃圾回收的时候就把不需要回收的内存直接复制到另一块过去，然后把那一块内存清除，如此循环往复
- 实现简单，运行高效
标记-整理算法：
- 标记之后，回收的时候直接向前移动，这样就避免了一半内存的浪费

2.2 JVM运行时数据区

Java虚拟机在执行Java程序的时候会把它管理的内存划分为若干个不同的数据区域，这些区域有各自的创建和销毁的时间，而Java的运行时数据区域包含这样几个部分

方法区：
- 存储已经被虚拟机加载的类的信息、常量、静态变量和JIT编译器编译后的代码，JVM的规范把方法区描述成了堆的一个逻辑部分
- 这个区域中垃圾回收方法比较少见
- 运行时常量池 Runtime Constant Pool
  - Java的class文件中除了有类的版本、字段、方法、接口等信息描述之外，还需要有常量池用于存放编译器生成的字面量和符号引用，这一部分内容将在类加载到方法区之后，在常量池中存放
  - 动态性：常量不一定需要编译器才能产生，运行期间也可以将新的常量放入常量池中，这种特性用的比较多的就是String类中的intern( )方法

堆：

是JVM管理的内存中最大的一块，是线程共享的的一块内存区域，在虚拟机启动的时候就会创建
所有对象的实例和数组都需要在堆上分配内存，也是垃圾收集器的主要管理区域
线程共享的Java堆可以划分出多个线程私有的分配缓冲区 TLAB
Java堆的内存空间不一定是物理上连续的，只要是逻辑上连续就可以

下面这段代码是非常常见的堆溢出异常，引发原因是对象实例过多

public class HeapOOM {
    static class OOMObject {
        int a;
    }
    public static void main(String[] args) {
        List<OOMObject> list = new ArrayList<OOMObject>();
        while (true) {
            list.add(new OOMObject());
        }
    }
}

虚拟机栈：
- Java的虚拟机栈也是线程私有的，生命周期和所属线程的生命周期相同
- 描述了Java方法执行的内存模型，在每个方法执行的时候会创建一个栈帧(Stack Frame),用于存储
  - 局部变量表
    - 存放了编译期就可以知道的数据类型(基本的boolean，byte，char，int等八种)、对象引用和returnAddress类型
    - 其中long和double需要占用2个局部变量空间slot(槽)，其他的都是1个空间
    - 局部变量表在运行期间就完成了分配，一个方法的分配的局部变量空间是完全确定的，因此方法运行期间不会改变局部变量的大小
  - 操作数栈
  - 动态链接
  - 方法出口
- 每一个方法从调用到执行结束的过程，就是一个栈帧在VMStack中入栈到出栈的过程
- 这个区域会抛出StackOverFlowError异常和OutOfMemoryError异常
本地方法栈：
- 和虚拟机栈发挥的作用比较类似，区别是本地方法栈执行的是本地的方法
程序计数器：
- 比较小的一块内存空间，和汇编语言中的PC一样用来指示当前运行的字节码的行号，各种分支、循环、跳转和异常处理都依赖PC实现
- Java虚拟机的多线程是通过线程的切换和分配处理器执行时间的方式来实现的，在任何一个确定的时候，一个处理器只能处理一个线程，因此每个线程都需要一个单独的PC，因此是线程私有的
- 如果执行的是本地的方法，则此时PC的值是undefined
不同数据区域的特性
- 这些区域中，方法区和堆直接和执行引擎进行交互，是线程共享的
- 而虚拟机栈、本地方法栈和程序计数器直接合本地库接口进行交互，是线程之间独立的

直接内存 Direct Memory
- 不是JVM中定义的内存区域，但是也被频繁使用
- 这是JDK后期引入的NIO类，基于通道和缓冲区的I/O方式，可以使用Native函数库直接分配堆外的内存，可以使用本地函数库直接分配对外内存，然后通过DirectByteBuffer对这些区域进行引用的需要 #### 2.2.1 Java的内存模式
Java的内存模型将内存分为共享内存和本地内存，共享内存又称为堆内存，指的就是线程之间共享的内容，包含所有的实例、静态域和数组，每个线程有一个仅自己可见的本地内存
- 每个线程都有单独的本地内存，通过save和load操作和主内存之间通信

2.3 Java的内存管理模型JMM

Java的内存模型主要定义了各个变量的访问规则，这里的变量包含了实例字段、静态字段和构成数组对象的元素，但是不包含局部变量和方法参数，因为这是线程私有的。
JMM规定了所有的变量都必须存储在主内存中，每个线程还有自己专用的工作内存，工作内存保存了该线程使用到的变量的副本拷贝
- 线程对变量的所有操作都必须在工作内存中进行，并且不能直接读写主内存中的变量
- volatile变量仍然有工作内存的拷贝，但是由于该关键字的特性，所以看起来像是直接在主内存中进行读写访问，不同的线程直接无法访问其他线程的工作内存中的变量，线程之间的值的传递都需要通过主内存来完成。
JMM的三大特性：原子性、可见性和有序性
- 原子性是指一个操作不能被打断，要不就彻底不执行，要不就完全执行
- 可见性：一个线程对共享变量进行修改之后其他线程立刻可以看到该变量的变化
- 有序性：多线程并发的程序中，一系列的操作按照一定的规则来进行，不会变的无序，Java中有volatile和synchronized两个关键字来保证操作的有序性