JAVA基础(未看)

Java基础知识大全

2019-11-08  本文已影响0人  伊凡的一天

1. JAVA基础

1.1 Java基本类型有哪些？它们分别占用多少字节？

Java中的基本类型包括：

关于boolean的占用大小，事实上，1 bit是计算机存储的最小单位，用它来表示boolean的语义也完全足够。但是考虑到计算机处理数据的最小单位是1byte，因此实际的存储空间至少为1byte。而在《Java虚拟机规范》一书中描述，对于当下32位的处理器（CPU）来说，一次处理数据是32位，32 位 CPU 使用 4 个字节是最为节省的，哪怕你是1 bit信息也需要占用 4 个字节。因为 CPU 寻址系统只能 32 位 32 位地寻址，具有高效存取的特点。

1.2 什么是Java装箱和拆箱？其原理？

Java中每一种基本数据类型都对应着一种包装器类型。装箱是指Java能够自动将基本数据类型自动转化成包装器类型。拆箱是指Java能够自动将包装器类型转化为基本数据类型。例如：

Integer i = 10;  //装箱
int j = i;  //拆箱

装箱是自动调用了Integer.valueOf(int i)方法。拆箱则是调用了Integer.intValue(Integer i)方法。

阅读下面一段代码：

public class Main {
    public static void main(String[] args) {
        Integer i1 = 100;
        Integer i2 = 100;
        Integer i3 = 200;
        Integer i4 = 200;
        System.out.println(i1==i2);
        System.out.println(i3==i4);
    }
}

其输出值为：

true
false

参考Integer.valueOf(int i)的实现：

public static Integer valueOf(int i) {
        if (i >= IntegerCache.low && i <= IntegerCache.high)
            return IntegerCache.cache[i + (-IntegerCache.low)];
        return new Integer(i);
    }

可以看到当i的范围在[-128, 127]时，Integer直接指向IntegerCache中的对象。否则，创建一个新的Integer对象。

而Double.valueOf(double d)的实现如下：

public static Double valueOf(double d) {
        return new Double(d);
}

因此装箱后的Double对象的比较总是返回false。

下面是Boolean.valueOf(boolean b)的实现：

public static Boolean valueOf(boolean b) {
        return (b ? TRUE : FALSE);
}

因此装箱后的Boolean对象的比较总是返回true。

1.3 String，StringBuffer和StringBuilder的区别

String类是不可变类，任何对于String对象的改变都会生成一个新的对象。StringBuffer和StringBuilder都是可变类，任何修改都会造成其内部的char数组的改变。StringBuffer是线程安全的，而StringBuilder则是线程不安全的。

1.4 Java类加载机制

1.5 LocalThread

1.6 引用类型

从JDK 1.2版本开始，把对象的引用分为4种级别，从而使程序能更加灵活地控制对象的生命周期。这4种级别由高到低依次为：强引用、软引用、弱引用和虚引用。

1.7 hashcode的设计

Java String类的hashcode方法实现如下：

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
}

关于hashcode的计算为何选取质数31，下面是一个解释：https://www.zhihu.com/question/24381016/answer/160483854

因此，一个常见的重写对象的hashcode的方法如下：

A、初始化一个整形变量，为此变量赋予一个非零的常数值，比如int result = 17;

B、选取equals方法中用于比较的所有域，然后针对每个域的属性进行计算：

C、最后，把每个域的散列码合并到对象的哈希码中。

下面是一个例子：

public class Person {
    private String name;
    private int age;
    private boolean gender;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public boolean isGender() {
        return gender;
    }

    public void setGender(boolean gender) {
        this.gender = gender;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age &&
                gender == person.gender &&
                Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        int hash = 17;
        hash = hash * 31 + getName().hashCode();
        hash = hash * 31 + getAge();
        return hash;
    }

1.8 重写和重载

重写（Override）是子类对父类的允许访问的方法的实现过程进行重新编写, 返回值和形参都不能改变。
而重载(overloading) 是指在一个类里面，方法名字相同，而参数不同。返回类型可以相同也可以不同。

1.9 Happens-Before规则

1.10 NIO

2. Java集合类

2.1 ArrayList

ArrayList本质上是一个动态数组，它是线程不安全的，读写时间为O(1)。
它的内部数据结构主要为：

//默认初始数组大小：10
private static final int DEFAULT_CAPACITY = 10;
//用于存储数据的数组
transient Object[] elementData; 
//记录size的变量
private int size;

transient表示elementData数组不参与序列化。然而在writeObject方法中，elementData数组又参与了序列化过程，这是为什么呢？因为elementData数组的length往往并不等于ArrayList.size，因此直接使用默认的序列化过程，会将elementData数组中的额外空间也序列化到输出流中。因此采用自定义writeObject方法，手动从elementData数组中取出size个元素进行序列化。具体实现如下：

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);
    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

add(E element), addAll(Collection<E> elements)方法总结：1. 首先判断是否越界，是否需要扩容。 2. 如果需要扩容，默认扩容当前大小的1.5倍。如果还不够，则直接扩容为所需要的最小size。然后复制数组。3. 修改modCount变量。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;//在数组末尾追加一个元素，并修改size
    return true;
}

private static final int DEFAULT_CAPACITY = 10;//默认扩容容量 10

private void ensureCapacityInternal(int minCapacity) {
    //利用 == 可以判断数组是否是用默认构造函数初始化的
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;//如果确定要扩容，会修改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);
    elementData = Arrays.copyOf(elementData, newCapacity);//拷贝，扩容，构建一个新数组
}

E Remove(int index)方法总结：1. 首先判断是否越界 2. 修改modCount，读出要删除的值，然后将[index + 1, size]内的所有元素复制到[index, size - 1]位置 3. 将下标为size-1的元素置为null 4. 返回被删除的元素

public E remove(int index) {
    rangeCheck(index);//判断是否越界
    modCount++;//修改modeCount 因为结构改变了
    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;
}

modCount变量用于记录List被修改的次数，因此在使用Iterator遍历时调用List.remove(E element)时会抛出java.util.ConcurrentModificationException。原因在于调用List.remove(E element)后会修改modCount变量，而Iterator遍历时会判断当前modCount值是否和expectedModCount（第一次遍历时的modCount）相同，如果不相同，则抛出java.util.ConcurrentModificationException。

增删改查中， add(E element)会导致扩容，因此会修改modCount，remove(E element)也会修改数组，因此也会修改modCount。 set(int index, E element)和get(int index)则不会修改modCount。

Vector内部也通过数组实现，它和ArrayList别在于Vector在API上都加了synchronized，所以它是线程安全的，并且Vector扩容时，是翻倍size，而ArrayList则是扩容50%。

2.2 LinkedList

LinkedList是基于双向链表实现的有序序列，它可以在任何位置进行高效的插入和删除。

它的内部数据结构如下：

// 链表长度
transient int size = 0;
// 链表头节点
transient Node<E> first;
// 链表尾节点
transient Node<E> last;

其中链表节点的数据结构如下：

private static class Node<E> {
    E item;      // 此节点包含的数据
    Node<E> next;  // 下一个节点的引用
    Node<E> prev;  // 前一个节点的引用

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

下面是boolean add(E element)方法的实现：

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;  // 获取尾部元素
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;  // 更新尾部节点为需要插入的节点
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

boolean add(E element)方法总结：1. 创建一个新节点，将last节点设置为其前节点，后节点为null 2. 如果last节点为null，将first节点设置为当前节点 3. 将当前节点设置为last节点，并将当前节点设置为原有last节点的后节点 4. 链表长度加1

下面是E get(int index)方法的实现：

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

 Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        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处于链表的前半段时，那么就从首节点开始遍历，反之则从尾节点遍历。

下面是E remove(int index)方法的实现：

public E remove(int index) {
    // 移除元素索引的合理性检查
    checkElementIndex(index);
    // 将节点删除
    return unlink(node(index));
}

