java：#

​ Java简单，易于设计，易于编写，因此比其他任何Java都易于编译，调试和学习。Java是面向对象的，用于构建模块化程序和其他应用程序中的可重用代码。Java与平台无关，可移植复制。

​ 首先Java是一个面向对象的编程语言，容易理解。而且略去了多重加载、指针等难以理解的概念。并且实现了自动垃圾回收，大大简化了程序设计。

​ 跨平台是Java最大的优势。Java运行在JVM（Java虚拟机）上，在任何平台只要安装了JVM。Java就可以运行。它架构在操作系统之上，屏蔽了底层的差异。真正实现了“Write once,run anywhere”。Java中没有指针，这样就没有办法直接访问内存了。

​ 另外Java也不容易出现内存泄露。

​ Java内置对多线程的支持，可以方便地在程序中实现多线程的功能。不像其他不支持多线程的语言，需要调用操作系统的多线程功能才能完成多线程的实现。

C++：#

C#：#

python：#

matlab：#

说一说对static关键字的理解？#

static关键字可以修饰类、方法、变量、代码块。

修饰类：普通类是不允许声明为静态的，只有内部类才可以使用static修饰。

修饰方法：修饰方法的时候，可以直接通过类名来进行调用。

修饰变量：被static修饰的成员变量叫做静态变量，也叫做类变量，说明这个变量是属于这个类的，而不是属于是对象，没有被static修饰的成员变量叫做实例变量，说明这个变量是属于某个具体的对象的。静态变量存放在方法区中，并且是被所有线程所共享的。

修饰代码块：静态代码块在类第一次被载入时执行。执行顺序：父类静态变量—>父类静态代码块—>子类静态变量—>子类静态代码块—>父类普通变量—>父类普通代码块—>父类构造函数—>子类普通变量—>子类普通代码块—>子类构造函数。

成员变量和静态变量的区别

• 成员变量随着对象的创建而存在随着对象的回收而释放。静态变量随着类的加载而存在随着类的消失而消失。
• 成员变量只能被对象调用。静态变量可以被对象调用，也可以用类名调用。（推荐用类名调用）
• 成员变量也称为实例变量。静态变量称为类变量。
• 成员变量数据存储在堆内存的对象中，所以也叫对象的特有数据。静态变量数据存储在方法区（共享数据区）的静态区，所以也叫对象的共享数据。

1.6.1 String的理解#

​ 先看String的源码：

1
public final class String
2
    implements java.io.Serializable, Comparable<String>, CharSequence {
3
    @Stable
4
    private final byte[] value;
5
    private final byte coder;
6
    private int hash; // Default to 0
7
    private static final long serialVersionUID = -6849794470754667710L;
8
    static final boolean COMPACT_STRINGS;
9
}

​ 从源码中关于String类的定义可以知道String类是用final修饰的，意味着String类不能被继承，并且它的成员方法都默认为final方法。在Java中final修饰的类是不允许被继承的。从类里面关于变量的定义我们可以知道，String存储字符串是使用一个final修饰的byte[ ]数组，final修饰的变量是不允许被更改的，因此String一旦被创建就是不可变的，这时候对该字符串做的修改操作，比如拼接、裁剪、替换都会生成一个新的字符串。

​ 字符串的分配和其他对象分配一样，是分配栈内存的，而且我们使用字符串的场景特别多，JVM为了提高性能和减少内存的开销，在实例化字符串的时候做了一些优化：使用字符串常量池，每当我们创建字符串常量时，JVM会首先检查字符串常量池，如果该字符已经在字符串常量池里面，那么直接返回常量池中的引用，如果不在的话，就会实例化字符串，并且将其放到常量池中。由于String的不可变性，我们能肯定的认为字符串常量池中不会存在两个相同的字符串。

1
注：常量池分为下面两种
2
  静态常量池：是.class文件中的常量池，不仅仅包括字符串、数字的字面量，还包括类、方法的信息，占用class文件的绝大部分空间。
3
  运行时常量池：是jvm类装载完成后，将class文件的常量池放入到内存中，并保存在方法区，我们常说的常量池，就是指方法区中的运行时常量池。

字符串的比较？是否相等？

1
String s1 = "Runoob";              // String 直接创建
2
String s2 = "Runoob";              // String 直接创建
3
String s3 = s1;                    // 相同引用
4
String s4 = new String("Runoob");   // String 对象创建
5
String s5 = new String("Runoob");   // String 对象创建
6
String s6 = "Run"+"oob";   // String 对象创建
7
//s1、s2、s3、s4、s5是否相等？
8
s1==s2? true; //s1和s2直接指向常量池，故相等
9
s2==s3? true; //
10
s4==s5? false;//s4是在堆区新建的对象，s5也是在堆区新建的对象，这是两个不同的对象，虽然存储的值是一样的
11
s1==s4? false;//s4是在堆区新建的对象，s1直接指向常量池
12
s1==s5? false;//同上
13
s1==s6? true; //s6看String的底层源码可以看到，两个字符串常量值在相加的时候，底层会直接优化成一个字符串。

1.6.2 String、StringBuffer、StringBuilder的区别？#

​ String：字符串常量，每次对字符串修改都会创建一个新的字符串

​ StringBuilder：字符串变量，线程不安全，对字符串修改就在其对象本身上修改

​ StringBuffer：字符串变量，线程安全，对字符串修改就在其对象本身上修改

​ 执行速度：在大部分情况下：StringBuilder>StringBuffer>String

1.6.3 String在jdk1.8和jdk1.9中的区别#

1
private final byte[] value;
2
private final byte coder;
3
//jdk1.8
4
private final char[] value;

​ String的底层实现在jdk1.8时使用的char[ ]数组，在jdk1.9的时候使用的是byte[ ]数组，这是因为开发者发现人们使用拉丁符号居多，而拉丁符号只占一个字节，char一个字符占两个字节，那么就会造成内存的浪费，GC（垃圾回收）的更加频繁，浪费了系统资源。因此jdk1.9将char数组改成了byte数组，使用byte数组会产生一个问题，因为中文字符存储是需要占两个字节，在jdk1.9中使用了一个标志位coder表示该字符串的编码方式，判断是Latin还是UTF-16。

1.7.1 错误 Error#

​ 错误一般是指与虚拟机相关的问题，如系统崩溃、虚拟机错误、动态链接失败等，这种错误无法恢复以及捕获，将导致程序中断。

1.7.2 编译时异常 Checked#

​ 编译时异常是可以被处理的异常，必须被显式的处理，如果不处理的话，不能通过编译。

1.7.3 运行时异常 RuntimeException#

​ 运行时异常，在程序运行时发生的异常，可以不处理也能通过编译，但是运行时会报错，需要通过try catch finally捕获或者抛出异常。

​ 异常的抛出：当程序出现错误时，系统会自动抛出异常，Java也允许程序员主动抛出异常，在业务代码中，判断某项错误的条件成立时，可以使用throw关键字向外抛出异常，在这种情况下，如果当前方法不知道该如何处理这个异常，可以在方法签名上通过throws关键字声明抛出异常，将异常交给JVM处理。

​ 异常的处理：在java语句中，处理异常的语句由try、catch、finally三部分组成，其中try用于包裹可能出现异常的业务代码，catch用于捕获并处理某个类型的异常，finally用于后处理，例如资源的释放。当业务代码发生异常时，系统会为此异常创建一个异常对象，创建异常对象之后，JVM会寻找可以处理该异常的catch块并交给其处理。finally中的语句块是总会执行的，即在执行try、catch后总会执行finally块。（finally不执行的例外情况：使用 System.exit(1); 来退出虚拟机）

在try和finally里面都有return会执行哪个？

​ 先执行try中的return，但不立即返回，而是去寻找是否有finally，如果有，继续执行finally中的代码，如果finally中没有return，那么执行完finally后回到try中执行return，如果finally中有return，那么直接返回。

1.7.4 怎么自定义异常？#

1. 创建一个自定义异常类继承Exception
2. 在需要用到这个自定义异常类的地方使用 throw new 自定义异常类名(“异常信息”);
3. 在方法上使用throws抛出这个自定义异常。

1.8.1 什么是反射？#

​ 一般我们要使用某个已知类时，直接使用new一个对象实例化，这是正向的创建一个类的对象，如果一开始我们不知道要创建的类是什么的时候，自然也就无法通过new关键字来创建对象，这时候我们就需要利用反射，使用JDK提供的反射API来进行反射调用。

​ 反射就是在运行时才知道要操作的类是什么，并且可以在运行时获取类的完整构造，并调用对应的方法。

1.8.2 通过反射获取class对象#

1. Class c = Class.forName(“类的全限定名称”);
2. Class c = String.class;//事先就知道要操作的类
3. Class c = 引用.getClass();//可以根据一个引用反向获取类的对象

