JAVA

标签： java springboot

判断文件服务器中文件是否存在

String path="http://127.0.0.1/upload/cardpic/aa.jpg";    
            try {
                URL url =new URL(path);//服务器路径用URL
                HttpURLConnection urlcon = (HttpURLConnection) url.openConnection();
                 urlcon.setRequestMethod("HEAD");  //请求方法用head
                 if (urlcon.getResponseCode() == HttpURLConnection.HTTP_OK){  根据返回code值判断是否存在，也可以用404代表不存在
                     mm.setHeadimgurl(path);    
                    }else{
                        mm.setHeadimgurl("");
                    }
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }

java.net.URL 和 java.net.HttpURLConnection

Java URL处理

1. URL（Uniform Resource Locator）中文名为统一资源定位符，有时也被俗称为网页地址。表示为互联网上的资源，如网页或者FTP地址。
2. 介绍Java是如处理URL的，URL可以分为如下几个部分：

• protocol(协议)可以是 HTTP、HTTPS、FTP 和 File，port 为端口号，path为文件路径及文件名。
  URL 解析：

协议为(protocol)：http
主机为(host:port)：www.runoob.com
端口号为(port): 80 ，以上URL实例并未指定端口，因为 HTTP 协议默认的端口号为 80。
文件路径为(path)：/index.html
请求参数(query)：language=cn
定位位置(fragment)：j2se，定位到网页中 id 属性为 j2se 的 HTML 元素位置 。

前面提到了从空间角度，Java 对象要比原始数据类型开销大的。你知道对象的内存结构是什么样的吗？比如，对象头的结构。如何计算或者获取某个 Java 对象的大小?

CAS机制

• CAS是英文单词Compare and Swap的缩写，翻译过来就是比较并替换。
• CAS机制中使用了3个基本操作数：内存地址V，旧的预期值A，要修改的新值B。
• 更新一个变量的时候，只有当变量的预期值A和内存地址V当中的实际值相同时，才会将内存地址V对应的值修改为B。
• 在java中除了上面提到的Atomic系列类，以及Lock系列类夺得底层实现，甚至在JAVA1.6以上版本，synchronized转变为重量级锁之前，也会采用CAS机制。
  CAS缺点：
  1） CPU开销过大``` 在并发量比较高的情况下，如果许多线程反复尝试更新某一个变量，却又一直更新不成功，循环往复，会给CPU带来很到的压力。

  <br />2） 不能保证代码块的原子性

  CAS机制所保证的知识一个变量的原子性操作，而不能保证整个代码块的原子性。比如需要保证3个变量共同进行原子性的更新，就不得不使用synchronized了。 ```
  3） ABA问题

HashMap中的哈希碰撞问题？及解决？

HashMap的结构

1. 在jdk7中hashMap的基础结构是数组+链表，在jdk8中引入了红黑树结构，在使用时，存储数据长度小于8时使用的是数据和链表的存储形式，当数据量超过8时，HashMap会将数据已红黑树的形式存储。因为HashMap是的形式进行存储，一个key对应一个Value,而key是通过hashmap中的hash算法，使用hashcode()获得hashCode值，这样会发生一个问题会出现key的值相同的状况发生，又因hashMap存储数据是按照hashCode值将数据存到对应的bucket，即被称为哈希碰撞。

• 解决哈希碰撞通常有两种方法：链表法和开放地址法；
• 链表法(使用单向链表)：将相同hash值的对象组织成一个链表存放在hash值对应的槽位；

• 开放地址法：通过一个探测算法，当某个槽位已被占据的情况下继续查找下一个使用的槽位。

  JAVA 网络编程模型

• 阻塞I/O模型：常见的I/O模型，在读写的时候客户端会发生阻塞。其工作流程为，在用户线程发出I/O请求之后，内核会检查数据是否就绪，此时用户线程一直处于阻塞等待内存数据就绪；在内存数据就绪后，内核将数据复制到用户线程中，并返回I/O执行结果到用户线程，此时用户线程将解除阻塞状态并开始处理数据。典型的阻塞I/O例子：data=socket.read()，如果内核数据没有就绪，socket线程就会一直阻塞在read()中等待内核数据就绪。

• 非阻塞I/O模型：指用户线程发起一个I/O操作后，无需阻塞就可以得到内核返回的一个结果。如果内核返回的结果为false，表示内核数据还没有准备好，需要稍后再次发起I/O操作。一旦内核数据准备好了，并且再次收到用户请求，内核就会立刻将数据复制到用户线程中并将复制结果通知给用户线程。
• 多路复用I/O模型：是多线程并发编程用的较多的模型，Java NIO就是基于多路复用I/O模型实现的。在多路复用I/O模型中会有一个被称为selector的线程不断的询问多个socket的状况，只有在socket读写事件时，才会通知用户线程进行I/O读写操作。
  • 非阻塞I/O模型是在每个用户线程中都进行socket状态检查，而在多路复用I/O模型是在系统内核中进行socket状态检查，所以效率比非阻塞高；
  • 多路复用I/O模型通过在一个selector线程上以轮询的方式检测多个socket上是否有事件到达，并逐个处理和响应。因此在事件响应体很大时，selector线程就会成为性能瓶颈。在实践应用中最后在事件处理中不多复杂的操作，只做数据的接收和转发，将具体的业务转发给后面的业务线程处理。
• 信号驱动I/O模型：该模型是，在用户线程发起一个I/O请求操作时，系统会为该请求对应的socket注册一个信号函数，然后用户线程可以继续执行其他业务；在内核数据准备就绪后，会发一个信号到用户线程，用户线程接收到信号后会在信号函数中调用对应的I/O操作；
• 异步I/O模型：在异步线程中，用户不需要关心整个I/O操作是如何进行的，只需要发起一个请求，在接收到内核返回的信号（成功或失败），表明I/O操作已经完成。在异步I/O模型中，I/O操作的两个阶段（请求的发起、数据的读取）都是在内核中自动完成的，最终发送一个信号告知用户线程I/O操作已经完成。与信号模型的区别是，信号模型在接收到信号后还需要用户线程调用I/O函数进行实际的I/O读写操作，在异步I/O中是，在接受的信号后，用户线程已经接收到I/O操作完的数据，可以直接使用数据。异步I/O需要操作系统的支持，需要有Asynchronous I/O的JDK版本。
• Java I/O：在整个java.io包中有重要的五个类和一个接口，五个类有File、outputstream、inputstream、writer、reader，一个接口是指serializable。
• Java NIO：主要包括三大块，selector(选择器)、channel（通道）和buffer（缓冲区）。
  • selector：用于监听多个channel事件，例如连接打开和数据到达；selector能够检测多个注册通道上是否有事件发生，若有事件发生，会获取事件然后针对每个事件进行响应处理。
  • channel：即为通道，与stream流类似，但与之不同，stream流是单向的，channel是双向的，从channel中读取数据或将数据写入channel中。channel中有四个类型：FileChannel(文件流通道)、DatagramChannel（UDP）、SocketChannel（TCP client端）、ServerSocketChannel（TCP server端）
  • buffer：表示缓冲区，实际上是一个容器，是一个连续数组。channel提供从文件或网络读取数据的渠道，数据的读写必须经过buffer，常用的buffer实现类有：ByteBuffer、IntBuffer、CharBuffer、LongBuffer、DoublebBuffer、FloatBuffer、ShortBuffer；

Java NIO 与BIO的区别：