 E unlink(Node<E> x) {
     final E element = x.item;  // 得到指定节点的值
     final Node<E> next = x.next; // 得到指定节点的后继节点
     final Node<E> prev = x.prev; // 得到指定节点的前继节点

     // 如果prev为null表示删除是头节点，否则就不是头节点
     if (prev == null) {
         first = next;
     } else {
         prev.next = next;
         x.prev = null; // 置空需删除的指定节点的前置节点（null）
     }

     // 如果next为null,则表示删除的是尾部节点，否则就不是尾部节点
     if (next == null) {
         last = prev;
     } else {
         next.prev = prev;
         x.next = null; //  置空需删除的指定节点的后置节点
     }

     // 置空需删除的指定节点的值
     x.item = null;
     size--; // 数量减1
     modCount++;
     return element;
}

LinkedList与ArrayList在性能上各有优缺点，都有各自适用的地方，总结如下：

2.3 HashMap

HashMap是一种底层为数组的哈希表实现。它是线程不安全的，允许key为null，value为null，遍历时无序。
它的内部数据结构如下：

transient Node<K,V>[] table;  //哈希桶，存放链表。初始大小为16

transient int size;     // HashMap中实际存在的Node数量

final float loadFactor;  //加载因子，用于计算哈希表元素数量的阈值。默认值为0.75。 

int threshold;  //哈希表内元素数量的阈值，当元素数量超过阈值时，会触发扩容。threshold = 哈希桶.length * loadFactor

threshold是HashMap在此Load factor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。

下面是哈希表数据类的定义，它的本质是一个单向链表：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;    //用来定位数组索引位置
    final K key;
    V value;
    Node<K,V> next;   //链表的下一个node
}

HashMap确定某个key所在哈希桶的位置方法如下：

//计算key的hash值
static final int hash(Object key) {
     int h;
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//根据hash值确定哈希桶位置
static int indexFor(int h, int length) {
     return h & (length-1);  
}

这里的Hash算法本质上就是三步：
(1) 取key的hashCode值：h = key.hashCode()
(2) 高位参与运算：h ^ (h >>> 16)
(3) 取模运算获得数组下标：h & (length-1)

首先我们先看HashMap如何根据一个hash值定位数组下标，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

而为什么不直接让key.hashCode()作为hash值呢？因为计算h & (table.length -1)时，由于length为2的n次方，因此table.length -1高位全部为0，以16为例，这样计算出来的index完全只保留hash值的低4位，所有hash的高位部分都丢失了。因此通过计算(h = key.hashCode()) ^ (h >>> 16)，将自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性，从而尽可能的减少碰撞。这也被称为扰动函数。

更多关于hash函数的解释，请参考：https://www.zhihu.com/question/20733617

关于put函数的流程图如下：


put(K key, V value)函数流程图

扩容机制：
HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，然后对所有的元素进行rehash。

一个最简单的rehash思路是遍历所有的元素，一个一个重新计算hash值和数组下标，然后进行分配。然而Java8对rehash进行了优化。请看下面一个例子：Hash桶初始大小为4，现在有两个hash值为1和5的元素，它们都被分配到了table[1]中。计算下标的过程如下：

1：（0000 0001）&（0000 0011）= 1  
5：（0000 0101）&（0000 0011）= 1

现在HashMap进行resize，那么哈希桶的大小变成了8，那么它们计算下标的过程如下：

1：（0000 0001）&（0000 0111）= 1  
5：（0000 0101）&（0000 0111）= 5

我们可以看到，事实上由于HashMap进行resize，是原有size * 2，因此元素下标位置只可能产生两种变化，即元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置（即加上原有桶大小）。

因此，可以产生如下伪代码：

if (hash & oldCapacity == 0) {
    //下标不变
} else {
   //下标 = 原有下标 + oldCapacity
}

更多关于resize的内容，请参考：https://blog.csdn.net/login_sonata/article/details/76598675

2.4 LinkedHashMap

LinkedHashMap是HashMap的子类，它在HashMap的基础上维护了一个双向队列，因此能够按照顺序遍历Map。它的内部数据结构如下：

public class LinkedHashMap<K, V> extends HashMap<K, V> {
    //链表头节点
    transient LinkedHashMap.Entry<K,V> head;
    //链表尾节点
    transient LinkedHashMap.Entry<K,V> tail;
    //遍历顺序，false表示按照插入顺序，true表示按照最近最少使用顺序
    final boolean accessOrder;
}

下面是LinkedHashMap节点的数据结构：

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;  //前继节点和后继节点
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

可以看到LinkedHashMap节点本质上是一个双向链表。
LinkedHashMap在HashMap的基础上重写了其钩子方法，其中主要的钩子方法如下：

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
      return null;
    //在取值后对参数accessOrder进行判断，如果为true，执行afterNodeAccess
    if (accessOrder)
      afterNodeAccess(e);
    return e.value;
}

afterNodeAccess(Node<K,V> p)方法用于将当前节点移动到双向队列尾部，因此accessOrder = true时，通过afterNodeAccess(Node<K,V> p)方法，就实现了LRU cache。

afterNodeRemoval(Node<K,V> e)则是由remove方法调用的，它主要用于更新LinkedHashMap内部维护的双向队列。

afterNodeInsertion(boolean evict)方法则是由put方法调用的，它的实现如下：

void afterNodeInsertion(boolean evict) {
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
       K key = first.key;
      removeNode(hash(key), key, null, false, true);
    }
}

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

我们可以看到，afterNodeInsertion(boolean evict)方法用于删除队首元素。默认情况下removeEldestEntry(Map.Entry<K,V> eldest)方法返回false，因此afterNodeInsertion(boolean evict)方法不会删除任何元素。

我们可以通过重写removeEldestEntry(Map.Entry<K,V> eldest)方法来实现一个LRU Cache：

class LRUCache extends LinkedHashMap<Integer, Integer> {
    
    private int capacity;

    public LRUCache(int capacity) {
        super(capacity, 1, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        if (containsKey(key)) {
            return get(key);
        }
        return -1;
    }

    public void put(int key, int value) {
        put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > capacity;
    }
}

这样，每当这个数据量超出这个LRU Cache的capacity时，LinkedHashMap会删除队首元素。由于super(capacity, 1, true)将accessOrder设置为了true，因此队首元素就是最近最少用元素，从而实现了一个简易的LRU Cache。

2.5 TreeMap

TreeMap是基于红黑树实现的key-value集合，它的元素是有有序的。
它的内部数据结构如下：

// 比较器对象
private final Comparator<? super K> comparator;
// 根节点
private transient Entry<K,V> root;
// 集合大小
private transient int size = 0;
// 树结构被修改的次数
private transient int modCount = 0;
// 静态内部类用来表示节点类型
static final class Entry<K,V> implements Map.Entry<K,V> {
    K key; 
    V value;
    Entry<K,V> left;  // 指向左子树的引用（指针）
    Entry<K,V> right;  // 指向右子树的引用（指针）
    Entry<K,V> parent;  // 指向父节点的引用（指针）
    boolean color = BLACK;  // 红黑flag
}

2.6 ConcurrentHashMap

ConcurrentHashMap是线程安全的HashMap，在Java 1.7中使用Segment分段锁实现。下面是ConcurrentHashMap在Java 1.7中的数据结构：


public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
        implements ConcurrentMap<K, V>, Serializable {
 
    // 将整个hashmap分成几个小的map，每个segment都是一个锁；与hashtable相比，这么设计的目的是对于put, remove等操作，可以减少并发冲突，对
    // 不属于同一个片段的节点可以并发操作，大大提高了性能
    final Segment<K,V>[] segments;
 
    // 本质上Segment类就是一个小的hashmap，里面table数组存储了各个节点的数据，继承了ReentrantLock, 可以作为互拆锁使用
    static final class Segment<K,V> extends ReentrantLock implements Serializable {
        transient volatile HashEntry<K,V>[] table;
        transient int count;
    }
 
    // 基本节点，存储Key， Value值
    static final class HashEntry<K,V> {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry<K,V> next;
    }
}

Java 1.7中，ConcurrentHashMap将数据分段存储，一个ConcurrentHashMap由多个Segment组成，每个Segment都有把锁，同时一个Segment下包含许多Node。一个Segment本质上就是一个继承了ReentrantLock的小的HashMap，因此锁粒度是以Segment为单位的，即以Hash桶的每个位置为单位进行锁操作。这样处于不同Hash段的元素可以并发操作。与HashTable相比，大大提高了性能。

在Java 1.8中，使用CAS操作对ConcurrentHashMap的实现进行了优化。其主要数据结构如下：

transient volatile Node<K,V>[] table;  //存储Node
private transient volatile Node<K,V>[] nextTable;  //扩容时存放数据，大小为table的2倍
private transient volatile int sizeCtl;  //控制标志，具有多种用途

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
}