通过反射创建对象：

1. 通过Class对象的newInstance方法：

   Class c = String.class;

   String str = (String)c.newInstance();

2. 通过Constructor对象的newInstance方法

   Constructor constructor = c.getConstructor();

   String str= (String )constructor.newInstance();

1.8.3 通过反射获取类属性、方法、构造器：#

属性：我们通过 Class 对象的 getFields() 方法可以获取 Class 类的属性，但无法获取私有属性。

​ 而如果使用 Class 对象的 getDeclaredFields() 方法则可以获取包括私有属性在内的所有属性。

1
Class clz = String.class;
2
Field[] fields = clz.getFields();//获取非私有属性
3
for (Field field : fields) {
4
    System.out.println(field.getName());
5
}
6

7
Class clz = String.class;
8
Field[] fields = clz.getDeclaredFields();//获取所有属性 包括私有的
9
for (Field field : fields) {
10
    System.out.println(field.getName());
11
}

方法：我们通过 Class 对象的 getMethods() 方法可以获取 Class 类的方法，但无法获取私有方法。

​ 而如果使用 Class 对象的 getDeclaredMethods() 方法则可以获取包括私有方法在内的所有方法。

构造器：我们通过 Class 对象的 getConstructors()方法可以获取 Class 类的构造器，但无法获取私有构造器。

​ 而如果使用 Class 对象的 getDeclaredConstructors()方法则可以获取包括私有构造器在内的所有构造器。

1.8.4 反射的优缺点#

优点：

• 增加程序的灵活性，避免将程序写死到代码里。
• 代码简洁，提高代码的复用率，外部调用方便

缺点：

• 性能问题：反射包括了一些动态类型，所以JVM无法对这些代码进行优化。因此，反射操作的效率要比那些非反射操作低得多。我们应该避免在经常被 执行的代码或对性能要求很高的程序中使用反射。
• 使用反射会模糊程序内部逻辑：程序人员希望在源代码中看到程序的逻辑，反射等绕过了源代码的技术，因而会带来维护问题。反射代码比相应的直接代码更复杂。
• 安全限制：使用反射技术要求程序必须在一个没有安全限制的环境中运行。如果一个程序必须在有安全限制的环境中运行，如Applet，那么这就是个问题了。
• 内部暴露：由于反射允许代码执行一些在正常情况下不被允许的操作(比如访问私有的属性和方法)，所以使用反射可能会导致意料之外的副作用。

2.2.1 ArrayList实现类#

1
public class ArrayList<E> extends AbstractList<E>
2
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
3
{
4
    private static final long serialVersionUID = 8683452581122892189L;
5
    private static final int DEFAULT_CAPACITY = 10;//初始默认容量
6
    private static final Object[] EMPTY_ELEMENTDATA = {};
7
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
8
    //被transient修饰的变量不参与序列化和反序列化
9
    transient Object[] elementData;//存储结构
10
    private int size;
11
}

​ ArrayList是List接口的实现类，首先满足List的特征，元素有序、可重复，ArrayList是线程不安全的，底层使用数组实现，默认初始容量是10，存满后按照1.5倍扩容，扩容源码如下：

1
private Object[] grow() {
2
    return grow(size + 1);
3
}
4
private Object[] grow(int minCapacity) {
5
    return elementData = Arrays.copyOf(elementData,
6
                                       newCapacity(minCapacity));
7
}
8
private int newCapacity(int minCapacity) {
9
    // overflow-conscious code
10
    int oldCapacity = elementData.length;
11
    //新容量大小=旧容量大小+旧容量右移一位（右移一位相当于除2）
12
    int newCapacity = oldCapacity + (oldCapacity >> 1);
13
    if (newCapacity - minCapacity <= 0) {
14
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
15
            return Math.max(DEFAULT_CAPACITY, minCapacity);
16
        if (minCapacity < 0) // overflow
17
            throw new OutOfMemoryError();
18
        return minCapacity;
19
    }
20
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
21
        ? newCapacity
22
        : hugeCapacity(minCapacity);
23
}

​ ArrayList在对象创建的时候并没有直接创建长度为10的数组，这个数组初始化的过程是在第一次插入元素的时候，（而在JDK1.7中是在对象创建的时候直接创建长度为10 的数组）。源码如下：

1
private void add(E e, Object[] elementData, int s) {
2
    if (s == elementData.length)//判断数组是不是空，如果是空第一次执行扩容，扩容到默认的大小
3
        elementData = grow();
4
    elementData[s] = e;
5
    size = s + 1;
6
}

ArrayList常用方法：

1
void add(int index, E element) 将指定元素插入此列表中的指定位置。
2
boolean add(E e) 将指定的元素追加到此列表的末尾。  ***********************
3
boolean contains(Object o) 如果此列表包含指定的元素，则返回 true 。 ******
4
E get(int index) 返回此列表中指定位置的元素。  ***********************
5
boolean isEmpty() 如果此列表不包含任何元素，则返回 true 。  **************
6
int indexOf(Object o) 返回此列表中第一次出现的指定元素的索引，如果此列表不包含该元素，则返回-1。
7
E remove(int index) 删除此列表中指定位置的元素。  ***********************
8
boolean remove(Object o) 从该列表中删除指定元素的第一个匹配项（如果存在）。
9
int size() 返回此列表中的元素数。  ***********************
10
Object[] toArray() 以适当的顺序（从第一个元素到最后一个元素）返回包含此列表中所有元素的数组。

ArrayList和数组的区别：

1. 数组长度固定，集合长度可变
2. 数组可以存基本数据类型，也可以存引用数据类型，而集合只能存引用数据类型。

2.2.2 Vector实现类#

1
public class Vector<E>
2
    extends AbstractList<E>
3
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
4
{
5
    protected Object[] elementData;
6
    protected int elementCount;
7
    protected int capacityIncrement;
8
    private static final long serialVersionUID = -2767605614048989439L;
9
    public Vector() {
10
        this(10);//默认初始容量是10
11
    }
12
}

​ Vector是List接口的实现类，首先满足List的特征，元素有序、可重复，Vector是线程安全的，底层使用数组实现，默认初始容量是10，存满后可以按照自己规定的扩容大小进行扩容默认是2倍扩容，扩容源码如下：

1
private int newCapacity(int minCapacity) {
2
    // overflow-conscious code
3
    int oldCapacity = elementData.length;
4
    //新容量大小 = 旧容量大小 + 增长倍数>0? 增长大小:旧容量;  意思是我们可以规定每次扩容多少容量，默认是两倍增长
5
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
6
                                     capacityIncrement : oldCapacity);
7
    if (newCapacity - minCapacity <= 0) {
8
        if (minCapacity < 0) // overflow
9
            throw new OutOfMemoryError();
10
        return minCapacity;
11
    }
12
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
13
        ? newCapacity
14
        : hugeCapacity(minCapacity);
15
}

Vector和ArrayList的区别：

1. 两者底层都是使用数组实现的，ArrayList的扩容是1.5倍，Vector的扩容可以自己设置，默认是2倍。
2. ArrayList是线程不安全的，Vector是线程安全的，因为Vector的主要方法上使用了synchronized修饰。
3. ArrayList效率较高，Vector因线程同步，效率较低，已不推荐使用。如果想获取线程同步的ArrayList可以使用Collections工具类里面的同步方法synchronizedList()方法。

2.2.3 LinkedList实现类#

1
public class LinkedList<E>
2
    extends AbstractSequentialList<E>
3
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
4
{
5
    transient int size = 0;
6
    transient Node<E> first;
7
    transient Node<E> last;
8
    ......
9
    private static class Node<E> {
10
        E item;
11
        Node<E> next;
12
        Node<E> prev;
13

14
        Node(Node<E> prev, E element, Node<E> next) {
15
            this.item = element;
16
            this.next = next;
17
            this.prev = prev;
18
        }
19
    }
20
}

​ LinkedList是List接口的实现类，首先满足List的特征，元素有序、可重复，LinkedList是线程不安全的，底层使用的是双向链表。

LinkedList的常用方法：

