2021-07-29 23:04 门头沟学院 Java

关注

Java后端知识总结

计算机网络

HTTP无状态

一、HTTP协议的状态

HTTP是一种无状态协议，即服务器不保留与客户通信时的任何状态。

也就是说，上一次的请求对这次的请求没有任何影响，服务端也不会对客户端上一次的请求进行任何记录处理。

二、HTTP协议的无状态性带来的问题

用户登录后，切换到其他界面，进行操作，服务器端是无法判断是哪个用户登录的。每次进行页面跳转的时候，得重新登录。

三、解决方案

既然HTTP协议是无状态的，不会记录用户信息，那么怎么样才能让HTTP协议记录用户信息呢？换句话说，服务器怎么判断发来HTTP请求的是哪个用户？

于是，两种用于保持HTTP状态的技术就应运而生了，一个是 Cookie，而另一个则是 Session。

TCP为什么要三次握手

TCP为什么要四次握手

IO方式

操作系统层的IO模型

阻塞IO模型

应用进程通过系统调用 recvfrom 接收数据，但由于内核还未准备好数据报，应用进程就会阻塞住，直到内核准备好数据报，recvfrom 完成数据报复制工作，应用进程才能结束阻塞状态。

非阻塞IO模型

应用进程通过轮询的方式与内核交互，不停的去询问内核数据准备有没有准备好。如果某一次轮询发现数据已经准备好了，那就把数据拷贝到用户空间中。

应用进程通过 recvfrom 调用不停的去和内核交互，直到内核准备好数据。如果没有准备好，内核会返回error，应用进程在得到error后，过一段时间再发送recvfrom请求。在两次发送请求的时间段，进程可以先做别的事情。

信号驱动IO模型

应用进程预先向内核注册一个信号处理函数，然后用户进程返回，并且不阻塞，当内核数据准备就绪时会发送一个信号给进程，用户进程便在信号处理函数中开始把数据拷贝的用户空间中。

IO多路复用模型

IO多路服用是多了一个select函数，多个进程的IO可以注册到同一个select上，当用户进程调用该select，select会监听所有注册好的IO，如果所有被监听的IO需要的数据都没有准备好时，select调用进程会阻塞。当任意一个IO所需的数据准备好之后，select调用就会返回，然后进程在通过recvfrom来进行数据拷贝。

这里的IO复用模型，并没有向内核注册信号处理函数，所以，他并不是非阻塞的。进程在发出select后，要等到select监听的所有IO操作中至少有一个需要的数据准备好，才会有返回，并且也需要再次发送请求去进行文件的拷贝。

异步IO模型

应用进程把IO请求传给内核后，完全由内核去操作文件拷贝。内核完成相关操作后，会发信号告诉应用进程本次IO已经完成。

用户进程发起aio_read操作之后，给内核传递描述符、缓冲区指针、缓冲区大小等，告诉内核当整个操作完成时，如何通知进程，然后就立刻去做其他事情了。当内核收到aio_read后，会立刻返回，然后内核开始等待数据准备，数据准备好以后，直接把数据拷贝到用户控件，然后再通知进程本次IO已经完成。

select/epoll（todo）

select

简单来说：select通过轮询去遍历所有的事件列表来监听多个IO事件，当其中一个IO或者多个IO可读或者可写的时候，它就会返回，而如果所有的IO都是不可读或者不可写的时候，这个进程就会被阻塞，直到超时或者IO可读写，当select函数返回后，可以通过遍历事件列表，来找到就绪的描述符，进行读写。

具体实现：

select使用了一个fd_set数据结构来存放所有的文件描述符，并对他们进行监控，当某个IO事件可读写之后，就把它对应的文件描述符设为就绪状态，select函数返回，并将fd_set拷贝到用户进程中，用户进程通过遍历fd_set来处理对应的IO事件。

每个select都要处理一个fd_set结构。fd_set简单地理解为一个长度是1024的比特位，每个比特位表示一个需要处理的文件描述符，如果是1，那么表示这个FD有需要处理的I/O事件。

缺点：

单个进程能够监视的文件描述符的数量存在最大限制，在Linux上一般为1024，可以通过修改宏定义甚至重新编译内核的方式提升这一限制，但是这样也会造成效率的降低，fd越多，越慢。
需要维护一个用来存放大量fd的数据结构，这样会使得用户空间和内核空间在传递该结构时复制开销大。
需要遍历一遍所有的fd找到活跃的描述符，这会带来大量的时间消耗（时间复杂度是O(n)，并且伴随着描述符越多，这开销呈线性增长）

poll

poll的实现和select非常相似，只是存放描述符的数据结构不同，因为它是使用链表维护这些文件描述符，poll不限制文件描述符的个数。

select和poll的共同缺点

都是同步IO，在IO事件未就绪之前都会被阻塞
包含大量文件描述符的数据被整体复制于用户态和内核的地址空间之间，而不论这些文件描述符是否就绪，它的开销随着文件描述符数量的增加而线性增大。

epoll

epoll使用一个epfd（epoll文件描述符）管理多个socket描述符，epoll不限制socket描述符的个数，将用户空间的socket描述符的事件存放到内核的一个事件表中，这样在用户空间和内核空间的copy只需一次。当epoll记录的socket产生就绪的时候，epoll会通过callback的方式来激活这个fd，这样子在epoll_wait便可以收到通知，告知应用层哪个socket就绪了，这种通知的方式是可以直接得到那个socket就绪的，因此相比于select和poll，它不需要遍历socket列表，时间复杂度是O(1)，不会因为记录的socket增多而导致开销变大。

epoll的操作模式

select和poll只支持LT模式。

epoll对socket描述符的操作有两种模式：LT（level trigger）和ET（edge trigger）。LT模式是默认模式，LT模式与ET模式的区别如下：

LT模式：即水平触发模式，当epoll_wait检测到socket描述符处于就绪时就通知应用程序，应用程序可以不立即处理它。下次调用epoll_wait时，还会再次产生通知。
ET模式：即边缘触发模式，当epoll_wait检测到socket描述符处于就绪时就通知应用程序，应用程序必须立即处理它。如果不处理，下次调用epoll_wait时，不会再次产生通知。

ET模式在很大程度上减少了epoll事件被重复触发的次数，因此效率要比LT模式高。epoll工作在ET模式的时候，必须使用非阻塞套接口，以避免由于一个文件句柄的阻塞读/阻塞写操作把处理多个文件描述符的任务饿死。

NIO

Get和Post区别

最直观的区别就是GET把参数包含在URL中，POST通过request body传递参数

GET和POST本质上就是TCP链接，并无差别。但是由于HTTP的规定和浏览器/服务器的限制，导致他们在应用过程中体现出一些不同。

GET和POST还有一个重大区别，简单的说：GET产生一个TCP数据包；POST产生两个TCP数据包。

对于GET方式的请求，浏览器会把http header和data一并发送出去，服务器响应200（返回数据）；
而对于POST，浏览器先发送header，服务器响应100 continue，浏览器再发送data，服务器响应200 ok（返回数据）。

Cookie和Session

Cookie 和 Session都是用来跟踪浏览器用户身份的会话方式，但是两者的应用场景不太一样。

Cookie 一般用来保存用户信息 比如①我们在 Cookie 中保存已经登录过得用户信息，下次访问网站的时候页面可以自动帮你登录的一些基本信息给填了；②一般的网站都会有保持登录也就是说下次你再访问网站的时候就不需要重新登录了，这是因为用户登录的时候我们可以存放了一个 Token 在 Cookie 中，下次登录的时候只需要根据 Token 值来查找用户即可(为了安全考虑，重新登录一般要将 Token 重写)；③登录一次网站后访问网站其他页面不需要重新登录。Session 的主要作用就是通过服务端记录用户的状态。 典型的场景是购物车，当你要添加商品到购物车的时候，系统不知道是哪个用户操作的，因为 HTTP 协议是无状态的。服务端给特定的用户创建特定的 Session 之后就可以标识这个用户并且跟踪这个用户了。

Cookie 数据保存在客户端(浏览器端)，Session 数据保存在服务器端。

Cookie 存储在客户端中，而Session存储在服务器上，相对来说 Session 安全性更高。如果使用 Cookie 的一些敏感信息不要写入 Cookie 中，最好能将 Cookie 信息加密然后使用到的时候再去服务器端解密。

转发(Forward)和重定向(Redirect)的区别

转发是服务器行为，重定向是客户端行为。

forward是服务器请求资源,服务器直接访问目标地址的URL,把那个URL的响应内容读取过来,然后把这些内容再发给浏览器.浏览器根本不知道服务器发送的内容从哪里来的,所以它的地址栏还是原来的地址. redirect是服务端根据逻辑,发送一个状态码,告诉浏览器重新去请求那个地址.所以地址栏显示的是新的URL.

操作系统

进程和线程

进程是程序的执行过程，是操作系统资源分配的基本单位，具有独立的内存地址空间，线程是进程中的一个执行任务，可以看作轻量级的进程；一个进程包含多个线程，多个线程共享进程的资源。

根本区别：进程是操作系统资源分配的基本单位，而线程是处理器任务调度和执行的基本单位

资源开销：每个进程都有独立的代码和数据空间（程序上下文），程序之间的切换会有较大的开销；线程可以看做轻量级的进程，同一类线程共享代码和数据空间，每个线程都有自己独立的运行栈和程序计数器（PC），线程之间切换的开销小。

包含关系：如果一个进程内有多个线程，则执行过程不是一条线的，而是多条线（线程）共同完成的；线程是进程的一部分，所以线程也被称为轻权进程或者轻量级进程。

内存分配：同一进程的线程共享本进程的地址空间和资源，而进程之间的地址空间和资源是相互独立的

影响关系：一个进程崩溃后，在保护模式下不会对其他进程产生影响，但是一个线程崩溃整个进程都死掉。所以多进程要比多线程健壮。

执行过程：每个独立的进程有程序运行的入口、顺序执行序列和程序出口。但是线程不能独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制，两者均可并发执行

上下文切换

当前任务在执行完 CPU 时间片切换到另一个任务之前会先保存自己的状态，以便下次再切换回这个任务时，可以再加载这个任务的状态。任务从保存到再加载的过程就是一次上下文切换。

线程私有

虚拟机栈： 每个 Java 方法在执行的同时会创建一个栈帧用于存储局部变量表、操作数栈、常量池引用等信息。从方法调用直至执行完成的过程，就对应着一个栈帧在 Java 虚拟机栈中入栈和出栈的过程。
本地方法栈： 和虚拟机栈所发挥的作用非常相似，区别是： 虚拟机栈为虚拟机执行 Java 方法（也就是字节码）服务，而本地方法栈则为虚拟机使用到的 Native 方法服务。 在 HotSpot 虚拟机中和 Java 虚拟机栈合二为一。

Java基础

包装类

当使用自动装箱方式创建一个Integer对象时，当数值在-128 ~127时，会将创建的 Integer 对象缓存起来，直接从缓存中取出对应的Integer对象。
浮点数之间的等值判断，基本数据类型不能用==来比较，包装数据类型不能用 equals 来判断。

List排序

自动装箱和自动拆箱

自动装箱 ----- 基本类型的值 → 包装类的实例