sizeCtl变量是一个用于同步多个线程的共享变量。当sizeCtl < 0时，表明当前HashMap正在被初始化（-1表示正在初始化）或者正在扩容中（-N表示有N-1个线程正在参与扩容）。如果为正数，则代表了需要扩容时的阀值（即capcity * 0.75）。

下面时HashMap初始化的源码：

private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
            if ((sc = sizeCtl) < 0)
                Thread.yield(); // lost initialization race; just spin
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    if ((tab = table) == null || tab.length == 0) {
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = tab = nt;
                        sc = n - (n >>> 2);
                    }
                } finally {
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
}

我们可以看到，ConcurrentHashMap通过CAS支持了多个线程同步操作，初始化步骤如下：
1. 如果当前table为null或table.length==0，开始进行初始化。
2. 读取sizeCtl变量，如果小于0，则表明此HashMap正在进行初始化，此时调用Thread.yield()方法让出时间片。
3. 如果sizeCtl变量不小于0，那么通过CAS操作将sizeCtl置为-1，CAS操作成功后，对table数组进行初始化，并将sizeCtl设置为Capcity * 0.75，即下次扩容触发的阀值。
4. 此时其他希望进行初始化的线程读取到table不为null了，即初始化完毕。

put方法主要流程如下：
1. 首先通过(n - 1) & hash获得下标位置，如果该位置为空，则使用CAS操作直接插入。
2. 如果该位置不为空，且该位置节点的hash值为-1，则代表该链表正在处于扩容阶段，此时放弃插入，直接调用helpTransfer(Node<K,V>[] tab, Node<K,V> f)方法帮助扩容。
3. 否则，对该位置节点加锁（Synchronized），执行add操作。
4. 如果链表长度超过8个，则调用treeifyBin(Node<K,V>[] tab, int index)方法将链表转化为红黑树。

扩容时ConcurrentHashMap会将一个ForwardingNode（hash值为-1）放置在原Node位置。这个ForwardingNode存储了Node<K,V>[] nextTable的引用。

treeifyBin方法并不一定会将链表转化为红黑树。如果当前table.length < 64(MIN_TREEIFY_CAPACITY)，此时调用tryPresize(n << 1)方法，对table进行扩容。如果table.length >= 64，此时才会进行红黑树转化操作。

在tryPresize(int size)方法中，并没有加锁，允许多个线程进入，如果数组正在扩张，则当前线程也去帮助其扩容。扩容的核心逻辑位于transfer(Node<K,V>[] tab, Node<K,V>[] nextTab)方法中。

默认情况下，每个线程处理 16 个桶。因此，如果table长度是 16 的时候，扩容的时候只会有一个线程扩容。如果table长度是 64 ，每个线程可以分到 16 个桶，各自处理，不会互相影响。


concurrenthashmap.jpg

下面时get方法的主要代码：

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;
        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) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
}

get方法主要流程如下：
1. 首先计算出记录的key的hashCode，然后通过(n - 1) & hash获得下标位置，如果该位置为null，则直接返回。
2. 如果该位置不为null，并且key与我们先要查找的key相等，则直接返回该位置节点的值。
3. 如果该节点的是TreeNode，则说明该位置上是一颗红黑树，则调用红黑树搜索逻辑返回节点值。
4. 否则说明该节点是一个链表，遍历链表，找到要查找的key对应节点，返回该节点的值。

计算Map大小的size方法实现如下：