1
void add(int index, E element) 将指定元素插入此列表中的指定位置。  **********
2
boolean add(E e) 将指定的元素追加到此列表的末尾。
3
void addFirst(E e) 在此列表的开头插入指定的元素。  ***********************
4
void addLast(E e) 将指定的元素追加到此列表的末尾。  ***********************
5
boolean contains(Object o) 如果此列表包含指定的元素，则返回 true 。*********
6
E element() 检索但不删除此列表的头部（第一个元素）。  ***********************
7
E get(int index) 返回此列表中指定位置的元素。  ***********************
8
E getFirst() 返回此列表中的第一个元素。
9
E getLast() 返回此列表中的最后一个元素。
10
int indexOf(Object o) 返回此列表中第一次出现的指定元素的索引，如果此列表不包含该元素，则返回-1。
11
int lastIndexOf(Object o) 返回此列表中指定元素最后一次出现的索引，如果此列表不包含该元素，则返回-1。
12
boolean offer(E e) 将指定的元素添加为此列表的尾部（最后一个元素）。  ***************
13
boolean offerFirst(E e) 在此列表的前面插入指定的元素。
14
boolean offerLast(E e) 在此列表的末尾插入指定的元素。
15
E peek() 检索但不删除此列表的头部（第一个元素）。  ***********************
16
E peekFirst() 检索但不删除此列表的第一个元素，如果此列表为空，则返回 null 。
17
E peekLast() 检索但不删除此列表的最后一个元素，如果此列表为空，则返回 null 。
18
E poll() 检索并删除此列表的头部（第一个元素）。  ***********************
19
E pollFirst() 检索并删除此列表的第一个元素，如果此列表为空，则返回 null 。
20
E pollLast() 检索并删除此列表的最后一个元素，如果此列表为空，则返回 null 。
21
E pop() 弹出此列表所代表的堆栈中的元素。  ***********************
22
void push(E e) 将元素推送到此列表所表示的堆栈上。  ***********************
23
E remove() 检索并删除此列表的头部（第一个元素）。  ***********************
24
E remove(int index) 删除此列表中指定位置的元素。  ***********************
25
boolean remove(Object o) 从该列表中删除指定元素的第一个匹配项（如果存在）。  *****
26
E removeFirst() 从此列表中删除并返回第一个元素。  ***********************
27
E removeLast() 从此列表中删除并返回最后一个元素。  **********************
28
int size() 返回此列表中的元素数。

ArrayList和LinkedList的区别：

1. ArrayList地层使用的是数组，LinkedList底层使用的是双向链表
2. 在随机位置的元素的访问上面，ArrayList是优于LinkedList，因为数组存储时连续的，可以直接得到存储位置，而链表存储不连续，需要遍历查找。
3. 对于插入和删除，LinkedList要优于ArrayList，因为链表的插入和删除不需要移动元素，只需要修改链表前后的引用，而数组删除需要移动元素，插入需要重新计算容量大小，如果容量不够还需要扩容。
4. LinkedList比ArrayList更占内存，因为链表存储前后节点的引用需要占用一部分内存。

2.2.4 有哪些线程安全的List？#

1. Vector类：不建议使用
2. Collections.synchronizedList(List引用)方法：每个方法带有同步锁，不是性能最优
3. CopyOnWriteArrayList类：性能最优、对内存压力大、GC更频繁，无法保证数据实时性

1
CopyOnWriteArrayList是Java并发包里提供的并发类，简单来说它就是一个线程安全且读操作无锁的ArrayList。正如其名字一样，在写操作时会复制一份新的List，在新的List上完成写操作，然后再将原引用指向新的List。这样就保证了写操作的线程安全。
2
CopyOnWriteArrayList允许线程并发访问读操作，这个时候是没有加锁限制的，性能较高。而写操作的时候，则首先将容器复制一份，然后在新的副本上执行写操作，这个时候写操作是上锁的。结束之后再将原容器的引用指向新容器。注意，在上锁执行写操作的过程中，如果有需要读操作，会作用在原容器上。因此上锁的写操作不会影响到并发访问的读操作。
3
  优点：读操作性能很高，因为无需任何同步措施，比较适用于读多写少的并发场景。在遍历传统的List时，若中途有别的线程对其进行修改，则会抛出ConcurrentModificationException异常。而CopyOnWriteArrayList由于其"读写分离"的思想，遍历和修改操作分别作用在不同的List容器，所以在使用迭代器进行遍历时候，也就不会抛ConcurrentModificationException异常了。
4
  缺点：一是内存占用问题，毕竟每次执行写操作都要将原容器拷贝一份，数据量大时，对内存压力较大，可能会引起频繁GC。二是无法保证实时性，Vector对于读写操作均加锁同步，可以保证读和写的强一致性。而CopyOnWriteArrayList由于其实现策略的原因，写和读分别作用在新老不同容器上，在写操作执行过程中，读不会阻塞但读取到的却是老容器的数据。

2.3.1 HashSet实现类#

1
public class HashSet<E>
2
    extends AbstractSet<E>
3
    implements Set<E>, Cloneable, java.io.Serializable
4
{
5
    static final long serialVersionUID = -5024744406713321676L;
6
    private transient HashMap<E,Object> map;//HashSet的存储是用的HashMap的Key
7
    private static final Object PRESENT = new Object();
8
    public HashSet() {
9
        map = new HashMap<>();
10
    }
11
}

​ HashSet是Set接口的实现类，首先满足Set集合的特征，元素无序、不可重复，HashSet是线程不安全的。HashSet的底层使用的HashMap，使用HashMap的key来存储元素，HashMap默认初始容量是16，扩容容量大小为2的幂（也就是2倍扩容）。

​ 元素唯一性的保证是通过hashCode()和equals()方法实现的，往一个Set集合存储元素的步骤是：先使用hashCode()方法计算该元素的hash值，利用hash值找到元素存储的位置，判断该位置是否为空，如果为空，那么该元素可以直接插入，如果该位置有元素，那么就调用equals()方法判断是否是同一个元素，如果是，那么就是同一个对象，无需存储，如果不是，那么在HashMap中是使用的链地址法解决哈希冲突，将新的元素链接到当前hashCode值的链表后面。

1
哈希冲突解决办法：
2
1.开放地址法：
3
（1）线性探测：按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上往后加一个单位，直至不发生哈希冲突。
4
（2）再平方探测：按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上先加1的平方个单位，若仍然存在则减1的平方个单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。
5
（3）伪随机探测：按顺序决定值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来值的基础上加上随机数，直至不发生哈希冲突。
6
2.链地址法：对于相同的值，使用链表进行连接。使用数组存储每一个链表。
7
3.再哈希法：对于冲突的哈希值再次进行哈希处理，直至没有哈希冲突。
8
4.建立公共溢出区：建立公共溢出区存储所有哈希冲突的数据。

HashSet的常用方法：

1
boolean add(E e) 如果指定的元素尚不存在，则将其添加到此集合（可选操作）。  ************
2
boolean contains(Object o) 如果此set包含指定的元素，则返回 true 。  **************
3
boolean isEmpty() 如果此集合不包含任何元素，则返回 true 。  ***********************
4
int size() 返回此集合中的元素数（基数）。  ***********************
5
boolean remove(Object o) 如果存在，则从该集合中移除指定的元素（可选操作）。  *********

2.3.2 TreeSet实现类#

1
public class TreeSet<E> extends AbstractSet<E>
2
    implements NavigableSet<E>, Cloneable, java.io.Serializable
3
{
4
    private transient NavigableMap<E,Object> m;
5
    private static final Object PRESENT = new Object();
6
}
7
public interface NavigableSet<K,V> extends SortedSet<K,V> {}
8
public interface SortedMap<K,V> extends Map<K,V> {}

​ TreeSet是Set接口的实现类，首先满足Set集合的特征，元素无序、不可重复，TreeSet是线程不安全的。TreeSet实现了NavigableSet接口，NavigableSet接口继承于SortedSet接口，TreeSet内部实现了比较器，所以存储元素有序。底层基于TreeMap实现， 元素唯一且已经排好序；唯一性同样需要重写hashCode和equals()方法 。

TreeSet的常用方法：

1
boolean add(E e) 如果指定的元素尚不存在，则将其添加到此集合（可选操作）。  **************
2
boolean contains(Object o) 如果此set包含指定的元素，则返回 true 。  ****************
3
E ceiling(E e) 返回此set中大于或等于给定元素的 null元素，如果没有这样的元素，则 null 。
4
E floor(E e) 返回此set中小于或等于给定元素的最大元素，如果没有这样的元素，则 null 。
5
E higher(E e) 返回此集合中的最小元素严格大于给定元素，如果没有这样的元素，则 null 。
6
E lower(E e) 返回此集合中的最大元素严格小于给定元素，如果没有这样的元素，则 null 。
7
boolean isEmpty() 如果此集合不包含任何元素，则返回 true 。  ***********************
8
E first() 返回此集合中当前的第一个（最低）元素。
9
E last() 返回此集合中当前的最后一个（最高）元素。
10
E pollFirst() 检索并删除第一个（最低）元素，如果此组为空，则返回 null 。
11
E pollLast() 检索并删除最后一个（最高）元素，如果此集合为空，则返回 null 。
12
int size() 返回此集合中的元素数（基数）。  ***********************
13
boolean remove(Object o) 如果存在，则从该集合中移除指定的元素（可选操作）。  *********

2.3.3 TreeSet和HashSet的区别#

TreeSet和HashSet都是Set接口下的实现类，都是元素无序且唯一，都是线程不安全的，区别是：