自动拆箱 ----- 基本类型的值 ← 包装类的实例

自动装箱：系统会自动把一个基本类型的值自动装箱为一个包装类的实例来使用
自动拆箱：系统会自动把一个包装类的实例自动拆箱为一个基本类型的值来使用

Arrays.asList

Arrays.asList()将数组转换为集合后,底层其实还是数组
不能使用List的修改方***抛出异常
Arrays.asList()是泛型方法，传入的对象必须是对象数组。
Arrays.asList() 方法返回是 java.util.Arrays 的一个内部类，这个内部类并没有实现集合的修改方法

Collection.toArray()、如何反转数组

该方法是一个泛型方法：<T> T[] toArray(T[] a); 如果toArray方法中没有传递任何参数的话返回的是Object类型数组

String [] s= new String[]{
    "dog", "lazy", "a", "over", "jumps", "fox", "brown", "quick", "A"
};
List<String> list = Arrays.asList(s);
Collections.reverse(list);
s=list.toArray(new String[0]);//没有指定类型的话会报错

不要在 foreach 循环里进行元素的 remove/add 操作

remove元素请使用Iterator方式
原因：单线程状态下产生的 fail-fast 机制

如何正确的将数组转换为ArrayList?

List list = new ArrayList<>(Arrays.asList("a", "b", "c"))

枚举类型

final 关键字

final关键字，意思是最终的、不可修改的，最见不得变化，用来修饰类、方法和变量，具有以下特点：

final修饰的类不能被继承，final类中的所有成员方法都会被隐式的指定为final方法；
final修饰的方法不能被重写；
final修饰的变量是常量，如果是基本数据类型的变量，则其数值一旦在初始化之后便不能更改；如果是引用类型的变量，则在对其初始化之后便不能让其指向另一个对象。

static 关键字

static 关键字主要有以下四种使用场景：

修饰成员变量和成员方法
静态代码块
静态内部类（static修饰类的话只能修饰内部类）
静态导包

被static 声明的成员变量属于静态成员变量，静态变量存放在 Java 内存区域的方法区。

方法区与 Java 堆一样，是各个线程共享的内存区域，它用于存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。

使用 this 和 super 要注意的问题

在构造器中使用 super（） 调用父类中的其他构造方法时，该语句必须处于构造器的首行，否则编译器会报错。另外，this 调用本类中的其他构造方法时，也要放在首行。
this、super不能用在static方法中。

静态代码块

静态代码块定义在类中方法外, 静态代码块在非静态代码块之前执行(静态代码块—非静态代码块—构造方法)。该类不管创建多少对象，静态代码块只执行一次.

静态内部类

静态内部类与非静态内部类之间存在一个最大的区别，我们知道非静态内部类在编译完成之后会隐含地保存着一个引用，该引用是指向创建它的外围类，但是静态内部类却没有。没有这个引用就意味着：

它的创建是不需要依赖外围类的创建。
它不能使用任何外围类的非static成员变量和方法。

`static{}`静态代码块与`{}`非静态代码块(构造代码块)

相同点：都是在JVM加载类时且在构造方法执行之前执行，在类中都可以定义多个，定义多个时按定义的顺序执行，一般在代码块中对一些static变量进行赋值。

不同点：静态代码块在非静态代码块之前执行(静态代码块—非静态代码块—构造方法)。静态代码块只在第一次new执行一次，之后不再执行，而非静态代码块在每new一次就执行一次。非静态代码块可在普通方法中定义(不过作用不大)；而静态代码块不行。

Java反射机制

反射机制介绍

JAVA 反射机制是在运行状态中，对于任意一个类，都能够知道这个类的所有属性和方法；对于任意一个对象，都能够调用它的任意一个方法和属性；这种动态获取的信息以及动态调用对象的方法的功能称为 java 语言的反射机制。

获取Class对象的方式

1.知道具体类的情况下可以使用：

Class alunbarClass = TargetObject.class

但是我们一般是不知道具体类的，基本都是通过遍历包下面的类来获取 Class 对象

2.通过 Class.forName()传入类的路径获取：

Class alunbarClass1 = Class.forName("cn.javaguide.TargetObject");Copy to clipboardErrorCopied

3.通过对象实例instance.getClass()获取：

Employee e;
Class alunbarClass2 = e.getClass();

静态编译和动态编译

静态编译： 在编译时确定类型，绑定对象
动态编译： 运行时确定类型，绑定对象

反射机制优缺点

优点： 运行期类型的判断，动态加载类，提高代码灵活度。
缺点：
1. 性能瓶颈：反射相当于一系列解释操作，通知 JVM 要做的事情，性能比直接的 java 代码要慢很多。
2. 安全问题，让我们可以动态操作改变类的属性同时也增加了类的安全隐患。

错误和异常

Throwable： Exception（异常）和 Error（错误）

Error（错误）:是在程序运行过程中出现的比较严重的问题，程序自己无法处理，由虚拟机生成并抛出，大多数错误与代码编写者所执行的操作无关。

异常（Exception）：异常是程序本身可以处理的，一般是由程序逻辑错误引起的，异常包括运行时异常和非运行时异常。

RuntimeException及其子类和Error是非必检异常，其他的异常是必检异常。

Java集合框架

Collection和Map

从下图可以看出，在 Java 中除了以 Map 结尾的类之外，其他类都实现了 Collection 接口。并且，以 Map 结尾的类都实现了 Map 接口。

集合框架底层数据结构总结

List

Arraylist： Object[]数组
Vector：Object[]数组
LinkedList：双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)

Set

HashSet（无序，唯一）: 基于 HashMap 实现的，底层采用 HashMap 来保存元素
LinkedHashSet：LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的 LinkedHashMap 其内部是基于 HashMap 实现一样，不过还是有一点点区别的
TreeSet（有序，唯一）：红黑树(自平衡的排序二叉树)

再来看看 Map 接口下面的集合。

Map

HashMap： JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间
LinkedHashMap： LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。详细可以查看：《LinkedHashMap 源码详细分析（JDK1.8）》
Hashtable：数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的
TreeMap：红黑树（自平衡的排序二叉树）

有哪些集合是线程不安全的？怎么解决呢？

我们常用的 Arraylist ,LinkedList,Hashmap,HashSet,TreeSet,TreeMap，PriorityQueue 都不是线程安全的。解决办法很简单，可以使用线程安全的集合来代替。

如果你要使用线程安全的集合的话， java.util.concurrent 包中提供了很多并发容器供你使用：

ConcurrentHashMap: 可以看作是线程安全的 HashMap
CopyOnWriteArrayList:可以看作是线程安全的 ArrayList，在读多写少的场合性能非常好，远远好于 Vector.
ConcurrentLinkedQueue:高效的并发队列，使用链表实现。可以看做一个线程安全的 LinkedList，这是一个非阻塞队列。
BlockingQueue: 这是一个接口，JDK 内部通过链表、数组等方式实现了这个接口。表示阻塞队列，非常适合用于作为数据共享的通道。
ConcurrentSkipListMap :跳表的实现。这是一个Map，使用跳表的数据结构进行快速查找。

Arraylist 与 LinkedList 区别?

是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
底层数据结构： Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
插入和删除是否受元素位置的影响： ① ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储，所以对于add(E e)方法的插入，删除元素时间复杂度不受元素位置的影响，近似 O(1)，如果是要在指定位置i插入和删除元素的话（(add(int index, E element)）时间复杂度近似为o(n))因为需要先移动到指定位置再插入。
是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
内存空间占用： ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

ArrayList和LinkedList内存占用

一般情况下，LinkedList的占用空间更大，因为每个节点要维护指向前后地址的两个节点，但也不是绝对，如果刚好数据量超过ArrayList默认的临时值时，ArrayList占用的空间也是不小的，因为扩容的原因会浪费将近原来数组一半的容量，不过，因为ArrayList的数组变量是用transient关键字修饰的，如果集合本身需要做序列化操作的话，ArrayList这部分多余的空间不会被序列化。

HashMap 和 Hashtable 的区别

线程是否安全： HashMap 是非线程安全的，HashTable 是线程安全的,因为 HashTable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
初始容量大小和每次扩充容量大小的不同： ① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。
底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

HashSet 如何检查重复

当你把对象加入HashSet时，HashSet 会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。（摘自我的 Java 启蒙书《Head fist java》第二版）

hashCode()与 equals()的相关规定：

如果两个对象相等，则 hashcode 一定也是相同的
两个对象相等,对两个 equals 方法返回 true
两个对象有相同的 hashcode 值，它们也不一定是相等的
综上，equals 方法被覆盖过，则 hashCode 方法也必须被覆盖
hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写 hashCode()，则该 class 的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

所以重写 hashcode 方法是为了让我们能够正常使用 HashMap 等集合类，因为 HashMap 判断对象是否相等既要比较 hashcode 又要使用 equals 比较。而这样的实现是为了提高 HashMap 的效率。

`HashMap` 的底层实现

1.4.5.1. JDK1.8 之前

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

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法换句话说使用扰动函数之后可以减少碰撞。

HashMap 的长度为什么是 2 的幂次方

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上面也讲到了过了，Hash 值的范围值-2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash”。（n 代表数组长度）。这也就解释了 HashMap 的长度为什么是 2 的幂次方。

这个算法应该如何设计呢？

我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方。

ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
实现线程安全的方式（重要）： ① 在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后对 synchronized 锁做了很多优化）整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

HashTable全表锁

JDK1.7的ConcurrentHashMap

JDK1.8 的 ConcurrentHashMap 不在是 Segment 数组 + HashEntry 数组 + 链表，而是 Node 数组 + 链表 / 红黑树。不过，Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode。当冲突链表达到一定长度时，链表会转换成红黑树。

ConcurrentHashMap 线程安全的具体实现方式/底层具体实现

JDK1.7

首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。

static class Segment<K,V> extends ReentrantLock implements Serializable {
}Copy to clipboardErrorCopied

一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。

JDK1.8

ConcurrentHashMap 取消了 Segment 分段锁，采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）

synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。

Java并发

synchronized底层原理

synchronzied使用

修饰实例方法: 作用于当前对象实例加锁，进入同步代码前要获得 当前对象实例的锁
修饰静态方法: 也就是给当前类加锁，会作用于类的所有对象实例，进入同步代码前要获得 当前 class 的锁。
修饰代码块 ：指定加锁对象，对给定对象/类加锁。

synchronzied是可重入锁

synchronzied代码块原理

synchronized 同步语句块的实现使用的是 monitorenter 和 monitorexit 指令，其中 monitorenter 指令指向同步代码块的开始位置，monitorexit 指令则指明同步代码块的结束位置。

当执行 monitorenter 指令时，线程试图获取锁也就是获取 对象监视器 monitor 的持有权。

在执行monitorenter时，会尝试获取对象的锁，如果锁的计数器为 0 则表示锁可以被获取，获取后将锁计数器设为 1 也就是加 1。如果获取对象锁失败，那当前线程就要阻塞等待，直到锁被另外一个线程释放为止。

在执行 monitorexit 指令后，将锁计数器设为 0，表明锁被释放。

scnchronzied修饰方法原理