public int size() {
        long n = sumCount();
        return ((n < 0L) ? 0 :
                (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                (int)n);
    }

我们看到，size()方法调用了sumCount()方法返回Map的大小。下面是sumCount()方法的实现：

   long sumCount() {
        CounterCell[] as = counterCells; CounterCell a;
        long sum = baseCount;
        if (as != null) {
            for (int i = 0; i < as.length; ++i) {
                if ((a = as[i]) != null)
                    sum += a.value;
            }
        }
        return sum;
    }

   static final class CounterCell {
        volatile long value;
        CounterCell(long x) { value = x; }
    }

首先ConcurrentHashMap中维护了一个baseCount变量用于记录size，每一次put新的元素时，ConcurrentHashMap都会通过addCount()方法CAS更新baseCount变量。然而在高并发情况下，很有可能出现put成功，而CAS更新baseCount失败，那么这些节点虽然已经被添加到哈希表中了，但是数量却没有被统计。

因此，addCount()方法在更新 baseCount失败的时候，会调用fullAddCount()方法将这些失败的结点包装成一个CounterCell对象，并保存在private transient volatile CounterCell[] counterCells; 数组中。那么整张表实际的 size 其实是baseCount加上CounterCell数组中元素的值之和。

更过关于ConcurrentHashMap的源码分析，请参考：

3. Java并发编程

3.1 Java对象头

Java对象头由8字节组成（数组对象则有12字节）。主要包含三部分：
1. Mark Word：4字节。存储hashcode或锁信息。
2. Class Metadata Address: 4字节。存储了指向对象数据类型的指针。
3. Array Length（数组对象才包含此部分）：存储数组长度。

对象头.jpg

3.2 Synchronized关键字

synchronized锁升级过程
synchronized锁升级过程

synchronized锁流程如下：
1. 检查MarkWord里面是不是自己的ThreadId ,如果是，表示当前线程是处于 “偏向锁”。
2. 如果MarkWord不是自己的ThreadId,锁升级，这时候，用CAS来执行切换，新的线程根据MarkWord里面现有的ThreadId，通知之前线程暂停，之前线程将Markword的内容置为空。
3. 两个线程都把对象的HashCode复制到自己新建的用于存储锁的记录空间，接着开始通过CAS操作，把共享对象的MarKword的内容修改为自己新建的记录空间的地址的方式竞争MarkWord。
4. 第三步中成功执行CAS的获得资源，失败的则进入自旋。
5. 自旋的线程在自旋过程中，成功获得资源(即之前获的资源的线程执行完成并释放了共享资源)，则整个状态依然处于 轻量级锁的状态，如果自旋失败。
6. 进入重量级锁的状态，这个时候，自旋的线程进行阻塞状态，等待前一个线程释放资源。

3.3 线程状态转化

Java线程状态图.JPG
Java中的线程状态主要有6种：
1. 初始(NEW)：新创建了一个线程对象，但还没有调用start()方法。
2. 运行(RUNNABLE)：Java线程中将就绪（ready）和运行中（running）两种状态笼统的称为“运行”。
线程对象调用start()方法后，该线程就处于就绪（ready）状态。此时它等待被线程调度选中，获取CPU的使用权。就绪（ready）状态的线程在获得CPU时间片后才真正变为运行中状态（running）。
3. 阻塞(BLOCKED)：表示线程由于无法获得锁而处于阻塞状态。此时所有被阻塞的线程处于一个同步队列中。
4. 等待(WAITING)：线程同样处于阻塞状态，然而此时被阻塞的线程处于等待队列中。正在运行的线程调用Object.wait()，Thread.join()方法后，线程就会处于等待状态。
5. 超时等待(TIMED_WAITING)：可以在指定的时间后自行返回的等待状态。
6. 终止(TERMINATED)：表示该线程已经执行完毕。

Java中常用线程状态转换API的区别：
1. Thread.sleep(long millis)：当前线程进入TIMED_WAITING状态，但不释放对象锁，millis后线程自动苏醒进入就绪状态。
2. Thread.yield()：当前线程让出CPU时间片，但不释放锁资源，由运行状态变为就绪状态，此时由OS来分配此线程让出的时间片（可能依旧分配给此线程）。
3. thread.join()/thread.join(long millis)：当前线程里调用其它线程t的join方法，当前线程进入WAITING/TIMED_WAITING状态，当前线程不会释放已经持有的对象锁。线程t执行完毕或者millis时间到，当前线程一般情况下进入RUNNABLE状态，也有可能进入BLOCKED状态（因为join是基于wait实现的）。
4. object.wait()：当前线程调用对象的wait()方法，当前线程释放对象锁，进入等待队列。依靠notify()/notifyAll()唤醒或者wait(long timeout) timeout时间到自动唤醒。
5. LockSupport.park()/LockSupport.parkNanos(long nanos),LockSupport.parkUntil(long deadlines),：当前线程进入WAITING/TIMED_WAITING状态。对比wait方法,不需要获得锁就可以让线程进入WAITING/TIMED_WAITING状态，需要通过LockSupport.unpark(Thread thread)唤醒。

3.4 Lock

Java中的Lock接口提供了与synchronized关键字类似的功能，只是在使用时需要显示的获取和释放锁。下面是Lock接口的主要方法：

public interface Lock {
    void lock();  //获取锁
    void lockInterruptibly() throws InterruptedException;  //可中断的获取锁；此方法会被Thread.interrupt()方法中断
    boolean tryLock();  //非阻塞的获取锁；此方法会立刻返回，true表示成功获取了锁
    boolean tryLock(long time, TimeUnit unit) throws InterruptedException;  //在指定时间内获取锁
    void unlock();  //释放锁
    Condition newCondition();  //构造与Lock关联的condition，用于实现等待唤醒

虽然Lock接口缺少了（synchronized块或方法所提供的）隐式获取和释放锁的便捷性，但是却拥有了锁获取与释放的可操作性，可中断的获取锁以及超时获取锁等synchronized关键字所不具备的同步特性。

常用的Lock接口实现类包括ReentrantLock（可重入锁），ReentrantReadWriteLock.ReadLock和ReentrantReadWriteLock.WriteLock。

3.5 AbstractQueuedSynchronizer

队列同步器AbstractQueuedSynchronizer，使用来构建锁或者其他同步组件的基础框架。Java中Lock的实现类都是通过聚合一个重写的AbstractQueuedSynchronizer来实现的。

AbstractQueuedSynchronizer中常用的可重写的方法如下：

protected boolean tryAcquire(int arg)：独占式的获取同步状态。实现该方法需要判断同步状态是否符合预期，然后进行CAS设置同步状态。

protected boolean tryRelease(int arg)：独占式释放同步状态。等待获取同步状态的线程将有机会获取同步状态。

protected boolean tryAcquireShared(int arg)：共享式获取同步状态。返回大于0的值，表示获取成功，反之，获取失败。

protected boolean tryReleaseShared(int arg)：共享式释放同步状态

protected boolean isHeldExclusively()：是否被当前线程独占

同步器提供的方法主要分为3类：独占式获取和释放同步状态，共享式获取和释放同步状态，查询同步队列中的等待线程情况。通过重写这些方法，就能实现一个同步组件。下面是ReentrantLock的实现：

public class ReentrantLock implements Lock {
    private final Sync sync;

    abstract static class Sync extends AbstractQueuedSynchronizer {

        abstract void lock();

        final boolean nonfairTryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                if (compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
                int nextc = c + acquires;
                if (nextc < 0) // overflow
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }

        protected final boolean tryRelease(int releases) {
            int c = getState() - releases;
            if (Thread.currentThread() != getExclusiveOwnerThread())
                throw new IllegalMonitorStateException();
            boolean free = false;
            if (c == 0) {
                free = true;
                setExclusiveOwnerThread(null);
            }
            setState(c);
            return free;
        }

        //omit...
   }    

    static final class NonfairSync extends Sync {
        private static final long serialVersionUID = 7316153563782823691L;

        /**
         * Performs lock.  Try immediate barge, backing up to normal
         * acquire on failure.
         */
        final void lock() {
            if (compareAndSetState(0, 1))
                setExclusiveOwnerThread(Thread.currentThread());
            else
                acquire(1);
        }

        protected final boolean tryAcquire(int acquires) {
            return nonfairTryAcquire(acquires);
        }
    }

     public ReentrantLock() {
        sync = new NonfairSync();
    }

    public ReentrantLock(boolean fair) {
        sync = fair ? new FairSync() : new NonfairSync();
    }

    public void lock() {
        sync.lock();
    }

    public void lockInterruptibly() throws InterruptedException {
        sync.acquireInterruptibly(1);
    }

    public boolean tryLock() {
        return sync.nonfairTryAcquire(1);
    }

    //omit...
}

ReentrantLock内部通过NonfairSync，FairSync重写了AbstractQueuedSynchronizer，从而实现了公平可重入锁和非公平可重入锁。

重入锁（ReentrantLock），就是支持重进入的锁，它表示该锁能够支持一个线程对资源的重复加锁。除此之外，该锁还支持获取锁时的公平和非公平性选择。如果在绝对时间上，先对锁进行请求的锁先被满足，那么这个锁就是公平的，反之，就是不公平的。公平的获取锁，也就是等待时间最长的线程最优先获得锁，也可以说锁的获取是顺序的。事实上，公平锁往往没有非公平锁的效率高（公平锁造成大量的线程切换开销），但是公平锁能够减少“饥饿”发生的概率。非公平锁虽然可能造成线程饥饿，但极少的线程切换，保证了其更大的吞吐量。

下面是AbstractQueuedSynchronizer内部的主要数据结构：

public abstract class AbstractQueuedSynchronizer extends AbstractOwnableSynchronizer {

    private transient volatile Node head;

    private transient volatile Node tail;

    private volatile int state;
    
    //omit...

    static final class Node {
        volatile Node prev;
        volatile Node next;
        volatile int waitStatus;
        volatile Thread thread;
        //omit...
    }

    protected final boolean compareAndSetState(int expect, int update) {
        return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
    }

    //独占式获取锁
    public final void acquire(int arg) {
        if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
    }
    
    //独占式释放锁
    public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head;
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h);
            return true;
         }
        return false;
    }

    //共享式获取锁
    public final void acquireShared(int arg) {
        if (tryAcquireShared(arg) < 0)
            doAcquireShared(arg);  // 执行获取锁失败的逻辑
    }

    //共享式释放锁
    public final boolean releaseShared(int arg) {
        if (tryReleaseShared(arg)) {
            doReleaseShared();  // 执行释放锁
            return true;
        }
        return false;
    }

    //独占式获取锁方法，应通过子类重写
    protected boolean tryAcquire(int arg) {
        throw new UnsupportedOperationException();
    }
    //独占式释放锁方法，应通过子类重写
    protected boolean tryRelease(int arg) {
        throw new UnsupportedOperationException();
    }
    //共享式获取锁方法，应通过子类重写
    protected int tryAcquireShared(int arg) {
        throw new UnsupportedOperationException();
    }
    //共享式释放锁方法，应通过子类重写
    protected boolean tryReleaseShared(int arg) {
        throw new UnsupportedOperationException();
    }
 }