1. HashSet是基于HashMap实现的（Node数组+链表+红黑树），TreeSet底层基于TreeMap实现的（红黑树）。
2. HashSet是不能保证元素的排列顺序，而TreeSet支持自然排序、定值排序。
3. HashSet可以存储null值，但是TreeSet不可以存null值。

2.4.1 ArrayDeque实现类#

1
public class ArrayDeque<E> extends AbstractCollection<E>
2
                           implements Deque<E>, Cloneable, Serializable
3
{
4
    transient Object[] elements;
5
    transient int head;
6
    transient int tail;
7
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
8
    public ArrayDeque() {
9
        elements = new Object[16];//初始化容量是16
10
    }
11
    ......
12
    private int newCapacity(int needed, int jump) {
13
        final int oldCapacity = elements.length, minCapacity;
14
        if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
15
            if (minCapacity < 0)
16
                throw new IllegalStateException("Sorry, deque too big");
17
            return Integer.MAX_VALUE;
18
        }
19
        if (needed > jump)
20
            return minCapacity;
21
        return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)
22
            ? oldCapacity + jump
23
            : MAX_ARRAY_SIZE;
24
    }
25
}

​ 底层是用循环数组实现的双端队列，初始默认容量是16，扩容是2倍。

​ 普通数组只能快速在末尾添加元素，为了支持FIFO，从数组头快速取出元素，就需要使用循环数组：有队头队尾两个下标：弹出元素时，队头下标递增；加入元素时，如果已到数组空间的末尾，则将元素循环赋值到数组0，同时队尾下标指向0，再插入下一个元素则赋值到数组[1]，队尾下标指向1。如果队尾的下标追上队头，说明数组所有空间已用完，进行双倍的数组扩容。

ArrayDeque的常用方法：

1
boolean add(E e) 在此双端队列的末尾插入指定的元素。  ***********************
2
void addFirst(E e) 在此双端队列的前面插入指定的元素。  ***********************
3
void addLast(E e) 在此双端队列的末尾插入指定的元素。  ***********************
4
boolean contains(Object o) 如果此双端队列包含指定的元素，则返回 true 。  ************
5
E element() 检索但不删除此双端队列表示的队列的头部。  ***********************
6
E getFirst() 检索但不删除此双端队列的第一个元素。
7
E getLast() 检索但不删除此双端队列的最后一个元素。
8
boolean isEmpty() 如果此双端队列不包含任何元素，则返回 true 。 ***********************
9
boolean offer(E e) 在此双端队列的末尾插入指定的元素。  ***********************
10
boolean offerFirst(E e) 在此双端队列的前面插入指定的元素。
11
boolean offerLast(E e) 在此双端队列的末尾插入指定的元素。
12
E peek() 检索但不删除此双端队列表示的队列的头部，如果此双端队列为空，则返回 null 。  *******
13
E poll() 检索并删除此双端队列表示的队列的头部（换句话说，此双端队列的第一个元素），如果此双端队列为空，则返回 null 。 ******
14
E pop() 从此双端队列表示的堆栈中弹出一个元素。  ***********************
15
void push(E e) 将元素推送到此双端队列表示的堆栈上。  ***********************
16
E remove() 检索并删除此双端队列表示的队列的头部。  **********************
17
E removeFirst() 检索并删除此双端队列的第一个元素。  ***********************
18
E removeLast() 检索并删除此双端队列的最后一个元素。  ***********************
19
int size() 返回此双端队列中的元素数。  ***********************

2.4.2 LinkedList实现类#

​ LinkedList是Queue接口的实现类，LinkedList是线程不安全的，底层使用的是双向链表，类的具体定义见2.2.3

2.4.3 PriorityQueue实现类#

1
public class PriorityQueue<E> extends AbstractQueue<E>
2
    implements java.io.Serializable {
3
    private static final long serialVersionUID = -7720805057305804111L;
4
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
5
    transient Object[] queue; // non-private to simplify nested class access
6
    int size;
7
    private final Comparator<? super E> comparator;
8
    transient int modCount;     // non-private to simplify nested class access
9
    public PriorityQueue() {
10
        this(DEFAULT_INITIAL_CAPACITY, null);
11
    }
12
    ......
13
    private void grow(int minCapacity) {
14
        int oldCapacity = queue.length;
15
        // Double size if small; else grow by 50%
16
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
17
                                         (oldCapacity + 2) :
18
                                         (oldCapacity >> 1));
19
        // overflow-conscious code
20
        if (newCapacity - MAX_ARRAY_SIZE > 0)
21
            newCapacity = hugeCapacity(minCapacity);
22
        queue = Arrays.copyOf(queue, newCapacity);
23
    }
24
}

​ PriorityQueue是Queue接口的实现类，PriorityQueue是线程不安全的，底层使用的是数组实现的二叉小根堆，可以保证每次取出的值都是最小的，我们也可以在构造时传入比较器，改变排序方式。数组的初始容量是11，扩容的话，如果当前容量小于64，则按两倍扩容，如果大于64则按1.5倍扩容。

PriorityQueue常用方法：

1
boolean add(E e) 将指定的元素插入此优先级队列。
2
E element() 检索但不删除此队列的头部。
3
boolean contains(Object o) 如果此队列包含指定的元素，则返回 true 。
4
boolean offer(E e) 将指定的元素插入此优先级队列。
5
E poll() 检索并删除此队列的头部，如果此队列为空，则返回 null 。
6
boolean remove(Object o) 从此队列中删除指定元素的单个实例（如果存在）。

2.5.1 HashMap实现类#

1
public class HashMap<K,V> extends AbstractMap<K,V>
2
    implements Map<K,V>, Cloneable, Serializable {
3
    private static final long serialVersionUID = 362498820763181265L;
4
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16  初始容量
5
    static final int MAXIMUM_CAPACITY = 1 << 30;
6
    static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认装载因子
7
    static final int TREEIFY_THRESHOLD = 8;     //链表树化的链表长度
8
    static final int UNTREEIFY_THRESHOLD = 6;  //树转链表的树的节点数
9
    static final int MIN_TREEIFY_CAPACITY = 64;//链表转树时，数组最低长度
10
    static class Node<K,V> implements Map.Entry<K,V> {//Node节点结构，我们的数据都存储在Node节点中
11
        final int hash;
12
        final K key;
13
        V value;
14
        Node<K,V> next;
15

16
        Node(int hash, K key, V value, Node<K,V> next) {
17
            this.hash = hash;
18
            this.key = key;
19
            this.value = value;
20
            this.next = next;
21
        }
22
    }
23
    transient Node<K,V>[] table;//Node数组，用于存储数据
24
    transient Set<Map.Entry<K,V>> entrySet;
25
    transient int size;      //节点数目
26
    transient int modCount;
27
    int threshold;         //扩容门限=装载因子*容量大小
28
    final float loadFactor;//装载因子
29
    //构造方法
30
    public HashMap(int initialCapacity, float loadFactor) {
31
        if (initialCapacity < 0)
32
            throw new IllegalArgumentException("Illegal initial capacity: " +
33
                                               initialCapacity);
34
        if (initialCapacity > MAXIMUM_CAPACITY)
35
            initialCapacity = MAXIMUM_CAPACITY;
36
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
37
            throw new IllegalArgumentException("Illegal load factor: " +
38
                                               loadFactor);
39
        this.loadFactor = loadFactor;
40
        this.threshold = tableSizeFor(initialCapacity);
41
    }
42
}

在jdk1.7中

​ HashMap底层采用的是Entry数组+链表的实现，即使用链表来处理哈希冲突，相同hashCode值的的节点都存在一个链表里，但是当某一个位置的冲突较多时，依次通过key值查找效率依然很低。

在jdk1.8中的优化

​ HashMap底层采用的是Node数组+链表+红黑树的实现，同样使用链地址法来 处理哈希冲突，只不过当链表长度达到8时，就会将链表转换成红黑树，大大减少了查找时间。当链表数组的容量超过初始容量的0.75时，再散列将链表数组扩大2倍，把原链表数组的搬移到新的数组中。

**总结：**HashMap底层采用的是Node数组+链表+红黑树的实现，可以存储null。初始容量是16，加载因子是0.75，当存储的容量达到0.75时扩容，扩容是两倍。HashMap是线程不安全的。

HashMap的扩容机制：

1. 数组的初始容量为16，而容量是以2的次方扩充的，一是为了提高性能使用足够大的数组，二是为了能使用位运算代替取模预算(据说提升了5~8倍)。

2. 数组是否需要扩充是通过负载因子判断的，如果当前元素个数为数组容量的0.75倍时，就会扩充数组。这个0.75就是默认的负载因子，可由构造器传入。我们也可以设置大于1的负载因子，这样数组就不会扩充，牺牲性能，节省内存。