synchronized 修饰的方法并没有 monitorenter 指令和 monitorexit 指令，取得代之的确实是 ACC_SYNCHRONIZED 标识，该标识指明了该方法是一个同步方法。JVM 通过该 ACC_SYNCHRONIZED 访问标志来辨别一个方法是否声明为同步方法，从而执行相应的同步调用。

总结

synchronized 修饰的方法并没有 monitorenter 指令和 monitorexit 指令，取得代之的确实是 ACC_SYNCHRONIZED 标识，该标识指明了该方法是一个同步方法。

不过两者的本质都是对对象监视器 monitor 的获取。

双重校验锁实现对象单例（线程安全）

public class Singleton {

    private volatile static Singleton uniqueInstance;

    private Singleton() {
    }

    public  static Singleton getUniqueInstance() {
       //先判断对象是否已经实例过，没有实例化过才进入加锁代码
        if (uniqueInstance == null) {
            //类对象加锁
            synchronized (Singleton.class) {
                if (uniqueInstance == null) {
                    uniqueInstance = new Singleton();
                }
            }
        }
        return uniqueInstance;
    }
}

threadLocal

ThreadLocal类并不是用来解决多线程环境下的共享变量问题，而是用来提供线程内部的共享变量，在多线程环境下，可以保证各个线程之间的变量互相隔离、相互独立。在线程中，可以通过get()/set()方法来访问变量。ThreadLocal实例通常来说都是private static类型的，它们希望将状态与线程进行关联。这种变量在线程的生命周期内起作用，可以减少同一个线程内多个函数或者组件之间一些公共变量的传递的复杂度。

实现原理

早期实现

ThreadLocal最简单的实现方式就是ThreadLocal类内部有一个线程安全的Map，然后用线程的ID作为Map的key，实例对象作为Map的value，这样就能达到各个线程的值隔离的效果。

改进

ThreadLocalMap类是ThreadLocal的静态内部类。每个Thread维护一个ThreadLocalMap映射表，这个映射表的key是ThreadLocal实例本身，value是真正需要存储的Object。这样的设计主要有以下几点优势：

这样设计之后每个Map的Entry数量变小了：之前是Thread的数量，现在是ThreadLocal的数量，能提高性能；
当Thread销毁之后对应的ThreadLocalMap也就随之销毁了，能减少内存使用量。

threadLocal存在的问题

ThreadLocalMap是使用ThreadLocal的==弱引用==作为Key的，如果一个ThreadLocal没有外部关联的强引用，那么在虚拟机进行垃圾回收时，这个ThreadLocal会被回收，所以ThreadLocalMap中就会出现key为null的Entry，这些key对应的value也就再无妨访问，但是value却存在一条从CurrentThread过来的强引用链。因此只有当CurrentThread销毁时，value才能得到释放。

因此，只要这个线程对象被gc回收，那些key为null对应的value也会被回收，这样也没什么问题，但在线程对象不被回收的情况下，比如使用线程池的时候，核心线程是一直在运行的，线程对象不会回收，若是在这样的线程中存在上述现象，就可能出现内存泄露的问题。

解决方法

ThreadLocalMap采用线性探查的方式来处理哈希冲突，所以会有一个while循环去查找对应的key，在查找过程中，若发现key为null，即通过弱引用的key被回收了，这时就会==清理==与key对应的value以及Entry。

如果我们既不需要添加value，也不需要获取value，那还是有可能产生内存泄漏的。所以很多情况下需要使用者手动调用ThreadLocal的remove()函数，手动删除不再需要的ThreadLocal，防止内存泄露。

最好的方式就是将ThreadLocal变量定义成private static的，这样的话ThreadLocal的生命周期就更长，由于一直存在ThreadLocal的强引用，所以ThreadLocal也就不会被回收，也就能保证任何时候都能根据ThreadLocal的弱引用访问到Entry的value值，然后remove它，可以防止内存泄露。

AQS

核心思想

如果被请求的资源空闲，那么就将当前请求资源的线程设为有效的工作线程，并且将共享资源设置为锁定状态。如果被请求的共享资源被占用，那么就需要一套线程阻塞等待以及被唤醒时锁分配的机制，这个机制 AQS 是用 CLH 队列锁实现的，即将暂时获取不到锁的线程加入到队列中。

具体实现

AQS在内部使用一个int类型的变量state来进行线程间的同步，使用ACS操作来修改state变量的值，内置一个FIFO的队列来管理等待的线程。

对资源的共享方式

1、独占

只有一个线程能够获得资源，如果一个线程获取到了资源，会标记这个线程获得了资源，其他线程再尝试操作state获取资源时会发现当前该资源不是自己持有的，就会在获取失败后被阻塞。

2、共享

当多个线程去请求资源时通过CAS方式竞争获取资源，当一个线程获取到了资源后，另外一个线程再次去获取时如果当前资源还能满足它的需要，则当前线程只需要使用CAS方式进行获取即可。

ReenTrantLock实现

继承自AQS实现的独占锁ReentrantLock，定义当state为0时表示锁空闲，为1时表示锁已经被占用。在内部需要使用CAS算法查看当前state是否为0，如果为0则使用CAS设置为1，并设置当前锁的持有者为当前线程，而后返回true，如果CAS失败则返回false。

获取锁

当一个线程获取锁时，如果锁当前没有被其他线程占用并且当前线程之前没有获取过该锁，则当前线程会获取到该锁，然后设置当前锁的拥有者为当前线程，并设置AQS的状态值为1，然后直接返回。如果当前线程之前已经获取过该锁，则这次只是简单地把AQS的状态值加1后返回。如果该锁已经被其他线程持有，则调用该方法的线程会被放入AQS队列后阻塞挂起。

释放锁

当一个线程释放锁时，如果当前线程持有该锁，则调用该方***让该线程对该线程持有的AQS状态值减1，如果减去1后当前状态值为0，则当前线程会释放该锁，否则仅仅减1而已。

总结

ReentrantLock的底层是使用AQS实现的可重入独占锁。在这里AQS状态值为0表示当前锁空闲，为大于等于1的值则说明该锁已经被占用。该锁内部有公平与非公平实现，默认情况下是非公平的实现。另外，由于该锁是独占锁，所以某时只有一个线程可以获取该锁。

ReentrantReadWriteLock实现

读写锁的内部维护了一个ReadLock和一个WriteLock，它们依赖Sync实现具体功能。而Sync继承自AQS，并且也提供了公平和非公平的实现。下面只介绍非公平的读写锁实现。我们知道AQS中只维护了一个state状态，而ReentrantReadWriteLock则需要维护读状态和写状态，一个state怎么表示写和读两种状态呢？ReentrantReadWriteLock巧妙地使用state的高16位表示读状态，也就是获取到读锁的次数；使用低16位表示获取到写锁的线程的可重入次数，并通过CAS对其进行操作实现了读写分离，这在读多写少的场景下比较适用。

获取写锁

写锁是个独占锁，某时只有一个线程可以获取该锁。如果当前没有线程获取到读锁和写锁，则当前线程可以获取到写锁，state加1然后返回。如果当前已经有线程获取到读锁和写锁，则当前请求写锁的线程会被阻塞挂起。另外，写锁是可重入锁，如果当前线程已经获取了该锁，再次获取只是简单地把state加1后直接返回。

释放写锁

如果当前线程持有写锁，对该线程持有的state减1，如果减去1后当前状态值为0则当前线程会释放该锁，否则仅仅减1而已。

获取读锁

获取读锁，如果当前没有其他线程持有写锁，则当前线程可以获取读锁，AQS的状态值state的高16位的值会增加1，然后方法返回。否则如果其他一个线程持有写锁，则当前线程会被阻塞。

释放读锁

如果当前线程持有写锁，对该线程持有的AQS状态值减1，线程释放读锁。

StampedLock实现

Semaphore 就是一个共享锁，Semaphore(信号量)可以指定多个线程同时访问某个资源。通过设置 state 变量来实现对这个变量的共享。当调用 acquire 方法的时候，state 变量就减去一，当调用 release 方法的时候，state 变量就加一。当 state 变量为 0 的时候，别的线程就不能进入代码块了，就会在 AQS 中阻塞等待。

线程池

线程池的好处

创建/销毁线程需要消耗系统资源，线程池可以复用已创建的线程。
控制并发的数量。并发数量过多，可能会导致资源消耗过多，从而造成服务器崩溃。（主要原因）
可以对线程做统一管理。

Executor框架

Executor 框架不仅包括了线程池的管理，还提供了线程工厂、队列以及拒绝策略等，Executor 框架让并发编程变得更加简单。

1、任务

任务需要实现 Runnable 接口 或 Callable接口。Runnable 接口或 Callable 接口 实现类都可以被 ThreadPoolExecutor 或 ScheduledThreadPoolExecutor 执行。

2、任务的执行

如下图所示，包括任务执行机制的核心接口 Executor ，以及继承自 Executor 接口的 ExecutorService 接口。ThreadPoolExecutor 和 ScheduledThreadPoolExecutor 这两个关键类实现了 ExecutorService 接口。

3、异步计算的结果

使用Future 接口以及 Future 接口的实现类 FutureTask 类都可以返回异步计算的结果。

当我们把 Runnable接口 或 Callable 接口 的实现类提交给 ThreadPoolExecutor 或 ScheduledThreadPoolExecutor 执行。调用 submit() 方法时会返回一个 FutureTask 对象，可以从FutureTask 对象中获取任务返回的结果。

Executor执行过程

synchronized锁优化

为社么Java的任意对象都可以作为锁？

在Java对象头中，存在一个monitor对象，每个对象自创建之后在对象头中就含有monitor对象，monitor是线程私有的，不同的对象monitor自然也是不同的，因此对象作为锁的本质是对象头中的monitor对象作为了锁。这便是为什么Java的任意对象都可以作为锁的原因。

偏向锁

偏向锁：一个线程获得锁之后，再次执行同步代码时就不需要获取锁，直接执行

偏向锁针对的是锁不存在竞争，每次仅有一个线程来获取该锁，为了提高获取锁的效率，因此将该锁偏向该线程。提升性能。

偏向锁的获取：

1.首先检测是否为可偏向状态（锁标识是否设置成1，锁标志位是否为01）.
2.如果处于可偏向状态，测试Mark Word中的线程ID是否指向自己，如果是，不需要再次获取锁，直接执行同步代码。
3.如果线程Id，不是自己的线程Id，通过CAS获取锁，获取成功表明当前偏向锁不存在竞争，获取失败，则说明当前偏向锁存在锁竞争，偏向锁膨胀为轻量级锁。

偏向锁的撤销：

偏向锁只有当出现竞争时，才会出现锁撤销。

1。等待一个全局安全点，此时所有的线程都是暂停的，检查持有锁的线程状态，如果能找到说明当前线程还存活，说明还在执行同步块中的代码，首相将该线程阻塞，然后进行锁升级，升级到轻量级锁，唤醒该线程继续执行代同步码。
2.如果持有偏向锁的线程未存活，将对象头中的线程置null，然后直接锁升级。

轻量级锁

轻量级锁的获取：