AbstractQueuedSynchronizer的主要数据结构有：
1. volatile变量state，来进行多个线程间的数据共享，客户端通过boolean compareAndSetState(int expect, int update)来控制boolean tryAcquire(int arg)，tryAcquireShared(int arg)等行为。
2. 内部维护了一个等待队列，通过volatile Node head和volatile Node tail头尾指针来访问。

AbstractQueuedSynchronizer还提供了一些模板方法和抽象方法，来屏蔽底层的线程排队和唤醒等待等操作。用户仅仅需要重写boolean tryAcquire(int arg)，boolean tryRelease(int arg)或tryAcquireShared(int arg)，boolean tryReleaseShared(int arg)就可以实现一个排他锁或共享锁。

下面是独占锁获取方法void acquire(int arg)的主要实现：

1. 通过 tryAcquire(int arg) 方法尝试获取锁，这个方法需要实现类进行实现。返回值为true则方法直接结束，返回值为false则执行后面加入等待队列的逻辑。
**

  1. 如果tryAcquire(int arg) 方法返回false，则执行 addWaiter(Node.EXCLUSIVE) 方法将当前线程封装成一个 Node 节点对象，并加入队列尾部。**
    3. 把当前线程执行封装成 Node 节点后，继续执行 acquireQueued 的逻辑。acquireQueued方法判断该节点的前置节点是否为head，如果是head，则重新调用 tryAcquire(int arg) 方法尝试获取锁。如果前置节点不为head或者它尝试获取锁失败，则通过LockSupport.park(this)方法阻塞当前线程，从而实现线程等待。

如果当前节点的前置节点为head，那么很有可能head节点已经释放锁了。因此不直接进入等待队列，而是再调用一次tryAcquire(int arg) 尝试获取锁，获取失败再进入等待队列。

而独占锁释放方法boolean release(int arg)的逻辑就比较简单了：

1. 首先调用boolean tryRelease(int arg)方法，这个方法需要实现类进行实现。
2. 如果boolean tryRelease(int arg)方法返回true，则通过unparkSuccessor(h)开始唤醒等待队列中下一个节点。

下面是共享锁获取方法void acquireShared(int arg)的实现：

1. 通过 tryAcquire(int arg) 方法尝试获取锁，这个方法需要实现类进行实现。返回值小于0则表示获取失败，执行doAcquireShared(int arg)方法加入队列中。
2. doAcquireShared(int arg)方法首先调用addWaiter(Node.SHARED)方法将当前线程封装成一个 Node 节点对象，并加入队列尾部。然后判断判断此节点的前置节点是否为head。如果是head节点，则调用tryAcquireShared(arg)方法再次尝试获取锁，如果获取成功，则会调用 setHeadAndPropagate 方法同时唤醒后继节点，从而实现共享模式。如果获取锁失败，则通过LockSupport.park(this)方法阻塞当前线程，从而实现线程等待。

setHeadAndPropagate 方法会将当前节点设置为新的头节点，再调用doReleaseShared方法唤醒后继节点，这是共享锁与独占锁最大的区别。独占锁获取锁之后就结束了，而共享锁则则会唤醒后继节点，后继节点继续尝试获取锁。而独占锁的释放也只会唤醒后继节点，而共享锁的释放则会遍历整个Node队列，然后通过LockSupport.park(node.thread)唤醒所有等待线程，被唤醒线程再重新开始新的锁竞争。

下面是共享锁释放方法boolean releaseShared(int arg)的实现如下：

1. 首先调用boolean tryReleaseShared(int arg)方法，这个方法需要实现类进行实现。
2. 如果boolean tryReleaseShared(int arg)方法返回true，则执行doReleaseShared()方法进行队列修改和线程唤醒操作。
3. doReleaseShared()方法会从head节点开始遍历整个Node队列，通过unparkSuccessor(node)方法依次唤醒队列中的等待线程。

更多关于AQS的实现原理，请参考：http://objcoding.com/2019/05/05/aqs-exclusive-lock/

3.6 ReadWriteLock

ReentrantLock是一种排它锁，它在同一时刻都只允许一个线程进行访问。而ReadWriteLock在同一时刻可以允许多个读线程进行访问，但在写线程访问时，所有的其他读线程和写线程均被阻塞。

ReadWriteLock内部维护了一个重写的队列同步器，一个读锁和一个写锁。读锁lock()时调用同步器的tryAcquireShared()方法，写锁lock()时调用同步器tryAcquire()方法。

下面是通过ReadWriteLock实现的一个线程安全的Cache：

public final class Cache {
    private static final Map<String, Object> container = new HashMap<>();   
    private static final ReadWriteLock lock = new ReentrantReadWriteLock();
    
    public static Object get(String key) {
        lock.readLock().lock();
        try {
            return container.get(key);
        } finally {
            lock.readLock().unlock();
        }
    }
    
    public static void put(String key, Object value) {
        lock.writeLock().lock();
        try {
            container.put(key, value);
        } finally {
            lock.writeLock().unlock();
        }
    }
}

3.7 Condition

我们知道，任意一个Java对象都有一组监视器方法（wait，notify），这些方法与synchronized关键字配合，可以实现等待/通知模式。而在Lock接口中，Condition提供了类似Object的监视器方法，与Lock配合可以实现等待/通知模式。
下面是使用Condition await/signal实现的一个有界队列：

public class BoundedQueue<T> {
    private Object[] elements;
    private int addIndex;
    private int removeIndex;
    private int size;
    private Lock lock = new ReentrantLock();
    private Condition notFull = lock.newCondition();
    private Condition notEmpty = lock.newCondition();

    public void offer(T t) throws InterruptedException {
        lock.lock();
        try {
            while (size == elements.length) {
                notFull.await();
            }
            elements[addIndex] = t;
            if (++addIndex == elements.length) {
                addIndex = 0;
            }
            size++;
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
    }

    public T poll() throws InterruptedException {
        lock.lock();
        try {
            while (size == 0) {
                notEmpty.await();
            }
            Object removed = elements[removeIndex];
            if (++removeIndex == elements.length) {
                removeIndex = 0;
            }
            size--;
            notFull.signal();
            return (T) removed;
        } finally {
            lock.unlock();
        }
    }
}

Condition与Object监视器方法相比，拥有两个额外特性：
1. 支持在等待状态中不响应中断：void awaitUninterruptibly()
2. 支持等待直至将来某个时间点：boolean awaitUntil（Date deadline） throws InterruptedException

3.8 ContdownLatch

CountDownLatch允许一个或多个线程等待其他线程完成操作。

CountDownLatch主要提供了两个API：

public CountDownLatch(int count);

public void countDown();

public void await() throws InterruptedException();

CountDownLatch通过构造器传入一个count值，每次调用countDown()方法count的值就会减一。在count值不为0时，所有调用了await方法的线程都会被阻塞，直到count的值为0为止。

CountDownlatch是通过聚合一个AQS实现的，下面是它的主要实现：

public class CountDownLatch {
    /**
     * Synchronization control For CountDownLatch.
     * Uses AQS state to represent count.
     */
    private static final class Sync extends AbstractQueuedSynchronizer {
        private static final long serialVersionUID = 4982264981922014374L;

        Sync(int count) {
            setState(count);
        }

        int getCount() {
            return getState();
        }

        protected int tryAcquireShared(int acquires) {
            return (getState() == 0) ? 1 : -1;
        }