• BIO是面向流的操作，NIO是面向缓冲区的；在面向流的操作中，数据只能在一个流中连续进行读写，数据没有缓冲，因此字节流无法前后移动。在NIO中，每次都是将数据从一个channel读取到一个buffer中，再从buffer中写入到channel中，因此可以方便的在缓冲区中进行移动等操作。
• BIO的流是阻塞模式的，NIO的流是非阻塞模式的；

Java基础

1. 重载与重写的区别

重载：方法名相同，但是参数必须不同，返回类型也可修改，异常类型也可以修改
重写：类上是父子类、接口与实现类，方法名相同，且参数不可修改，返回类型也不可修改，异常可减少或删除，但不能扩展。

1. StringBuffer 和 StringBuilder

• 线程安全：StringBuffer是线程安全的（有关键字synchronized）,stringbuilder没有是使用synchroized修饰
• 缓冲区：StringBuffer的toString()方法中，每次获取toString都会使用缓存区中的toStringCache值来构造一个字符串；StringBuilder每次都需要复制一次字符数组，再造一个字符串。
• 性能：StringBuffer是线程安全的，又是所有方法都公开的且是同步的，StringBuilder是没有对方法加锁同步的，所以StringBuilder性能优先于StringBuffer。

Java集合

ArrayList与LinkedList的区别是什么？

1. 底层使用的数据结构
   • ArrayList底层使用的是Object数组，初始化时就会指向的会是一个static修饰的空数组，数组的长度一开始为0，插入第一个元素是数组长度会初始化为10，之后每次数组空间不够，进行扩容时都是原来的1.5倍。ArrayList的空间浪费主要体现在list列表的结尾会预留一定的容量空间（为了避免添加元素时，数组空间不够导致频繁申请内存），而LinkedList的空间花费则体现在，其每一个元素浪费的空间更多（存放后继指针next和前驱指针pre以及数据）
   • LinkedList底层使用的数据结构是双向链表，每个节点都保存了指向前驱节点和后继节点的指针。初始化时，不执行任何操作，添加第一个元素时，再去构造链表中的节点。
2. 是否保证线程安全

ArrayList和LinkedList都是不同步的，即都是线程不安全的。
因为ArrayList的插入元素的方法就是裸奔，直接将原数组index及后面的元素拷贝到index+1及后面的位置上，然后将index位置设置为插入的值，并发修改时保证不了数据安全性，所以也不允许并发修改，一旦检测到并发修改，会抛出ConcurrentModificationException异常；

/**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     * ArrayList的插入元素的方法
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //将原数组index之后的元素拷贝到元素组index+1后面的位置上
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

1. 插入和删除的复杂度
   • ArrayList采用数组存储，元素的物理存储地址是连续的，支持以O(1)的时间复杂度对元素的快速访问。插入和删除元素后，需要将后面的元素进行移动，所以插入和删除元素的时间复杂度受元素位置的影响。复杂度是O(1)。
   • LinkedList采用链表存储，所以不能快速随机访问。所以首尾插入，删除元素时间复杂度不受元素位置影响，都是近似O(1)（如果是插入到中间位置还需要考虑寻找插入位置的时间复杂度）。而数组为近似O(n)。
2. 继承树
   • ArrayList继承AbstractList，实现了List，RandomAccess，Cloneable，java.io.Serializable接口。
   • LinkedList继承自AbstractSequentialList，实现了List，Deque，Cloneable，java.io.Serializable接口。

AbstractSequuentList是AbstractList类的子类，实现了根据下标来访问元素的一些方法，主要是通过ListIterator便利获取特定元素。
List接口代表的是有序集合，与Set相反，List的元素是按照移动的顺序进行排列。
Cloneable接口代表类会重写父类Object的clone()方法，支持对实例对象的clone操作。
java.io.Serializable接口代表类支持序列化。
RandomAccess是一个标示性接口，代表ArrayList支持快速访问，而LinkedList不支持。
Deque接口是双端队列的意思，代表LinkedList支持两端元素插入和移动。

怎么使ArrayList，LinkedList变成线程安全的？

1. 使用SynchronizedList

SynchronizedList是一个线程安全的包装类。继承于SynchronizedCollection,SynchronizedCollection实现了Collection接口，SynchronizedList包含一个List对象，对List的访问修改方法进行了一些封装，在封装的方法中会对list使用同步锁加锁，然后再进行存取和修改操作。使用方法如下：

LinkedList<Integer> linkedList = new LinkedList<Integer>();
//调用Collections的synchronizedList方法，传入一个linkedList,会返回一个SynchronizedList实例对象
List<Integer> synchronizedList = Collections.synchronizedList(linkedList);
//调用Collections的synchronizedList方法，ArrayList，返回一个SynchronizedRandomAccessList实例对象
ArrayList<Integer> arrayList = new ArrayList<Integer>();
List<Integer> synchronizedRandomAccessList = Collections.synchronizedList(arrayList);

1. 使用CopyOnWriteArrayList

CopyOnWriteArrayList与ArrayList类似，都实现了List接口，只不过它的父类是Object，而不是AbstractList。CopyOnWriteArrayList与ArrayList不同：

• 内部持有一个ReentrantLock类型的lock锁，用于控制并发访问（在对数组进行修改的方法中，都会先获取lock，获取成功才能进行修改，修改完释放锁，保证每次只允许一个线程对数组进行修改）

    /** The lock protecting all mutators */
    final transient ReentrantLock lock = new ReentrantLock();