1.在线程的栈帧中创建用于存储锁记录得空间
2.并将Mark Word复制到锁记录中，（这一步不论是否存在竞争都可以执行）。
3.尝试使用CAS将对象头中的Mark word字段变成指向锁记录得指针。
4 操作成功，不存在锁竞争，执行同步代码。
5操作失败，锁已经被其它线程抢占了，通过自旋获取锁，自旋一定次数还没有获取锁，这时轻量级锁膨胀为重量级锁。

轻量级锁得释放：

反替换，使用CAS将栈帧中得锁录空间替换到对象头，成功没有锁竞争，锁得以释放，失败说明存在竞争，那块指向锁记录得指针有别的线程在用，因此锁膨胀升级为重量级锁。

重量级锁

重量级锁描述同一时刻有多个线程竞争同一把锁。

当多个线程共同竞争同一把锁时，竞争失败得锁会被阻塞，等到持有锁的线程将锁释放后再次唤醒阻塞的线程，因为线程的唤醒和阻塞是一个很耗费CPU资源的操作，因此此处采取自适应自旋来获取重量级锁。

锁的升级

无锁 – > 偏向锁 -----> 轻量级锁 ---- > 重量级锁

其它优化

自旋锁：

线程未获得锁后，不是一昧的阻塞，而是让线程不断尝试获取锁。

缺点：若线程占用锁时间过长，导致CPU资源白白浪费。

解决方式：当尝试次数达到每个值得时候，线程挂起。

自适应自旋锁：

自旋得次数由上一次获取锁的自旋次数决定，次数稍微延长一点点。

锁消除

对于线程的私有变量，不存在并发问题，没有必要加锁，即使加锁编译后，也会去掉。

锁粗化

当一个循环中存在加锁操作时，可以将加锁操作提到循环外面执行，一次加锁代替多次加锁，提升性能。

线程池

线程池的参数

5个必须的参数

int corePoolSize：该线程池中核心线程数最大值

核心线程：线程池中有两类线程，核心线程和非核心线程。核心线程默认情况下会一直存在于线程池中，即使这个核心线程什么都不干（铁饭碗），而非核心线程如果长时间的闲置，就会被销毁（临时工）。
int maximumPoolSize：该线程池中线程总数最大值 。

该值等于核心线程数量 + 非核心线程数量。
long keepAliveTime：非核心线程闲置超时时长。

非核心线程如果处于闲置状态超过该值，就会被销毁。如果设置allowCoreThreadTimeOut(true)，则会也作用于核心线程。
TimeUnit unit：keepAliveTime的单位。

NANOSECONDS ： 1微毫秒 = 1微秒 / 1000 MICROSECONDS ： 1微秒 = 1毫秒 / 1000 MILLISECONDS ： 1毫秒 = 1秒 /1000 SECONDS ：秒 MINUTES ：分 HOURS ：小时 DAYS ：天
BlockingQueue workQueue：阻塞队列，维护着等待执行的Runnable任务对象。

常用的几个阻塞队列：
1. LinkedBlockingQueue
  
  链式阻塞队列，底层数据结构是链表，默认大小是Integer.MAX_VALUE，也可以指定大小。
2. ArrayBlockingQueue
  
  数组阻塞队列，底层数据结构是数组，需要指定队列的大小。
3. SynchronousQueue
  
  同步队列，内部容量为0，每个put操作必须等待一个take操作，反之亦然。
4. DelayQueue
  
  延迟队列，该队列中的元素只有当其指定的延迟时间到了，才能够从队列中获取到该元素。

两个非必须的参数：

ThreadFactory threadFactory

创建线程的工厂，用于批量创建线程，统一在创建线程时设置一些参数，如是否守护线程、线程的优先级等。如果不指定，会新建一个默认的线程工厂。
RejectedExecutionHandler handler

拒绝处理策略，线程数量大于最大线程数就会采用拒绝处理策略，四种拒绝处理的策略为：
1. ThreadPoolExecutor.AbortPolicy：默认拒绝处理策略，丢弃任务并抛出RejectedExecutionException异常。
2. ThreadPoolExecutor.DiscardPolicy：丢弃新来的任务，但是不抛出异常。
3. ThreadPoolExecutor.DiscardOldestPolicy：丢弃队列头部（最旧的）的任务，然后重新尝试执行程序（如果再次失败，重复此过程）。
4. ThreadPoolExecutor.CallerRunsPolicy：由调用线程处理该任务。

线程池的状态

线程池创建后处于RUNNING状态。
调用shutdown()方法后处于SHUTDOWN状态，线程池不能接受新的任务，清除一些空闲worker,会等待阻塞队列的任务完成。
调用shutdownNow()方法后处于STOP状态，线程池不能接受新的任务，中断所有线程，阻塞队列中没有被执行的任务全部丢弃。此时，poolsize=0,阻塞队列的size也为0。
当所有的任务已终止，ctl记录的”任务数量”为0，线程池会变为TIDYING状态。接着会执行terminated()函数。

ThreadPoolExecutor中有一个控制状态的属性叫ctl，它是一个AtomicInteger类型的变量。

线程池处在TIDYING状态时，执行完terminated()方法之后，就会由 TIDYING -> TERMINATED，线程池被设置为TERMINATED状态。

execute的执行流程

// JDK 1.8 
public void execute(Runnable command) {
    if (command == null)
        throw new NullPointerException();   
    int c = ctl.get();
    // 1.当前线程数小于corePoolSize,则调用addWorker创建核心线程执行任务
    if (workerCountOf(c) < corePoolSize) {
       if (addWorker(command, true))
           return;
       c = ctl.get();
    }
    // 2.如果不小于corePoolSize，则将任务添加到workQueue队列。
    if (isRunning(c) && workQueue.offer(command)) {
        int recheck = ctl.get();
        // 2.1 如果isRunning返回false(状态检查)，则remove这个任务，然后执行拒绝策略。
        if (! isRunning(recheck) && remove(command))
            reject(command);
            // 2.2 线程池处于running状态，但是没有线程，则创建线程
        else if (workerCountOf(recheck) == 0)
            addWorker(null, false);
    }
    // 3.如果放入workQueue失败，则创建非核心线程执行任务，
    // 如果这时创建非核心线程失败(当前线程总数不小于maximumPoolSize时)，就会执行拒绝策略。
    else if (!addWorker(command, false))
         reject(command);
}

ctl.get()是获取线程池状态，用int类型表示。第二步中，入队前进行了一次isRunning判断，入队之后，又进行了一次isRunning判断。

总结一下处理流程

线程总数量 < corePoolSize，调用一个核心线程执行任务（让核心线程数量快速达到corePoolSize，在核心线程数量 < corePoolSize时）。注意，这一步需要获得全局锁。
线程总数量 >= corePoolSize时，新来的线程任务会进入任务队列中等待，然后空闲的核心线程会依次去缓存队列中取任务来执行（体现了线程复用）。
当缓存队列满了，说明这个时候任务已经多到爆棚，需要一些“临时工”来执行这些任务了。于是会创建非核心线程去执行这个任务。注意，这一步需要获得全局锁。
缓存队列满了，且总线程数达到了maximumPoolSize，则会采取上面提到的拒绝策略进行处理。

线程复用

核心线程会从任务队列中不断获取任务并执行，当没有任务时就会被阻塞挂起，不会占用CPU的资源，从而达到复用线程的目的。

四种常用的线程池

newCachedThreadPool

corePoolSize为0的关系，不创建核心线程
线程池最大为Integer.MAX_VALUE
如果SynchronousQueue已有任务在等待，入列操作将会阻塞。
CachedThreadPool会在60s后收回。

newFixedThreadPool

corePoolSize == maximumPoolSize ，所以FixedThreadPool只会创建核心线程。
在 getTask() 方法，如果队列里没有任务可取，线程会一直阻塞在 LinkedBlockingQueue.take() ，线程不会被回收。
没有任务的情况下， FixedThreadPool占用资源更多。

newSingleThreadExecutor

仅有一个核心线程（ corePoolSize == maximumPoolSize=1），使用了LinkedBlockingQueue（容量很大）
不会创建非核心线程。所有任务按照先来先执行的顺序执行

newScheduledThreadPool

创建一个定长线程池，支持定时及周期性任务执行。

阻塞队列

BlockingQueue是Java util.concurrent包下重要的数据结构，区别于普通的队列，BlockingQueue提供了线程安全的队列访问方式，并发包下很多高级同步类的实现都是基于BlockingQueue实现的。

BlockingQueue一般用于生产者-消费者模式，生产者是往队列里添加元素的线程，消费者是从队列里拿元素的线程。BlockingQueue就是存放元素的容器。

阻塞队列的操作方法

阻塞队列提供了四组不同的方法用于插入、移除、检查元素：

方法\处理方式	抛出异常	返回特殊值	一直阻塞	超时退出
插入方法	add(e)	offer(e)	put(e)	offer(e,time,unit)
移除方法	remove()	poll()	take()	poll(time,unit)
检查方法	element()	peek()	-	-

BlockingQueue的实现类

1、ArrayBlockingQueue

由数组结构组成的有界阻塞队列。内部结构是数组，故具有数组的特性。
可以初始化队列大小，且一旦初始化不能改变。构造方法中的fair表示控制对象的内部锁是否采用公平锁，默认是非公平锁。

2、LinkedBlockingQueue

由链表结构组成的有界阻塞队列。内部结构是链表，具有链表的特性。默认队列的大小是Integer.MAX_VALUE，也可以指定大小。此队列按照先进先出的原则对元素进行排序。

3、DelayQueue

该队列中的元素只有当其指定的延迟时间到了，才能够从队列中获取到该元素。注入其中的元素必须实现 java.util.concurrent.Delayed 接口。
DelayQueue是一个没有大小限制的队列，因此往队列中插入数据的操作（生产者）永远不会被阻塞，而只有获取数据的操作（消费者）才会被阻塞。

4、PriorityBlockingQueue

基于优先级的无界阻塞队列（优先级的判断通过构造函数传入的Compator对象来决定），内部控制线程同步的锁采用的是公平锁。

5、SynchronousQueue

这个队列比较特殊，没有任何内部容量，甚至连一个队列的容量都没有。并且每个 put 必须等待一个 take，反之亦然。

注意

PriorityBlockingQueue不会阻塞数据生产者（因为队列是无界的），而只会在没有可消费的数据时，阻塞数据的消费者。因此使用的时候要特别注意，生产者生产数据的速度绝对不能快于消费者消费数据的速度，否则时间一长，会最终耗尽所有的可用堆内存空间。对于使用默认大小的LinkedBlockingQueue也是一样的

阻塞队列的原理

使用了Lock锁的多条件阻塞控制（Condition）
内部锁lock
锁的监视器notEmpty和notFull
当线程是put操作时，给他加上监视器notFull，标记这个线程是一个生产者
当线程是take操作时，给他加上监视器notEmpty，标记这个线程是消费者。

put操作

所有执行put操作的线程竞争lock锁，拿到了lock锁的线程进入下一步，没有拿到lock锁的线程自旋竞争锁。
判断阻塞队列是否满了，如果满了，则调用await方法阻塞这个线程，并标记为notFull（生产者）线程，同时释放lock锁，等待被消费者线程唤醒。
如果没有满，则调用enqueue方法将元素put进阻塞队列。注意这一步的线程还有一种情况是第二步中阻塞的线程被唤醒且又拿到了lock锁的线程。
唤醒一个标记为notEmpty（消费者）的线程。
释放锁。