        protected boolean tryReleaseShared(int releases) {
            for (;;) {
                int c = getState();
                if (c == 0)
                    return false;
                int nextc = c-1;
                if (compareAndSetState(c, nextc))
                    return nextc == 0;
            }
        }
    }

    private final Sync sync;

    public CountDownLatch(int count) {
        if (count < 0) throw new IllegalArgumentException("count < 0");
        this.sync = new Sync(count);
    }

    public void await() throws InterruptedException {
        sync.acquireSharedInterruptibly(1);
    }
 
    public void countDown() {
        sync.releaseShared(1);
    }

    public long getCount() {
        return sync.getCount();
    }

3.9 Semaphore

Semaphore（信号量）用来控制同时访问特定资源的线程数量。它通过协调各个线程，以保证多线程合理的使用公共资源。

Semaphore主要API如下：

public Semaphore(int permits);

public void acquire() throws InterruptedException;

public void release(int permits);

Semaphore通过构造器传入一个初始许可证数量，每次通过void acquire()方法尝试访问同步资源，访问成功则计数器值减一；通过release(int permits)退出同步资源，退出成功则计数器值加一。因此通过Semaphore，我们可以控制并行访问资源的线程数量。

下面是一个使用Semaphore的例子：

public class DatabaseWriter {
    
    private static final int IO_THREAD_COUNT = 20;
    
    private static final int MAX_DB_CONNECTION_COUNT = 10;
    
    private static final ExecutorService threadPool = Executors.newFixedThreadPool(IO_THREAD_COUNT);
    
    private static final Semaphore semaphore = new Semaphore(MAX_DB_CONNECTION_COUNT);
    
    public static void main(String[] args) {
        for (int i=0; i< IO_THREAD_COUNT; i++) {
            threadPool.execute(() -> {
                try {
                    semaphore.acquire();
                    System.out.println(Thread.currentThread() + " connect to database...");
                    semaphore.release();
                } catch (Exception e) {
                    e.printStackTrace();
                }
            });
        }
        threadPool.shutdown();
    }

}

Semaphore可以用作流量控制，特别是公共资源有限的应用场景。比如有一个需求，要读取几万个文件的数据，因为都是IO密集型任务，我们可以启动及时个线程并发的读取。但是读入内存后，要存储到数据库中，而数据库连接只有10个，这时我们必须控制只有10个线程可以同时获取到数据库连接保存数据。

Semaphore底层也是通过聚合一个AQS实现的，下面是它的主要实现：

public void acquire(int permits) throws InterruptedException {
    if (permits < 0) throw new IllegalArgumentException();
    sync.acquireSharedInterruptibly(permits);
}

 public void release(int permits) {
     if (permits < 0) throw new IllegalArgumentException();
     sync.releaseShared(permits);
 }

abstract static class Sync extends AbstractQueuedSynchronizer {

     Sync(int permits) {
         setState(permits);
     }

     protected boolean tryReleaseShared(int releases) {
          for (;;) {
                int current = getState();
                int next = current + releases;
                if (next < current) // overflow
                    throw new Error("Maximum permit count exceeded");
                if (compareAndSetState(current, next))
                    return true;
            }
     }

     protected int tryAcquireShared(int acquires) {
            for (;;) {
                int available = getState();
                int remaining = available - acquires;
                if (remaining < 0 ||
                    compareAndSetState(available, remaining))
                    return remaining;
            }
      }
}

3.10 ThreadPoolExecutor

Java中的线程池是运用场景最多的并发框架，几乎所有需要异步或并发执行任务的程序都可以使用线程池。在开发过程中，合理使用线程池能够带来3个好处：

  1. 降低资源消耗。通过重复利用已创建的线程降低线程创建和销毁造成的消耗。
  2. 提高响应速度。当任务到达时，任务可以不需要等到线程创建就能立刻执行。
  3. 提高线程的可管理性。线程是稀缺资源，如果无限制的创建，不仅会消耗系统资源，还会降低系统的稳定性，使用线程池可以进行统一分配，调优和监控。

下面是线程池的构造函数定义：

public ThreadPoolExecutor(int corePoolSize,
                              int maximumPoolSize,
                              long keepAliveTime,
                              TimeUnit unit,
                              BlockingQueue<Runnable> workQueue,
                              ThreadFactory threadFactory,
                              RejectedExecutionHandler handler);

创建一个线程池的主要参数有：

通常可以使用两种API向线程池提交任务：

//用于提交不需要返回值的任务
void execute(Runnable command);
//返回Future接口，通过调用其get()方法来获取返回值，get()方法会阻塞当前线程直到任务返回。
Future<T> submit(Callable<T> task);

另外，我们可以通过void shuntdown()或者List<Runnable> shutdownNow()方法来关闭线程池。它们的原理是遍历线程池中的工作线程，然后调用interrupt方法来中断线程，所以无法响应中断的任务可能永远无法停止。

void shuntdown()方法将线程池的状态设为SHUTDOWN状态，可以达到拒绝任何新的任务的效果。但是不会对已经提交了的任务造成影响。

而List<Runnable> shutdownNow()方法在void shuntdown()方法的基础上，会尝试中断已经提交了的任务。如果任务忽略中断，那么效果和void shuntdown()方法一样。List<Runnable> shutdownNow()方法会返回线程池中所有处于等待状态的任务。

3.11 Executors

Executor框架主要由3大部分组成：

1. 任务。包括被执行的任务需要实现的接口：Runnable和Callable。
2. 任务的执行。包括任务执行机制的核心接口Executor，以及继承自Executor的ExecutorService接口。Executor框架有两个关键类实现了ExecutorService接口：ThreadPoolExecutor和ScheduledThreadPoolExecutor。
3. 异步计算的结果。包括接口Future和实现Future接口的FutureTask类。

ThreadPoolExecutor是线程池的核心实现类，用来执行被提交的任务。

ScheduledThreadPoolExecutor可以在给定的时间延迟后运行命令，或者定期执行命令。

Executors工具类可以创建3中不同类型的ThreadPoolExecutor：SingleThreadExecutor，FixedThreadPool和CachedThreadPool。

1. Executors.newFixedThreadPool(int nThreads)：创建使用固定线程数的线程池。它适用于为了满足资源管理的需求，而需要限制当前线程数量的应用场景，适合负载较重的服务器。

2. Executors.newSingleThreadExecutor()：创建使用单个线程的线程池。适用于需要保证顺序的执行各个任务，并且在任意时间点，不会有多个线程活动的应用场景。

3. Executors.newCachedThreadPool()：创建一个大小无界的线程池。适用于执行大量短期的异步执行的任务，适合负载较轻的服务器。由于使用SynchronousQueue，并且maximumPoolSize无限，keepAliveTime为60s，因此吞吐量最好。与FixedThreadPool不同，当新的任务到来，如果有线程空闲，那么空闲的线程会直接接受该任务，如果没有空闲的线程，线程池可以无限创建新的线程。

3.11.1 Executors.newFixedThreadPool(int nThreads)的实现

public static ExecutorService newFixedThreadPool(int nThreads) {
        return new ThreadPoolExecutor(nThreads, nThreads,
                                      0L, TimeUnit.MILLISECONDS,
                                      new LinkedBlockingQueue<Runnable>());
}

可以看到，FixedThreadPool 的核心线程数和最大线程数都是指定值，也就是说当线程池中的线程数超过核心线程数后，任务都会被放到阻塞队列中。

此外 keepAliveTime 为 0，也就是多余的空余线程会被立即终止（由于这里没有多余线程，这个参数也没什么意义了）。

这里选用的阻塞队列是 LinkedBlockingQueue，使用的是默认容量 Integer.MAX_VALUE，相当于没有上限。因此maximumPoolSize是一个无效参数。

下面是FixedThreadPool的任务处理流程：

1. 对于一个新的task，如果当前线程数少于核心线程数，新建新的线程执行任务。

2. 如果当前线程数等于核心线程数后，将任务加入阻塞队列。

3. 执行完任务的线程反复去队列中取任务执行。

FixedThreadPool适用于为了满足资源管理的需求，而需要限制当前线程数量的应用场景，适合负载较重的服务器。

3.11.2 Executors.newSingleThreadExecutor()的实现

public static ExecutorService newSingleThreadExecutor() {
        return new FinalizableDelegatedExecutorService
            (new ThreadPoolExecutor(1, 1,
                                    0L, TimeUnit.MILLISECONDS,
                                    new LinkedBlockingQueue<Runnable>()));
}

SingleThreadExecutor的corePoolSize和maximumPoolSize被设置为1，其他参数和FixedThreadPool相同。

SingleThreadExecutor适用于需要保证顺序的执行各个任务，并且在任意时间点，不会有多个线程活动的应用场景。

3.11.3 Executors.newCachedThreadPool()的实现