• 使用volatile修饰Object数组，使得变量具备内存可见性

    /** The array, accessed only via getArray/setArray. */
    //CopyOnWriteArrayList
    private transient volatile Object[] array;
    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    //ArrayList
    transient Object[] elementData; // non-private to simplify nested class access

  可以看到区别主要在于CopyOnWriteArrayList的Object是使用volatile来修饰，volatile可以使变量具备内存可见性，一个线程在工作内存中对变量进行修改后，会立即更新到物理内存，并且使得其他线程中的这个变量缓存失效，其它线程在读取时，会去物理内存中读取最新的值。（volatile修饰的是指向数组的引用变量，所以对数组添加元素，删除元素不会改变引用，只有对数组变量array重新赋值才会改变。所以为了保证内存可见性，CopyOnWriteArrayList.add()方法在添加元素时，都是复制出一个新数组，进行修改操作后，在设置到数组上）
  注意事项：Object数组都使用transient修饰，是因为transient修饰的属性不会参与序列化，ArrayList通过实现writeObject()和readObject()方法来自定义序列化方法（基于反序列化时节约空间考虑，如果用默认的序列方法，源elementData数组长度为100，实际上只有10个元素，反序列化时也会出现分配长度为100的数组，造成内存浪费）。下面是copyOpyOnWriteArrayList的add()方法

  /**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        //使用ReetrantLock，保证写线程在同时刻只有一个
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            //获取旧数组引用
            Object[] elements = getArray();
            int len = elements.length;
            if (index > len || index < 0)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+len);
            //创建新数组，并将就数组的数据复制到新数组中
            Object[] newElements;
            int numMoved = len - index;
            if (numMoved == 0)
                newElements = Arrays.copyOf(elements, len + 1);
            else {             
                newElements = new Object[len + 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index, newElements, index + 1,
                                 numMoved);
            }
            //向新数组中添加新的数组
            newElements[index] = element;
            //将旧数组引用指向新的数组
            setArray(newElements);
        } finally {
            lock.unlock();
        }
    }

1. SynchronizedList和CopyOnWriteArrayList优缺点

• SynchronizedList:读写都加锁，SynchronizedList是通过在方法上使用synchronized修饰来实现方法同步，即便只是多个线程在读数据，也不能进行，如果是读比较多的的场景下，会使性能不高，所以适合读写均匀的情况下；

• CopyOnWriteArrayList：读不加锁，写加锁，因CopyOnWriteArrayList是读写分离的，只有对写操作加锁，但是每次写操作（添加和删除元素）时都会复制出一个新的数组，完成修改后将新数组设置到旧数组的引用上，所以在写比较多的情况写，会有很大的性能开销，所以适合读比较多的应用场景。

  ArrayList遍历时删除元素有哪些方法？

  首先结论如下：

• 普通for循环正序删除（结果：会漏掉元素判断）

• 普通for循环倒序删除（结果：正确删除）
• for-each循环删除（结果：抛出异常）
• Iterator遍历，使用ArrayList.remove()删除元素（结果：抛出异常）
• Iterator遍历，使用Iterator的remove删除元素（结果：正确删除）

首先创建一个数组

public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        arrayList.add(3);
        arrayList.add(4);
        arrayList.add(5);
        removeWayOne(arrayList);
    }

1. 普通for循环正序删除（结果：会漏掉对后一个元素的判断）

   for (int i = 0; i < arrayList.size(); i++) {
    if (arrayList.get(i) == 3) {//3是要删除的元素
        arrayList.remove(i);
        //解决方案: 加一行代码i = i - 1; 删除元素后，下标减1
    }
    System.out.println("当前arrayList是"+arrayList.toString());
   }
   //原ArrayList是[1, 2, 3, 3, 4, 5]
   //删除后是[1, 2, 3, 4, 5]

   原因在于调用remove删除元素时，remove方法调用System.arraycopy()方法将后面的元素移动到前面的位置

2. 普通for循环倒序删除（结果：正确删除）

   for (int i = arrayList.size() -1 ; i>=0; i--) {
    if (arrayList.get(i).equals(3)) {
        arrayList.remove(i);
    }
    System.out.println("当前arrayList是"+arrayList.toString());
   }

   这用方法可以正确删除元素，是因为调用remove删除元素时，remove方法调用System.arraycopy()将删除的元素后面的元素向前移动，而不会影响删除元素之前的元素，所以倒序遍历可以正常删除元素。

3. for-each循环删除（结果：抛出异常）

抛出异常的根本原因在于for-each是使用Iterator来实现遍历的，调用ArrayList.remove()方法会将modCount+1，而Iterator内部的expectedModCount却没有更新，这样在下次循环时调用Iterator.next()会对modCount和expectedModCount进行比较，不一致就会抛出ConcurrentModificationException异常。

public static void removeWayThree(ArrayList<Integer> arrayList) {
    for (Integer value : arrayList) {
        if (value.equals(3)) {//3是要删除的元素
            arrayList.remove(value);
        }
    System.out.println("当前arrayList是"+arrayList.toString());
    }
}

Iterator.hasNext()来判断是否还有下一个元素和Iterator.next()方法来获取下一个元素。而因为在删除元素时，remove()方法会调用fastRemove()方法，其中会调用modCount+1，代表对数组进行修改，将修改次数+1。

/**
     * Removes the first occurrence of the specified element from this list,
     * if it is present.  If the list does not contain the element, it is
     * unchanged.  More formally, removes the element with the lowest index
     * <tt>i</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
     * (if such an element exists).  Returns <tt>true</tt> if this list
     * contained the specified element (or equivalently, if this list
     * changed as a result of the call).
     *
     * @param o element to be removed from this list, if present
     * @return <tt>true</tt> if this list contained the specified element
     */
    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;
    }
    /*
     * Private remove method that skips bounds checking and does not
     * return the value removed.
     */
    private void fastRemove(int index) {
        modCount++;
        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
    }

HashMap添加一个键值对过程？

流程图如下：

1. 初始化table

判断table是否为空或为null，否则执行resize()方法（resize方法一般是扩容时调用，也可以调用来初始化table）

1. 计算hash值

根据键值key计算hash值。（因为hashCode是一个int类型的变量，是4字节，32位，所以这里会将hashCode的低16位与高16位进行一个异或运算，来保留高位的运算，以便于得到的hash值更加均匀分布）