take操作

所有执行take操作的线程竞争lock锁，拿到了lock锁的线程进入下一步，没有拿到lock锁的线程自旋竞争锁。
判断阻塞队列是否为空，如果是空，则调用await方法阻塞这个线程，并标记为notEmpty（消费者）线程，同时释放lock锁，等待被生产者线程唤醒。
如果没有空，则调用dequeue方法返回出队的元素。注意这一步的线程还有一种情况是第二步中阻塞的线程被唤醒且又拿到了lock锁的线程。
唤醒一个标记为notFull（生产者）的线程。
释放锁。

注意

put和tack操作都需要先获取锁，没有获取到锁的线程会被挡在第一道大门之外自旋拿锁，直到获取到锁。
就算拿到锁了之后，也不一定会顺利进行put/take操作，需要判断队列是否可用（是否满/空），如果不可用，则会被阻塞，并释放锁。
在第2点被阻塞的线程会被唤醒，但是在唤醒之后，依然需要拿到锁才能继续往下执行，否则，自旋拿锁，拿到锁了再while判断队列是否可用（这也是为什么不用if判断，而使用while判断的原因）。

锁接口和类

锁的分类

1、可重入锁和非可重入锁

支持重新进入的锁，也就是说这个锁支持一个线程对资源重复加锁。
synchronized和ReentrantLock就是使用的可重入锁。

2、公平锁和非公平锁

如果对一个锁来说，先对锁获取请求的线程一定会先被满足，后对锁获取请求的线程后被满足，那这个锁就是公平的。反之，那就是不公平的。
非公平锁能提升一定的效率。但是非公平锁可能会发生线程饥饿（有一些线程长时间得不到锁）的情况。

3、读写锁和排他锁

synchronized和ReentrantLock，其实都是“排它锁”。也就是说，这些锁在同一时刻只允许一个线程进行访问。
Java提供了ReentrantReadWriteLock类作为读写锁的默认实现，内部维护了两个锁：一个读锁，一个写锁。通过分离读锁和写锁，使得在“读多写少”的环境下，大大地提高了性能。

HashCode和Equals

作用

重写hashCode()是为了对同一个key，能得到相同的HashCode，这样HashMap就可以定位到我们指定的key上。
重写equals()是为了向HashMap表明当前对象和key上所保存的对象是相等的，这样我们才真正地获得了这个key所对应的这个键值对。

为什么重写equals方法，还必须要重写hashcode方法

是为了提高效率，采取重写hashcode方法，先进行hashcode比较，如果不同，那么就没必要在进行equals的比较了，这样就大大减少了equals比较的次数，这对比需要比较的数量很大的效率提高是很明显的，一个很好的例子就是在集合中的使用；

总结

hashCode主要用于提升查询效率，来确定在散列结构中对象的存储地址；
重写equals()必须重写hashCode()，二者参与计算的自身属性字段应该相同；
hash类型的存储结构，添加元素重复性校验的标准就是先取hashCode值，后判断equals()；
equals()相等的两个对象，hashcode()一定相等；
反过来：hashcode()不等，一定能推出equals()也不等；
hashcode()相等，equals()可能相等，也可能不等。

JVM

运行时内存区域

简介

堆——堆是所有线程共享的，主要用来存储对象。其中，堆可分为：年轻代和老年代两块区域。使用NewRatio参数来设定比例。对于年轻代，一个Eden区和两个Suvivor区，使用参数SuvivorRatio来设定大小；
Java虚拟机栈/本地方法栈——线程私有的，主要存放局部变量表，操作数栈，动态链接和方法出口等；
程序计数器——同样是线程私有的，记录当前线程的行号指示器，为线程的切换提供保障；
方法区——线程共享的，主要存储类信息、常量池、静态变量、JIT编译后的代码等数据。方法区理论上来说是堆的逻辑组成部分；
运行时常量池——是方法区的一部分，用于存放编译期生成的各种字面量和符号引用；

程序计数器

线程独有
字节码解释器通过改变程序计数器来依次读取指令
程序计数器用于记录当前线程执行的位置

虚拟机栈/本地方法栈

在进行方法调用时，会创建一个栈帧，栈帧中都含有：局部变量表、操作数、动态链接、方法出口信息，每个栈帧会被push到虚拟机栈中。

堆内存

新生代

生命周期比较短的对象，会频繁的进行GC
采用复制法进行GC
分为Eden区和2个Survival区
每次使用Eden和其中一块survior，当回收时，将Eden和survior中还存活着的对象一次性地复制到另外一块survior空间上，最后清理掉Eden和刚才用过的survior空间。当Eden空间

老年代

年老代里存放的都是存活时间较久的，大小较大的对象，因此年老代使用标记整理算法。
当年老代容量满的时候，会触发一次Major GC（full GC）

方法区

方法区与 Java 堆一样，是各个线程共享的内存区域，它用于存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。虽然 Java 虚拟机规范把方法区描述为堆的一个逻辑部分

元空间

使用本地内存
存放类的元数据信息

方法区和元空间的区别

在Java8中取消了永久代，使用元空间。
方法区是一个规范，规范没变，它就一直在。那么取代永久代的就是元空间
存储位置不同，永久代物理是是堆的一部分，和新生代，老年代地址是连续的，而元空间属于本地内存；
存储内容不同，元空间存储类的元数据信息，静态变量和常量池等并入堆中。相当于永久代的数据被分到了堆和元空间中。

运行时常量池

存放字面量和引用，用来索引和查找字段和方法名称和描述符的。

直接内存

本机直接内存的分配不会受到Java堆大小的限制，但是，既然是内存，则肯定还是会受到本机总内存

OutOfMemoryError异常

Java堆溢出

场景

设置的jvm内存太小，对象所需内存太大，创建对象时分配空间，就会抛出这个异常。
通过不断地创建对象, 并将对象保存在 list 中防止其被垃圾回收, 因此当对象过多时, 就会使堆内存溢出。

堆相关参数

堆的最小值-Xms
堆的最大值-Xmx
-XX：+HeapDumpOnOutOf-MemoryError可以让虚拟机在出现内存溢出异常的时候Dump出当前的内存堆转储快照以便进行事后分析

分析方法

常规的处理方法是首先通过内存映像分析工具（如Eclipse Memory Analyzer）对Dump出来的堆转储快照进行分析。

第一步首先应确认内存中导致OOM的对象是否是必要的，也就是要先分清楚到底是出现了内存泄漏（Memory Leak）还是内存溢出（Memory Overflow）
如果是内存泄漏，可进一步通过工具查看泄漏对象到GC Roots的引用链，找到泄漏对象是通过怎样的引用路径、与哪些GC Roots相关联，才导致垃圾收集器无法回收它们，进而找出产生内存泄漏的代码的具***置。
如果不是内存泄漏，换句话说就是内存中的对象确实都是必须存活的，那就应当检查Java虚拟机的堆参数（-Xmx与-Xms）设置，与机器的内存对比，看看是否还有向上调整的空间。再从代码上检查是否存在某些对象生命周期过长、持有状态时间过长、存储结构设计不合理等情况，尽量减少程序运行期的内存消耗。

Java堆内存泄漏

Java中的内存泄漏是一些对象不再被应用程序使用但垃圾收集无法识别的情况。因此，这些未使用的对象仍然在Java堆空间中无限期地存在。不停的堆积最终会触发java . lang.OutOfMemoryError。
在使用HashMap时，key类并没有重写它的equals()方法，如果2个key的hashCode不一样，但euqals相同，则会导致写入重复的key和value，造成内存泄漏。

虚拟机栈和本地方法栈溢出

栈参数

栈容量只能由-Xss参数来设定。

场景

方法递归调用太深、递归调用没有终止条件，进入死循环，产生的栈帧太多，导致栈溢出。

分析方法

如果线程请求的栈深度大于虚拟机所允许的最大深度，将抛出StackOverflowError异常。
如果虚拟机的栈内存允许动态扩展，当扩展栈容量无法申请到足够的内存时，将抛出OutOfMemoryError异常。

操作系统分配给每个进程的内存是有限制的，因此为每个线程分配到的栈内存越大，可以建立的线程数量自然就越少，建立线程时就越容易把剩下的内存耗尽。

解决

栈深度在大多数情况下（因为每个方法压入栈的帧大小并不是一样的，所以只能说大多数情况下）到达1000~2000是完全没有问题，对于正常的方法调用（包括不能做尾递归优化的递归调用），这个深度应该完全够用了。但是，如果是建立过多线程导致的内存溢出，在不能减少线程数量或者更换64位虚拟机的情况下，就只能通过减少最大堆和减少栈容量来换取更多的线程。

方法区和运行时常量池溢出

自JDK 7起，原本存放在永久代的字符串常量池被移至Java堆之中，所以在JDK 7及以上版本，限制方法区的容量对该测试用例来说是毫无意义的。

JDK 7（以及部分其他虚拟机，例如JRockit）的intern()方法实现就不需要再拷贝字符串的实例到永久代了，既然字符串常量池已经移到Java堆中，那只需要在常量池里记录一下首次出现的实例引用即可。

方法区的主要职责是用于存放类型的相关信息，如类名、访问修饰符、常量池、字段描述、方法描述等。对于这部分区域的测试，基本的思路是运行时产生大量的类去填满方法区。

方法区溢出也是一种常见的内存溢出异常，这类场景除了之前提到的程序使用了CGLib字节码增强和动态语言外，常见的还有：大量JSP或动态产生JSP文件的应用（JSP第一次运行时需要编译为Java类）、基于OSGi的应用。

参数

-XX：MaxMetaspaceSize：设置元空间最大值，默认是-1，即不限制，或者说只受限于本地内存大小。
-XX：MetaspaceSize：指定元空间的初始空间大小，以字节为单位，达到该值就会触发垃圾收集进行类型卸载，同时收集器会对该值进行调整：如果释放了大量的空间，就适当降低该值；如果释放了很少的空间，那么在不超过-XX：MaxMetaspaceSize（如果设置了的话）的情况下，适当提高该值。
-XX：MinMetaspaceFreeRatio：作用是在垃圾收集之后控制最小的元空间剩余容量的百分比，可减少因为元空间不足导致的垃圾收集的频率。类似的还有-XX：Max-MetaspaceFreeRatio，用于控制最大的元空间剩余容量的百分比。

本机直接内存溢出

参数

-XX：MaxDirectMemorySize参数来指定，如果不去指定，则默认与Java堆最大值（由-Xmx指定）一致

原因

由直接内存导致的内存溢出，一个明显的特征是在Heap Dump文件中不会看见有什么明显的异常情况，如果读者发现内存溢出之后产生的Dump文件很小，而程序中又直接或间接使用了DirectMemory（典型的间接使用就是NIO），那就可以考虑重点检查一下直接内存方面的原因了。

垃圾收集

判断对象是否存活

1. 引用计数法

原理：在对象中添加一个引用计数器，每当有一个地方引用它时，计数器值就加一；当引用失效时，计数器值就减一；任何时刻计数器为零的对象就是不可能再被使用的。

缺陷：很难解决循环引用的问题，大部分主流虚拟机不采用。

2. 可达性分析算法