3. 为了解决碰撞，数组中的元素是单向链表类型。当链表长度到达一个阈值时（8），会将链表转换成红黑树提高性能。而当链表长度缩小到另一个阈值时（6），又会将红黑树转换回单向链表提高性能。

4. 对于第三点补充说明，检查链表长度转换成红黑树之前，还会先检测当前数组数组是否到达一个阈值（64），如果没有到达这个容量，会放弃转换，先去扩充数组。所以上面也说了链表长度的阈值是7或8，因为会有一次放弃转换的操作。

HashMap的put(key,value)和get(key)操作：

​ get(key)操作：调用hashCode()根据key计算出hash值，从而找到对象存储位置，然后调用equals()方法在该位置上的链表一直判断，直到找到key相同的对象，返回value。

​ put(key,value)操作：先判断Node数组是否为null，如果为null则先扩容，扩容后调用hashCode()根据key计算出hash值，从而找到对象存储的位置，判断该位置是否为null，如果为null，直接插入，如果不为null，调用equals()挨个判断该hash值链接的链表或者红黑树，如果有key相同的则直接覆盖，没有相同的则插入链表或者红黑树，如果插入节点后链表长度达到8，那么要对链表进行树化操作。

​ 树化操作：链表节点数达到8时，会调用树化的方法，先判断Node数组的长度有没有达到64，如果没有达到64，那么执行扩容，放弃树化，如果Node数组的长度达到64，那么执行树化操作，将链表转化成红黑树。

树化操作代码如下：

1
final void treeifyBin(Node<K,V>[] tab, int hash) {
2
    int n, index; Node<K,V> e;
3
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
4
        resize();//扩容
5
    else if ((e = tab[index = (n - 1) & hash]) != null) {
6
        TreeNode<K,V> hd = null, tl = null;
7
        do {
8
            TreeNode<K,V> p = replacementTreeNode(e, null);
9
            if (tl == null)
10
                hd = p;
11
            else {
12
                p.prev = tl;
13
                tl.next = p;
14
            }
15
            tl = p;
16
        } while ((e = e.next) != null);
17
        if ((tab[index] = hd) != null)
18
            hd.treeify(tab);
19
    }
20
}

hashmap为什么在链表长度为8的时候变为红黑树?为什么是8？

​ 源码中的注释写的很清楚，因为树节点所占空间是普通节点的两倍，所以只有当节点足够多的时候，才会使用树节点。也就是说，节点少的时候，尽管时间复杂度上，红黑树比链表好一点，但是红黑树所占空间比较大，综合考虑，认为只能在节点太多的时候，红黑树占空间大这一劣势不太明显的时候，才会舍弃链表，使用红黑树。

​ 源码上说，为了配合使用分布良好的hashCode，树节点很少使用。并且在理想状态下，受随机分布的hashCode影响，链表中的节点遵循泊松分布，而且根据统计，链表中节点数是8的概率已经接近千分之一，而且此时链表的性能已经很差了。所以在这种比较罕见和极端的情况下，才会把链表转变为红黑树。因为链表转换为红黑树也是需要消耗性能的，特殊情况特殊处理，为了挽回性能，权衡之下，才使用红黑树，提高性能。也就是大部分情况下，hashmap还是使用的链表，如果是理想的均匀分布，节点数不到8，hashmap就自动扩容了。

HashMap的线程安全问题：HashMap是线程不安全的，在多线程并发访问的时候会出现死循环、数据丢失、数据覆盖的问题。

​ 在jdk1.7中，在多线程访问的情况下，并发执行put操作时，如果这时候刚好HashMap需要扩容，两个线程同时对HashMap进行扩容，在内存中会存在两个HashMap的Node数组，如果一个线程对链表节点的处理结束但还没有重新设置HashMap的引用，另一个线程又对链表就行设置就会出现死循环的现象，这是由于链表插入采用的是头插法，会形成环，

​ 在jdk1.8中使用的尾插法，解决了这个头插法产生的弊端，但是如果多线程访问需要对链表转换成树或者对树进行操作可能出现死循环的问题。

​ 数据覆盖：假如说两个线程A、B都在进行put操作，并且由hash值算出来的数据下标都一样，这样就出现了碰撞，假设线程A在执行到的那一行由于时间片用完了，线程B能够正常的放进去（因为A还没有将数据放进去），但是当轮到线程A执行的时候，由于之前已经判断过了，此时会直接覆盖掉线程B存放的数据，导致数据覆盖还有一个地方就是++size这行代码，由于它不是原子操作，当A+1操作后还未写会主存，由于时间片用完，线程B拿到的还是原来的size，也就是说A、B都+1了，加了两次，实际上只有1次，从而造成线程的不安全。

HashMap为什么采用红黑树而不是AVL树、B树或者B+树？

​ 平衡二叉树和红黑树的查找时间相差不多，时间复杂度都为O(lgn)，但是AVL树更加强调平衡，为了达到平衡多了很多树的调整操作。但实际上AVL树在查找密集型任务上更快：利用更好的平衡，树遍历平均更短。另一方面，插入和删除方面，AVL树速度较慢：需要更高的旋转次数才能在修改时正确地重新平衡数据结构。红黑树和AVL都是O（log n）查找，但平衡AVL树可能需要O（log n）旋转，而红黑树将需要最多两次旋转使其达到平衡（尽管可能需要检查O（log n）节点以确定旋转的位置）。旋转本身是O（1）操作，因为你只是移动指针。

​ B/B+树多用于外存上时，B/B+也被成为一个磁盘友好的数据结构。HashMap本来是Node数组+链表的形式，链表由于其查找慢的特点，所以需要被查找效率更高的树结构来替换。如果用B/B+树的话，在数据量不是很多的情况下，数据都会“挤在”一个结点里面，这个时候遍历效率就退化成了链表。

HashMap的常用方法：

1
boolean containsKey(Object key) 如果此映射包含指定键的映射，则返回 true 。
2
boolean containsValue(Object value) 如果此映射将一个或多个键映射到指定值，则返回 true 。
3
Set<Map.Entry<K,V>> entrySet() 返回此映射中包含的映射的Set视图。
4
V get(Object key) 返回指定键映射到的值，如果此映射不包含键的映射，则返回 null 。
5
boolean isEmpty() 如果此映射不包含键 - 值映射，则返回 true 。
6
Set<K> keySet() 返回此映射中包含的键的Set视图。
7
V put(K key, V value) 将指定的值与此映射中的指定键相关联。
8
V remove(Object key) 从此映射中删除指定键的映射（如果存在）。
9
int size() 返回此映射中键 - 值映射的数量。

2.5.2 Hashtable实现类#

1
public class Hashtable<K,V>
2
    extends Dictionary<K,V>
3
    implements Map<K,V>, Cloneable, java.io.Serializable {
4
    private transient Entry<?,?>[] table;
5
    private transient int count;
6
    private int threshold;
7
    private float loadFactor;
8
    private transient int modCount = 0;
9
    private static final long serialVersionUID = 1421746759512286392L;
10
    public Hashtable() {
11
        this(11, 0.75f);
12
    }
13
}

​ Hashtable底层是使用的Entry数组+链表的实现，初始容量是11，默认加载因子是0.75，扩容是原来容量的2倍加1（新容量=旧容量 * 2 + 1）。Hashtable是线程安全的，因为在其主要的方法上都加了synchronized关键字进行同步。

Hashtable和HashMap的区别：*

1. Hashtable底层是使用的Entry数据+链表的实现，初始容量是11，扩容是原来容量的2倍加1，HashMap底层采用的是Node数组+链表+红黑树的实现，初始容量是16，扩容是两倍。

2. Hashtable是一个线程安全的Map实现，但HashMap是线程不安全的实现，所以HashMap比Hashtable的性能高一点。

3. Hashtable不允许使用null作为key和value，如果试图把null值放进Hashtable中，将会引发空指针异常，但HashMap可以使用null作为key或value。

2.5.3 TreeMap实现类#

1
public class TreeMap<K,V>
2
    extends AbstractMap<K,V>
3
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
4
{
5
    private final Comparator<? super K> comparator;
6
    private transient Entry<K,V> root;
7
    private transient int size = 0;
8
    private transient int modCount = 0;
9
}

​ TreeMap底层是使用的红黑树实现的，线程不安全，实现SortedMap，支持遍历时按元素的大小有序遍历。该集合最重要的特点就是可排序，该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator比较器进行排序，具体取决于使用的构造方法。

2.5.4 如何得到一个线程安全的Map？#

1. 使用Collections工具类，将线程不安全的Map包装成线程安全的Map； Collections.synchronizedMap(map);
2. 使用java.util.concurrent(JUC)包下的Map，如ConcurrentHashMap；
3. 不建议使用Hashtable，虽然Hashtable是线程安全的，但是性能较差。