/**
     * Computes key.hashCode() and spreads (XORs) higher bits of hash
     * to lower.  Because the table uses power-of-two masking, sets of
     * hashes that vary only in bits above the current mask will
     * always collide. (Among known examples are sets of Float keys
     * holding consecutive whole numbers in small tables.)  So we
     * apply a transform that spreads the impact of higher bits
     * downward. There is a tradeoff between speed, utility, and
     * quality of bit-spreading. Because many common sets of hashes
     * are already reasonably distributed (so don't benefit from
     * spreading), and because we use trees to handle large sets of
     * collisions in bins, we just XOR some shifted bits in the
     * cheapest possible way to reduce systematic lossage, as well as
     * to incorporate impact of the highest bits that would otherwise
     * never be used in index calculations because of table bounds.
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

1. 插入或更新节点

根据（n-1）& hash计算得到插入的数组下标i，然后进行判断
3.1 数组为空（table[i] == null）
那么说明当前数组下标下，没有hash冲突的元素，直接新建节点添加。
3.2 等于下标首元素，table[i].hash hash && (table[i] key || (key != null && key.equals(table[i].key)))
判断table[i]的首个元素是否和key，如果相同直接更新value。
3.3 数组下标存的是红黑树，table[i] instanceof TreeNode
判断table[i]是否为treeNode，即table[i]是否是红黑树，如果是红黑树，则直接在树中插入键值对。
3.4 数组下标存的是链表
上面的判断条件都不满足，说明table[i]存储的是一个链表，那么遍历链表，判断是否存在已有元素的key与插入键值对key相等，如果是，那么更新value，如果没有，那么在链表末尾插入一个新节点。插入之后判断链表长度链表长度是否大于8，大于8的话把链表转换为红黑树。

1. 扩容

插入成功后，判断实际存在的键值对数量size是否超过了最大容量threshold（一般是数组长度*负载因子0.75），如果超过，进行扩容。
源码如下：

/**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    /**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //1.tab为空则创建
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //2.计算index，并对null做处理
        //3.插入元素
        //(n - 1) & hash 确定元素存放在哪个数组下标下
        //下标没有元素，新生成节点放入中（此时，这个节点是放在数组中）
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        //下标中已存在元素
        else {
            Node<K,V> e; K k;
            //节点key存在，直接覆盖value
            //比较桶中第一个元素（数组中的节点）的hash值相等，key相等
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //将第一个元素直接赋值给e,用e来记录
                e = p;
            //判断该链为红黑树
            //hash值不相等，即key不相等，为红黑树节点
            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;
                    }
                    //判断链表中结点的key值与插入的元素的key值是否相等
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        //相等，跳出循环
                        break;
                    //用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                    p = e;
                }
            }
            //表示在桶中找到了key值、hash值与插入元素相等的结点
            if (e != null) { // existing mapping for key
                //纪录e的value
                V oldValue = e.value;
                //onlyIfAbsent为false或者旧值为null
                if (!onlyIfAbsent || oldValue == null)
                    //用新值代替旧值
                    e.value = value;
                //访问后回调
                afterNodeAccess(e);
                //返回旧值
                return oldValue;
            }
        }
        ++modCount;
        //超过最大容量就扩容，实际大小大于阈值则扩容
        if (++size > threshold)
            resize();
        //插入后回调
        afterNodeInsertion(evict);
        return null;
    }

扩容方法：

/**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
     * Otherwise, because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move
     * with a power of two offset in the new table.
     *
     * @return the table
     */
    final Node<K,V>[] resize() {
        //记录表值
        Node<K,V>[] oldTab = table;
        //判断oldTab的空间大小
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

ConcurrentHashMap添加一个键值对的工程是怎样的？

ConcurrentHashMap的工作流程图：

1. 判断null值

判断key null 或者 value == null，如果是，抛出空指针异常。

1. 计算hash

根基key计算hash值（计算结果跟hashMap是一致的，写法不同）。

1. 进入for循环，插入或更新元素

3.1 如果tab null || tab.length == 0，说明数组未初始化
说明当前数组tab还没有初始化。
那么调用initTable()方法初始化tab。（在initTable方法中，为了控制只有一个线程对table进行初始化，当前线程会通过CAS操作对SIZECTL变量赋值为-1，如果赋值成功，线程才能初始化table，否则会调用Thread.yield()方法让出时间片。
3.2 如果f == null，说明当前下标没有哈希冲突的键值对
说明当前数组下标还没有哈希冲突的键值对。
Node f是根据key的hash值计算得到数组下标，下标存储的元素，f可能是null，也有可能是链表头节点，红黑树根节点或迁移标志节点ForwardNode，那么根据key和value创建一个Node，使用CAS操作设置在当前数组下标下，并且break出for循环。
3.3 如果 f != null && f.hash = -1,说明存储的是标志节点，表示在扩容
说明ConcurrentHashMap正在扩容，当前的节点f是一个标志节点，当前下标存储的hash冲突的元素已经迁移了。那么当前线程会调用helpTransfer()方法来辅助扩容，扩容完成后会将tab指向新的table，然后继续执行for循环。
3.4 除了上面三种以外情况，说明是下标存储链表或者是红黑树
说明f节点是一个链表的头结点或者是红黑树的根节点，那么对f加synchronize同步锁，然后进行以下判断：

  - f.hash > 0

如果是f的hash值大于0，当前数组下标存储的是一个链表，f是链表的头结点。
对链表进行遍历，如果有节点跟当前需要插入的节点的hash值相同，那么节点的value进行更新，否则根据key，value创建一个Node，添加到链表末尾

  - f instanceof TreeBin

如果f是TreeBin类型，那么说明当前数组下标存储的是一个红黑树，f是红黑树的根节点，调用putTreeVal方法，插入或更新节点。

• 插入完成后，判断binCount（数组下标存储是一个链表时，binCount是链表长度），当binCount超过8时，并且数组的长度大于64时，那么调用treeifyBin方法将链表转换为红黑树。最后break出for循环。

PS:
当原来的链表长度超过8时，确实会调用treeifyBin方法，但是在treeifyBin方法中会判断当前tab是否为空或者数组长度是否小于64，如果满足条件，那么调用resize方法对tab初始化或者扩容。就不会将链表转换为红黑树了。
treeifyBin方法源码：

/**
     * Replaces all linked nodes in bin at given index unless table is
     * too small, in which case resizes instead.
     */
    private final void treeifyBin(Node<K,V>[] tab, int index) {
        Node<K,V> b; int n, sc;
        if (tab != null) {
            if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
                tryPresize(n << 1);
            else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
                synchronized (b) {
                    if (tabAt(tab, index) == b) {
                        TreeNode<K,V> hd = null, tl = null;
                        for (Node<K,V> e = b; e != null; e = e.next) {
                            TreeNode<K,V> p =
                                new TreeNode<K,V>(e.hash, e.key, e.val,
                                                  null, null);
                            if ((p.prev = tl) == null)
                                hd = p;
                            else
                                tl.next = p;
                            tl = p;
                        }
                        setTabAt(tab, index, new TreeBin<K,V>(hd));
                    }
                }
            }
        }
    }

1. 判断是否需要扩容

调用addCount()方法对当前数组长度加一，在addCount()方法中，会判断当前元素个数是否超过sizeCtl（扩容阈值，总长度0.75），如果是，那么会进行扩容，如果正处于扩容中，当前线程会辅助扩容。
*ConcurrentHashMap源码：

/** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        //ConcurrentHashMap不允许key和value为null，否则抛出异常
        if (key == null || value == null) throw new NullPointerException();
        //计算hash值
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) { //进入循环
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0) //数组如果为空
                tab = initTable(); //初始化数组
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                //如果发现此数组下标下没有哈希冲突的元素，就直接使用CAS操作将Node设置到此下标下
                if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            } else if ((fh = f.hash) == MOVED) //代表当前下标的头结点是标识结点，代表数组在扩容
                tab = helpTransfer(tab, f); //协助扩容
            else { //这种是普通情况，存在的是链表或者红黑树，进行插入
                V oldVal = null;
                synchronized (f) { //加同步锁，避免多线程进行插入
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) { //头结点hash值大于0，此数组下标下代表存的一个链表
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) { //遍历链表
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) { //键值对是新添加的，在链表尾部插入新节点
                                    pred.next = new Node<K,V>(hash, key,value, null);
                                    break;
                                }
                            }
                        } else if (f instanceof TreeBin) { //下标下存的是红黑树
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD) //链表长度>=8,转换为红黑树
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

HashMap与HashTable，ConcurrentHashMap的区别是什么

主要从底层数据结构，线程安全，执行效率，是否允许Null值，初始容量及扩容，hash值计算来进行分析。

1. 底层数据结构

   transient Node<K,V>[] table;  //HashMap
   transient volatile Node<K,V>[] table;  //ConcurrentHashMap
   private transient Entry<?,?>[] table;  //HashTable

   HashMap = 数组+链表+红黑树
   HashMap的底层数据结构是一个数组+链表+红黑树，数组的每个元素存储是一个链表的头结点，链表中存储了一组哈希冲突的键值对，通过链地址法来解决哈希冲突的。为了避免链表长度过长，影响查找元素的效率，当链表的长度大于8时，会将链表转换为红黑树，链表的长度小于6时，将红黑树转换为链表（但是红黑树转换为链表的时机不是在删除链表时，而是在扩容时，发现红黑树分解后的两个链表小于6，就按链表处理，否则就建立两个小的红黑树，设置到扩容后的位置）。之所以临界点为8是因为红黑树的查找时间复杂度为logN，链表的平均时间查找复杂度为N/2，当N为8时，logN为3是小于N/2的，正好可以通过转换红黑树减少查找的时间复杂度。

ConcurrentHashMap = 数组+链表+红黑树
ConcurrentHashMap底层数据结构跟HashMap一致，底层数据结构是一个数组+链表+红黑树。只不过使用了volatile来进行修饰他的属性，来保证内存可见性（一个线程修改了这些属性后，会使其他线程对于该属性的缓存失效，以便下次读取时取最新的值）。
HashTable = 数组+链表
HashTable底层数据结构跟HashMap一致，底层数据结构是数组+链表，也是通过链地址法来解决冲突，只不过链表过长时，不会转为红黑树来减少查找的时间复杂度。HashTable属于历史遗留类，实际开发中很少使用。

1. 线程安全

HashMap 非线程安全
HashMap是非线程安全的。（例如多个线程插入多个键值对，如果两个键值对的key哈希冲突，可能使得两个线程在操作同一个链表中的节点，导致一个键值对的value被覆盖）
HashTable 线程安全
HashTable是线程安全的，主要通过使用synchronize关键字修饰大部分方法，使得每次只能一个线程对HashTable进行同步修改，性能开销较大。
ConcurrentHashMap 线程安全
ConcurrentHashMap 是线程安全的，主要通过CAS操作+synchronize来保证线程安全的。
CAS操作
往ConcurrentHashMap中插入新的键值对是，如果对应的数组下标元素为null，那么通过CAS操作原子性的将节点设置到数组中。

//这是添加新的键值对的方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
...其他代码
  if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
    if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))                 
        break; // 因为对应的数组下标元素为null，所以null作为预期值，new Node<K,V>(hash, key, value, null)作为即将更新的值，只有当内存中的值与即将预期值一致时，才会进行更新，保证原子性。
  }
...其他代码
}
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                        Node<K,V> c, Node<K,V> v) {
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

多线程

Java中创建线程有哪些方式

继承Thread类，重写run方法

这种方式通过自定义类继承Thread类，重写run()方法，然后在创建自定义类的对象，然后调用start()方法，JVM会创建一个新线程。并且为线程创建方法调用栈和程序计数器，此时线程处于就绪状态，当线程获取CPU时间片后，线程会进入到运行状态，回去调用run()方法。并且创建自定义类对象的线程与调用run()方法的线程之间是并发的。

class CustomThread extends Thread {
    public static void main(String[] args) {
        System.out.println(Thread.currentThread().getName()+"线程调用了main方法");
        for (int i = 0; i < 10; i++) {
            if (i == 1) {
                CustomThread customThread = new CustomThread();
                customThread.start();
                System.out.println(Thread.currentThread().getName()+"线程--i是"+i);
            }
        }
        System.out.println("main()方法执行完毕！");
    }
    void run() {
        System.out.println(Thread.currentThread().getName()+"线程调用了run()方法");
        for (int j = 0; j < 5; j++) {
            System.out.println(Thread.currentThread().getName()+"线程--j是"+j);
        }
        System.out.println("run()方法执行完毕！");
    }
}

执行原理
首先看start方法的源码，在源码中首先会判断threadStatus是否为0，如果为0会抛出异常。然后会将当前对象添加到线程组，最后调用start()方法。

/**
     * Causes this thread to begin execution; the Java Virtual Machine
     * calls the <code>run</code> method of this thread.
     * <p>
     * The result is that two threads are running concurrently: the
     * current thread (which returns from the call to the
     * <code>start</code> method) and the other thread (which executes its
     * <code>run</code> method).
     * <p>
     * It is never legal to start a thread more than once.
     * In particular, a thread may not be restarted once it has completed
     * execution.
     *
     * @exception  IllegalThreadStateException  if the thread was already
     *               started.
     * @see        #run()
     * @see        #stop()
     */
    public synchronized void start() {
        /**
         * This method is not invoked for the main method thread or "system"
         * group threads created/set up by the VM. Any new functionality added
         * to this method in the future may have to also be added to the VM.
         *
         * A zero status value corresponds to state "NEW".
         */
        if (threadStatus != 0)
            throw new IllegalThreadStateException();
        /* Notify the group that this thread is about to be started
         * so that it can be added to the group's list of threads
         * and the group's unstarted count can be decremented. */
        //将对象添加到线程组
        group.add(this);
        boolean started = false;
        try {
            start0(); //这是一个native方法，调用后JVM会新建一个线程来调用run方法
            started = true;
        } finally {
            try {
                if (!started) {
                    group.threadStartFailed(this);
                }
            } catch (Throwable ignore) {
                /* do nothing. If start0 threw a Throwable then
                  it will be passed up the call stack */
            }
        }
    }
    private native void start0();

拓展问题：多次调用Thread对象的start()方法会怎么样？
会抛出IllegalThreadStateException异常。其实在Thread#start()方法里面的注释中有提到，多次调用start()方法是非法的，所以在上面的start()方法源码中一开始就对threadStatus进行判断，不为0就会抛出IllegalThreadStateException异常。
注意：start()方法中判断threadStatus是否为0，是判断当前线程是否新建态，0是代表新建态（上图中源码注释里有提到），而不是就绪态，因为Java的Thread类中，Thread的Runnable状态包括了线程的就绪态和运行态，（Thread的state的RUNNABLE时（也就是threadStatus为4时），代表线程为就绪态或运行态）。执行start()方法的线程还不是JVM新建线程，所以不是就绪态

实现Runnable接口

这种方式就是创建一个类（target类），实现Runnable接口的Run()方法，然后将target类的实例对象作为Thread的构造器入参target，实际上的线程对象还是Thread实例，只不过线程Thread与线程执行体（target类的run方法）分离了，耦合度更低一些。

class ThreadTarget implements Runnable {
    void run() {
        System.out.println(Thread.currentThread().getName()+"线程执行了run方法");
    }
    public static void main(String[] args) {
        System.out.println(Thread.currentThread().getName()+"线程执行了main方法");
        ThreadTarget target = new ThreadTarget();
        Thread thread = new Thread(target);
        thread.start();
    }
}

原理：因为Thread类的run()方法中会判断成员变量target是否为空，不为空就会调用target类的run方法。

    /* What will be run. */
    private Runnable target;       
    /**
     * If this thread was constructed using a separate
     * <code>Runnable</code> run object, then that
     * <code>Runnable</code> object's <code>run</code> method is called;
     * otherwise, this method does nothing and returns.
     * <p>
     * Subclasses of <code>Thread</code> should override this method.
     *
     * @see     #start()
     * @see     #stop()
     * @see     #Thread(ThreadGroup, Runnable, String)
     */
    @Override
    public void run() {
        if (target != null) {
            target.run();
        }
    }

另外一种写法
匿名内部类
可以不用创建target类，可以使用匿名内部类的方式实现，因此上面的代码也可以按照一下方式写：

Thread thread = new Thread(new Runnable() {
    @Override
    public void run() {
              System.out.println(Thread.currentThread().getName()+"线程执行了run方法");
    }
});
thread.start();

lamda表达式
在Java8后使用了@FunctionalInterface注解来修饰Runnable接口，表明Runnable接口是一个函数式接口，有且只有一个抽象方法，也可以Lamda方式来创建Runnable对象，比匿名类的方式更简洁。

@FunctionalInterface
public interface Runnable {
    /**
     * When an object implementing interface <code>Runnable</code> is used
     * to create a thread, starting the thread causes the object's
     * <code>run</code> method to be called in that separately executing
     * thread.
     * <p>
     * The general contract of the method <code>run</code> is that it may
     * take any action whatsoever.
     *
     * @see     java.lang.Thread#run()
     */
    public abstract void run();
}

因此上面的的代码也可以按以下方式写：

Thread thread = new Thread(()->{
      System.out.println(Thread.currentThread().getName()+"线程执行了run方法");
})
thread.start()

总结
这种写法不用继承Thread类，但同样也有缺点，就是线程方法体（Run()方法）不能设置返回值。

实现Callable接口

Runnable接口中的run方法是没有返回值，如果需要执行的任务带返回值就不能使用Runnable接口。创建一个类CallableTarget，实现Callable接口，实现带有返回值的call()方法，然后根据CallableTarget创建一个任务FutureTask，然后根据FutureTask来创建一个线程Thread，调用Thread的start方法执行任务。