原理：通过一系列称为“GCRoots”的根对象作为起始节点集，从这些节点开始，根据引用关系向下搜索，搜索过程所走过的路径称为“引用链”（Reference Chain），如果某个对象到GC Roots间没有任何引用链相连，或者用图论的话来说就是从GC Roots到这个对象不可达时，则证明此对象是不可能再被使用的。

可作为GC Roots的对象

在虚拟机栈（栈帧中的本地变量表）中引用的对象，譬如各个线程被调用的方法堆栈中使用到的参数、局部变量、临时变量等。
在方法区中类静态属性引用的对象，譬如Java类的引用类型静态变量。
在方法区中常量引用的对象，譬如字符串常量池（String Table）里的引用。
在本地方法栈中JNI（即通常所说的Native方法）引用的对象。
Java虚拟机内部的引用，如基本数据类型对应的Class对象，一些常驻的异常对象（比如NullPointExcepiton、OutOfMemoryError）等，还有系统类加载器。
所有被同步锁（synchronized关键字）持有的对象。

引用

1. 强引用

无论任何情况下，只要强引用关系还存在，垃圾收集器就永远不会回收掉被引用的对象。

2. 软引用

如果内存空间足够，垃圾回收器就不会回收它，如果内存空间不足了，就会回收这些对象的内存。

3. 弱引用

一旦发现了只具有弱引用的对象，不管当前内存空间足够与否，都会回收它的内存。

4. 虚引用

引用并不会决定对象的生命周期。如果一个对象仅持有虚引用，那么它就和没有任何引用一样，在任何时候都可能被垃圾回收。

虚引用主要用来跟踪对象被垃圾回收的活动。

回收方法区

方法区的垃圾收集主要回收两部分内容：废弃的常量和不再使用的类型。

分代收集

部分收集：对Java堆中的部分进行收集

新生代收集：只是新生代的垃圾收集。
老年代收集：只是老年代的垃圾收集。目前只有CMS收集器会有单独收集老年代的行为。
混合收集：收集整个新生代以及部分老年代的垃圾收集。目前只有G1收集器会有这种行为。

整堆收集：收集整个Java堆和方法区的垃圾收集。

垃圾收集算法

1. 标记-清除法

原理：算法分为“标记”和“清除”两个阶段：首先标记出所有需要回收的对象，在标记完成后，统一回收掉所有被标记的对象

缺陷：

第一个是执行效率不稳定，如果Java堆中包含大量对象，这时必须进行大量标记和清除的动作，导致执行效率都随对象数量增长而降低。
第二个是内存空间的碎片化问题，标记、清除之后会产生大量不连续的内存碎片，空间碎片太多可能会导致当以后在程序运行过程中需要分配较大对象时无法找到足够的连续内存，进而提前触发另一次垃圾收集动作。

2. 标记-复制法（复制法）

原理：它将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再把已使用过的内存空间一次清理掉。适用于频繁进行垃圾收集的新生代。

缺陷：

如果内存中多数对象都是存活的，将会产生大量的内存间复制的开销。
将可用内存缩小为了原来的一半，造成空间浪费。

3. 标记-整理法

原理：其中的标记过程仍然与“标记-清除”算法一样，但后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向内存空间一端移动，然后直接清理掉边界以外的内存。适用于老年代。

缺陷：

移动存活对象会存在较大开销

垃圾收集器

Serial收集器：单线程工作
ParNew收集器：多线程工作，并行收集
Parallel Scavenge收集器
Serial Old收集器

CMS收集器

基于标记－清除法实现。运行过程包括：

初始标记：标记GC Roots能直接关联到的对象，速度很快。
并发标记：从GC Roots的直接关联对象开始遍历整个对象图的过程，这个过程耗时较长但是不需要停顿用户线程，可以与垃圾收集线程一起并发运行。
重新标记：为了修正并发标记期间，因用户程序继续运作而导致标记产生变动的那一部分对象的标记记录。
并发清除：并发清理删除掉标记阶段判断的已经死亡的对象。

优点：并发收集、低停顿

缺点：

占用了一部分线程而导致应用程序变慢，降低总吞吐量。
存在空间碎片。

G1收集器

原理：将Region作为单次回收的最小单元，维护一个优先级列表，优先处理回收价值收益最大的那些Region

运行过程：

初始标记：标记一下GC Roots能直接关联到的对象。
并发标记：从GC Root开始对堆中对象进行可达性分析，递归扫描整个堆里的对象图，找出要回收的对象
最终标记：处理并发阶段结束后仍遗留下来的最后那少量的SATB记录
筛选回收：对各个Region的回收价值和成本进行排序，把决定回收的那一部分Region的存活对象复制到空的Region中，再清理掉整个旧Region的全部空间

Class类文件结构

任何一个Class文件都对应着唯一的一个类或接口的定义信息[插图]，但是反过来说，类或接口并不一定都得定义在文件里（譬如类或接口也可以动态生成，直接送入类加载器中）。

虚拟机加载Class文件的时候进行动态连接。也就是说，在Class文件中不会保存各个方法、字段最终在内存中的布局信息，这些字段、方法的符号引用不经过虚拟机在运行期转换的话是无法得到真正的内存入口地址，也就无法直接被虚拟机使用的。当虚拟机做类加载时，将会从常量池获得对应的符号引用，再在类创建时或运行时解析、翻译到具体的内存地址之中。

总结

Class文件的头4个字节被称为魔数
第5和第6个字节是次版本号，第7和第8个字节是主版本号
常量池入口
在常量池结束之后，紧接着的2个字节代表访问标志
类索引、父类索引与接口索引集合
字段表集合
方法表集合
属性表集合

字节码

组成

操作数
操作码

Java虚拟机采用面向操作数栈而不是面向寄存器的架构，所以大多数指令都不包含操作数，只有一个操作码，指令参数都存放在操作数栈中。

Java虚拟机操作码的长度为一个字节

类加载机制

Java语言里面，类型的加载、连接和初始化过程都是在程序运行期间完成的
Java应用提供了极高的扩展性和灵活性，Java天生可以动态扩展的语言特性就是依赖运行期动态加载和动态连接这个特点实现的。
编写一个面向接口的应用程序，可以等到运行时再指定其实际的实现类

加载过程

加载
验证
准备
解析（某些情况下可以在初始化之后）
初始化
卸载

1. 加载

通过一个类的全限定名来获取定义此类的二进制字节流。
将这个字节流所代表的静态存储结构转化为方法区的运行时数据结构。
在内存中生成一个代表这个类的java.lang.Class对象，作为方法区这个类的各种数据的访问入口。

2. 验证

文件格式验证
元数据验证
字节码验证
符号引用验证

3. 准备

为类变量分配内存并设置变量初始值（零值）

4. 解析

解析阶段是Java虚拟机将常量池内的符号引用替换为直接引用的过程
符号引用：符号引用以一组符号来描述所引用的目标，符号可以是任何形式的字面量，只要使用时能无歧义地定位到目标即可。
直接引用：直接引用是可以直接指向目标的指针、相对偏移量或者是一个能间接定位到目标的句柄。
解析动作主要针对类或接口、字段、类方法、接口方法、方法类型、方法句柄和调用点限定符这7类符号引用进行

5. 初始化

始化阶段就是执行类构造器<clinit>()方法的过程。</clinit>
类变量赋值，执行静态语句块
Java虚拟机会保证在子类的<clinit>()方法执行前，父类的<clinit>()方法已经执行完毕。</clinit></clinit>
Java虚拟机必须保证一个类的<clinit>()方法在多线程环境中被正确地加锁同步</clinit>

类加载器

启动类加载器

扩展类加载器

应用类加载器

双亲委派模型

双亲委派模型要求除了顶层的启动类加载器外，其余的类加载器都应有自己的父类加载器。不过这里类加载器之间的父子关系一般不是以继承（Inheritance）的关系来实现的，而是通常使用组合（Composition）关系来复用父加载器的代码。

双亲委派模型的工作过程是：如果一个类加载器收到了类加载的请求，它首先不会自己去尝试加载这个类，而是把这个请求委派给父类加载器去完成，每一个层次的类加载器都是如此，因此所有的加载请求最终都应该传送到最顶层的启动类加载器中，只有当父加载器反馈自己无法完成这个加载请求（它的搜索范围中没有找到所需的类）时，子加载器才会尝试自己去完成加载。

`JavaWeb`

Servlet

在Java Web程序中，Servlet主要负责接收用户请求 HttpServletRequest,在doGet(),doPost()中做相应的处理，并将回应HttpServletResponse反馈给用户。Servlet 可以设置初始化参数，供Servlet内部使用。一个Servlet类只会有一个实例，在它初始化时调用init()方法，销毁时调用destroy()方法。Servlet需要在web.xml中配置（MyEclipse中创建Servlet会自动配置），一个Servlet可以设置多个URL访问。Servlet不是线程安全，因此要谨慎使用类变量。

Servlet不能够自行创建并执行，它是在Servlet容器中运行的，容器将用户的请求传递给Servlet程序，并将Servlet的响应回传给用户。

Servlet生命周期

生命周期： Web容器加载Servlet并将其实例化后，Servlet生命周期开始，容器运行其init()方法进行Servlet的初始化；请求到达时调用Servlet的service()方法，service()方***根据需要调用与请求对应的doGet或doPost等方法；当服务器关闭或项目被卸载时服务器会将Servlet实例销毁，此时会调用Servlet的destroy()方法

自动刷新

自动刷新不仅可以实现一段时间之后自动跳转到另一个页面，还可以实现一段时间之后自动刷新本页面。Servlet中通过HttpServletResponse对象设置Header属性实现自动刷新

Servlet不是线程安全的

Servlet不是线程安全的，多线程并发的读写会导致数据不同步的问题。 解决的办法是尽量不要定义name属性，而是要把name变量分别定义在doGet()和doPost()方法内。虽然使用synchronized(name){}语句块可以解决问题，但是会造成线程的等待，不是很科学的办法。注意：多线程的并发的读写Servlet类属性会导致数据不同步。但是如果只是并发地读取属性而不写入，则不存在数据不同步的问题。因此Servlet里的只读属性最好定义为final类型的。

框架

RPC框架：远程过程调用

实现原理

Call ID映射：函数名和Call ID对应
序列化和反序列化：参数序列化为字节流参数
网络传输：传输数据包（TCP，UDP）

简单模型

// Client端 
//    int l_times_r = Call(ServerAddr, Multiply, lvalue, rvalue)
1. 将这个调用映射为Call ID。这里假设用最简单的字符串当Call ID的方法
2. 将Call ID，lvalue和rvalue序列化。可以直接将它们的值以二进制形式打包
3. 把2中得到的数据包发送给ServerAddr，这需要使用网络传输层
4. 等待服务器返回结果
5. 如果服务器调用成功，那么就将结果反序列化，并赋给l_times_r

// Server端
1. 在本地维护一个Call ID到函数指针的映射call_id_map，可以用std::map<std::string, std::function<>>
2. 等待请求
3. 得到一个请求后，将其数据包反序列化，得到Call ID
4. 通过在call_id_map中查找，得到相应的函数指针
5. 将lvalue和rvalue反序列化后，在本地调用Multiply函数，得到结果
6. 将结果序列化后通过网络返回给Client