 public static ExecutorService newCachedThreadPool() {
        return new ThreadPoolExecutor(0, Integer.MAX_VALUE,
                                      60L, TimeUnit.SECONDS,
                                      new SynchronousQueue<Runnable>());
}

可以看到，CachedThreadPool 没有核心线程，非核心线程数无上限，也就是全部使用外包，但是每个外包空闲的时间只有 60 秒，超过后就会被回收。

CachedThreadPool 使用的队列是 SynchronousQueue，这个队列的作用就是传递任务，并不会保存。

因此当提交任务的速度大于处理任务的速度时，每次提交一个任务，就会创建一个线程。极端情况下会创建过多的线程，耗尽 CPU 和内存资源。

下面是CachedThreadPool的任务处理流程：

1. 对于一个新的task，由于没有核心线程数量为0，因此首先执行Synchronous.offer(Runnable task)，如果线程池中有空闲线程正在执行Synchronous.pool(timeAlive)，那么主线程执行offer操作与空闲线程执行poll操作匹配成功，任务交给空闲线程执行，execute方法执行完成。

2. 当线程池为空或者线程池中没有空闲线程时，这种情况下offer操作失败，此时线程池创建新的线程执行任务，execute方法执行完成。

3. 执行任务的线程执行完毕后，会执行Synchronous.pool(timeAlive)操作，这个poll操作会让空闲线程最多等待60秒，如果60秒内没有获得新的任务执行，那么这个空闲线程将被终止。

因此，CachedThreadPool适用于执行大量短期的异步执行的任务，适合负载较轻的服务器。

3.11.4 ScheduledThreadPoolExecutor

Executors同样可以创建两种类型的ScheduledThreadPoolExecutor：

  1. Executors.newScheduledThreadPool(int corePoolSize)
public static ScheduledExecutorService newScheduledThreadPool(int corePoolSize)

创建固定线程数量的ScheduledThreadPool。适用于需要多个后台线程执行周期性任务，同时为了满足资源管理的需求而限制后台的线程数量。

  1. Executors.newSingleThreadScheduledExecutor()
public static ScheduledExecutorService newSingleThreadScheduledExecutor()

适用于需要单个后台线程执行周期性任务，同时需要保证顺序的执行各个任务的场景。

ScheduledThreadPoolExecutor的执行主要分为两步：

1. 调用ScheduledThreadPoolExecutor的scheduleAtFixedRate()方法或者scheduleWithFixedDelay()方法，会向ScheduledThreadPoolExecutor的DelayQueue（无界阻塞队列）添加一个ScheduledFutureTask。

2. 线程池从DelayQueue中获取ScheduledFutureTask，然后执行任务。

ScheduledFutureTask主要包含三个关键变量：

DelayQueue封装了一个PriorityQueue，这个PriorityQueue会对队列中的ScheduledFutureTask排序，time小的排在前面。

下面是ScheduledThreadPoolExecutor的某个线程执行周期性任务的步骤：

1. 线程从DelayQueue中获取已到期的ScheduledFutureTask，并执行。

2. 执行完毕后线程修改这个task的time为下次要执行的时间。

3. 把修改后的task放回DelayQueue中。

下面是ScheduledThreadPoolExecutor的某个线程从DelayQueue中获取 ScheduledFutureTask的过程：

1. 获取Lock。

2. 如果PriorityQueue为空，则当前线程到Condition中等待。

3. 如果PriorityQueue的头元素的time比当前时间大，则在Condition中等待到time时间点。

4. 获取PriorityQueue的头元素，如果PriorityQueue不为空，则唤醒在Condition中等待的所有线程。

5. 释放Lock。

下面是ScheduledThreadPoolExecutor向DelayQueue中添加 ScheduledFutureTask的过程：

1. 获取Lock。

2. 向PriorityQueue中添加任务。

3. 如果添加的任务是头元素，唤醒所有等待在Condition中的线程。

4. 释放Lock。

3.12 常见问题

4.Java虚拟机

4.1 JVM内存模型

运行时数据区.jpg

Java虚拟机运行时数据区包括：

[图片上传中...(常量池.png-fa20ce-1563929526139-0)]

字面量是指字符串或者数值。例如int a = 8; String s = "hello"; 这里的8和"hello"都是字面量。而符号引用是用于无歧义的定位到一个目标的。例如org.simple.People类引用了org.simple.Language类，在编译时People类并不知道Language类的实际内存地址，因此只能使用符号org.simple.Language来表示Language类的地址。在程序运行时，JVM会去运行时常量池中查找这个符号引用并将其替换为直接引用（实际存储在内存中的地址）。

4.2 垃圾回收算法

JVM在清理堆内存时，首先要判断是否应该回收该对象。常见的判断算法有两种：引用计数法和可达性分析法。

在Java语言中，可作为GC Roots的对象包括下面几种：

  1. 虚拟机栈（栈帧中的本地变量表）中引用的对象。
  2. 方法区中类静态属性引用的对象。
  3. 方法区中常量引用的对象。
  4. 本地方法栈中JNI（即Native方法）引用的对象。

JVM常见的垃圾回收算法包括：标记-清除算法，复制算法和标记-整理算法。

4.2.1 标记-清除算法

标记-清除算法，顾名思义分为标记和清除两个步骤：首先标记出所有需要回收的对象，然后统一清除待回收对象。它的缺点主要有两点：

  1. 效率问题。标记和清除两个操作效率都不高。
  2. 内存碎片问题。标记清除之后会产生大量的内存碎片，空间碎片太多可能导致无法分配较大的对象，从而再次触发新一轮的垃圾收集动作。

4.2.2 复制算法

为了解决内存碎片问题，出现了复制算法。它的思想是将堆内存分为两块，每次只使用其中一块。当第一块内存空间用完，就将所有存活的对象复制到另一块上，然后把已经使用过的内存一次性清理掉。

在真实的商业虚拟机中，又将堆内存分为了新生代（占用1/3堆内存）和老年代（占用2/3堆内存）。通常在新生代上使用复制算法。由于新生代中98%的对象都是朝生夕死的，所以并不需要按照1比1的比例来划分内存空间，而是将内存划分为一块较大的Eden空间和两块较小的Survivor空间。每次使用Eden和其中一块Survivor空间。当回收时，将Eden和Survivor中还存活着的对象一次性复制到另一块Survivor中，最后清理掉使用过的Enden和Survivor空间。这意味着只有大约10%的内存会被浪费。当然，我们没有办法保证每次回收都只有不多于10%的对象存活，当Survivor空间不足时，需要依赖其他内存（这里指老年代）进行分配担保（Handle Promotion）。

分配担保：如果另一块Survivor空间没有足够空间存放上一次新生代收集下来的存活对象，这些对象将直接通过分配担保机制进入老年代。

为什么要使用两块Survivor？答案是为了减少内存碎片。假如只有一块Eden和一块Survivor，那么垃圾回收时，Eden和Survivor区各自拥有一些存活对象，在清理了Survivor区后，此时将Eden区存活对象复制到Survivor区，必然造成了内存的不连续性。

Minor GC：从新生代（Eden和Survivor）空间回收内存。Eden区域满了就会触发Minor GC。
Major GC：从老年代空间回收内存。
Full GC：清理整个堆空间包括新生代和老年代。

4.2.3 标记-整理算法

复制收集算法在对象存活率较高的情况下就要进行较多的复制操作，效率将变低。更关键的是，需要有额外的内存空间进行分配担保，所以老年代一般不选用这种算法，而是采用了标记-整理算法。

标记-整理算法：标记过程与标记-清除算法一样，但是后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向一端移动，然后直接清理掉边界以外的内存。

4.2.4 分代收集算法

分代收集算法根据对象存活周期的不同将内存划分为几块，一般是将Java堆分为新生代和老年代。在新生代中，每次垃圾收集时都有大批对象死去，只有少量存活，因此可以选用复制算法。而老年代中的对象存活率高，没有额外空间对它进行分配担保，就必须使用标记-清理或者标记-整理算法来进行垃圾收集。

4.3 CMS和G1

CMS和G1的区别如下：

1.堆(Heap)空间分配不同