2.5.5 JUC下的ConcurrentHashMap介绍#

JDK 1.7中的实现：

​ 在 jdk 1.7 中，ConcurrentHashMap 是由 Segment 数据结构和 HashEntry 数组结构构成，采取分段锁来保证安全性。Segment 是 ReentrantLock 重入锁，在 ConcurrentHashMap 中扮演锁的角色，HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组，一个Segment 里包含一个 HashEntry 数组，Segment 的结构和 HashMap 类似，是一个数组和链表结构。

JDK 1.8中的实现：

​ JDK1.8 的实现已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用CAS+synchronized+volatile来操作，整个看起来就像是优化过且线程安全的HashMap

ConcurrentHashMap的put()和get()操作：

get()操作： ConcurrentHashMap 同样是通过Key的哈希值与数组长度取模确定该Key在数组中的索引。如果头节点的 hash 值小于 0，说明正在扩容或者该节点是红黑树。为了避免不太好的Key的hashCode设计，它通过如下方法计算得到Key的最终哈希值。

1
static final int spread(int h) {
2
    return (h ^ (h >>> 16)) & HASH_BITS;
3
}

**put()操作：**ConcurrentHashMap 是通过Key的哈希值与数组长度取模确定该Key在数组中的索引，第一步先判断数组是不是空，如果为空先进行数组初始化过程，然后根据索引查看当前位置是否为空，如果为空用使用 CAS 操作将这个新值放入这个位置，如果不为空，首先判断该位置的首个元素的hash 值如果等于 MOVED ，说明在扩容，帮助数据迁移 helpTransfer，否则获取synchronized 监视器锁，然后在该索引下的链表遍历，如果有key相等直接覆盖，如果都不相等，在链表的结尾添加该对象，然后根据链表的长度判断链表是否需要树化。

1
static final int MOVED     = -1; // hash for forwarding nodes 扩容，正在转移结点
2
static final int TREEBIN   = -2; // hash for roots of trees   是红黑树节点
3
static final int RESERVED  = -3; // hash for transient reservations
4
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash 用于计算最终hash值

HashMap和ConcurrentHashMap的区别：

​ HashMap是非线程安全的，这意味着不应该在多线程中对这些Map进行修改操作，否则会产生数据不一致的问题，甚至还会因为并发插入元素而导致链表成环，这样在查找时就会发生死循环，影响到整个应用程序。

​ Collections工具类可以将一个Map转换成线程安全的实现，其实也就是通过一个包装类，然后把所有功能都委托给传入的Map，而包装类是基于synchronized关键字来保证线程安全的（Hashtable也是基于synchronized关键字），底层使用的是互斥锁，性能与吞吐量比较低。

​ ConcurrentHashMap的实现细节远没有这么简单，因此性能也要高上许多。它没有使用一个全局锁来锁住自己，而是采用了减少锁粒度的方法，尽量减少因为竞争锁而导致的阻塞与冲突，而且ConcurrentHashMap的检索操作是不需要锁的。

3.1.1 继承Thread#

通过Thread继承类来创建并启动线程的步骤：

1. 定义Thread类的子类，重写run()方法，（run()方法里面试线程执行的任务）run()方法无返回值。
2. 创建Thread子类的实例对象
3. 调用Thread子类实例的start()方法启动线程。

1
class MyThread extends Thread{   //1
2
    @Override
3
    public void run(){
4
        //线程执行体
5
    }
6
}
7
//使用MyThread
8
Thread t = new MyThread();       //2
9
t.start();                      //3

3.1.2 实现Runnable接口#

1. 定义一个Runnable接口的实现类，重写run()方法。run()方法无返回值。
2. 创建一个Runnable接口实现类的实例对象
3. 将Runnable接口实现类的实例对象作为Target用来创建一个Thread对象
4. 调用Thread对象的start()方法启动线程。

1
class MyRunnable implements Runnable{   //1
2
    @Override
3
    public void run() {
4
        //线程执行体
5
    }
6
}
7
//使用MyRunnable
8
MyRunnable myRunnable = new MyRunable();  //2
9
Thread t = new Thread(myRunnable);       //3
10
t.start();                              //4

3.1.3 实现Callable接口#

1. 定义一个Callable接口的实现类，重写cal()方法。其中call()方法是有返回值的。
2. 创建Callable接口实现类的实例对象
3. 将Callable接口实现类的实例对象作为参数，创建一个Futuretask实例对象，FutureTask封装了call()方法的返回值。
4. 将FutureTask的实例对象作为Target用来创建一个Thread对象
5. 调用Thread对象的start()方法启动线程。
6. 调用FutureTask实例对象的get()方法获取子线程执行结束的返回值

1
class MyCallable implements Callable{     //1
2
    @Override
3
    public Object call() throws Exception {
4
        //线程执行体
5
        return 线程执行完需要返回的值;
6
    }
7
}
8
//使用MyCallable
9
MyCallable myCallable = new MyCallable()     //2
10
FutureTask futureTask = new FutureTask(myCallable);  //3
11
Thread t = new Thread(futureTask);         //4
12
t.start();                                //5
13
线程执行完返回值=futureTask.get();//6.执行get()会抛出异常InterruptedException,ExecutionException,需要使用try catch处理

3.1.4 使用线程池创建线程#

​ 从Java 5开始，Java内建支持线程池。Java 5新增了一个Executors工厂类来产生线程池，该工厂类包含如下几个静态工厂方法来创建线程池。创建出来的线程池，都是通过ThreadPoolExecutor类来实现的。

newCachedThreadPool()：创建一个具有缓存功能的线程池，系统根据需要创建线程，这些线程将会被缓存在线程池中。

newFixedThreadPool(int nThreads)：创建一个可重用的、具有固定线程数的线程池。

newSingleThreadExecutor()：创建一个只有单线程的线程池，它相当于调用newFixedThreadPool()方法时传入参数为1。

newScheduledThreadPool(int corePoolSize)：创建具有指定线程数的线程池，它可以在指定延迟后执行线程任务。corePoolSize指池中所保存的线程数，即使线程是空闲的也被保存在线程池内。

newSingleThreadScheduledExecutor()：创建只有一个线程的线程池，它可以在指定延迟后执行线程任务。

ExecutorService newWorkStealingPool(int parallelism)：创建持有足够的线程的线程池来支持给定的并行级别，该方法还会使用多个队列来减少竞争。

ExecutorService newWorkStealingPool()：该方法是前一个方法的简化版本。如果当前机器有4个CPU，则目标并行级别被设置为4，也就是相当于为前一个方法传入4作为参数。

1
//使用ThreadPoolExecutor
2
ThreadPoolExecutor threadPoolExecutor = new ThreadPoolExecutor(5,5,1L, TimeUnit.SECONDS,
3
                new LinkedBlockingQueue<Runnable>(100),//队列
4
                new ThreadPoolExecutor.CallerRunsPolicy(),//线程创建工厂
5
                new AbortPolicy();//拒绝策略
6
                );//创建一个线程池
7
for (int i = 0; i < 20; i++) {
8
    Runnable worker = new MyRunnable(""+i);
9
    threadPoolExecutor.execute(worker);
10
}
11
threadPoolExecutor.shutdown();
12
while(!threadPoolExecutor.isTerminated()){}
13
System.out.println("Finished all threads");
14

15
//使用Executors工厂类中的方法来创建线程，Executors内部其实也是调用的ThreadPoolExecutor
16
ExecutorService executorService = Executors.newFixedThreadPool(5);
17
for (int i = 0; i < 20; i++) {
18
    Runnable worker = new MyRunnable(""+i);
19
    executorService.execute(worker);
20
}
21
executorService.shutdown();

**线程池的参数：**ThreadPoolExecutor括号中的参数含义

1. corePoolSize（核心工作线程数）：当向线程池提交一个任务时，若线程池已创建的线程数小于corePoolSize，即便此时存在空闲线程，也会通过创建一个新线程来执行该任务，直到已创建的线程数大于或等于corePoolSize时。

2. maximumPoolSize（最大线程数）：线程池所允许的最大线程个数。当队列满了，且已创建的线程数小于maximumPoolSize，则线程池会创建新的线程来执行任务。另外，对于无界队列，可忽略该参数。

3. keepAliveTime（多余线程存活时间）：当线程池中线程数大于核心线程数时，线程的空闲时间如果超过线程存活时间，那么这个线程就会被销毁，直到线程池中的线程数小于等于核心线程数。

4. workQueue（队列）：用于传输和保存等待执行任务的阻塞队列。

5. threadFactory（线程创建工厂）：用于创建新线程。threadFactory创建的线程也是采用newThread()方式，threadFactory创建的线程名都具有统一的风格：pool-m-thread-n（m为线程池的编号，n为线程池内的线程编号）。

6. handler（拒绝策略）：当线程池和队列都满了，再加入线程会执行此策略。

为什么使用线程池？

​ 系统启动一个新线程的成本是比较高的，因为它涉及与操作系统交互。在这种情形下，使用线程池可以很好地提高性能，尤其是当程序中需要创建大量生存期很短暂的线程时，更应该考虑使用线程池。与数据库连接池类似的是，线程池在系统启动时即创建大量空闲的线程，程序将一个Runnable对象或Callable对象传给线程池，线程池就会启动一个空闲的线程来执行它们的run()或call()方法，当run()或call()方法执行结束后，该线程并不会死亡，而是再次返回线程池中成为空闲状态，等待执行下一个Runnable对象的run()或call()方法。

线程池的工作流程？

1. 判断核心线程池是否已满，没满则创建一个新的工作线程来执行任务。

2. 判断任务队列是否已满，没满则将新提交的任务添加在工作队列。

3. 判断整个线程池是否已满，没满则创建一个新的工作线程来执行任务，已满则执行饱和（拒绝）策略。

线程池的拒绝策略：

​ 当线程池的任务缓存队列已满并且线程池中的线程数目达到maximumPoolSize，如果还有任务到来就会采取任务拒绝策略，通常有以下四种策略：

1. AbortPolicy：丢弃任务并抛出RejectedExecutionException异常。

2. DiscardPolicy：也是丢弃任务，但是不抛出异常。

3. DiscardOldestPolicy：丢弃队列最前面的任务，然后重新尝试执行任务（重复该过程）。

4. CallerRunsPolicy：由调用线程处理该任务。

3.4.1 synchronized#

synchronized是什么？

​ synchronized 是Java的关键字，其作用是对同步的代码加锁，使得在同一时间只能有一个线程进入代码，从而达到同步的目的。synchronized 可以同步方法，也可以同步代码块。

使用synchronized 同步代码块：

​ synchronized 同步代码块的时候底层是通过monitorenter、monitorexit指令来实现的。因为每个对象都是一个monitor（监视器锁），当这个锁被占用的时候，整个对象就处于锁定状态，当一个线程执行monitorenter指令尝试去获取对象锁的时候，如果monitor的进入数为0，则该线程进入monitor，然后将进入数设置为1，该线程即为monitor的所有者。如果线程已经占有该monitor，只是重新进入，则进入monitor的进入数加1。如果其他线程已经占用了monitor，则该线程进入阻塞状态，直到monitor的进入数为0，再重新尝试获取monitor的所有权。

使用synchronized 同步方法：

​ 当方法调用时，调用指令将会检查方法的 ACC_SYNCHRONIZED 访问标志是否被设置，如果设置了，执行线程将先获取monitor，获取成功之后才能执行方法体，方法执行完后再释放monitor。在方法执行期间，其他任何线程都无法再获得同一个monitor对象。

synchronized可以修饰静态方法，但不能修饰静态代码块。

​ 当修饰静态方法时，监视器锁（monitor）便是对象的Class实例，因为Class数据存在于方法区，因此静态方法锁相当于该类的一个全局锁。

线程之间的通信：wait()、notify()、notifyAll()

​ 如果线程之间采用synchronized来保证线程安全，则可以利用wait()、notify()、notifyAll()来实现线程通信。这三个方法都不是Thread类中所声明的方法，而是Object类中声明的方法。原因是每个对象都拥有锁，所以让当前线程等待某个对象的锁，当然应该通过这个对象来操作。并且因为当前线程可能会等待多个线程的锁，如果通过线程来操作，就非常复杂了。

wait()方法可以让当前线程释放对象锁并进入阻塞状态。

notify()方法用于唤醒一个正在等待相应对象锁的线程，使其进入就绪队列，以便在当前线程释放锁后竞争锁，进而得到CPU的执行。

notifyAll()用于唤醒所有正在等待相应对象锁的线程，使它们进入就绪队列，以便在当前线程释放锁后竞争锁，进而得到CPU的执行。

1
注：每个锁对象都有两个队列，一个是就绪队列，一个是阻塞队列。就绪队列存储了已就绪（将要竞争锁）的线程，阻塞队列存储了被阻塞的线程。当一个阻塞线程被唤醒后，才会进入就绪队列，进而等待CPU的调度。反之，当一个线程被wait后，就会进入阻塞队列，等待被唤醒。

synchronized锁升级：

​ 锁的状态有四种：无锁、偏向锁、轻量级锁、重量级锁。并且四种状态会随着竞争的情况逐渐升级，而且是不可逆的过程，即不可降级，这四种锁的级别由低到高依次是：无锁、偏向锁，轻量级锁，重量级锁。如下图所示：

1. 无锁

   无锁是指没有对资源进行锁定，所有的线程都能访问并修改同一个资源，但同时只有一个线程能修改成功。无锁的特点是修改操作会在循环内进行，线程会不断的尝试修改共享资源。如果没有冲突就修改成功并退出，否则就会继续循环尝试。如果有多个线程修改同一个值，必定会有一个线程能修改成功，而其他修改失败的线程会不断重试直到修改成功。

2. 偏向锁

   初次执行到synchronized代码块的时候，锁对象变成偏向锁（通过CAS修改对象头里的锁标志位），字面意思是“偏向于第一个获得它的线程”的锁。执行完同步代码块后，线程并不会主动释放偏向锁。当第二次到达同步代码块时，线程会判断此时持有锁的线程是否就是自己（持有锁的线程ID也在对象头里），如果是则正常往下执行。由于之前没有释放锁，这里也就不需要重新加锁。如果自始至终使用锁的线程只有一个，很明显偏向锁几乎没有额外开销，性能极高。

3. 轻量级锁

   轻量级锁是指当锁是偏向锁的时候，却被另外的线程所访问，此时偏向锁就会升级为轻量级锁，其他线程会通过自旋的形式尝试获取锁，线程不会阻塞，从而提高性能。

   长时间的自旋操作是非常消耗资源的，一个线程持有锁，其他线程就只能在原地空耗CPU，执行不了任何有效的任务，这种现象叫做忙等（busy-waiting）。

4. 重量级锁

   忙等是有限度的（有个计数器记录自旋次数，默认允许循环10次，可以通过虚拟机参数更改）。如果锁竞争情况严重，某个达到最大自旋次数的线程，会将轻量级锁升级为重量级锁（依然是CAS修改锁标志位，但不修改持有锁的线程ID）。当后续线程尝试获取锁时，发现被占用的锁是重量级锁，则直接将自己挂起（而不是忙等），等待将来被唤醒。

   重量级锁是指当有一个线程获取锁之后，其余所有等待获取该锁的线程都会处于阻塞状态。

扩展：

​ synchronized 用的锁是存在Java对象头里的，那么什么是对象头呢？我们以 Hotspot 虚拟机为例进行说明，Hopspot 对象头主要包括两部分数据：Mark Word（标记字段） 和 Klass Pointer（类型指针）。

1
  - Mark Word：默认存储对象的HashCode，分代年龄和锁标志位信息。这些信息都是与对象自身定义无关的数据，所以Mark Word被设计成一个非固定的数据结构以便在极小的空间内存存储尽量多的数据。它会根据对象的状态复用自己的存储空间，也就是在运行期间Mark Word里存储的数据会随着锁标志位的变化而变化。

• Klass Point：对象指向它的类元数据的指针，虚拟机通过这个指针来确定这个对象是哪个类的实例。

1
一个对象在内存中的存储布局可以划分为三部分：对象头、实例数据、对齐填充
2
  对象头：包括MarkWord和类型指针
3
  实例数据：对象真正存储的有效信息。无论是从父类继承下来的还是子类中定义的字段都必须定义
4
  对齐填充：不是必然存在，仅是占位符。（由于HotSpot虚拟机的自动管理系统要求起始地址必须是8字节的整数倍，所以任何对象的大小都必须是8的整数倍）

​ 那么，synchronized 具体是存在对象头哪里呢？答案是：存在锁对象的对象头的Mark Word中，那么MarkWord在对象头中到底长什么样，它到底存储了什么呢？

​ 在64位的虚拟机中：

3.4.2 Lock锁#

synchronized的缺陷

​ 一个代码块被synchronized修饰了，当一个线程获取了对应的锁，并执行该代码块时，其他线程便只能一直等待，等待获取锁的线程释放锁，而这里获取锁的线程释放锁只会有两种情况：1）获取锁的线程执行完了该代码块，然后线程释放对锁的占有；2）线程执行发生异常，此时JVM会让线程自动释放锁。

缺陷情况：

​ 1. 某个已经获得锁的线程由于要等待IO或者其他原因（比如调用sleep方法）被阻塞了，但是又没有释放锁，其他想要获取锁的线程便只能一直阻塞，直到获得锁的线程释放锁了才能进入到同步代码块。

​ 2. 当有多个线程读写文件时，读操作和写操作会发生冲突现象，写操作和写操作会发生冲突现象，但是读操作和读操作不会发生冲突现象。如果多个线程都只是进行读操作，当一个线程在进行读操作时，其他线程只能等待无法进行读操作。

Lock是一个接口，里面定义了获取锁，释放锁等相关的抽象方法。

1
public interface Lock {
2
2     void lock();//用来获取锁的
3
3     void lockInterruptibly() throws InterruptedException;
4
4     boolean tryLock();
5
5     boolean tryLock(long time, TimeUnit unit) throws InterruptedException;
6
6     void unlock();
7
7     Condition newCondition();
8
8 }

1. lock()方法是用来获取锁的，是我们平时使用最多的一个方法，如果锁已被其他线程获取，则进行等待。我们之前说过了，使用lock获取锁的时候，必须手动释放锁，并且在发生异常的时候，不会自动释放锁。因此一般来说，使用Lock必须在try{}catch{}块中进行，并且将释放锁的操作放在finally块中进行，以保证锁一定被被释放，防止死锁的发生。
2. tryLock()方法是有返回值的，它表示用来尝试获取锁，如果获取成功，则返回true，如果获取失败（即锁已被其他线程获取），则返回false，也就说这个方法无论如何都会立 即返回。在拿不到锁时不会一直在那等待。
3. tryLock(long time, TimeUnit unit)方法和tryLock()方法是类似的，只不过区别在于这个方法在**拿不到锁时会等待一定的时间，**在时间期限之内如果还拿不到锁，就返回false。 如果如果一开始拿到锁或者在等待期间内拿到了锁，则返回true。
4. lockInterruptibly()方法比较特殊，当通过这个方法去获取锁时，如果线程正在等待获取锁，则这个线程能够响应中断，即中断线程的等待状态。也就使说，当两个线程同时通 过lock.lockInterruptibly()想获取某个锁时，假若此时线程A获取到了锁，而线程B只有在等待，那么对线程B调用threadB.interrupt()方法能够中断线程B的等待过程。

​ Lock只负责获取锁和释放锁，如果需要实现类似wait()/notify()这种等待/通知的机制，还需要借助Condition接口。

1
Condition接口提供了最基本的实现等待/通知机制的API，但是它比wait()/notify()更强大，这里先介绍一些它最基本的API。
2
await()：让当前线程进入WAITING状态，同时释放锁，类似wait()的作用。
3
signal()：通知某个处于WAITING状态的线程，可以继续获取锁执行。类似notify()的作用。
4
signalAll()：通知所有处于WAITING状态的线程，开始争抢锁然后执行。类似notifyAll()的作用。

​ 从ReentrantLock.newCondition()方法的实现可以看出来，其实这个Condition是每次都new出来的，所以是一个Lock可以存在多个Condition的。类似于一个说存在多个条件，各个条件管控自己的await()和signal()状态，相互之间并不影响。

ReentrantLock：可重入锁：Lock的实现类

何为可重入锁？

​ 当一个线程获得了当前实例的锁，并进入方法A，这个线程在没有释放这把锁的时候，可以再次进入方法A。

1
public class ReentrantLock implements Lock, java.io.Serializable {
2
    private static final long serialVersionUID = 7373984872572414699L;
3
    /** Synchronizer providing all implementation mechanics */
4
    private final Sync sync;
5
    abstract static class Sync extends AbstractQueuedSynchronizer {
6
        private static final long serialVersionUID = -5179523762034025860L;
7
        ....
8
    }
9
    static final class NonfairSync extends Sync {
10
        private static final long serialVersionUID = 7316153563782823691L;
11
        protected final boolean tryAcquire(int acquires) {
12
            return nonfairTryAcquire(acquires);
13
        }
14
    }
15
    static final class FairSync extends Sync {
16
        private static final long serialVersionUID = -3000897897090466540L;
17
        ...
18
    }
19
}

​ ReentrantLock 是基于 AQS 实现的， AQS 即 AbstractQueuedSynchronizer （抽象队列同步器）的缩写，这个内部提供了一个FIFO队列。该队列是一个双向链表，就是用来实现线程的并发访问控制。

​ AQS使用一个整型的volatile变量state来维护同步状态，这个volatile变量是实现ReentrantLock的关键

1
state初始化为0，表示未锁定状态.A线程lock时，会调用tryAcquire独占该锁并将state+1。此后，其他线程再tryAcquire时就会失败，直到A线程unlock到state=0（即释放锁）为止，其它线程才有机会获取该锁。当然，释放锁之前，A线程自己是可以重复获取此锁的（state会累加），这就是可重入的概念。但要注意，获取多少次就要释放多么次，这样才能保证state是能回到零态的。

AQS提供了两种功能：独占和共享

​ 独占：就是在lock.lock()之后的代码在同一时刻只能有一个线程来执行，其余的线程将会被阻塞，直到该线程执行了lock.unlock()。

​ 共享：就是读锁与读锁可以共享，读锁与写锁不可以共享（排他），写锁与写锁不可以共享（排他）

**对于ReentrantLock，有两种获取锁的模式：公平锁和非公平锁。**构造方法（不带参数 和带参数 true： 公平锁； false: 非公平锁）

​ ReentrantLock 的公平锁和非公平锁都委托了 AbstractQueuedSynchronizer#acquire 去请求获取

​ 公平锁：FairSync：公平锁的实现机理在于每次有线程来抢占锁的时候，都会检查一遍有没有等待队列，如果有，将当前线程加入到等待队列。

​ 非公平锁：NonfairSync：与公平锁的区别在于新晋获取锁的进程会有多次机会去抢占锁，被加入了等待队列后则跟公平锁没有区别。

​ 总结：从这里我们也能看出公平锁和非公平锁的区别：公平锁的新入线程不能直接获取锁，必须去排队（除非没有任何竞争发生） 。 而非公平锁新入的线程则可以先尝试获取锁，如果失败了再排队。

​ 公平锁和非公平锁在说的获取上都使用到了 volatile 关键字修饰的state字段， 这是保证多线程环境下锁的获取与否的核心。但是当并发情况下多个线程都读取到 state == 0 时，则必须用到CAS技术，一门CPU的原子锁技术，可通过CPU对共享变量加锁的形式，实现数据变更的原子操作。volatile 和 CAS的结合是并发抢占的关键。

说一说synchronized与Lock的区别

1. synchronized是Java关键字，在JVM层面实现加锁和解锁；Lock是一个接口，在代码层面实现加锁和解锁。

2. synchronized可以用在代码块上、方法上；Lock只能写在代码里。

3. synchronized在代码执行完或出现异常时自动释放锁；Lock不会自动释放锁，需要在finally中显示释放锁。

4. synchronized会导致线程拿不到锁一直等待；Lock可以设置获取锁失败的超时时间。

5. synchronized无法得知是否获取锁成功；Lock则可以通过tryLock得知加锁是否成功。

6. synchronized锁可重入、不可中断、非公平；Lock锁可重入、可中断、可公平/不公平，并可以细分读写锁以提高效率。

悲观锁与乐观锁：

​ 悲观锁：总是假设最坏的情况，每次去拿数据的时候都认为别人会修改，所以每次在拿数据的时候都会上锁，这样别人想拿这个数据就会阻塞直到它拿到锁。Java中悲观锁是通过synchronized关键字或Lock接口来实现的。

​ 乐观锁：顾名思义，就是很乐观，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判断一下在此期间别人有没有去更新这个数据。乐观锁适用于多读的应用类型，这样可以提高吞吐量。在JDK1.5 中新增 java.util.concurrent (JUC)就是建立在CAS之上的。相对于对于synchronized 这种阻塞算法，CAS是非阻塞算法的一种常见实现。所以JUC在性能上有了很大的提升。

1
CAS操作：
2
CAS,compare and swap的缩写，中文翻译成比较并交换。
3
  CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。 如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置值更新为新值 。否则，处理器不做任何操作。无论哪种情况，它都会在 CAS 指令之前返回该 位置的值。（在 CAS 的一些特殊情况下将仅返回 CAS 是否成功，而不提取当前 值。）CAS 有效地说明了“我认为位置 V 应该包含值 A；如果包含该值，则将 B 放到这个位置；否则，不要更改该位置，只告诉我这个位置现在的值即可。”
4
  通常将 CAS 用于同步的方式是从地址 V 读取值 A，执行多步计算来获得新值 B，然后使用 CAS 将 V 的值从 A 改为 B。如果 V 处的值尚未同时更改，则 CAS 操作成功。
5
  类似于 CAS 的指令允许算法执行读-修改-写操作，而无需害怕其他线程同时 修改变量，因为如果其他线程修改变量，那么 CAS 会检测它（并失败），算法 可以对该操作重新计算。