ArrayList源码解读

ArraysList属性

private static final int DEFAULT_CAPACITY = 10;

private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient Object[] elementData; // non-private to simplify nested class access

private int size;

默认容量DEFAULT_CAPACITY 10；
一个空数组EMPTY_ELEMENTDATA；
一个默认空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA；
一个未初始化的数组elementData；
容量size；
modCount：记录List修改的次数

ArrayList构造方法

    /**
     *默认构造函数，使用初始容量10构造一个空列表(无参数构造)
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 带初始容量参数的构造函数。（用户自己指定容量）
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {//初始容量大于0
            //创建initialCapacity大小的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {//初始容量等于0
            //创建空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {//初始容量小于0，抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }


   /**
    *构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回
    *如果指定的集合为null，throws NullPointerException。 
    */
     public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

ArrayList指定长度构造方法，当指定长度大于0时，新建一个Object空数组，长度为指定长度，赋值给elementData；为0时将EMPTY_ELEMENTDATA赋值给elementData；小于0则报错；
无参构造方法：将空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值给elementData。注意：无参构造上的注释说，构造了一个容量为10的空数组，其实并没有！
传入一个Collection对象初始化：将Collection对象转换为数组并赋值给elementData，将Collection长度赋值给size，判断c.toArray()是否为Object数组，不是则要转换为Object数组。为了集合能存储不能数据类型数据；

ArrayList常用方法

1. add(E e)方法

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

判断是否需要扩容：
- 如果是空数组，第一次添加元素时扩容到初始容量10
- 如果当前最小容量(size + 1)大于数组长度，则进行扩容，否则不扩容
- 扩容：
  - 新容量为原容量的1.5倍
  - 如果新容量还小于最小容量，那么就把最小需要容量当作数组的新容量
  - 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，
  - 如果minCapacity大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。
  - 调用Arrays.copyOf复制一个新的容量的数组

2. add(int index, E element)

    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //arraycopy()方法实现数组自己复制自己
        //elementData:源数组;index:源数组中的起始位置;elementData：目标数组；index + 1：目标数组中          的起始位置； size - index：要复制的数组元素的数量；
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }

在列表中的指定位置插入指定的元素。
先调用 rangeCheckForAdd 对index进行界限检查；
然后调用 ensureCapacityInternal 方法保证capacity足够大；
再将从index开始之后的所有成员后移一个位置；
将element插入index位置；最后size加1；

3. remove(int index)

    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

检查边界
将index后元素前移，再将最后一个有值元素置null
size减一
返回删除的元素

4. remove(Object o)

    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

通过循环找元素的下标，然后remove
元素为空时直接判断，否则调用equals方法判断

5. clear()方法

    public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

将elementData所有元素置null
将size置为0

LinkedList源码解读

简要介绍

LinkedList底层采用的双向链表结构。LinkedList 也支持空值和重复值。由于 LinkedList 基于链表实现，存储元素过程中，无需像 ArrayList 那样进行扩容。LinkedList 存储元素的节点需要额外的空间存储前驱和后继的引用。LinkedList 在链表头部和尾部插入效率比较高，但在指定位置进行插入时，效率一般。原因是，在指定位置插入需要定位到该位置处的节点，此操作的时间复杂度为O(N)。最后，LinkedList 是非线程安全的集合类，并发环境下，多个线程同时操作 LinkedList，会引发不可预知的错误。

继承

实现了List和Deque接口

源码分析

1. 查找

从链表头结点（或尾节点）向后查找，时间复杂度为 O(N)

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    /*
     * 则从头节点开始查找，否则从尾节点查找
     * 查找位置 index 如果小于节点数量的一半，
     */    
    if (index < (size >> 1)) {
        Node<E> x = first;
        // 循环向后查找，直至 i == index
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

主要是通过遍历的方式定位目标位置的节点。获取到节点后，取出节点存储的值返回即可。这里面有个小优化，即通过比较 index 与节点数量 size/2 的大小，决定从头结点还是尾节点进行查找。

2. 迭代器遍历

通常情况下，我们会使用 foreach 遍历 LinkedList，而 foreach 最终转换成迭代器形式。所以分析 LinkedList 的遍历的核心就是它的迭代器实现。

public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;

    /** 构造方法将 next 引用指向指定位置的节点 */
    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public boolean hasNext() {
        return nextIndex < size;
    }

    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();

        lastReturned = next;
        next = next.next;    // 调用 next 方法后，next 引用都会指向他的后继节点
        nextIndex++;
        return lastReturned.item;
    }

    // 省略部分方法
}

3. 插入

/** 在链表尾部插入元素 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

/** 在链表指定位置插入元素 */
public void add(int index, E element) {
    checkPositionIndex(index);

    // 判断 index 是不是链表尾部位置，如果是，直接将元素节点插入链表尾部即可
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

/** 将元素节点插入到链表尾部 */
void linkLast(E e) {
    final Node<E> l = last;
    // 创建节点，并指定节点前驱为链表尾节点 last，后继引用为空
    final Node<E> newNode = new Node<>(l, e, null);
    // 将 last 引用指向新节点
    last = newNode;
    // 判断尾节点是否为空，为空表示当前链表还没有节点
    if (l == null)
        first = newNode;
    else
        l.next = newNode;    // 让原尾节点后继引用 next 指向新的尾节点
    size++;
    modCount++;
}

/** 将元素节点插入到 succ 之前的位置 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    // 1. 初始化节点，并指明前驱和后继节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 2. 将 succ 节点前驱引用 prev 指向新节点
    succ.prev = newNode;
    // 判断尾节点是否为空，为空表示当前链表还没有节点    
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;   // 3. succ 节点前驱的后继引用指向新节点
    size++;
    modCount++;
}

以 linkBefore 为例，它的逻辑流程如下：

创建新节点，并指明新节点的前驱和后继
将 succ 的前驱引用指向新节点
如果 succ 的前驱不为空，则将 succ 前驱的后继引用指向新节点

4. 删除

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        // 遍历链表，找到要删除的节点
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);    // 将节点从链表中移除
                return true;
            }
        }
    }
    return false;
}

public E remove(int index) {
    checkElementIndex(index);
    // 通过 node 方法定位节点，并调用 unlink 将节点从链表中移除
    return unlink(node(index));
}

/** 将某个节点从链表中移除 */
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    // prev 为空，表明删除的是头节点
    if (prev == null) {
        first = next;
    } else {
        // 将 x 的前驱的后继指向 x 的后继
        prev.next = next;
        // 将 x 的前驱引用置空，断开与前驱的链接
        x.prev = null;
    }

    // next 为空，表明删除的是尾节点
    if (next == null) {
        last = prev;
    } else {
        // 将 x 的后继的前驱指向 x 的前驱
        next.prev = prev;
        // 将 x 的后继引用置空，断开与后继的链接
        x.next = null;
    }

    // 将 item 置空，方便 GC 回收
    x.item = null;
    size--;
    modCount++;
    return element;
}

unlink 方法的逻辑如下（假设删除的节点既不是头节点，也不是尾节点）：

将待删除节点 x 的前驱的后继指向 x 的后继
将待删除节点 x 的前驱引用置空，断开与前驱的链接
将待删除节点 x 的后继的前驱指向 x 的前驱
将待删除节点 x 的后继引用置空，断开与后继的链接

HashMap源码解读

介绍

HashMap 允许 null 键和 null 值，在计算哈键的哈希值时，null 键哈希值为 0。HashMap 并不保证键值对的顺序，这意味着在进行某些操作后，键值对的顺序可能会发生变化。另外，需要注意的是，HashMap 是非线程安全类，在多线程环境下可能会存在问题。

原理

源码分析

1. 构造方法

第一个构造方法很简单，仅将 loadFactor 变量设为默认值。构造方法2调用了构造方法3，而构造方法3仍然只是设置了一些变量。构造方法4则是将另一个 Map 中的映射拷贝一份到自己的存储结构中来，这个方法不是很常用。

/** 构造方法 1 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

/** 构造方法 2 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/** 构造方法 3 */
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

/** 构造方法 4 */
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

2. 初始容量、负载因子、阈值

在 HashMap 构造方法中，可供我们调整的参数有两个，一个是初始容量 initialCapacity，另一个负载因子 loadFactor。通过这两个设定这两个参数，可以进一步影响阈值大小。但初始阈值 threshold 仅由 initialCapacity 经过移位操作计算得出。

HashMap 初始容量是16，负载因子为 0.75。这里并没有默认阈值，原因是阈值可由容量乘上负载因子计算而来

找到大于或等于 cap 的最小2的幂

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

对于 HashMap 来说，负载因子是一个很重要的参数，该参数反应了 HashMap 桶数组的使用情况（假设键值对节点均匀分布在桶数组中）。通过调节负载因子，可使 HashMap 时间和空间复杂度上有不同的表现。

当我们调低负载因子时，HashMap 所能容纳的键值对数量变少。扩容时，重新将键值对存储新的桶数组里，键的键之间产生的碰撞会下降，链表长度变短。此时，HashMap 的增删改查等操作的效率将会变高，这里是典型的拿空间换时间。

如果增加负载因子（负载因子可以大于1），HashMap 所能容纳的键值对数量变多，空间利用率高，但碰撞率也高。这意味着链表长度变长，效率也随之降低，这种情况是拿时间换空间。至于负载因子怎么调节，这个看使用场景了。一般情况下，我们用默认值就可以了。

3. 查找

HashMap 的查找操作比较简单，查找步骤与原理篇介绍一致，即先定位键值对所在的桶的位置，然后再对链表或红黑树进行查找。

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 1. 定位键值对所在桶的位置
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // 2. 如果 first 是 TreeNode 类型，则调用黑红树查找方法
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);

            // 2. 对链表进行查找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

通过(n - 1)& hash即可算出桶的在桶数组中的位置，HashMap 中桶数组的大小 length 总是2的幂，此时，(n - 1) & hash 等价于对 length 取余。但取余的计算效率没有位运算高，所以(n - 1) & hash也是一个小的优化。

计算Hash值

/**
 * 计算键的 hash 值
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

计算余数时，由于 n 比较小，hash 只有低16位参与了计算，高位的计算可以认为是无效的。这样导致了计算结果只与低位信息有关，高位数据没发挥作用。为了处理这个缺陷，我们可以将 hash 高16位数据与低16位数据进行异或运算，即 hash ^ (hash >>> 16)。通过这种方式，让高位数据与低位数据进行异或，以此加大低位信息的随机性，变相的让高位数据参与到计算中。

重新计算 hash 的另一个好处是可以增加 hash 的复杂度。当我们覆写 hashCode 方法时，可能会写出分布性不佳的 hashCode 方法，进而导致 hash 的冲突率比较高。通过移位和异或运算，可以让 hash 变得更复杂，进而影响 hash 的分布性。

4. 遍历

遍历所有的键时，首先要获取键集合KeySet对象，然后再通过 KeySet 的迭代器KeyIterator进行遍历。KeyIterator 类继承自HashIterator类，核心逻辑也封装在 HashIterator 类中。HashIterator 的逻辑并不复杂，在初始化时，HashIterator 先从桶数组中找到包含链表节点引用的桶。然后对这个桶指向的链表进行遍历。遍历完成后，再继续寻找下一个包含链表节点引用的桶，找到继续遍历。找不到，则结束遍历。

public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}

/**
 * 键集合
 */