  1. CMS本质上采用标记-清除算法，因此会产生大量的内存碎片。而G1则采用标记-复制算法，不会产生内存碎片。并且CMS仅仅用于老年代的垃圾回收（新生代使用ParNew回收器，采用标记-复制算法），而G1则可以完成所有内存区域的垃圾回收。

Stop the World机制，简称STW，即在执行垃圾收集算法时,Java应用程序的其他所有除了垃圾收集收集器线程之外的线程都被挂起。在垃圾回收器标记阶段，JVM会执行Stop the World操作。

CMS.PNG
[图片上传中...(G1_2.PNG-e0c368-1571715147359-0)]
G1_2.PNG ZGC.PNG

参考文章：http://huzb.me/2019/02/21/CMS-G1%E5%92%8CZGC/
参考文章：https://www.cnblogs.com/littleLord/p/5380624.html#initialMark

5. Spring

5.1 IOC源码

Spring源码分析之IOC

5.2 AOP源码

Spring源码分析之AOP

5.3 循环依赖问题

循环依赖其实就是循环引用，也就是两个或则两个以上的 bean 互相持有对方，最终形成闭环。比如 A 依赖于 B，B 又依赖于A。在 Spring 中这样的场景有很多，比如构造器参数中的循环依赖（Spring无法解决，会抛出exception），属性注入时的循环依赖。而其中，只有单例对象的属性注入循环依赖是可以被解决的。

Spring主要通过三级缓存来解决属性注入的循环依赖问题：

/** Cache of singleton objects: bean name --> bean instance */
private final Map<String, Object> singletonObjects = new ConcurrentHashMap<String, Object>(256);

/** Cache of early singleton objects: bean name --> bean instance */
private final Map<String, Object> earlySingletonObjects = new HashMap<String, Object>(16);

/** Cache of singleton factories: bean name --> ObjectFactory */
private final Map<String, ObjectFactory<?>> singletonFactories = new HashMap<String, ObjectFactory<?>>(16);

Spring 创建Bean实例的过程是：

而对于刚实例化完成却还未填充属性的Bean，Spring会将其保存在二级缓存earlySingletonObjects中，来解决循环依赖的问题。

protected Object getSingleton(String beanName, boolean allowEarlyReference) {

    // 从 singletonObjects 获取 beanA 的实例，因为还没完全创建成功，所以获取不到
    Object singletonObject = this.singletonObjects.get(beanName);

    // 判断 beanA 是否正在创建中，在第 4 步已经把 beanA 标记为正在创建
    if (singletonObject == null && isSingletonCurrentlyInCreation(beanName)) {
        synchronized (this.singletonObjects) {
            // 从 earlySingletonObjects 中获取提前曝光的 beanA，这里依旧没有
            singletonObject = this.earlySingletonObjects.get(beanName);
            if (singletonObject == null && allowEarlyReference) {
                // 从 singletonFactories 获取 beanA 的对象工厂，在第 5 步已经把 beanA 的对象工厂添加进去
                ObjectFactory<?> singletonFactory = this.singletonFactories.get(beanName);
                if (singletonFactory != null) {
                    // 通过对象工厂获取 beanA 的早期引用
                    singletonObject = singletonFactory.getObject();
                    // 将 beanA 的早期引用放入缓存 earlySingletonObjects 中
                    this.earlySingletonObjects.put(beanName, singletonObject);
                    // 将 beanA 的对象工厂从缓存 singletonFactories 中移除
                    this.singletonFactories.remove(beanName);
                }
            }
        }
    }
    // 返回 beanA 的早期引用
    return (singletonObject != NULL_OBJECT ? singletonObject : null);
}

getSingleton方法由doGetBean方法调用，doGetBean首次调用getSingleton方法会返回null，因此doGetBean方法会调用createBean方法并将该Bean对应的ObjectFactory放入三级缓存singletonFactory中。此时doGetBean方法再次调用getSingleton方法时，首先从一级缓存和二级缓存中查找对应Bean，查找不到再从三级缓存中查找，并调用三级缓存中保存的ObjectFactory.getObject方法（内部本质上是实例化Bean的过程）获得Bean，然后将获得Bean加入二级缓存，并将对应Bean从三级缓存中移除。

对于prototype作用域Bean，Spring容器无法完成依赖注入，因为“prototype”作用域的Bean，Spring容
器不进行缓存，因此无法提前暴露一个创建中的Bean。

5.3 Spring MVC执行流程

  1. 用户发送请求至前端控制器DispatcherServlet
  2. DispatcherServlet收到请求调用HandlerMapping，HadnlerMapping是一个接口，主要用于根据url找到对应的Bean，其实现类包括RequestMappingHandlerMapping（用于处理@RequestMapping注解）和BeanNameUrlHandlerMapping（通过对比url和bean的name找到对应的对象）等等。
  3. 处理器映射器根据请求url找到具体的Handler，生成处理器执行链HandlerExecutionChain(包括处理器对象和处理器拦截器)一并返回给DispatcherServlet。
  4. DispatcherServlet根据Handler获取HandlerAdapter并执行HandlerAdapter处理一系列的操作，如：参数封装，数据格式转换，数据验证等操作。常见的HandlerAdapter包括RequestMappingHandlerAdapter（和上面的RequestMappingHandlerMapping配对使用，针对@RequestMapping）和SimpleControllerHandlerAdapter等等。

SimpleControllerHandlerAdapter的主要方法ModelAndView handle(HttpServletRequest request, HttpServletResponse response, Object handler)会直接调用return ((Controller) handler).handleRequest(request, response)，因此handlerAdapter通常在handler的基础上增加了一些额外的功能，如参数封装，数据格式转换，数据验证等。

  1. 执行处理器Handler(Controller，也叫页面控制器)。
  2. Handler执行完成返回ModelAndView
  3. HandlerAdapter将Handler执行结果ModelAndView返回到DispatcherServlet
  4. DispatcherServlet将ModelAndView传给ViewReslover视图解析器
  5. ViewReslover解析后返回具体View（Handler返回的ModelAndView中不包含真正的视图，只返回一 个逻辑视图名称，ViewResolver会把该逻辑视图名称解析为真正的视图View对象）
  6. DispatcherServlet对View进行渲染视图（即将模型数据model填充至视图中）。
  7. DispatcherServlet响应用户。

6. JVM监控和故障排查

上一篇下一篇

猜你喜欢

热点阅读