public class CallableTarget implements Callable<Integer> {
    public Integer call() throws InterruptedException {
        System.out.println(Thread.currentThread().getName()+"线程执行了call方法");
        Thread.sleep(5000);
        return 1;
    }
    public static void main(String[] args) throws ExecutionException, InterruptedException {
        System.out.println(Thread.currentThread().getName()+"线程执行了main方法");
        CallableTarget callableTarget = new CallableTarget();
        FutureTask<Integer> task = new FutureTask<Integer>(callableTarget);
        Thread thread = new Thread(task);
        thread.start();
        Integer result = task.get();//当前线程会阻塞，一直等到结果返回。
        System.out.println("执行完毕，打印result="+result);
        System.out.println("执行完毕");
    }
}

原理就是Thread类默认的run()方法实现会去调自身的实例变量target的run()方法，（target就是构造器Thread传入的FutureTask），而FutureTask的run方法中就会调用Callable接口的实例的call()方法。

//Thread类的run方法实现
    /**
     * If this thread was constructed using a separate
     * <code>Runnable</code> run object, then that
     * <code>Runnable</code> object's <code>run</code> method is called;
     * otherwise, this method does nothing and returns.
     * <p>
     * Subclasses of <code>Thread</code> should override this method.
     *
     * @see     #start()
     * @see     #stop()
     * @see     #Thread(ThreadGroup, Runnable, String)
     */
    @Override
    public void run() {
        //这里target就是在创建Thread时传入的FutureTask实例变量
        if (target != null) {
            target.run();
        }
    }
//FutureTask类的run方法实现
public void run() {
        if (state != NEW ||
            !UNSAFE.compareAndSwapObject(this, runnerOffset,
                                         null, Thread.currentThread()))
            return;
        try {
            Callable<V> c = callable;
            if (c != null && state == NEW) {
                V result;
                boolean ran;
                try {
                    //这里调用Callable实例的call方法
                    result = c.call();
                    ran = true;
                } catch (Throwable ex) {
                    result = null;
                    ran = false;
                    setException(ex);
                }
                if (ran)
                    set(result);
            }
        } finally {
            // runner must be non-null until state is settled to
            // prevent concurrent calls to run()
            runner = null;
            // state must be re-read after nulling runner to prevent
            // leaked interrupts
            int s = state;
            if (s >= INTERRUPTING)
                handlePossibleCancellationInterrupt(s);
        }
    }

Java中Runnable、Callable、Future、FutureTask的区别和联系？

最原始的通过新建线程执行任务的方法就是我们创建一个新类，继承Thread，然后重写run方法，因为限制太大了，Java不支持多继承，所以有了Runnable接口。

Runnable

Runnable接口，只需要新建一个类实现这个接口，然后重写run方法，将该类的实例作为参数创建Thread。线程运行时调用该类的run方法。
Thread.start()方法->Thread.run()方法->target.run()方法

Callable

Callable是跟Runnable类似，也是一个接口。只不过它的call方法有返回值，可以供程序接受任务执行的结果。

@FunctionalInterface
public interface Callable<V> {
    /**
     * Computes a result, or throws an exception if unable to do so.
     *
     * @return computed result
     * @throws Exception if unable to compute a result
     */
    V call() throws Exception;
}

Future

Future也是一个接口，Future就像是一个管理容器一样，进一步对Runnable和Callable的实例进行封装，提供了取消任务的cancel()方法，查询任务是否完成的isDone()方法，获取执行结果的get方法，带有超时时间来获取执行结果的get()方法。

public interface Future<V> {
    /**
     * Attempts to cancel execution of this task.  This attempt will
     * fail if the task has already completed, has already been cancelled,
     * or could not be cancelled for some other reason. If successful,
     * and this task has not started when {@code cancel} is called,
     * this task should never run.  If the task has already started,
     * then the {@code mayInterruptIfRunning} parameter determines
     * whether the thread executing this task should be interrupted in
     * an attempt to stop the task.
     *
     * <p>After this method returns, subsequent calls to {@link #isDone} will
     * always return {@code true}.  Subsequent calls to {@link #isCancelled}
     * will always return {@code true} if this method returned {@code true}.
     *
     * @param mayInterruptIfRunning {@code true} if the thread executing this
     * task should be interrupted; otherwise, in-progress tasks are allowed
     * to complete
     * @return {@code false} if the task could not be cancelled,
     * typically because it has already completed normally;
     * {@code true} otherwise
     */
    boolean cancel(boolean mayInterruptIfRunning);
    /**
     * Returns {@code true} if this task was cancelled before it completed
     * normally.
     *
     * @return {@code true} if this task was cancelled before it completed
     */
    boolean isCancelled();
    /**
     * Returns {@code true} if this task completed.
     *
     * Completion may be due to normal termination, an exception, or
     * cancellation -- in all of these cases, this method will return
     * {@code true}.
     *
     * @return {@code true} if this task completed
     */
    boolean isDone();
    /**
     * Waits if necessary for the computation to complete, and then
     * retrieves its result.
     *
     * @return the computed result
     * @throws CancellationException if the computation was cancelled
     * @throws ExecutionException if the computation threw an
     * exception
     * @throws InterruptedException if the current thread was interrupted
     * while waiting
     */
    V get() throws InterruptedException, ExecutionException;
    /**
     * Waits if necessary for at most the given time for the computation
     * to complete, and then retrieves its result, if available.
     *
     * @param timeout the maximum time to wait
     * @param unit the time unit of the timeout argument
     * @return the computed result
     * @throws CancellationException if the computation was cancelled
     * @throws ExecutionException if the computation threw an
     * exception
     * @throws InterruptedException if the current thread was interrupted
     * while waiting
     * @throws TimeoutException if the wait timed out
     */
    V get(long timeout, TimeUnit unit)
        throws InterruptedException, ExecutionException, TimeoutException;
}

FutureTask

因为Future只是一个接口，并不能实例化，可以认为FutureTask就是Future接口的实现类，FutureTask实现了RunnableFuture接口，而RunnableFuture接口继承了Runnable接口和Future接口。

public class FutureTask<V> implements RunnableFuture<V> {
...
}
public interface RunnableFuture<V> extends Runnable, Future<V> {
    void run();
}

volatile关键字有什么用？怎么理解可见性？一般什么场景去用可见性？

当线程进行一个volatile变量写操作时，JIT编译器生成的汇编指令会在写操作的指令后面加上一个lock指令，代码如下：

instance = new Singleton(); // instance是volatile变量
转变成汇编代码，如下。
0x01a3de1d: movb $0×0,0×1104800(%esi);0x01a3de24: lock addl $0×0,(%esp);

“lock”有三个作用：

1. 将当前CPU缓存行的数据会写回到系统内存。
2. 这个写回内存的操作会使得其他CPU里缓存该内存地址的数据无效。
3. 确保指令重排序时，内存屏障前的指令不会排到后面去，内存屏障后面的指令不会排到前面去。

可见性可以理解为一个线程的写操作可以立即被其他线程得知。为了提高CPU处理速度，CPU一般不直接与内存进行通信，而是将系统内存的数据读取到内存缓存，再进行操作。对于普通的变量，修改完不知道何时会更新到系统内存。但是如果是对volatile修饰的变量进行写操作，JVM会向处理器发送一条Lock前缀的指令，将这个变量所在的缓存行的数据立即写回到系统内存。但是即便写回到系统内存，其他CPU的缓存行数据还是旧数据，为了保证数据一致性，其他CPU会嗅探在总线上传播的数据来检查自己缓存的行的值是否过期，当CPU发现缓存行对应的内存地址被修改，那么就会将当前缓存行设置为无效，下次当CPU对这个缓存进行修改时，会重新从系统内存中把数据读到处理器缓存里。

使用场景

1. 读写锁
   如果需要实现一个读写锁，每次只能一个线程去写数据，但是有多个线程来读取数据，就synchronize同步锁来对set方法加锁，get方法不加锁，使用volatile修饰变量，保存内存可见性，不然多个线程可能会在变量修改后还读到一个旧值。

   volatile Integer a;
   //可以实现一写多读的场景，保证并发修改数据时的正确。
   set(Integer c) {
   synchronized(this.a) {
      this.a = c;
   }
   }
   get() {
    return a;
   }

2. 状态位

用于做状态位标志，如果多个线程去需要根据一个状态位来执行一些操作，使用volatile修饰可以保存内存可见性。用于单例模式，保证1内存可见性，以防止指令重排序。

Java中线程的状态是怎么样的？

在传统操作系统中，线程等于轻量级的进程。

所以传统的操作系统线程一般有以下状态：

1. 新建状态：使用new关键字和Thread类或其子类建立一个线程对象后，该线程对象就处于新建状态。它保持这个状态直到程序start()这个线程；
2. 就绪状态：当线程对象调用了start()方法之后，该线程就进入就绪状态。该线程就处于就绪队列中，要等待JVM里线程调度器的调度。
3. 运行状态：如果就绪状态的线程获取CPU资源，就可以执行run()方法，此时线程便处于运行状态。处于运行状态的线程最为复杂，它可以变为阻塞状态、就绪状态和死亡状态。
4. 阻塞状态：如果一个线程执行了sleep（睡眠）、suspend（挂起）等方法，失去所占用资源之后，该线程就从运行状态进入阻塞状态。在睡眠时间已到或获得设备资源后可以重新进入就绪状态。可以分为三种：
   • 等待阻塞：运行状态中的线程执行wait()方法，使线程进入到等待阻塞状态。
   • 同步阻塞：线程在获取synchronized同步锁失败（因为同步锁被其他线程占用）。
   • 其他阻塞：通过调用线程的sleep()或join()发出I/O请求时，线程就会进入到阻塞状态。当sleep()状态超时，join()等待线程终止或超时，或者I/O处理完毕，线程重新转入就绪状态。
5. 死亡状态：一个运行状态的线程完成任务或者在其他终止条件发生时，该线程进入到终止状态。

但是Java中Thread对象的状态划分跟传统的操作系统线程状态有一些区别。

/**
     * A thread state.  A thread can be in one of the following states:
     * <ul>
     * <li>{@link #NEW}<br>
     *     A thread that has not yet started is in this state.
     *     </li>
     * <li>{@link #RUNNABLE}<br>
     *     A thread executing in the Java virtual machine is in this state.
     *     </li>
     * <li>{@link #BLOCKED}<br>
     *     A thread that is blocked waiting for a monitor lock
     *     is in this state.
     *     </li>
     * <li>{@link #WAITING}<br>
     *     A thread that is waiting indefinitely for another thread to
     *     perform a particular action is in this state.
     *     </li>
     * <li>{@link #TIMED_WAITING}<br>
     *     A thread that is waiting for another thread to perform an action
     *     for up to a specified waiting time is in this state.
     *     </li>
     * <li>{@link #TERMINATED}<br>
     *     A thread that has exited is in this state.
     *     </li>
     * </ul>
     *
     * <p>
     * A thread can be in only one state at a given point in time.
     * These states are virtual machine states which do not reflect
     * any operating system thread states.
     *
     * @since   1.5
     * @see #getState
     */
    public enum State {
        /**
         * Thread state for a thread which has not yet started.
         */
        NEW, //新建状态
        /**
         * Thread state for a runnable thread.  A thread in the runnable
         * state is executing in the Java virtual machine but it may
         * be waiting for other resources from the operating system
         * such as processor.
         */
        RUNNABLE, //运行态
        /**
         * Thread state for a thread blocked waiting for a monitor lock.
         * A thread in the blocked state is waiting for a monitor lock
         * to enter a synchronized block/method or
         * reenter a synchronized block/method after calling
         * {@link Object#wait() Object.wait}.
         */
        BLOCKED,  //阻塞状态
        /**
         * Thread state for a waiting thread.
         * A thread is in the waiting state due to calling one of the
         * following methods:
         * <ul>
         *   <li>{@link Object#wait() Object.wait} with no timeout</li>
         *   <li>{@link #join() Thread.join} with no timeout</li>
         *   <li>{@link LockSupport#park() LockSupport.park}</li>
         * </ul>
         *
         * <p>A thread in the waiting state is waiting for another thread to
         * perform a particular action.
         *
         * For example, a thread that has called <tt>Object.wait()</tt>
         * on an object is waiting for another thread to call
         * <tt>Object.notify()</tt> or <tt>Object.notifyAll()</tt> on
         * that object. A thread that has called <tt>Thread.join()</tt>
         * is waiting for a specified thread to terminate.
         */
        WAITING,  //等待态
        /**
         * Thread state for a waiting thread with a specified waiting time.
         * A thread is in the timed waiting state due to calling one of
         * the following methods with a specified positive waiting time:
         * <ul>
         *   <li>{@link #sleep Thread.sleep}</li>
         *   <li>{@link Object#wait(long) Object.wait} with timeout</li>
         *   <li>{@link #join(long) Thread.join} with timeout</li>
         *   <li>{@link LockSupport#parkNanos LockSupport.parkNanos}</li>
         *   <li>{@link LockSupport#parkUntil LockSupport.parkUntil}</li>
         * </ul>
         */
        TIMED_WAITING,   //有时间限制的等待态
        /**
         * Thread state for a terminated thread.
         * The thread has completed execution.
         */
        TERMINATED;  //死亡态
    }

NEW 新建态：处于NEW状态的线程此时尚未启动，还没有调用Thread实例的start()方法。
RUNNABLE 运行态：表示当前线程正在运行中。处于RUNNABLE状态的线程可能在Java虚拟机中运行，也有可能在等待其他系统资源（比如I/O）。Java线程的RUNNABLE状态其实是包括了传统操作系统线程的ready和running两个状态。
BLOCKED 阻塞态：阻塞状态，处于BLOCKED状态的线程等待锁的释放以进入同步区。
WAITING 等待态：等待状态，处于等待状态的线程变成RUNNABLE状态需要其他线程唤醒。调用如下三个方法会使线程进入等待状态：

• Object.wait()：使当前线程处于等待状态直到另一个线程调用notify唤醒它；
• Thread.join()：等待线程执行完毕，底层调用的是Object实例的wait()方法；
• LockSupport.park()：除非获得调用许可，否则禁用当前线程进行线程调用。

TIMED_WAITING 超时等待状态：超时等待状态，线程等待一个具体时间，时间到后悔被自动唤醒。调用如下方法会是线程进入超时等待状态：

• Thread.sleep(long millis)：使当前线程睡眠指定时间；
• Object.wait(long timeout)：线程休眠指定时间，等待期间可以通过notify()/notifyAll()唤醒；
• Thread.join(long millis)：等待当前线程最多执行millis毫秒，如果millis为0，则会一直执行；
• LockSupport.parkNanos(long nanos)： 除非获得调用许可，否则禁用当前线程进行线程调度指定时间；
  
• LockSupport.parkUntil(long deadline)：同上，也是禁止线程进行调度指定时间；
  

TERMINATED 终止态：终止状态，此时线程已执行完毕。
状态转换
1. BLOCKED与RUNNABLE状态转换
处于BLOCKED状态的线程是因为在等待锁的释放，当获得锁之后就转换为RUNNABLE状态。

1. WAITING状态与RUNNABLE状态转换

Object.wait()，Thread.join()和LockSupport.park()这3个方法可以使线程从RUNNABLE状态转为WAITING状态。

1. TIMED_WAITING与RUNNABLE状态转换

TIMED_WAITING与WAITING状态类似，只是TIMED_WAITING状态等待的时间是指定的。调用Thread.sleep(long)，Object.wait(long)，Thread.join(long)会使得RUNNABLE状态转换为TIMED_WAITING状态

wait()、join()、sleep()方法有什么作用

Object.wait()方法是什么？

调用wait()方法前线程必须持有对象Object锁。线程调用wait()方法后，会释放当前的Object锁，进入锁的monitor对象的等待队列，知道有其他线程调用notify()/notifyAll()方法唤醒等待锁的线程。
需要注意的是，其他线程调用notify()方法只会唤醒单个等待锁的线程，也不一定马上把时间片分给刚才放弃锁的那个线程，具体看系统调度。

Thread.join()方法是什么？

join()方法是Thread类的一个实例方法。它的作用是让当前线程陷入“等待”状态。等join的这个线程threadA执行完成后，再继续执行当前线程。实现原理是join()方法本身是一个sychronized修饰的方法，也就是调用join()这个方法需要先获取threadA的锁，获得锁之后再调用wait()方法来进行等待，一直到threadA执行完成后，threadA会调用notify_all()方法,唤醒所有等待的线程，当前线程才会结束等待。
join()源码如下：

public final void join() throws InterruptedException {
    join(0);//0的话代表没有超时时间一直等下去
}
public final synchronized void join(long millis)
throws InterruptedException {
    long base = System.currentTimeMillis();
    long now = 0;
    if (millis < 0) {
        throw new IllegalArgumentException("timeout value is negative");
    }
    if (millis == 0) {
        while (isAlive()) {
            wait(0);
        }
    } else {
        while (isAlive()) {
            long delay = millis - now;
            if (delay <= 0) {
                break;
            }
            wait(delay);
            now = System.currentTimeMillis() - base;
        }
    }
}

sleep()方法是什么

sleep方法是thread类的一个静态方法，它的作用是让当前线程休眠一段时间。sleep方法不会释放当前线程持有的锁，而wait方法会。
sleep与wait区别：

• wait可以指定时间，也可以不指定；而sleep必须指定时间。
• wait释放CPU资源，同时释放锁；sleep释放CPU资源，不会释放锁，所以易死锁。（调用join方法也不会释放锁）
• wait必须放在同步块或同步方法中，而sleep可以在任意位置。

  Thread.sleep(),Object.wait(),LockSupport.part()有什么区别？

1. 这三个方法都会让线程挂起，释放CPU时间片，进入到阻塞态。但是Object.wait()需要释放锁，所以必须早synchronized同步锁中使用，同理配套的Object.notify()也是。而Thread.sleep(),LockSupport.part()方法不需要在synchronized中使用，并且调用时也不会释放锁。
2. 由于Thread.sleep()没有对应的唤醒线程的方法，所以必须指定超时时间，超过时间后，线程恢复。所以调用Thread.sleep()后的线程一般是出于TIME_WAITING状态，而调用了Object.wait()，LockSupport.park()的方法是进入到WAITING状态。
3. Object.wait()对应的唤醒方法为Object.notify()，LockSupport.park()对应的唤醒方法为LockSupport.unpark()。
4. 在代码中必须能保证wait方法比notify方法先执行，如果notify方法比wait方法早执行的话，就会导致因wait方法进入休眠的线程接收不到唤醒通知的问题。而park、unpark则不会有这个问题，我们可以先调用unpark方法释放一个许可证，这样后面线程调用park方法时，发现已经许可证了，就可以直接获取许可证而不用进入休眠状态了。（LockSupport.park() 的实现原理是通过二元信号量做的阻塞，要注意的是，这个信号量最多只能加到1，也就是无论执行多少次unpark()方法，也最多只会有一个许可证。）
5. 三种方法让线程进入阻塞态后，都可以响应中断，也就是调用Thread.interrupt()方法会设置中断标志位，之前执行Thread.sleep(),Object.wait()了的线程会抛出InterruptedException异常，然后需要代码进行处理。而调用了park()方法的线程在响应中断只会相当于一次正常的唤醒操作（等价于调用unpark()方法），让线程唤醒，继续执行后面的代码，不会抛出InterruptedException异常。

怎么实现一个生产者消费者？

1. 使用Object.wait()和Object.notify()实现

使用一个queue作为一个队列，存放数据，并且使用Synchronized同步锁，每次只能同时存在一个线程来生产或者消费数据，生成线程发现队列容量大于10，生产者线程进入waiting状态，，一旦成功往队列添加数据，那么就唤醒所有线程（主要是消费者线程起来消费）。消费线程消费时，当队列容量等于0，也会主动1进入waiting状态。
伪代码如下：

LinkedList<Integer> queue = new LinkedList<>();
void produce(Integer value) {
  synchronized(queue) {//加锁控制，保证同一时间点，只能有一个线程生成或者消费
    while(queue.size()>10) {
                    queue.waiting();
    }
    queue.add(value);
    //唤醒消费者线程
    queue.notifyAll();
  }
}
Integer consumer() {
  synchronized(queue) {//加锁控制，保证同一时间点，只能有一个线程生成或者消费
    while(queue.size()==0) {
       queue.waiting();
    }
    Integer value = queue.poll();
    //唤醒生产者线程
    queue.notifyAll();
        return value;
  }
}

完整代码如下：

public static void main(String[] args) {
    Queue<Integer> queue    = new LinkedList<>();
    final Customer customer = new Customer(queue);
    final Producer producer = new Producer(queue);
    ExecutorService pool = Executors.newCachedThreadPool();
    for (int i = 0; i < 1000; i++) {
        pool.execute(new Runnable() {
            @Override
            public void run() {
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                Integer a = customer.removeObject();
                System.out.println("消费了数据 "+a);
            }
        });
        pool.execute(new Runnable() {
            @Override
            public void run() {
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                Random  random = new Random();
                Integer a      = random.nextInt(1000);
                System.out.println("生成了数据 "+a);
                producer.addObject(a);
            }
        });
    }
}
private static class Customer {
    Queue<Integer> queue;
    Customer(Queue<Integer> queue) { this.queue = queue; }
    public Integer removeObject() {
        synchronized (queue) {
            try {
                while (queue.size()==0) {
                    System.out.println("队列中没有元素了，进行等待");
                    queue.wait();
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            Integer number = queue.poll();
            System.out.println("唤醒所有生产线程，当前queue大小是" + queue.size());
            queue.notifyAll();
            return number;
        }
    }
}
private static class Producer {
    Queue<Integer> queue;
    Producer(Queue<Integer> queue) { this.queue = queue; }
    public void addObject(Integer number) {
        synchronized (queue) {
            try {
                while (queue.size()>10) {
                    queue.wait();
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            queue.add(number);
            queue.notifyAll();
            System.out.println("唤醒所有消费线程，当前queue大小是"+queue.size());
        }
    }
}