final class KeySet extends AbstractSet<K> {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator<K> iterator()     { return new KeyIterator(); }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
    // 省略部分代码
}

/**
 * 键迭代器
 */
final class KeyIterator extends HashIterator 
    implements Iterator<K> {
    public final K next() { return nextNode().key; }
}

abstract class HashIterator {
    Node<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot

    HashIterator() {
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // advance to first entry 
            // 寻找第一个包含链表节点引用的桶
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        if ((next = (current = e).next) == null && (t = table) != null) {
            // 寻找下一个包含链表节点引用的桶
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }
    //省略部分代码
}

5. 插入

插入操作的入口方法是 put(K,V)，但核心逻辑在V putVal(int, K, V, boolean, boolean) 方法中。putVal 方法主要做了这么几件事情：

当桶数组 table 为空时，通过扩容的方式初始化 table
查找要插入的键值对是否已经存在，存在的话根据条件判断是否用新值替换旧值
如果不存在，则将键值对链入链表中，并根据链表长度决定是否将链表转为红黑树
判断键值对数量是否大于阈值，大于的话则进行扩容操作

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 初始化桶数组 table，table 被延迟到插入新数据时再进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果桶中不包含键值对节点引用，则将新键值对节点的引用存入桶中即可
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 如果键的值以及节点 hash 等于链表中的第一个键值对节点时，则将 e 指向该键值对
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;

        // 如果桶中的引用类型为 TreeNode，则调用红黑树的插入方法
        else if (p instanceof TreeNode)  
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 对链表进行遍历，并统计链表长度
            for (int binCount = 0; ; ++binCount) {
                // 链表中不包含要插入的键值对节点时，则将该节点接在链表的最后
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果链表长度大于或等于树化阈值，则进行树化操作
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }

                // 条件为 true，表示当前链表包含要插入的键值对，终止遍历
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }

        // 判断要插入的键值对是否存在 HashMap 中
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 键值对数量超过阈值时，则进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

6. 扩容机制

在 HashMap 中，桶数组的长度均是2的幂，阈值大小为桶数组长度与负载因子的乘积。当 HashMap 中的键值对数量超过阈值时，进行扩容。

HashMap 的扩容机制与其他变长集合的套路不太一样，HashMap 按当前桶数组长度的2倍进行扩容，阈值也变为原来的2倍（如果计算过程中，阈值溢出归零，则按阈值公式重新计算）。扩容之后，要重新计算键值对的位置，并把它们移动到合适的位置上去。

下面的源码总共做了3件事，分别是：

计算新桶数组的容量 newCap 和新阈值 newThr
根据计算出的 newCap 创建新的桶数组，桶数组 table 也是在这里进行初始化的
将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组。

在 JDK 1.8 中，重新映射节点需要考虑节点类型。对于树形节点，需先拆分红黑树再映射。对于链表类型节点，则需先对链表进行分组，然后再映射。需要的注意的是，分组后，组内节点相对位置保持不变。

7. 链表树化、红黑树链化与拆分

树化

在扩容过程中，树化要满足两个条件：

链表长度大于等于 TREEIFY_THRESHOLD（默认8）
桶数组容量大于等于 MIN_TREEIFY_CAPACITY（默认64）

当桶数组容量比较小时，键值对节点 hash 的碰撞率可能会比较高，进而导致链表长度较长。这个时候应该优先扩容，而不是立马树化。

红黑树拆分

扩容后，普通节点需要重新映射，红黑树节点也不例外。在将普通链表转成红黑树时，HashMap 通过两个额外的引用 next 和 prev 保留了原链表的节点顺序。这样再对红黑树进行重新映射时，完全可以按照映射链表的方式进行。这样就避免了将红黑树转成链表后再进行映射，无形中提高了效率。

红黑树链化

红黑树中仍然保留了原链表节点顺序。有了这个前提，再将红黑树转成链表就简单多了，仅需将 TreeNode 链表转成 Node 类型的链表即可。

8. 删除

HashMap 的删除操作并不复杂，仅需三个步骤即可完成。

第一步是定位桶位置
第二步遍历链表并找到键值相等的节点
第三步删除节点。

9. 其他细节

被 transient 所修饰 table 变量

桶数组 table 被申明为 transient。transient 表示易变的意思，在 Java 中，被该关键字修饰的变量不会被默认的序列化机制序列化。

HashMap 并没有使用默认的序列化机制，而是通过实现readObject/writeObject两个方法自定义了序列化的内容。

布隆过滤器

介绍

一个名叫 Bloom 的人提出了一种来检索元素是否在给定大集合中的数据结构，这种数据结构是高效且性能很好的，但缺点是具有一定的错误识别率和删除难度。并且，理论情况下，添加到集合中的元素越多，误报的可能性就越大。

原理

当一个元素加入布隆过滤器中的时候，会进行如下操作：

使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值（有几个哈希函数得到几个哈希值）。
根据得到的哈希值，在位数组中把对应下标的值置为 1。

当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行如下操作：

对给定元素再次进行相同的哈希计算；
得到值之后判断位数组中的每个元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中。

布隆过滤器hash计算

使用场景

判断给定数据是否存在：比如判断一个数字是否在于包含大量数字的数字集中（数字集很大，5亿以上！）、防止缓存穿透（判断请求的数据是否有效避免直接绕过缓存请求数据库）等等、邮箱的垃圾邮件过滤、黑名单功能等等。
去重：比如爬给定网址的时候对已经爬取过的 URL 去重。

数据库调优

数据库设计规范

1.　所有表使用Innodb存储引擎
2.　数据库和表的字符集统一使用UTF8
3.　所有表和字段都需要添加注释
4.　尽量控制单表数据量的大小，建议控制在500万以内
5.　谨慎使用MySQL分区表
6.　尽量做到冷热数据分离，减小表的宽度
7.　禁止在表中建立预留字段
8.　禁止在数据库中存储图片，文件等大的二进制数据
9.　禁止在线上做数据库压力测试
10.　禁止从开发环境、测试环境直接连接产生环境数据库

数据库字段设计规范

优先选择符合存储需要的最小的数据类型
避免使用ENUM类型
尽可能把所有列定义为NOT NULL

索引设计规范

限制每张表上的索引数量，建议单张表索引不超过5个
禁止给表中的每一列都建立单独的索引
每个Innodb表必须有个主键
常见索引列建议
1. 出现在 SELECT、UPDATE、DELETE 语句的 WHERE 从句中的列
2. 包含在 ORDER BY、GROUP BY、DISTINCT 中的字段
3. 并不要将符合 1 和 2 中的字段的列都建立一个索引，通常将 1、2 中的字段建立联合索引效果更好
4. 多表 join 的关联列
如何选择索引列的顺序

建立索引的目的是：希望通过索引进行数据查找，减少随机 IO，增加查询性能，索引能过滤出越少的数据，则从磁盘中读入的数据也就越少。
- 区分度最高的放在联合索引的最左侧（区分度=列中不同值的数量/列的总行数）
- 尽量把字段长度小的列放在联合索引的最左侧（因为字段长度越小，一页能存储的数据量越大，IO 性能也就越好）
- 使用最频繁的列放到联合索引的左侧（这样可以比较少的建立一些索引）
避免建立冗余索引和重复索引
对于频繁的查询优先考虑使用覆盖索引
- 避免 Innodb 表进行索引的二次查询
- 可以把随机 IO 变成顺序 IO 加快查询效率
尽量避免使用外键约束

数据库SQL开发规范

建议使用预编译语句进行数据库操作
避免数据类型的隐式转换
充分利用表上已经存在的索引

数据库

BIO、NIO、AIO总结

BIO

同步阻塞I/O模式，数据的读取写入必须阻塞在一个线程内等待其完成。

数据结构

平衡二叉树

是二叉查找树的升级版，也叫做AVL树，平衡二叉树要求对于每一个节点来说，它的左右子树的高度之差不能超过1。

如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。

解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。

1和4两种情况是对称的，这两种情况的旋转算法是一致的，只需要经过一次旋转就可以达到目标，我们称之为单旋转。2和3两种情况也是对称的，这两种情况的旋转算法也是一致的，需要进行两次旋转，我们称之为双旋转。

右旋（左左）

k1和k2的BF设为０
k2作为根节点，k1作为右子树的根节点

先左旋再右旋（左右）

当左子树 L 的平衡因子为1时（LH）就进行简单的右旋转，为-1（RH）时就先对子树L做左旋转再对最小不平衡树T做右旋转。
修改平衡因子
1. 当Lr 的平衡因子为LH(相当于1)时，T的平衡因子变为-1，L的平衡因子变为0
2. 当Lr的平衡因子为EH(相当于0）时，T的平衡因子变为0，L的平衡因子变为0
3. 当Lr的平衡因子RH(相当于-1)时，T的平衡因子变为0，L的平衡因子变为1

红黑树

红黑树的性质

红黑树是一种自平衡二叉树，在平衡二叉树的基础上每个节点又增加了一个颜色的属性，节点的颜色只能是红色或黑色。具有以下性质：

节点要么是红色，要么是黑色，
根节点只能是黑色；
性质3.所有叶子都是黑色。（叶子是NUIL节点）
红色节点的父节点和左右孩子节点都是黑色，及黑红相间；
在任何一棵子树中，从根节点向下走到空节点的路径上所经过的黑节点的数目相同，从而保证了是一个平衡二叉树。

算法

排序算法

归并排序

import org.junit.Test;
public class MergeSort {
    //两路归并算法，两个排好序的子序列合并为一个子序列
    public void merge(int []a,int left,int mid,int right){
        int []tmp=new int[a.length];//辅助数组
        int p1=left,p2=mid+1,k=left;//p1、p2是检测指针，k是存放指针
        while(p1<=mid && p2<=right){
            if(a[p1]<=a[p2])
                tmp[k++]=a[p1++];
            else
                tmp[k++]=a[p2++];
        }
        while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
        while(p2<=right) tmp[k++]=a[p2++];//同上
        //复制回原素组
        for (int i = left; i <=right; i++) 
            a[i]=tmp[i];
    }

    public void mergeSort(int [] a,int start,int end){
        if(start<end){//当子序列中只有一个元素时结束递归
            int mid=(start+end)/2;//划分子序列
            mergeSort(a, start, mid);//对左侧子序列进行递归排序
            mergeSort(a, mid+1, end);//对右侧子序列进行递归排序
            merge(a, start, mid, end);//合并
        }
    }

    @Test
    public void test(){
        int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
        mergeSort(a, 0, a.length-1);
        System.out.println("排好序的数组：");
        for (int e : a)
            System.out.print(e+" ");
    }
}

快速排序

    void quickSort(int[] nums, int left, int right) {
        if(left >= right)
            return;
        int i = left, j = right;
        int v = nums[left];
        while(i < j) {
            while(j > i && nums[j] > v)
                j--;
            while(j > i && nums[i] <= v)
                i++;
            if(i < j) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        int tmp = nums[i];
        nums[i] = nums[left];
        nums[left] = tmp;
        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }