集合概述

常见的集合

集合相关类和接又都在java.util中，主要分为 3 种：List（列表）、Map（映射）、Set(集)。

其中Collection是集合List、Set的父接口，它主要有两个子接口：

List ：存储的元素有序，可重复。
Set ：存储的元素无序，不可重复。

Map是另外的接口，是键值对映射结构的集合。

List, Set, Queue, Map 四者的区别

list (对付顺序的好帮手): 存储的元素是有序的、可重复的。
Set (注重独一无二的性质): 存储的元素是无序的、不可重复的。
Queue (实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。
Map (用 key 来搜索的专家): 使用键值对（key-value）存储，类似于数学上的函数 y=f(x)，”x” 代表 key，”y” 代表 value，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

如何选用集合?

主要根据集合的特点来选用，比如我们需要根据键值获取到元素值时就选用 Map 接口下的集合，需要排序时选择TreeMap,不需要排序时就选择HashMap,需要保证线程安全就选用ConcurrentHashMap。

当我们只需要存放元素值时，就选择实现Collection接口的集合，需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或HashSet，不需要就选择实现 List 接口的比如 ArrayList或 LinkedList，然后再根据实现这些接口的集合的特点来选用。

底层数据结构

先来看一下 Collection 接口下面的集合。

List

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

Set

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

Queue

PriorityQueue: Object[] 数组来实现二叉堆
ArrayQueue: Object[] 数组 + 双指针

Map

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

线程安全

java.util包下的集合类大部分都是线程不安全的，例如我们常用的HashSet、TreeSet、ArrayList、LinkedList、ArrayDeque、HashMap、TreeMap，这些都是线程不安全的集合类，但是它们的优点是性能好。如果需要使用线程安全的集合类，则可以使用Collections工具类提供的**synchronizedXxx()**方法，将这些集合类包装成线程安全的集合类。

java.util包下也有线程安全的集合类，例如Vector、Hashtable。这些集合类都是比较古老的API，虽然实现了线程安全，但是性能很差。所以即便是需要使用线程安全的集合类，也建议将线程不安全的集合类包装成线程安全集合类的方式，而不是直接使用这些古老的API。

从Java5开始，Java在java.util.concurrent包下提供了大量支持高效并发访问的集合类，它们既能包装良好的访问性能，有能包装线程安全。这些集合类可以分为两部分，它们的特征如下：

以Concurrent开头的集合类：

以Concurrent开头的集合类代表了支持并发访问的集合，它们可以支持多个线程并发写入访问，这些写入线程的所有操作都是线程安全的，但读取操作不必锁定。以Concurrent开头的集合类采用了更复杂的算法来保证永远不会锁住整个集合，因此在并发写入时有较好的性能。
以CopyOnWrite开头的集合类：

以CopyOnWrite开头的集合类采用复制底层数组的方式来实现写操作。当线程对此类集合执行读取操作时，线程将会直接读取集合本身，无须加锁与阻塞。当线程对此类集合执行写入操作时，集合会在底层复制一份新的数组，接下来对新的数组执行写入操作。由于对集合的写入操作都是对数组的副本执行操作，因此它是线程安全的。

List

ArrayList和LinkedList

（ 1 ）数据结构不同

ArrayList基于数组实现
LinkedList基于双向链表实现

（ 2 ）多数情况下，ArrayList更利于查找，LinkedList更利于增删

ArrayList基于数组实现，get(int index)可以直接通过数组下标获取，时间复杂度是O(1)；LinkedList基于链表实现，get(int index)需要遍历链表，时间复杂度是O(n)；当然，get(Eelement)这种查找，两种集合都需要遍历，时间复杂度都是O(n)。
ArrayList增删如果是数组末尾的位置，直接插入或者删除就可以了，但是如果插入中间的位置，就需要把插入位置后的元素都向前或者向后移动，甚至还有可能触发扩容；双向链表的插入和删除只需要改变前驱节点、后继节点和插入节点的指向就行了，不需要移动元素。

注意，这个地方可能会出陷阱，LinkedList更利于增删更多是体现在平均步长上，不是体现在时间复杂度上，二者增删的时间复杂度都是O(n)

（ 3 ）是否支持随机访问

ArrayList基于数组，所以它可以根据下标查找，支持随机访问，当然，它也实现了RandmoAccess 接口，这个接口只是用来标识是否支持随机访问。
LinkedList基于链表，所以它没法根据序号直接获取元素，它没有实现RandmoAccess 接口，标记不支持随机访问。

（ 4 ） 内存占用，ArrayList基于数组，是一块连续的内存空间，LinkedList基于链表，内存空
间不连续，它们在空间占用上都有一些额外的消耗：

ArrayList是预先定义好的数组，可能会有空的内存空间，存在一定空间浪费
LinkedList每个节点，需要存储前驱和后继，所以每个节点会占用更多的空间

ArrayList的扩容机制

ArrayList是基于数组的集合，数组的容量是在定义的时候确定的，如果数组满了，再插入，就会数组溢出。所以在插入时候，会先检查是否需要扩容，如果当前容量+1超过数组长度，就会进行扩容。

ArrayList的扩容是创建一个 1.5倍 的新数组，然后把原数组的值拷贝过去。

ArrayList序列化

ArrayList的序列化不太一样，它使用transient修饰存储元素的elementData的数组，transient关键字的作用是让被修饰的成员属性不被序列化。

为什么ArrayList不直接序列化元素数组呢？

出于效率的考虑，数组可能长度 100 ，但实际只用了 50 ，剩下的 50 不用其实不用序列化，这样可以提高序列化和反序列化的效率，还可以节省内存空间。

那ArrayList怎么序列化呢？

ArrayList通过两个方法 readObject、writeObject 自定义序列化和反序列化策略，实际直接使用两个流ObjectOutputStream和ObjectInputStream来进行序列化和反序列化。

快速失败(fail-fast)和安全失败(fail-safe)

快速失败（fail—fast）：快速失败是Java集合的一种错误检测机制

在用迭代器遍历一个集合对象时，如果线程A遍历过程中，线程B对集合对象的内容进行了修改（增加、删除），则会抛出Concurrent Modification Exception。
原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount变量。集合在被遍历期间如果内容发生变化，就会改变modCount 的值。每当迭代器使用**hashNext()/next()**遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。
注意：这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。
场景：java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改），比如ArrayList 类。

安全失败（fail—safe）

采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。
原理：由于迭代器是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发Concurrent Modification Exception。
缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。
场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改，比如CopyOnWriteArrayList类。

官方文档解释

当Iterator这个迭代器被创建后，除了迭代器本身的方法(remove)**可以改变集合的结构外，其他的因素如若改变了集合的结构，都被抛出ConcurrentModificationException**异常。

迭代器的快速失败行为是不一定能够得到保证的，一般来说，存在非同步的并发修改时，不可能做出任何坚决的保证的。但是快速失败迭代器会做出最大的努力来抛出ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是不正确的。正确的做法应该是：迭代器的快速失败行为应该仅用于检测程序中的bug.

结构上的改变
例如集合上的插入和删除就是结构上的改变，但是，如果是对集合中某个元素进行修改的话，并不是结构上的改变。

1、单线程的环境下，fail-fast抛出异常的实例：

List<Integer> list = new ArrayList<>();
    for(int i = 0; i < 20; i++){
        list.add(i);
    }
    Iterator<Integer> it = list.iterator();
    int temp = 0;
    while(it.hasNext()){
        if(temp == 3){
            temp++;
            list.remove(3);
        }else{
            temp++;
            System.out.println(it.next());
        }
    }
}

打印结果：

结果分析：因为当temp==3的时候，执行list.remove()方法，集合的结构被改变了，所以再次遍历迭代器的时候，就会抛出异常。

HashMap发生fail-fast：

public static void main(String[] args) {
           Map<String, String> map = new HashMap<>();
           for (int i = 0 ; i < 10 ; i ++ ) {
                map.put(i+"", i+"");
           }
           Iterator<Entry<String, String>> it = map.entrySet().iterator();
           int i = 0;
           while (it.hasNext()) {
                if (i == 3) {
                     map.remove(3+"");
                }
                Entry<String, String> entry = it.next();
                System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
                i++;
        }
     }

该段代码定义了一个hashmap对象并存放了10个键值对，在迭代遍历过程中，使用map的remove方法移除了一个元素，导致抛出了 ConcurrentModificationException异常：

2、多线程环境下：

public class FailFastTest {
     public static List<String> list = new ArrayList<>();
 
     private static class MyThread1 extends Thread {
           @Override
           public void run() {
                Iterator<String> iterator = list.iterator();
                while(iterator.hasNext()) {
                     String s = iterator.next();
                     System.out.println(this.getName() + ":" + s);
                     try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                }
                super.run();
           }
     }
 
     private static class MyThread2 extends Thread {
           int i = 0;
           @Override
           public void run() {
                while (i < 10) {
                     System.out.println("thread2:" + i);
                     if (i == 2) {
                           list.remove(i);
                     }
                     try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                     i ++;
                }
           }
     }
 
     public static void main(String[] args) {
           for(int i = 0 ; i < 10;i++){
            list.add(i+"");
        }
           MyThread1 thread1 = new MyThread1();
           MyThread2 thread2 = new MyThread2();
           thread1.setName("thread1");
           thread2.setName("thread2");
           thread1.start();
           thread2.start();
     }
}

启动两个线程，分别对其中一个对list进行迭代，另一个在线程1的迭代过程中去remove一个元素，结果也是抛出了java.util.ConcurrentModificationException

fail-fast的工作原理

fail-fast是如何抛出ConcurrentModificationException异常的，又是在什么情况下才会抛出?

我们知道，对于集合如list，map类，我们都可以通过迭代器来遍历，而Iterator其实只是一个接口，具体的实现还是要看具体的集合类中的内部类去实现Iterator并实现相关方法。这里我们就以ArrayList类为例。在ArrayList中，当调用list.iterator()时，其源码是：

1
2
3

public Iterator<E> iterator() {
    return new Itr();
}

即它会返回一个新的Itr类，而Itr类是ArrayList的内部类，实现了Iterator接口，下面是该类的源码：

/**
     * An optimized version of AbstractList.Itr
     */
    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;
 
        public boolean hasNext() {
            return cursor != size;
        }
 
        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
 
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
 
            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
 
        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }
 
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

其中，有三个属性：

1
2
3

int cursor;       // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;

cursor是指集合遍历过程中的即将遍历的元素的索引，lastRet是cursor -1，默认为-1，即不存在上一个时，为-1，它主要用于记录刚刚遍历过的元素的索引。expectedModCount这个就是fail-fast判断的关键变量了，它初始值就为ArrayList中的modCount。（modCount是抽象类AbstractList中的变量，默认为0，而ArrayList 继承了AbstractList ，所以也有这个变量，modCount用于记录集合操作过程中作的修改次数，与size还是有区别的，并不一定等于size）

我们一步一步来看：

1
2
3

public boolean hasNext() {
    return cursor != size;
}

迭代器迭代结束的标志就是hasNext()返回false，而该方法就是用cursor游标和size(集合中的元素数目)进行对比，当cursor等于size时，表示已经遍历完成。

接下来看看最关心的next()方法，看看为什么在迭代过程中，如果有线程对集合结构做出改变，就会发生fail-fast：

@SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

从源码知道，每次调用next()方法，在实际访问元素前，都会调用checkForComodification方法，该方法源码如下：

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

可以看出，该方法才是判断是否抛出ConcurrentModificationException异常的关键。在该段代码中，当modCount != expectedModCount时，就会抛出该异常。但是在一开始的时候，expectedModCount初始值默认等于modCount，为什么会出现modCount != expectedModCount，很明显expectedModCount在整个迭代过程除了一开始赋予初始值modCount外，并没有再发生改变，所以可能发生改变的就只有modCount，在前面关于ArrayList扩容机制的分析中，可以知道在ArrayList进行add，remove，clear等涉及到修改集合中的元素个数的操作时，modCount就会发生改变(modCount ++),所以当另一个线程(并发修改)或者同一个线程遍历过程中，调用相关方法使集合的个数发生改变，就会使modCount发生变化，这样在checkForComodification方法中就会抛出ConcurrentModificationException异常。

类似的，hashMap中发生的原理也是一样的。

避免fail-fast

了解了fail-fast机制的产生原理，接下来就看看如何解决fail-fast

方法1

在单线程的遍历过程中，如果要进行remove操作，可以调用迭代器的remove方法而不是集合类的remove方法。看看ArrayList中迭代器的remove方法的源码：

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();
 
    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

可以看到，该remove方法并不会修改modCount的值，并且不会对后面的遍历造成影响，因为该方法remove不能指定元素，只能remove当前遍历过的那个元素，所以调用该方法并不会发生fail-fast现象。该方法有局限性。

例子：

public static void main(String[] args) {
      List<String> list = new ArrayList<>();
      for (int i = 0 ; i < 10 ; i++ ) {
           list.add(i + "");
      }
      Iterator<String> iterator = list.iterator();
      int i = 0 ;
      while(iterator.hasNext()) {
           if (i == 3) {
                iterator.remove(); //迭代器的remove()方法
           }
           System.out.println(iterator.next());
           i ++;
      }
}

方法2

使用java并发包(java.util.concurrent)中的类来代替 ArrayList 和hashMap。

比如使用 CopyOnWriterArrayList代替 ArrayList， CopyOnWriterArrayList在是使用上跟 ArrayList几乎一样， CopyOnWriter是写时复制的容器(COW)，在读写时是线程安全的。该容器在对add和remove等操作时，并不是在原数组上进行修改，而是将原数组拷贝一份，在新数组上进行修改，待完成后，才将指向旧数组的引用指向新数组，所以对于 CopyOnWriterArrayList在迭代过程并不会发生fail-fast现象。但 CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。

对于HashMap，可以使用ConcurrentHashMap， ConcurrentHashMap采用了锁机制，是线程安全的。在迭代方面，ConcurrentHashMap使用了一种不同的迭代方式。在这种迭代方式中，当iterator被创建后集合再发生改变就不再是抛出ConcurrentModificationException，取而代之的是在改变时new新的数据从而不影响原有的数据，iterator完成后再将头指针替换为新的数据，这样iterator线程可以使用原来老的数据，而写线程也可以并发的完成改变。即迭代不会发生fail-fast，但不保证获取的是最新的数据。

fail-safe与fail-fast的区别

当我们对集合结构上做出改变的时候，fail-fast机制就会抛出异常。但是，对于采用fail-safe机制来说，就不会抛出异常。

这是因为，当集合的结构被改变的时候，fail-safe机制会在复制原集合的一份数据出来，然后在复制的那份数据遍历。

因此，虽然fail-safe不会抛出异常，但存在以下缺点

复制时需要额外的空间和时间上的开销。
不能保证遍历的是最新内容。

线程安全的List

**Vector **

Vector是比较古老的API，虽然保证了线程安全，但是由于效率低一般不建议使用。
Collections.SynchronizedList

SynchronizedList是Collections的内部类，Collections提供了synchronizedList方法，可以将一个线程不安全的List包装成线程安全的List，即SynchronizedList。它比Vector有更好的扩展性和兼容性，但是它所有的方法都带有同步锁，也不是性能最优的List。
CopyOnWriteArrayList

CopyOnWriteArrayList是Java 1.5在java.util.concurrent包下增加的类，它采用复制底层数组的方式来实现写操作。当线程对此类集合执行读取操作时，线程将会直接读取集合本身，无须加锁与阻塞。当线程对此类集合执行写入操作时，集合会在底层复制一份新的数组，接下来对新的数组执行写入操作。由于对集合的写入操作都是对数组的副本执行操作，因此它是线程安全的。在所有线程安全的List中，它是性能最优的方案。

CopyOnWriteArrayList原理

CopyOnWriteArrayList就是线程安全版本的ArrayList。

它的名字叫CopyOnWrite——写时复制，已经明示了它的原理。

CopyOnWriteArrayList采用了一种读写分离的并发策略。CopyOnWriteArrayList容器允许并发读，读操作是无锁的，性能较高。至于写操作，比如向容器中添加一个元素，则首先将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器。

优点：读操作性能很高，因为无需任何同步措施，比较适用于读多写少的并发场景。在遍历传统的List时，若中途有别的线程对其进行修改，则会抛出ConcurrentModificationException异常。而CopyOnWriteArrayList由于其”读写分离“的思想，遍历和修改操作分别作用在不同的List容器，所以在使用迭代器进行遍历时候，也就不会抛出ConcurrentModificationException异常了。
缺点：一是内存占用问题，毕竟每次执行写操作都要将原容器拷贝一份，数据量大时，对内存压力较大，可能会引起频繁GC。二是无法保证实时性，Vector对于读写操作均加锁同步，可以保证读和写的强一致性。而CopyOnWriteArrayList由于其实现策略的原因，写和读分别作用在新老不同容器上，在写操作执行过程中，读不会阻塞但读取到的却是老容器的数据

Queue

Queue 与 Deque

Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。

Queue扩展了Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。

`Queue` 接口	抛出异常	返回特殊值
插入队尾	add(E e)	offer(E e)
删除队首	remove()	poll()
查询队首元素	element()	peek()

Deque是双端队列，在队列的两端均可以插入或删除元素。

Deque扩展了 Queue的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：

`Deque` 接口	抛出异常	返回特殊值
插入队首	addFirst(E e)	offerFirst(E e)
插入队尾	addLast(E e)	offerLast(E e)
删除队首	removeFirst()	pollFirst()
删除队尾	removeLast()	pollLast()
查询队首元素	getFirst()	peekFirst()
查询队尾元素	getLast()	peekLast()

事实上，Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。

PriorityQueue

PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。

这里列举其相关的一些要点：

PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据
PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。
PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。

PriorityQueue 在面试中可能更多的会出现在手撕算法的时候，典型例题包括堆排序、求第K大的数、带权图的遍历等，所以需要会熟练使用才行。

ArrayDeque 与 LinkedList

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？
ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。
ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。
ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。

Set

Set概述

Set 注重独一无二的性质,该体系集合用于存储无序(存入和取出的顺序不一定相同)元素，值不能重复。对象的相等性本质是对象 hashCode 值（java 是依据对象的内存地址计算出的此序号）判断的，如果想要让两个不同的对象视为相等的，就必须覆盖 Object 的 hashCode 方法和 equals 方法。

HashSet（Hash 表）

哈希表存放的是哈希值。HashSet 存储元素的顺序并不是按照存入时的顺序（和 List 显然不同）而是按照哈希值来存的所以取数据也是按照哈希值取得。元素的哈希值是通过元素的 hashcode 方法来获取的, HashSet 首先判断两个元素的哈希值，如果哈希值一样，接着会比较 equals 方法如果 equals 结果为 true ，HashSet 就视为同一个元素。如果 equals 为 false 就不是同一个元素。

哈希值相同 equals 为 false 的元素是怎么存储呢,就是在同样的哈希值下顺延（可以认为哈希值相同的元素放在一个哈希桶中）。也就是哈希一样的存一列。如图 1 表示 hashCode 值不相同的情况；图 2 表示 hashCode 值相同，但 equals 不相同的情况。

HashSet 通过 hashCode 值来确定元素在内存中的位置。一个 hashCode 位置上可以存放多个元素。

TreeSet（二叉树）

TreeSet()是使用二叉树的原理对新 add()的对象按照指定的顺序排序（升序、降序），每增加一个对象都会进行排序，将对象插入的二叉树指定的位置。
Integer 和 String 对象都可以进行默认的 TreeSet 排序，而自定义类的对象是不可以的，自己定义的类必须实现 Comparable 接口，并且覆写相应的 compareTo()函数，才可以正常使用。
在覆写 compare()函数时，要返回相应的值才能使 TreeSet 按照一定的规则来排序
比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。

LinkHashSet（HashSet+LinkedHashMap）

对于 LinkedHashSet 而言，它继承与 HashSet、又基于 LinkedHashMap 来实现的。 LinkedHashSet 底层使用 LinkedHashMap 来保存所有元素，它继承与 HashSet，其所有的方法操作上又与 HashSet 相同，因此 LinkedHashSet 的实现上非常简单，只提供了四个构造方法，并通过传递一个标识参数，调用父类的构造器，底层构造一个 LinkedHashMap 来实现，在相关操作上与父类 HashSet 的操作相同，直接调用父类 HashSet 的方法即可。

HashSet的底层结构

HashSet是基于HashMap实现的，默认构造函数是构建一个初始容量为16，负载因子为0.75 的HashMap。它封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。

HashSet的add方法，直接调用HashMap的put方法，将添加的元素作为key，new一个Object作为value，直接调用HashMap的put方法，它会根据返回值是否为空来判断是否插入元素成功。

1
2
3

public boolean add(E e) {
	return map.put(e, PRESENT)==null;
}

而在HashMap的putVal方法中，进行了一系列判断，最后的结果是，只有在key在table数组中不存在的时候，才会返回插入的值。

if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
    e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

HashSet 如何检查重复

你把对象加入HashSet时，HashSet 会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。

在openjdk8中，HashSet的add()方法只是简单的调用了HashMap的put()方法，并且判断了一下返回值以确保是否有重复元素。直接看一下HashSet中的源码：

// Returns: true if this set did not already contain the specified element
// 返回值：当set中没有包含add的元素时返回真
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}

而在HashMap的putVal()方法中也能看到如下说明：

// Returns : previous value, or null if none
// 返回值：如果插入位置没有元素返回null，否则返回上一个元素
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
...
}

也就是说，在openjdk8中，实际上无论HashSet中是否已经存在了某元素，HashSet都会直接插入，只是会在add()方法的返回值处告诉我们插入前是否存在相同元素。

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

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

==与 equals 的区别

对于基本类型来说，== 比较的是值是否相等；
对于引用类型来说，== 比较的是两个引用是否指向同一个对象地址（两者在内存中存放的地址（堆内存地址）是否指向同一个地方）；
对于引用类型（包括包装类型）来说，equals 如果没有被重写，对比它们的地址是否相等；如果 equals()方法被重写（例如 String），则比较的是地址里的内容。

HashSet、LinkedHashSet 和 TreeSet 三者的异同

HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类，都能保证元素唯一，并且都不是线程安全的。
HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表（基于 HashMap 实现）。LinkedHashSet 的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。
底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景，LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景，TreeSet 用于支持对元素自定义排序规则的场景。

Map

Map接口的实现类

Map接口有很多实现类，其中比较常用的有HashMap、LinkedHashMap、TreeMap、ConcurrentHashMap。

对于不需要排序的场景，优先考虑使用HashMap，因为它是性能最好的Map实现。如果需要保证线程安全，则可以使用ConcurrentHashMap。它的性能好于Hashtable，因为它在put时采用分段锁/CAS的加锁机制，而不是像Hashtable那样，无论是put还是get都做同步处理。

对于需要排序的场景，如果需要按插入顺序排序则可以使用LinkedHashMap，如果需要将key按自然顺序排列甚至是自定义顺序排列，则可以选择TreeMap。如果需要保证线程安全，则可以使用Collections工具类将上述实现类包装成线程安全的Map。

HashMap

HashMap 中的 key 的类型

平时可能大家使用的最多的就是使用 String 作为 HashMap 的 key，但是现在我们想使用某个自定义类作为 HashMap 的 key，那就需要注意以下几点：

如果类重写了 equals 方法，它也应该重写 hashCode 方法。
类的所有实例需要遵循与 equals 和 hashCode 相关的规则。
如果一个类没有使用 equals，你不应该在 hashCode 中使用它。
咱们自定义 key 类的最佳实践是使之为不可变的，这样，hashCode 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保 hashCode 和 equals 在未来不会改变，这样就会解决与可变相关的问题了。
HashMap是线程不安全的实现；
HashMap可以使用null作为key或value。

HashMap 的底层结构

JDK1.8 之前

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

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

JDK 1.8 HashMap 的 hash 方法源码:

JDK 1.8 的 hash 方法相比于 JDK 1.7 hash 方法更加简化，但是原理不变。

static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^ ：按位异或
      // >>>:无符号右移，忽略符号位，空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

对比一下 JDK1.7 的 HashMap 的 hash 方法源码.

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

相比于 JDK1.8 的 hash 方法，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。

所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

JDK1.8 之后

相比于之前的版本， JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。

基于hash算法，通过put方法和get方法存储和获取对象。

存储对象时，我们将K/V传给put方法时，它调用K的hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。

如果发生碰撞的时候，HashMap通过链表将产生碰撞冲突的元素组织起来。在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。

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

第一个方面为了能让 HashMap 存数据和取数据的效率高，尽可能地减少 hash 值的碰撞，也就是说尽量把数据能均匀的分配，每个链表或者红黑树长度尽量相等。我们首先可能会想到 % 取模的操作来实现。取余（%）操作中如果除数是 2 的幂次，则等价于与其除数减一的与（&）操作（也就是说hash % length == hash &(length - 1) 的前提是 length 是 2 的 n 次方）。并且，采用二进制位操作 & ，相对于 % 能够提高运算效率。

第二个方面是在扩容时，利用扩容后的大小也是 2 的倍数，将已经产生hash碰撞的元素完美的转移到新的table中去

红黑树

你对红黑树了解多少？为什么不用二叉树/平衡树呢？

红黑树本质上是一种二叉查找树，为了保持平衡，它又在二叉查找树的基础上增加了一些规则：

每个节点要么是红色，要么是黑色；
根节点永远是黑色的；
所有的叶子节点都是是黑色的（注意这里说叶子节点其实是图中的 NULL 节点）；
每个红色节点的两个子节点一定都是黑色；
从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；

之所以不用二叉树：

红黑树是一种平衡的二叉树，插入、删除、查找的最坏时间复杂度都为 O(logn)，避免了二叉树最坏情况下的O(n)时间复杂度。

之所以不用平衡二叉树：

平衡二叉树是比红黑树更严格的平衡树，为了保持保持平衡，需要旋转的次数更多，也就是说平衡二叉树保持平衡的效率更低，所以平衡二叉树插入和删除的效率比红黑树要低。

红黑树怎么保持平衡的知道吗？

红黑树有两种方式保持平衡：旋转和染色。

旋转：旋转分为两种，左旋和右旋

染色：

为什么HashMap链表转红黑树的阈值为 8 呢？

树化发生在table数组的长度大于 64 ，且链表的长度大于 8 的时候。

为什么是 8 呢？源码的注释也给出了答案。

红黑树节点的大小大概是普通节点大小的两倍，所以转红黑树，牺牲了空间换时间，更多的是一种兜底的策略，保证极端情况下的查找效率。

阈值为什么要选 8 呢？和统计学有关。理想情况下，使用随机哈希码，链表里的节点符合泊松分布，出现节点个数的概率是递减的，节点个数为 8 的情况，发生概率仅为0.00000006。

至于红黑树转回链表的阈值为什么是 6 ，而不是 8 ？是因为如果这个阈值也设置成 8 ，假如发生碰撞，节点增减刚好在 8 附近，会发生链表和红黑树的不断转换，导致资源浪费。

HashMap 的扩容机制

扩容概述

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

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

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

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

扩容过程

HashMap是基于数组+链表和红黑树实现的，但用于存放key值的桶数组的长度是固定的，由初始化参数确定。

那么，随着数据的插入数量增加以及负载因子的作用下，就需要扩容来存放更多的数据。而扩容中有一个非常重要的点，就是jdk1.8中的优化操作，可以不需要再重新计算每一个元素的哈希值。

因为HashMap的初始容量是 2 的次幂，扩容之后的长度是原来的二倍，新的容量也是 2 的次幂，所以，元素，要么在原位置，要么在原位置再移动 2 的次幂。

看下这张图，n为table的长度，图a表示扩容前的key1和key2两种key确定索引的位置，图b表示扩容后key1和key2两种key确定索引位置。

元素在重新计算hash之后，因为n变为 2 倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

所以在扩容时，只需要看原来的hash值新增的那一位是 0 还是 1 就行了，是 0 的话索引没变，是 1的化变成原索引+oldCap，看看如 16 扩容为 32 的示意图：

扩容节点迁移主要逻辑：

扩容在什么时候呢？为什么扩容因子是0.75？

为了减少哈希冲突发生的概率，当当前HashMap的元素个数达到一个临界值的时候，就会触发扩容，把所有元素rehash之后再放在扩容后的容器中，这是一个相当耗时的操作。

而这个临界值threshold就是由加载因子和当前容器的容量大小来确定的，假如采用默认的构造方法：

1 2	临界值（threshold ）= 默认容量（DEFAULT_INITIAL_CAPACITY） * 默认扩容因子（DEFAULT_LOAD_FACTOR）

那就是大于16x0.75=12时，就会触发扩容操作。

那么为什么选择了0.75作为HashMap的默认加载因子呢？

简单来说，这是对空间成本和时间成本平衡的考虑。

在HashMap中有这样一段注释：

我们都知道，HashMap的散列构造方式是Hash取余，负载因子决定元素个数达到多少时候扩容。

假如我们设的比较大，元素比较多，空位比较少的时候才扩容，那么发生哈希冲突的概率就增加了，查找的时间成本就增加了。

我们设的比较小的话，元素比较少，空位比较多的时候就扩容了，发生哈希碰撞的概率就降低了，查找时间成本降低，但是就需要更多的空间去存储元素，空间成本就增加了。

如果初始化HashMap，传一个 17 的值 new HashMap<>new HashMap<> ，它会怎么处理？

简单来说，就是初始化时，传的不是 2 的倍数时，HashMap会向上寻找离得最近的 2 的倍数，所以传入 17 ，但HashMap的实际容量是 32 。

我们来看看详情，在HashMap的初始化中，有这样一段方法；

public HashMap(int initialCapacity, float loadFactor) {
    ...
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

阀值 threshold ，通过方法tableSizeFor 进行计算，是根据初始化传的参数来计算的。
同时，这个方法也要要寻找比初始值大的，最小的那个 2 进制数值。比如传了 17 ，我应该找到的是 32 。

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

MAXIMUM_CAPACITY = 1 << 30，这个是临界范围，也就是最大的Map集合。
计算过程是向右移位 1 、 2 、 4 、 8 、 16 ，和原来的数做| 运算，这主要是为了把二进制的各个位置都填上 1 ，当二进制的各个位置都是 1 以后，就是一个标准的 2 的倍数减 1 了，最后把结果加 1 再返回即可。

以 17 为例，看一下初始化计算table容量的过程：

HashMap 的线程安全

HashMap不是线程安全的，可能会发生这些问题：

多线程下扩容死循环。JDK1.7 中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8 使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
多线程的 put 可能导致元素的丢失。多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在 JDK1.7 和 JDK 1.8 中都存在。
put 和 get 并发时，可能导致 get 为 null。线程 1 执行 put 时，因为元素个数超出 threshold而导致 rehash，线程 2 此时执行 get，有可能导致这个问题。这个问题在 JDK 1.7 和 JDK 1.8 中都存在。

有什么办法能解决HashMap线程不安全的问题呢

Java 中有 HashTable、Collections.synchronizedMap、以及 ConcurrentHashMap 可以实现线程安全的 Map。

HashTable 是直接在操作方法上加 synchronized 关键字，锁住整个table数组，粒度比较大；
Collections.synchronizedMap 是使用 Collections 集合工具的内部类，通过传入 Map 封装出一个SynchronizedMap 对象，内部定义了一个对象锁，方法内通过对象锁实现；
ConcurrentHashMap 在jdk1.7中使用分段锁，在jdk1.8中使用CAS+synchronized。

HashMap 的put流程

首先进行哈希值的扰动，获取一个新的哈希值。**(key == null)? 0 : (h = key.hashCode()) ^ (h >>> 16)**;
判断tab是否位空或者长度为 0 ，如果是则进行扩容操作。

1 2	if ((tab = table) == null \|\| (n = tab.length) == 0 ) n = (tab = resize()).length;

根据哈希值计算下标，如果对应小标正好没有存放数据，则直接插入即可否则需要覆
判断tab[i]是否为树节点，否则向链表中插入数据，是则向树中插入节点。
如果链表中插入节点的时候，链表长度大于等于 8 ，则需要把链表转换为红黑树。treeifyBin(tab, hash);
最后所有元素处理完成后，判断是否超过阈值；threshold，超过则扩容。

HashMap 的查找元素过程

HashMap的查找就简单很多：

1. 使用扰动函数，获取新的哈希值
2. 计算数组下标，获取节点
3. 当前节点和key匹配，直接返回
4. 否则，当前节点是否为树节点，查找红黑树
5. 否则，遍历链表查找

HashMap 的哈希/扰动函数

HashMap的哈希函数是先拿到 key 的hashcode，是一个 32 位的int类型的数值，然后让hashcode的高 16 位和低 16 位进行异或操作。

static final int hash(Object key) {
int h;
// key的hashCode和key的hashCode右移 16 位做异或运算
return (key == null)? 0 : (h = key.hashCode()) ^ (h >>> 16 );
}

为什么哈希/扰动函数能降hash碰撞

因为 key.hashCode() 函数调用的是 key 键值类型自带的哈希函数，返回 int 型散列值。int 值范围为 -2147483648~2147483647 ，加起来大概 40 亿的映射空间。

只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。

假如 HashMap 数组的初始大小才 16 ，就需要用之前需要对数组的长度取模运算，得到的余数才能用来访问数组下标。

源码中模运算就是把散列值和数组长度 - 1 做一个 “与&” 操作，位运算比取余 % 运算要快。

bucketIndex = indexFor(hash, table.length);
static int indexFor(int h, int length) {
	return h & (length- 1 );
}

顺便说一下，这也正好解释了为什么 HashMap 的数组长度要取 2 的整数幂。因为这样（数组长度 - 1）正好相当于一个 “低位掩码”。与操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度 16 为例，16-1=15。 2 进制表示是0000 0000 0000 0000 0000 0000 0000 1111。和某个散列值做与操作如下，结果就是截取了最低的四位值。

这样是要快捷一些，但是新的问题来了，就算散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。如果散列本身做得不好，分布上成等差数列的漏洞，如果正好让最后几个低位呈现规律性重复，那就更难搞了。

这时候扰动函数的价值就体现出来了，看一下扰动函数的示意图：

右移 16 位，正好是 32bit 的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

你还知道哪些哈希函数的构造方法呢？

HashMap里哈希构造函数的方法叫：

除留取余法：H（key)=key%p（p<=N）,关键字除以一个不大于哈希表长度的正整数p，所得余数为地址，当然HashMap里进行了优化改造，效率更高，散列也更均衡。

除此之外，还有这几种常见的哈希函数构造方法：

直接定址法

直接根据key来映射到对应的数组位置，例如 1232 放到下标 1232 的位置。
数字分析法

取key的某些数字（例如十位和百位）作为映射的位置
平方取中法

取key平方的中间几位作为映射的位置
折叠法

将key分割成位数相同的几段，然后把它们的叠加和作为映射的位置

解决哈希冲突有哪些方法呢？

我们到现在已经知道，HashMap使用链表的原因为了处理哈希冲突，这种方法就是所谓的：

链地址法：在冲突的位置拉一个链表，把冲突的元素放进去。

除此之外，还有一些常见的解决冲突的办法：

开放定址法 ：开放定址法就是从冲突的位置再接着往下找，给冲突元素找个空位。

找到空闲位置的方法也有很多种：

- 线行探查法: 从冲突的位置开始，依次判断下一个位置是否空闲，直至找到空闲位置
- 平方探查法: 从冲突的位置x开始，第一次增加1^2 个位置，第二次增加2^2 ...，直
  至找到空闲的位置
  ......

再哈希法：换种哈希函数，重新计算冲突元素的地址。
建立公共溢出区：再建一个数组，把冲突的元素放进去。

HashMap JDK1.8优化

1. 数据结构 ：数组 + 链表改成了数组 + 链表或红黑树
原因：发生 hash 冲突，元素会存入链表，链表过长转为红黑树，将时间复杂度由O(n)降为O(logn)
2. 链表插入方式 ：链表的插入方式从头插法改成了尾插法
简单说就是插入时，如果数组位置上已经有元素，1.7 将新元素放到数组中，原始节点作为新节点的后继节点，1.8 遍历链表，将元素放置到链表的最后。
原因：因为 1.7 头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环。
3. 扩容rehash ：扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8 采用更简单的判断逻辑，不需要重新通过哈希函数计算位置，新的位置不变或索引 + 新增容量大小。
原因：提高扩容的效率，更快地扩容。
4. 扩容时机 ：在插入时，1.7 先判断是否需要扩容，再插入，1.8 先进行插入，插入完成再判断是否需要扩容；
5. 散列函数 ：1.7 做了四次移位和四次异或，jdk1.8只做一次。
原因：做 4 次的话，边际效用也不大，改为一次，提升效率。

HashMap 手写实现

我们实现的简单的HashMap命名为ThirdHashMap，先确定整体的设计：

散列函数：hashCode()+除留余数法
冲突解决：链地址法

整体结构如下：

自定义HashMap整体结构

内部节点类

我们需要定义一个节点来作为具体数据的载体，它不仅要承载键值对，同样还得作为单链表的节点：

/**
    * 节点类
    *
    * @param <K>
    * @param <V>
    */
   class Node<K, V> {
       //键值对
       private K key;
       private V value;

       //链表，后继
       private Node<K, V> next;

       public Node(K key, V value) {
           this.key = key;
           this.value = value;
       }

       public Node(K key, V value, Node<K, V> next) {
           this.key = key;
           this.value = value;
           this.next = next;
       }
   }

成员变量

主要有四个成员变量，其中桶数组作为装载数据元素的结构：

//默认容量
   final int DEFAULT_CAPACITY = 16;
   //负载因子
   final float LOAD_FACTOR = 0.75f;
   //HashMap的大小
   private int size;
   //桶数组
   Node<K, V>[] buckets;

构造方法

构造方法有两个，无参构造方法，桶数组默认容量，有参指定桶数组容量。

/**
     * 无参构造器，设置桶数组默认容量
     */
    public ThirdHashMap() {
        buckets = new Node[DEFAULT_CAPACITY];
        size = 0;
    }

    /**
     * 有参构造器，指定桶数组容量
     *
     * @param capacity
     */
    public ThirdHashMap(int capacity) {
        buckets = new Node[capacity];
        size = 0;
    }

散列函数

散列函数，就是我们前面说的hashCode()和数组长度取余。

/**
     * 哈希函数，获取地址
     *
     * @param key
     * @return
     */
    private int getIndex(K key, int length) {
        //获取hash code
        int hashCode = key.hashCode();
        //和桶数组长度取余
        int index = hashCode % length;
        return Math.abs(index);
    }

put方法

我用了一个putval方法来完成实际的逻辑，这是因为扩容也会用到这个方法。

大概的逻辑：

获取元素插入位置
当前位置为空，直接插入
位置不为空，发生冲突，遍历链表
如果元素key和节点相同，覆盖，否则新建节点插入链表头部

/**
     * put方法
     *
     * @param key
     * @param value
     * @return
     */
    public void put(K key, V value) {
        //判断是否需要进行扩容
        if (size >= buckets.length * LOAD_FACTOR) resize();
        putVal(key, value, buckets);
    }

    /**
     * 将元素存入指定的node数组
     *
     * @param key
     * @param value
     * @param table
     */
    private void putVal(K key, V value, Node<K, V>[] table) {
        //获取位置
        int index = getIndex(key, table.length);
        Node node = table[index];
        //插入的位置为空
        if (node == null) {
            table[index] = new Node<>(key, value);
            size++;
            return;
        }
        //插入位置不为空，说明发生冲突，使用链地址法,遍历链表
        while (node != null) {
            //如果key相同，就覆盖掉
            if ((node.key.hashCode() == key.hashCode())
                    && (node.key == key || node.key.equals(key))) {
                node.value = value;
                return;
            }
            node = node.next;
        }
        //当前key不在链表中，插入链表头部
        Node newNode = new Node(key, value, table[index]);
        table[index] = newNode;
        size++;
    }

扩容方法

扩容的大概过程：

创建两倍容量的新数组
将当前桶数组的元素重新散列到新的数组
新数组置为map的桶数组

/**
    * 扩容
    */
   private void resize() {
       //创建一个两倍容量的桶数组
       Node<K, V>[] newBuckets = new Node[buckets.length * 2];
       //将当前元素重新散列到新的桶数组
       rehash(newBuckets);
       buckets = newBuckets;
   }

   /**
    * 重新散列当前元素
    *
    * @param newBuckets
    */
   private void rehash(Node<K, V>[] newBuckets) {
       //map大小重新计算
       size = 0;
       //将旧的桶数组的元素全部刷到新的桶数组里
       for (int i = 0; i < buckets.length; i++) {
           //为空，跳过
           if (buckets[i] == null) {
               continue;
           }
           Node<K, V> node = buckets[i];
           while (node != null) {
               //将元素放入新数组
               putVal(node.key, node.value, newBuckets);
               node = node.next;
           }
       }
   }

get方法

get方法就比较简单，通过散列函数获取地址，这里我省去了有没有成链表的判断，直接查找链表。

/**
     * 获取元素
     *
     * @param key
     * @return
     */
    public V get(K key) {
        //获取key对应的地址
        int index = getIndex(key, buckets.length);
        if (buckets[index] == null) return null;
        Node<K, V> node = buckets[index];
        //查找链表
        while (node != null) {
            if ((node.key.hashCode() == key.hashCode())
                    && (node.key == key || node.key.equals(key))) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

HashMap 的常见遍历方式?

随着 JDK 1.8 Streams API 的发布，使得 HashMap 拥有了更多的遍历的方式，但应该选择那种遍历方式？反而成了一个问题。

本文先从 HashMap 的遍历方法讲起，然后再从性能、原理以及安全性等方面，来分析 HashMap 各种遍历方式的优势与不足，本文主要内容如下图所示：

遍历方式

HashMap 遍历从大的方向来说，可分为以下 4 类：

迭代器（Iterator）方式遍历；
For Each 方式遍历；
Lambda 表达式遍历（JDK 1.8+）;
Streams API 遍历（JDK 1.8+）。

但每种类型下又有不同的实现方式，因此具体的遍历方式又可以分为以下 7 种：

使用迭代器（Iterator）EntrySet 的方式进行遍历；
使用迭代器（Iterator）KeySet 的方式进行遍历；
使用 For Each EntrySet 的方式进行遍历；
使用 For Each KeySet 的方式进行遍历；
使用 Lambda 表达式的方式进行遍历；
使用 Streams API 单线程的方式进行遍历；
使用 Streams API 多线程的方式进行遍历。

接下来我们来看每种遍历方式的具体实现代码。

1.迭代器 EntrySet

public class HashMapTest {

   public static void main(String[] args) {

     // 创建并赋值 HashMap

    Map<Integer, String> map = new HashMap();

    map.put(1, "Java");

    map.put(2, "JDK");

    map.put(3, "Spring Framework");

    map.put(4, "MyBatis framework");

    map.put(5, "Java中文社群");

     // 遍历

     Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();

     while (iterator.hasNext()) {

       Map.Entry<Integer, String> entry = iterator.next();

       System.out.println(entry.getKey());

       System.out.println(entry.getValue());

     }

   }

}

以上程序的执行结果为：

   1

   Java

   2

  JDK

   3

   Spring Framework

   4

   MyBatis framework

   5

   Java中文社群

2.迭代器 KeySet

public class HashMapTest {

   public static void main(String[] args) {

     // 创建并赋值 HashMap

     Map<Integer, String> map = new HashMap();

    map.put(1, "Java");

    map.put(2, "JDK");

    map.put(3, "Spring Framework");

    map.put(4, "MyBatis framework");

    map.put(5, "Java中文社群");

     // 遍历

     Iterator<Integer> iterator = map.keySet().iterator();

     while (iterator.hasNext()) {

       Integer key = iterator.next();

       System.out.println(key);

       System.out.println(map.get(key));

     }

   }

}

以上程序的执行结果为：

   1

   Java

   2

  JDK

   3

   Spring Framework

   4

   MyBatis framework

   5

   Java中文社群

3.ForEach EntrySet

public class HashMapTest {

   public static void main(String[] args) {

     // 创建并赋值 HashMap

     Map<Integer, String> map = new HashMap();

    map.put(1, "Java");

    map.put(2, "JDK");

    map.put(3, "Spring Framework");

    map.put(4, "MyBatis framework");

    map.put(5, "Java中文社群");

     // 遍历

     for (Map.Entry<Integer, String> entry : map.entrySet()) {

       System.out.println(entry.getKey());

       System.out.println(entry.getValue());

     }

   }

}

以上程序的执行结果为：

   1

   Java

   2

  JDK

   3

   Spring Framework

   4

   MyBatis framework

   5

   Java中文社群

4.ForEach KeySet

public class HashMapTest {

   public static void main(String[] args) {

     // 创建并赋值 HashMap

     Map<Integer, String> map = new HashMap();

    map.put(1, "Java");

    map.put(2, "JDK");

   map.put(3, "Spring Framework");

    map.put(4, "MyBatis framework");

    map.put(5, "Java中文社群");

     // 遍历

     for (Integer key : map.keySet()) {

       System.out.println(key);

       System.out.println(map.get(key));

     }

   }

}

以上程序的执行结果为：

   1

   Java

   2

  JDK

   3

   Spring Framework

   4

   MyBatis framework

   5

   Java中文社群

5.Lambda

public class HashMapTest {

   public static void main(String[] args) {

     // 创建并赋值 HashMap

     Map<Integer, String> map = new HashMap();

    map.put(1, "Java");

    map.put(2, "JDK");

    map.put(3, "Spring Framework");

    map.put(4, "MyBatis framework");

    map.put(5, "Java中文社群");

     // 遍历

   map.forEach((key, value) -> {

       System.out.println(key);

       System.out.println(value);

     });

   }

}

以上程序的执行结果为：

   1

   Java

   2

  JDK

   3

   Spring Framework

   4

   MyBatis framework

   5

   Java中文社群

6.Streams API 单线程

public class HashMapTest {

   public static void main(String[] args) {

     // 创建并赋值 HashMap

     Map<Integer, String> map = new HashMap();

    map.put(1, "Java");

    map.put(2, "JDK");

    map.put(3, "Spring Framework");

    map.put(4, "MyBatis framework");

    map.put(5, "Java中文社群");

     // 遍历

    map.entrySet().stream().forEach((entry) -> {

       System.out.println(entry.getKey());

       System.out.println(entry.getValue());

     });

   }

}

以上程序的执行结果为：

   1

   Java

   2

  JDK

   3

   Spring Framework

   4

   MyBatis framework

   5

   Java中文社群

7.Streams API 多线程

public class HashMapTest {

   public static void main(String[] args) {

     // 创建并赋值 HashMap

     Map<Integer, String> map = new HashMap();

    map.put(1, "Java");

    map.put(2, "JDK");

    map.put(3, "Spring Framework");

    map.put(4, "MyBatis framework");

    map.put(5, "Java中文社群");

     // 遍历

    map.entrySet().parallelStream().forEach((entry) -> {

       System.out.println(entry.getKey());

       System.out.println(entry.getValue());

     });

   }

}

以上程序的执行结果为：

   4

   MyBatis framework

   5

   Java中文社群

   1

   Java

   2

  JDK

   3

   Spring Framework

性能测试

接下来我们使用 Oracle 官方提供的性能测试工具 JMH（Java Microbenchmark Harness，JAVA 微基准测试套件）来测试一下这 7 种循环的性能。

首先，我们先要引入 JMH 框架，在 pom.xml 文件中添加如下配置：

然后编写测试代码，如下所示：

@BenchmarkMode(Mode.AverageTime) // 测试完成时间

@OutputTimeUnit(TimeUnit.NANOSECONDS)

@Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // 预热 2 轮，每次 1s

@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS) // 测试 5 轮，每次 1s

@Fork(1) // fork 1 个线程

@State(Scope.Thread) // 每个测试线程一个实例

public class HashMapCycleTest {

   static Map<Integer, String> map = new HashMap() {{

     // 添加数据

     for (int i = 0; i < 100; i++) {

       put(i, "val:" + i);

     }

   }};

   public static void main(String[] args) throws RunnerException {

     // 启动基准测试

    Options opt = new OptionsBuilder()

         .include(HashMapCycle.class.getSimpleName()) // 要导入的测试类

         .output("/Users/admin/Desktop/jmh-map.log") // 输出测试结果的文件

         .build();

     new Runner(opt).run(); // 执行测试

   }

   @Benchmark

   public void entrySet() {

     // 遍历

     Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();

     while (iterator.hasNext()) {

       Map.Entry<Integer, String> entry = iterator.next();

       Integer k = entry.getKey();

       String v = entry.getValue();

     }

   }

   @Benchmark

   public void forEachEntrySet() {

     // 遍历

     for (Map.Entry<Integer, String> entry : map.entrySet()) {

       Integer k = entry.getKey();

       String v = entry.getValue();

     }

   }

   @Benchmark

   public void keySet() {

     // 遍历

     Iterator<Integer> iterator = map.keySet().iterator();

     while (iterator.hasNext()) {

       Integer k = iterator.next();

       String v = map.get(k);

     }

   }

   @Benchmark

   public void forEachKeySet() {

     // 遍历

     for (Integer key : map.keySet()) {

       Integer k = key;

       String v = map.get(k);

     }

   }

   @Benchmark

   public void lambda() {

     // 遍历

    map.forEach((key, value) -> {

       Integer k = key;

       String v = value;

     });

   }

   @Benchmark

   public void streamApi() {

     // 单线程遍历

    map.entrySet().stream().forEach((entry) -> {

       Integer k = entry.getKey();

       String v = entry.getValue();

     });

   }

   public void parallelStreamApi() {

     // 多线程遍历

    map.entrySet().parallelStream().forEach((entry) -> {

       Integer k = entry.getKey();

       String v = entry.getValue();

     });

   }

}

所有被添加了 @Benchmark 注解的方法都会被测试，因为 parallelStream 为多线程版本性能一定是最好的，所以就不参与测试了，其他 6 个方法的测试结果如下：

其中 Units 为 ns/op 意思是执行完成时间（单位为纳秒），而 Score 列为平均执行时间， ± 符号表示误差。从以上结果可以看出，两个 entrySet 的性能相近，并且执行速度最快，接下来是 stream ，然后是两个 keySet，性能最差的是 KeySet 。

注：以上结果基于测试环境：JDK 1.8 / Mac mini (2018) / Idea 2020.1

结论

从以上结果可以看出 entrySet 的性能比 keySet 的性能高出了一倍之多，因此我们应该尽量使用 entrySet 来实现 Map 集合的遍历。

字节码分析

要理解以上的测试结果，我们需要把所有遍历代码通过 javac 编译成字节码来看具体的原因。

编译后，我们使用 Idea 打开字节码，内容如下：

//

// Source code recreated from a .class file by IntelliJ IDEA

// (powered by Fernflower decompiler)

//

package com.example;

import java.util.HashMap;

import java.util.Iterator;

import java.util.Map;

import java.util.Map.Entry;

public class HashMapTest {

   static Map<Integer, String> map = new HashMap() {

     {

       for(int var1 = 0; var1 < 2; ++var1) {

         this.put(var1, "val:" + var1);

       }

     }

   };

   public HashMapTest() {

   }

   public static void main(String[] var0) {

     entrySet();

     keySet();

     forEachEntrySet();

     forEachKeySet();

     lambda();

     streamApi();

     parallelStreamApi();

   }

   public static void entrySet() {

     Iterator var0 = map.entrySet().iterator();

     while(var0.hasNext()) {

       Entry var1 = (Entry)var0.next();

       System.out.println(var1.getKey());

       System.out.println((String)var1.getValue());

     }

   }

   public static void keySet() {

     Iterator var0 = map.keySet().iterator();

     while(var0.hasNext()) {

       Integer var1 = (Integer)var0.next();

       System.out.println(var1);

       System.out.println((String)map.get(var1));

     }

   }

   public static void forEachEntrySet() {

     Iterator var0 = map.entrySet().iterator();

     while(var0.hasNext()) {

       Entry var1 = (Entry)var0.next();

       System.out.println(var1.getKey());

       System.out.println((String)var1.getValue());

     }

   }

   public static void forEachKeySet() {

     Iterator var0 = map.keySet().iterator();

     while(var0.hasNext()) {

      Integer var1 = (Integer)var0.next();

       System.out.println(var1);

       System.out.println((String)map.get(var1));

     }

   }

   public static void lambda() {

    map.forEach((var0, var1) -> {

       System.out.println(var0);

       System.out.println(var1);

     });

   }

   public static void streamApi() {

    map.entrySet().stream().forEach((var0) -> {

       System.out.println(var0.getKey());

       System.out.println((String)var0.getValue());

     });

   }

   public static void parallelStreamApi() {

    map.entrySet().parallelStream().forEach((var0) -> {

       System.out.println(var0.getKey());

       System.out.println((String)var0.getValue());

     });

   }

}

从结果可以看出，除了 Lambda 和 Streams API 之外，通过迭代器循环和 for 循环的遍历的 EntrySet 最终生成的代码是一样的，他们都是在循环中创建了一个遍历对象 Entry ，代码如下：

public static void entrySet() {

   Iterator var0 = map.entrySet().iterator();

   while(var0.hasNext()) {

     Entry var1 = (Entry)var0.next();

     System.out.println(var1.getKey());

     System.out.println((String)var1.getValue());

   }

}

public static void forEachEntrySet() {

   Iterator var0 = map.entrySet().iterator();

   while(var0.hasNext()) {

     Entry var1 = (Entry)var0.next();

     System.out.println(var1.getKey());

     System.out.println((String)var1.getValue());

   }

}

而 KeySet 的代码也是类似的，如下所示：

public static void keySet() {

   Iterator var0 = map.keySet().iterator();

   while(var0.hasNext()) {

     Integer var1 = (Integer)var0.next();

     System.out.println(var1);

     System.out.println((String)map.get(var1));

   }

} 

public static void forEachKeySet() {

   Iterator var0 = map.keySet().iterator();

   while(var0.hasNext()) {

     Integer var1 = (Integer)var0.next();

     System.out.println(var1);

     System.out.println((String)map.get(var1));

   }

}

所以我们在使用迭代器或是 for 循环 EntrySet 时，他们的性能都是相同的，因为他们最终生成的字节码基本都是一样的；同理 KeySet 的两种遍历方式也是类似的。

性能分析

EntrySet 之所以比 KeySet 的性能高是因为，KeySet 在循环时使用了 map.get(key)，而 map.get(key) 相当于又遍历了一遍 Map 集合去查询 key 所对应的值。为什么要用“又”这个词？那是因为在使用迭代器或者 for 循环时，其实已经遍历了一遍 Map 集合了，因此再使用 map.get(key) 查询时，相当于遍历了两遍。

而 EntrySet 只遍历了一遍 Map 集合，之后通过代码“Entry<Integer, String> entry = iterator.next()”把对象的 key 和 value 值都放入到了 Entry 对象中，因此再获取 key 和 value 值时就无需再遍历 Map 集合，只需要从 Entry 对象中取值就可以了。

所以，EntrySet 的性能比 KeySet 的性能高出了一倍，因为 KeySet 相当于循环了两遍 Map 集合，而 EntrySet 只循环了一遍。

安全性测试

从上面的性能测试结果和原理分析，我想大家应该选用那种遍历方式，已经心中有数的，而接下来我们就从「安全」的角度入手，来分析那种遍历方式更安全。

我们把以上遍历划分为四类进行测试：迭代器方式、For 循环方式、Lambda 方式和 Stream 方式，测试代码如下。

1.迭代器方式

Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();

while (iterator.hasNext()) {

   Map.Entry<Integer, String> entry = iterator.next();

   if (entry.getKey() == 1) {

     // 删除

     System.out.println("del:" + entry.getKey());

    iterator.remove();

   } else {

     System.out.println("show:" + entry.getKey());

   }

}

以上程序的执行结果：

  show:0

  del:1

  show:2

测试结果：迭代器中循环删除数据安全。

2.For 循环方式

for (Map.Entry<Integer, String> entry : map.entrySet()) {

   if (entry.getKey() == 1) {

     // 删除

     System.out.println("del:" + entry.getKey());

    map.remove(entry.getKey());

   } else {

     System.out.println("show:" + entry.getKey());

   }

}

以上程序的执行结果：

测试结果：For 循环中删除数据非安全。

3.Lambda 方式

map.forEach((key, value) -> {

   if (key == 1) {

     System.out.println("del:" + key);

    map.remove(key);

   } else {

     System.out.println("show:" + key);

   }

});

以上程序的执行结果：

测试结果：Lambda 循环中删除数据非安全。

Lambda 删除的正确方式：

// 根据 map 中的 key 去判断删除

map.keySet().removeIf(key -> key == 1);

map.forEach((key, value) -> {

   System.out.println("show:" + key);

});

以上程序的执行结果：

  show:0

  show:2

从上面的代码可以看出，可以先使用 Lambda 的 removeIf 删除多余的数据，再进行循环是一种正确操作集合的方式。

4.Stream 方式

map.entrySet().stream().forEach((entry) -> {

   if (entry.getKey() == 1) {

     System.out.println("del:" + entry.getKey());

    map.remove(entry.getKey());

   } else {

     System.out.println("show:" + entry.getKey());

   }

});

以上程序的执行结果：

测试结果：Stream 循环中删除数据非安全。

Stream 循环的正确方式：

map.entrySet().stream().filter(m -> 1 != m.getKey()).forEach((entry) -> {

   if (entry.getKey() == 1) {

     System.out.println("del:" + entry.getKey());

   } else {

     System.out.println("show:" + entry.getKey());

   }

});

以上程序的执行结果：

  show:0

  show:2

从上面的代码可以看出，可以使用 Stream 中的 filter 过滤掉无用的数据，再进行遍历也是一种安全的操作集合的方式。

小结

我们不能在遍历中使用集合 map.remove() 来删除数据，这是非安全的操作方式，但我们可以使用迭代器的 iterator.remove() 的方法来删除数据，这是安全的删除集合的方式。同样的我们也可以使用 Lambda 中的 removeIf 来提前删除数据，或者是使用 Stream 中的 filter 过滤掉要删除的数据进行循环，这样都是安全的，当然我们也可以在 for 循环前删除数据在遍历也是线程安全的。

总结

本文我们讲了 HashMap 4 种遍历方式：迭代器、for、lambda、stream，以及具体的 7 种遍历方法，综合性能和安全性来看，我们应该尽量使用迭代器（Iterator）来遍历 EntrySet 的遍历方式来操作 Map 集合，这样就会既安全又高效了。

Hashtable

底层数据结构：Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；

实现线程安全的方式（重要）：

Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

Hashtable:

TreeMap

TreeMap基于红黑树（Red-Black tree）实现。映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。TreeMap的基本操作containsKey、get、put、remove方法，它的时间复杂度是log(N)。

TreeMap包含几个重要的成员变量：root、size、comparator。其中root是红黑树的根节点。它是Entry类型，Entry是红黑树的节点，它包含了红黑树的6个基本组成：key、value、left、right、parent和color。Entry节点根据Key排序，包含的内容是value。Entry中key比较大小是根据比较器comparator来进行判断的。size是红黑树的节点个数。

TreeMap 实现 SortedMap 接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的。如果使用排序的映射，建议使用 TreeMap。

在使用 TreeMap 时，key 必须实现 Comparable 接口或者在构造 TreeMap 传入自定义Comparator，否则会在运行时抛出 java.lang.ClassCastException 类型的异常。

LinkedHashMap

LinkedHashMap使用双向链表来维护key-value对的顺序（其实只需要考虑key的顺序），该链表负责维护Map的迭代顺序，迭代顺序与key-value对的插入顺序保持一致。

LinkedHashMap可以避免对HashMap、Hashtable里的key-value对进行排序（只要插入key-value对时保持顺序即可），同时又可避免使用TreeMap所增加的成本。

LinkedHashMap需要维护元素的插入顺序，因此性能略低于HashMap的性能。但因为它以链表来维护内部顺序，所以在迭代访问Map里的全部元素时将有较好的性能。

LinkedHashMap继承于HashMap，它在HashMap的基础上，通过维护一条双向链表，解决了HashMap不能随时保持遍历顺序和插入顺序一致的问题。在实现上，LinkedHashMap很多方法直接继承自HashMap，仅为维护双向链表重写了部分方法。

每当有新的键值对节点插入时，新节点最终会接在tail引用指向的节点后面。而tail引用则会移动到新的节点上，这样一个双向链表就建立起来了。

ConcurrentHashmap

ConcurrentHashmap的底层实现

ConcurrentHashmap线程安全在jdk1.7版本是基于分段锁实现，在jdk1.8是基于CAS+synchronized实现。

1.7 分段锁

从结构上说，1.7版本的ConcurrentHashMap采用分段锁机制，里面包含一个Segment数组，Segment继承于ReentrantLock，Segment则包含HashEntry的数组，HashEntry本身就是一个链表的结构，具有保存key、value的能力能指向下一个节点的指针。

实际上就是相当于每个Segment都是一个HashMap，默认的Segment长度是 16 ，也就是支持 16个线程的并发写，Segment之间相互不会受到影响。

put流程

当执行put操作时，会经历两个步骤：

判断是否需要扩容；
定位到添加元素的位置，将其放入 HashEntry 数组中。

插入过程会进行第一次 key 的 hash 来定位 Segment 的位置，如果该 Segment 还没有初始化，即通过 CAS 操作进行赋值，然后进行第二次 hash 操作，找到相应的 HashEntry 的位置，这里会利用继承过来的锁的特性，在将数据插入指定的 HashEntry 位置时（尾插法），会通过继承 ReentrantLock 的 tryLock() 方法尝试去获取锁，如果获取成功就直接插入相应的位置，如果已经有线程获取该Segment的锁，那当前线程会以自旋的方式去继续的调用 tryLock() 方法去获取锁，超过指定次数就挂起，等待唤醒。

get流程

Segment的get操作实现非常简单和高效，先经过一次再散列，然后使用这个散列值通过散列运算定位到 Segment，再通过散列算法定位到元素。get操作的高效之处在于整个get过程都不需要加锁，除非读到空的值才会加锁重读。原因就是将使用的共享变量定义成 volatile 类型。

1.8 CAS+synchronized

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

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

put流程

1. 首先计算hash，遍历node数组，如果node是空的话，就通过CAS+自旋的方式初始化node数组初始化：

1	tab = initTable();

node 数组初始化：

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 )) { //CAS
        操作
    try {
        if ((tab = table) == null || tab.length == 0 ) {
            int n = (sc > 0 )? sc : DEFAULT_CAPACITY;
            @SuppressWarnings("unchecked")
            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
            table = tab = nt;
            sc = n - (n >>> 2 );
    	}
    } finally {
    	sizeCtl = sc;
        }
            break;
        }
    }
	return tab;
}

2.如果当前数组位置是空则直接通过CAS自旋写入数据

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);
}

3. 如果hash==MOVED，说明需要扩容，执行扩容

1 2	else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f);

final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
    Node<K,V>[] nextTab; int sc;
    if (tab != null && (f instanceof ForwardingNode) &&
        (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
            int rs = resizeStamp(tab.length);
            while (nextTab == nextTable && table == tab &&
                (sc = sizeCtl) < 0 ) {
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                sc == rs + MAX_RESIZERS || transferIndex <= 0 )
                break;
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1 )) {
                transfer(tab, nextTab);
            break;
            }
        }
        return nextTab;
    }
    return table;
}

4. 如果都不满足，就使用synchronized写入数据，写入数据同样判断链表、红黑树，链表写入和HashMap的方式一样，key hash一样就覆盖，反之就尾插法，链表长度超过 8 就转换成红黑树

1
2
3

synchronized (f){
......
}

get查询

get很简单，和HashMap基本相同，通过key计算位置，table该位置key相同就返回，如果是红黑树按照红黑树获取，否则就遍历链表获取。

HashMap 和 Hashtable 的区别

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

HashMap 和 HashSet 区别

如果你看过 HashSet 源码的话就应该知道：**HashSet** 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

`HashMap`	`HashSet`
实现了 `Map` 接口	实现 `Set` 接口
存储键值对	仅存储对象
调用 `put()`向 map 中添加元素	调用 `add()`方法向 `Set` 中添加元素
`HashMap` 使用键（Key）计算 `hashcode`	`HashSet` 使用成员对象来计算 `hashcode` 值，对于两个对象来说 `hashcode` 可能相同，所以`equals()`方法用来判断对象的相等性

集合工具

Comparable 和 Comparator

comparable 接口实际上是出自java.lang包它有一个 **compareTo(Object obj)**方法用来排序

comparator接口实际上是出自 java.util 包它有一个**compare(Object obj1, Object obj2)**方法用来排序

一般我们需要对一个集合使用自定义排序时，我们就要重写compareTo()方法或compare()方法，当我们需要对某一个集合实现两种排序方式，比如一个 song 对象中的歌名和歌手名分别采用一种排序方法的话，我们可以重写compareTo()方法和使用自制的Comparator方法或者以两个 Comparator 来实现歌名排序和歌星名排序，第二种代表我们只能使用两个参数版的 Collections.sort().

Comparator 定制排序

ArrayList<Integer> arrayList = new ArrayList<Integer>();
       arrayList.add(-1);
       arrayList.add(3);
       arrayList.add(3);
       arrayList.add(-5);
       arrayList.add(7);
       arrayList.add(4);
       arrayList.add(-9);
       arrayList.add(-7);
       System.out.println("原始数组:");
       System.out.println(arrayList);
       // void reverse(List list)：反转
       Collections.reverse(arrayList);
       System.out.println("Collections.reverse(arrayList):");
       System.out.println(arrayList);

       // void sort(List list),按自然排序的升序排序
       Collections.sort(arrayList);
       System.out.println("Collections.sort(arrayList):");
       System.out.println(arrayList);
       // 定制排序的用法
       Collections.sort(arrayList, new Comparator<Integer>() {

           @Override
           public int compare(Integer o1, Integer o2) {
               return o2.compareTo(o1);
           }
       });
       System.out.println("定制排序后：");
       System.out.println(arrayList);

Output:

原始数组:
[-1, 3, 3, -5, 7, 4, -9, -7]
Collections.reverse(arrayList):
[-7, -9, 4, 7, -5, 3, 3, -1]
Collections.sort(arrayList):
[-9, -7, -5, -1, 3, 3, 4, 7]
定制排序后：
[7, 4, 3, 3, -1, -5, -7, -9]

重写 compareTo 方法实现按年龄来排序

// person对象没有实现Comparable接口，所以必须实现，这样才不会出错，才可以使treemap中的数据按顺序排列
// 前面一个例子的String类已经默认实现了Comparable接口，详细可以查看String类的API文档，另外其他
// 像Integer类等都已经实现了Comparable接口，所以不需要另外实现了

public  class Person implements Comparable<Person> {
    private String name;
    private int age;
    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }

    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;
    }

    /**
     * T重写compareTo方法实现按年龄来排序
     */
    @Override
    public int compareTo(Person o) {
        if (this.age > o.getAge()) {
            return 1;
        }
        if (this.age < o.getAge()) {
            return -1;
        }
        return 0;
        }
}

Output：

5-小红
10-王五
20-李四
30-张三

Collections 工具类

Collections 工具类常用方法:

排序
查找,替换操作
同步控制(不推荐，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合)

排序操作

void reverse(List list)//反转
void shuffle(List list)//随机排序
void sort(List list)//按自然排序的升序排序
void sort(List list, Comparator c)//定制排序，由Comparator控制排序逻辑
void swap(List list, int i , int j)//交换两个索引位置的元素
void rotate(List list, int distance)//旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面

查找,替换操作

int binarySearch(List list, Object key)//对List进行二分查找，返回索引，注意List必须是有序的
int max(Collection coll)//根据元素的自然顺序，返回最大的元素。 类比int min(Collection coll)
int max(Collection coll, Comparator c)//根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)
void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素
int frequency(Collection c, Object o)//统计元素出现次数
int indexOfSubList(List list, List target)//统计target在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target)
boolean replaceAll(List list, Object oldVal, Object newVal)//用新元素替换旧元素

同步控制

Collections 提供了多个synchronizedXxx()方法·，该方法可以将指定集合包装成线程同步的集合，从而解决多线程并发访问集合时的线程安全问题。

我们知道 HashSet，TreeSet，ArrayList,LinkedList,HashMap,TreeMap 都是线程不安全的。Collections 提供了多个静态方法可以把他们包装成线程同步的集合。

最好不要用下面这些方法，效率非常低，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合。

方法如下：

synchronizedCollection(Collection<T>  c) //返回指定 collection 支持的同步（线程安全的）collection。
synchronizedList(List<T> list)//返回指定列表支持的同步（线程安全的）List。
synchronizedMap(Map<K,V> m) //返回由指定映射支持的同步（线程安全的）Map。
synchronizedSet(Set<T> s) //返回指定 set 支持的同步（线程安全的）set。

Stream

Stream概述

Java 8 是一个非常成功的版本，这个版本新增的Stream，配合同版本出现的 Lambda ，给我们操作[集合]（Collection）提供了极大的便利。

那么什么是Stream？

Stream将要处理的元素集合看作一种流，在流的过程中，借助Stream API对流中的元素进行操作，比如：筛选、排序、聚合等。

Stream可以由数组或集合创建，对流的操作分为两种：

中间操作，每次返回一个新的流，可以有多个。
终端操作，每个流只能进行一次终端操作，终端操作结束后流无法再次使用。终端操作会产生一个新的集合或值。

另外，Stream有几个特性：

stream不存储数据，而是按照特定的规则对数据进行计算，一般会输出结果。
stream不会改变数据源，通常情况下会产生一个新的集合或一个值。
stream具有延迟执行特性，只有调用终端操作时，中间操作才会执行。

Stream的创建

Stream可以通过集合数组创建。

1、通过 java.util.Collection.stream() 方法用集合创建流

List<String> list = Arrays.asList("a", "b", "c");
// 创建一个顺序流
Stream<String> stream = list.stream();
// 创建一个并行流
Stream<String> parallelStream = list.parallelStream();

2、使用java.util.Arrays.stream(T[] array)方法用数组创建流

1 2	int[] array={1,3,5,6,8}; IntStream stream = Arrays.stream(array);

3、使用Stream的静态方法：of()、iterate()、generate()

Stream<Integer> stream = Stream.of(1, 2, 3, 4, 5, 6);

Stream<Integer> stream2 = Stream.iterate(0, (x) -> x + 3).limit(4);
stream2.forEach(System.out::println);

Stream<Double> stream3 = Stream.generate(Math::random).limit(3);
stream3.forEach(System.out::println);

输出结果：

0 3 6 9
0.6796156909271994
0.1914314208854283
0.8116932592396652

stream和parallelStream的简单区分： stream是顺序流，由主线程按顺序对流执行操作，而parallelStream是并行流，内部以多线程并行执行的方式对流进行操作，但前提是流中的数据处理没有顺序要求。例如筛选集合中的奇数，两者的处理不同之处：

如果流中的数据量足够大，并行流可以加快处速度。

除了直接创建并行流，还可以通过parallel()把顺序流转换成并行流：

1	Optional<Integer> findFirst = list.stream().parallel().filter(x->x>6).findFirst();

Stream的使用

在使用stream之前，先理解一个概念：Optional 。

Optional类是一个可以为null的容器对象。如果值存在则isPresent()方法会返回true，调用get()方法会返回该对象。
更详细说明请见：菜鸟教程Java 8 Optional类

接下来，大批代码向你袭来！我将用20个案例将Stream的使用整得明明白白，只要跟着敲一遍代码，就能很好地掌握。

案例使用的员工类

这是后面案例中使用的员工类：

List<Person> personList = new ArrayList<Person>();
personList.add(new Person("Tom", 8900, "male", "New York"));
personList.add(new Person("Jack", 7000, "male", "Washington"));
personList.add(new Person("Lily", 7800, "female", "Washington"));
personList.add(new Person("Anni", 8200, "female", "New York"));
personList.add(new Person("Owen", 9500, "male", "New York"));
personList.add(new Person("Alisa", 7900, "female", "New York"));

class Person {
	private String name;  // 姓名
	private int salary; // 薪资
	private int age; // 年龄
	private String sex; //性别
	private String area;  // 地区

	// 构造方法
	public Person(String name, int salary, int age,String sex,String area) {
		this.name = name;
		this.salary = salary;
		this.age = age;
		this.sex = sex;
		this.area = area;
	}
	// 省略了get和set，请自行添加

}

遍历/匹配（foreach/find/match）

Stream也是支持类似集合的遍历和匹配元素的，只是Stream中的元素是以Optional类型存在的。Stream的遍历、匹配非常简单。

在这里插入图片描述

// import已省略，请自行添加，后面代码亦是

public class StreamTest {
	public static void main(String[] args) {
        List<Integer> list = Arrays.asList(7, 6, 9, 3, 8, 2, 1);

        // 遍历输出符合条件的元素
        list.stream().filter(x -> x > 6).forEach(System.out::println);
        // 匹配第一个
        Optional<Integer> findFirst = list.stream().filter(x -> x > 6).findFirst();
        // 匹配任意（适用于并行流）
        Optional<Integer> findAny = list.parallelStream().filter(x -> x > 6).findAny();
        // 是否包含符合特定条件的元素
        boolean anyMatch = list.stream().anyMatch(x -> x > 6);
        System.out.println("匹配第一个值：" + findFirst.get());
        System.out.println("匹配任意一个值：" + findAny.get());
        System.out.println("是否存在大于6的值：" + anyMatch);
    }
}

筛选（filter）

筛选，是按照一定的规则校验流中的元素，将符合条件的元素提取到新的流中的操作。

在这里插入图片描述

案例一：筛选出Integer集合中大于7的元素，并打印出来

public class StreamTest {
	public static void main(String[] args) {
		List<Integer> list = Arrays.asList(6, 7, 3, 8, 1, 2, 9);
		Stream<Integer> stream = list.stream();
		stream.filter(x -> x > 7).forEach(System.out::println);
	}
}

预期结果：

8 9

案例二：筛选员工中工资高于8000的人，并形成新的集合。 形成新集合依赖collect（收集），后文有详细介绍。

public class StreamTest {
	public static void main(String[] args) {
		List<Person> personList = new ArrayList<Person>();
		personList.add(new Person("Tom", 8900, 23, "male", "New York"));
		personList.add(new Person("Jack", 7000, 25, "male", "Washington"));
		personList.add(new Person("Lily", 7800, 21, "female", "Washington"));
		personList.add(new Person("Anni", 8200, 24, "female", "New York"));
		personList.add(new Person("Owen", 9500, 25, "male", "New York"));
		personList.add(new Person("Alisa", 7900, 26, "female", "New York"));

		List<String> fiterList = personList.stream().filter(x -> x.getSalary() > 8000).map(Person::getName)
				.collect(Collectors.toList());
		System.out.print("薪资高于8000美元的员工：" + fiterList);
	}
}

运行结果：

1	薪资高于8000美元的员工：[Tom, Anni, Owen]

聚合（max/min/count)

max、min、count这些字眼你一定不陌生，没错，在mysql中我们常用它们进行数据统计。Java stream中也引入了这些概念和用法，极大地方便了我们对集合、数组的数据统计工作。

在这里插入图片描述

案例一：获取String集合中最长的元素。

public class StreamTest {
	public static void main(String[] args) {
		List<String> list = Arrays.asList("adnm", "admmt", "pot", "xbangd", "weoujgsd");

		Optional<String> max = list.stream().max(Comparator.comparing(String::length));
		System.out.println("最长的字符串：" + max.get());
	}
}

输出结果：

1	最长的字符串：weoujgsd

案例二：获取Integer集合中的最大值。

public class StreamTest {
	public static void main(String[] args) {
		List<Integer> list = Arrays.asList(7, 6, 9, 4, 11, 6);

		// 自然排序
		Optional<Integer> max = list.stream().max(Integer::compareTo);
		// 自定义排序（从大到小排序）
		Optional<Integer> max2 = list.stream().max((o1, o2) -> o2 - o1);
		System.out.println("自然排序的最大值：" + max.get());
		System.out.println("自定义排序的最大值：" + max2.get());
	}
}

输出结果：

1 2	自然排序的最大值：11 自定义排序的最大值：4

案例三：获取员工薪资最高的人。

public class StreamTest {
	public static void main(String[] args) {
		List<Person> personList = new ArrayList<Person>();
		personList.add(new Person("Tom", 8900, 23, "male", "New York"));
		personList.add(new Person("Jack", 7000, 25, "male", "Washington"));
		personList.add(new Person("Lily", 7800, 21, "female", "Washington"));
		personList.add(new Person("Anni", 8200, 24, "female", "New York"));
		personList.add(new Person("Owen", 9500, 25, "male", "New York"));
		personList.add(new Person("Alisa", 7900, 26, "female", "New York"));

		Optional<Person> max = personList.stream().max(Comparator.comparingInt(Person::getSalary));
		System.out.println("员工薪资最大值：" + max.get().getSalary());
	}
}

输出结果：

1	员工薪资最大值：9500

案例四：计算Integer集合中大于6的元素的个数。

import java.util.Arrays;
import java.util.List;

public class StreamTest {
	public static void main(String[] args) {
		List<Integer> list = Arrays.asList(7, 6, 4, 8, 2, 11, 9);

		long count = list.stream().filter(x -> x > 6).count();
		System.out.println("list中大于6的元素个数：" + count);
	}
}

输出结果：

1	list中大于6的元素个数：4

映射(map/flatMap)

映射，可以将一个流的元素按照一定的映射规则映射到另一个流中。分为map和flatMap：

map：接收一个函数作为参数，该函数会被应用到每个元素上，并将其映射成一个新的元素。
flatMap：接收一个函数作为参数，将流中的每个值都换成另一个流，然后把所有流连接成一个流。

在这里插入图片描述

案例一：英文字符串数组的元素全部改为大写。整数数组每个元素+3。

public class StreamTest {
	public static void main(String[] args) {
		String[] strArr = { "abcd", "bcdd", "defde", "fTr" };
		List<String> strList = Arrays.stream(strArr).map(String::toUpperCase).collect(Collectors.toList());

		List<Integer> intList = Arrays.asList(1, 3, 5, 7, 9, 11);
		List<Integer> intListNew = intList.stream().map(x -> x + 3).collect(Collectors.toList());

		System.out.println("每个元素大写：" + strList);
		System.out.println("每个元素+3：" + intListNew);
	}
}

输出结果：

1 2	每个元素大写：[ABCD, BCDD, DEFDE, FTR] 每个元素+3：[4, 6, 8, 10, 12, 14]

案例二：将员工的薪资全部增加1000。

public class StreamTest {
	public static void main(String[] args) {
		List<Person> personList = new ArrayList<Person>();
		personList.add(new Person("Tom", 8900, 23, "male", "New York"));
		personList.add(new Person("Jack", 7000, 25, "male", "Washington"));
		personList.add(new Person("Lily", 7800, 21, "female", "Washington"));
		personList.add(new Person("Anni", 8200, 24, "female", "New York"));
		personList.add(new Person("Owen", 9500, 25, "male", "New York"));
		personList.add(new Person("Alisa", 7900, 26, "female", "New York"));

		// 不改变原来员工集合的方式
		List<Person> personListNew = personList.stream().map(person -> {
			Person personNew = new Person(person.getName(), 0, 0, null, null);
			personNew.setSalary(person.getSalary() + 10000);
			return personNew;
		}).collect(Collectors.toList());
		System.out.println("一次改动前：" + personList.get(0).getName() + "-->" + personList.get(0).getSalary());
		System.out.println("一次改动后：" + personListNew.get(0).getName() + "-->" + personListNew.get(0).getSalary());

		// 改变原来员工集合的方式
		List<Person> personListNew2 = personList.stream().map(person -> {
			person.setSalary(person.getSalary() + 10000);
			return person;
		}).collect(Collectors.toList());
		System.out.println("二次改动前：" + personList.get(0).getName() + "-->" + personListNew.get(0).getSalary());
		System.out.println("二次改动后：" + personListNew2.get(0).getName() + "-->" + personListNew.get(0).getSalary());
	}
}

输出结果：

一次改动前：Tom–>8900
一次改动后：Tom–>18900
二次改动前：Tom–>18900
二次改动后：Tom–>18900

案例三：将两个字符数组合并成一个新的字符数组。

public class StreamTest {
	public static void main(String[] args) {
		List<String> list = Arrays.asList("m,k,l,a", "1,3,5,7");
		List<String> listNew = list.stream().flatMap(s -> {
			// 将每个元素转换成一个stream
			String[] split = s.split(",");
			Stream<String> s2 = Arrays.stream(split);
			return s2;
		}).collect(Collectors.toList());

		System.out.println("处理前的集合：" + list);
		System.out.println("处理后的集合：" + listNew);
	}
}

输出结果：

1 2	处理前的集合：[m-k-l-a, 1-3-5] 处理后的集合：[m, k, l, a, 1, 3, 5]

此外，map系列还有mapToInt、mapToLong、mapToDouble三个函数，它们以一个映射函数为入参，将流中每一个元素处理后生成一个新流。以mapToInt为例，看两个示例：

public static void main(String[] args)  {
	// 输出字符串集合中每个字符串的长度
    List<String> stringList = Arrays.asList("mu", "CSDN", "hello",
            "world", "quickly");
    stringList.stream().mapToInt(String::length).forEach(System.out::println);
    // 将int集合的每个元素增加1000
    List<Integer> integerList = Arrays.asList(4, 5, 2, 1, 6, 3);
    integerList.stream().mapToInt(x -> x + 1000).forEach(System.out::println);
}

mapToInt三个函数生成的新流，可以进行很多后续操作，比如求最大最小值、求和、求平均值：

public static void main(String[] args) {
    List<Double> doubleList = Arrays.asList(1.0, 2.0, 3.0, 4.0, 2.0);
    double average = doubleList.stream().mapToDouble(Number::doubleValue).average().getAsDouble();
    double sum = doubleList.stream().mapToDouble(Number::doubleValue).sum();
    double max = doubleList.stream().mapToDouble(Number::doubleValue).max().getAsDouble();
    System.out.println("平均值：" + average + "，总和：" + sum + "，最大值：" + max);
}

归约([reduce]

归约，也称缩减，顾名思义，是把一个流缩减成一个值，能实现对集合求和、求乘积和求最值操作。

案例一：求Integer集合的元素之和、乘积和最大值。

public class StreamTest {
	public static void main(String[] args) {
		List<Integer> list = Arrays.asList(1, 3, 2, 8, 11, 4);
		// 求和方式1
		Optional<Integer> sum = list.stream().reduce((x, y) -> x + y);
		// 求和方式2
		Optional<Integer> sum2 = list.stream().reduce(Integer::sum);
		// 求和方式3
		Integer sum3 = list.stream().reduce(0, Integer::sum);
		
		// 求乘积
		Optional<Integer> product = list.stream().reduce((x, y) -> x * y);

		// 求最大值方式1
		Optional<Integer> max = list.stream().reduce((x, y) -> x > y ? x : y);
		// 求最大值写法2
		Integer max2 = list.stream().reduce(1, Integer::max);

		System.out.println("list求和：" + sum.get() + "," + sum2.get() + "," + sum3);
		System.out.println("list求积：" + product.get());
		System.out.println("list求最大值：" + max.get() + "," + max2);
	}
}

输出结果：

1
2
3

list求和：29,29,29
list求积：2112
list求最大值：11,11

案例二：求所有员工的工资之和和最高工资。

public class StreamTest {
	public static void main(String[] args) {
		List<Person> personList = new ArrayList<Person>();
		personList.add(new Person("Tom", 8900, 23, "male", "New York"));
		personList.add(new Person("Jack", 7000, 25, "male", "Washington"));
		personList.add(new Person("Lily", 7800, 21, "female", "Washington"));
		personList.add(new Person("Anni", 8200, 24, "female", "New York"));
		personList.add(new Person("Owen", 9500, 25, "male", "New York"));
		personList.add(new Person("Alisa", 7900, 26, "female", "New York"));

		// 求工资之和方式1：
		Optional<Integer> sumSalary = personList.stream().map(Person::getSalary).reduce(Integer::sum);
		// 求工资之和方式2：
		Integer sumSalary2 = personList.stream().reduce(0, (sum, p) -> sum += p.getSalary(),
				(sum1, sum2) -> sum1 + sum2);
		// 求工资之和方式3：
		Integer sumSalary3 = personList.stream().reduce(0, (sum, p) -> sum += p.getSalary(), Integer::sum);

		// 求最高工资方式1：
		Integer maxSalary = personList.stream().reduce(0, (max, p) -> max > p.getSalary() ? max : p.getSalary(),
				Integer::max);
		// 求最高工资方式2：
		Integer maxSalary2 = personList.stream().reduce(0, (max, p) -> max > p.getSalary() ? max : p.getSalary(),
				(max1, max2) -> max1 > max2 ? max1 : max2);
		// 求最高工资方式3：
		Integer maxSalary3 = personList.stream().map(Person::getSalary).reduce(Integer::max).get();

		System.out.println("工资之和：" + sumSalary.get() + "," + sumSalary2 + "," + sumSalary3);
		System.out.println("最高工资：" + maxSalary + "," + maxSalary2 + "," + maxSalary3);
	}
}

输出结果：

1 2	工资之和：49300,49300,49300 最高工资：9500,9500

收集(collect)

collect，收集，可以说是内容最繁多、功能最丰富的部分了。从字面上去理解，就是把一个流收集起来，最终可以是收集成一个值也可以收集成一个新的集合。

collect主要依赖java.util.stream.Collectors类内置的静态方法。

归集(toList/toSet/toMap)

因为流不存储数据，那么在流中的数据完成处理后，需要将流中的数据重新归集到新的集合里。toList、toSet和toMap比较常用，另外还有toCollection、toConcurrentMap等复杂一些的用法。

下面用一个案例演示toList、toSet和toMap：

public class StreamTest {
	public static void main(String[] args) {
		List<Integer> list = Arrays.asList(1, 6, 3, 4, 6, 7, 9, 6, 20);
		List<Integer> listNew = list.stream().filter(x -> x % 2 == 0).collect(Collectors.toList());
		Set<Integer> set = list.stream().filter(x -> x % 2 == 0).collect(Collectors.toSet());

		List<Person> personList = new ArrayList<Person>();
		personList.add(new Person("Tom", 8900, 23, "male", "New York"));
		personList.add(new Person("Jack", 7000, 25, "male", "Washington"));
		personList.add(new Person("Lily", 7800, 21, "female", "Washington"));
		personList.add(new Person("Anni", 8200, 24, "female", "New York"));
		
		Map<?, Person> map = personList.stream().filter(p -> p.getSalary() > 8000)
				.collect(Collectors.toMap(Person::getName, p -> p));
		System.out.println("toList:" + listNew);
		System.out.println("toSet:" + set);
		System.out.println("toMap:" + map);
	}
}

运行结果：

1
2
3

toList：[6, 4, 6, 6, 20]
toSet：[4, 20, 6]
toMap：{Tom=mutest.Person@5fd0d5ae, Anni=mutest.Person@2d98a335}

统计(count/averaging)

Collectors提供了一系列用于数据统计的静态方法：

计数：count
平均值：averagingInt、averagingLong、averagingDouble
最值：maxBy、minBy
求和：summingInt、summingLong、summingDouble
统计以上所有：summarizingInt、summarizingLong、summarizingDouble

案例：统计员工人数、平均工资、工资总额、最高工资。

public class StreamTest {
	public static void main(String[] args) {
		List<Person> personList = new ArrayList<Person>();
		personList.add(new Person("Tom", 8900, 23, "male", "New York"));
		personList.add(new Person("Jack", 7000, 25, "male", "Washington"));
		personList.add(new Person("Lily", 7800, 21, "female", "Washington"));

		// 求总数
		Long count = personList.stream().collect(Collectors.counting());
		// 求平均工资
		Double average = personList.stream().collect(Collectors.averagingDouble(Person::getSalary));
		// 求最高工资
		Optional<Integer> max = personList.stream().map(Person::getSalary).collect(Collectors.maxBy(Integer::compare));
		// 求工资之和
		Integer sum = personList.stream().collect(Collectors.summingInt(Person::getSalary));
		// 一次性统计所有信息
		DoubleSummaryStatistics collect = personList.stream().collect(Collectors.summarizingDouble(Person::getSalary));

		System.out.println("员工总数：" + count);
		System.out.println("员工平均工资：" + average);
		System.out.println("员工工资总和：" + sum);
		System.out.println("员工工资所有统计：" + collect);
	}
}

运行结果：

员工总数：3
员工平均工资：7900.0
员工工资总和：23700
员工工资所有统计：DoubleSummaryStatistics{count=3, sum=23700.000000,min=7000.000000, average=7900.000000, max=8900.000000}

分组(partitioningBy/groupingBy)

区：将stream按条件分为两个Map，比如员工按薪资是否高于8000分为两部分。
分组：将集合分为多个Map，比如员工按性别分组。有单级分组和多级分组。

案例：将员工按薪资是否高于8000分为两部分；将员工按性别和地区分组

public class StreamTest {
	public static void main(String[] args) {
		List<Person> personList = new ArrayList<Person>();
		personList.add(new Person("Tom", 8900, "male", "New York"));
		personList.add(new Person("Jack", 7000, "male", "Washington"));
		personList.add(new Person("Lily", 7800, "female", "Washington"));
		personList.add(new Person("Anni", 8200, "female", "New York"));
		personList.add(new Person("Owen", 9500, "male", "New York"));
		personList.add(new Person("Alisa", 7900, "female", "New York"));

		// 将员工按薪资是否高于8000分组
        Map<Boolean, List<Person>> part = personList.stream().collect(Collectors.partitioningBy(x -> x.getSalary() > 8000));
        // 将员工按性别分组
        Map<String, List<Person>> group = personList.stream().collect(Collectors.groupingBy(Person::getSex));
        // 将员工先按性别分组，再按地区分组
        Map<String, Map<String, List<Person>>> group2 = personList.stream().collect(Collectors.groupingBy(Person::getSex, Collectors.groupingBy(Person::getArea)));
        System.out.println("员工按薪资是否大于8000分组情况：" + part);
        System.out.println("员工按性别分组情况：" + group);
        System.out.println("员工按性别、地区：" + group2);
	}
}

输出结果：

1
2
3

员工按薪资是否大于8000分组情况：{false=[mutest.Person@2d98a335, mutest.Person@16b98e56, mutest.Person@7ef20235], true=[mutest.Person@27d6c5e0, mutest.Person@4f3f5b24, mutest.Person@15aeb7ab]}
员工按性别分组情况：{female=[mutest.Person@16b98e56, mutest.Person@4f3f5b24, mutest.Person@7ef20235], male=[mutest.Person@27d6c5e0, mutest.Person@2d98a335, mutest.Person@15aeb7ab]}
员工按性别、地区：{female={New York=[mutest.Person@4f3f5b24, mutest.Person@7ef20235], Washington=[mutest.Person@16b98e56]}, male={New York=[mutest.Person@27d6c5e0, mutest.Person@15aeb7ab], Washington=[mutest.Person@2d98a335]}}

接合(joining)

joining可以将stream中的元素用特定的连接符（没有的话，则直接连接）连接成一个字符串。

public class StreamTest {
	public static void main(String[] args) {
		List<Person> personList = new ArrayList<Person>();
		personList.add(new Person("Tom", 8900, 23, "male", "New York"));
		personList.add(new Person("Jack", 7000, 25, "male", "Washington"));
		personList.add(new Person("Lily", 7800, 21, "female", "Washington"));

		String names = personList.stream().map(p -> p.getName()).collect(Collectors.joining(","));
		System.out.println("所有员工的姓名：" + names);
		List<String> list = Arrays.asList("A", "B", "C");
		String string = list.stream().collect(Collectors.joining("-"));
		System.out.println("拼接后的字符串：" + string);
	}
}

运行结果：

1 2	所有员工的姓名：Tom,Jack,Lily 拼接后的字符串：A-B-C

归约(reducing)

Collectors类提供的reducing方法，相比于stream本身的reduce方法，增加了对自定义归约的支持。

public class StreamTest {
	public static void main(String[] args) {
		List<Person> personList = new ArrayList<Person>();
		personList.add(new Person("Tom", 8900, 23, "male", "New York"));
		personList.add(new Person("Jack", 7000, 25, "male", "Washington"));
		personList.add(new Person("Lily", 7800, 21, "female", "Washington"));

		// 每个员工减去起征点后的薪资之和（这个例子并不严谨，但一时没想到好的例子）
		Integer sum = personList.stream().collect(Collectors.reducing(0, Person::getSalary, (i, j) -> (i + j - 5000)));
		System.out.println("员工扣税薪资总和：" + sum);

		// stream的reduce
		Optional<Integer> sum2 = personList.stream().map(Person::getSalary).reduce(Integer::sum);
		System.out.println("员工薪资总和：" + sum2.get());
	}
}

运行结果：

1 2	员工扣税薪资总和：8700 员工薪资总和：23700

排序(sorted)

sorted，中间操作。有两种排序：

sorted()：自然排序，流中元素需实现Comparable接口
sorted(Comparator com)：Comparator排序器自定义排序

案例：将员工按工资由高到低（工资一样则按年龄由大到小）排序

public class StreamTest {
	public static void main(String[] args) {
		List<Person> personList = new ArrayList<Person>();

		personList.add(new Person("Sherry", 9000, 24, "female", "New York"));
		personList.add(new Person("Tom", 8900, 22, "male", "Washington"));
		personList.add(new Person("Jack", 9000, 25, "male", "Washington"));
		personList.add(new Person("Lily", 8800, 26, "male", "New York"));
		personList.add(new Person("Alisa", 9000, 26, "female", "New York"));

		// 按工资升序排序（自然排序）
		List<String> newList = personList.stream().sorted(Comparator.comparing(Person::getSalary)).map(Person::getName)
				.collect(Collectors.toList());
		// 按工资倒序排序
		List<String> newList2 = personList.stream().sorted(Comparator.comparing(Person::getSalary).reversed())
				.map(Person::getName).collect(Collectors.toList());
		// 先按工资再按年龄升序排序
		List<String> newList3 = personList.stream()
				.sorted(Comparator.comparing(Person::getSalary).thenComparing(Person::getAge)).map(Person::getName)
				.collect(Collectors.toList());
		// 先按工资再按年龄自定义排序（降序）
		List<String> newList4 = personList.stream().sorted((p1, p2) -> {
			if (p1.getSalary() == p2.getSalary()) {
				return p2.getAge() - p1.getAge();
			} else {
				return p2.getSalary() - p1.getSalary();
			}
		}).map(Person::getName).collect(Collectors.toList());

		System.out.println("按工资升序排序：" + newList);
		System.out.println("按工资降序排序：" + newList2);
		System.out.println("先按工资再按年龄升序排序：" + newList3);
		System.out.println("先按工资再按年龄自定义降序排序：" + newList4);
	}
}

运行结果：

按工资升序排序：[Lily, Tom, Sherry, Jack, Alisa]
按工资降序排序：[Sherry, Jack, Alisa, Tom, Lily]
先按工资再按年龄升序排序：[Lily, Tom, Sherry, Jack, Alisa]
先按工资再按年龄自定义降序排序：[Alisa, Jack, Sherry, Tom, Lily]

提取/组合

流也可以进行合并、去重、限制、跳过等操作。

public class StreamTest {
	public static void main(String[] args) {
		String[] arr1 = { "a", "b", "c", "d" };
		String[] arr2 = { "d", "e", "f", "g" };

		Stream<String> stream1 = Stream.of(arr1);
		Stream<String> stream2 = Stream.of(arr2);
		// concat:合并两个流 distinct：去重
		List<String> newList = Stream.concat(stream1, stream2).distinct().collect(Collectors.toList());
		// limit：限制从流中获得前n个数据
		List<Integer> collect = Stream.iterate(1, x -> x + 2).limit(10).collect(Collectors.toList());
		// skip：跳过前n个数据
		List<Integer> collect2 = Stream.iterate(1, x -> x + 2).skip(1).limit(5).collect(Collectors.toList());

		System.out.println("流合并：" + newList);
		System.out.println("limit：" + collect);
		System.out.println("skip：" + collect2);
	}
}

运行结果：

1
2
3

流合并：[a, b, c, d, e, f, g]
limit：[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
skip：[3, 5, 7, 9, 11]

集合使用注意事项总结

集合判空

判断所有集合内部的元素是否为空，使用 isEmpty() 方法，而不是 size()==0 的方式。

这是因为 isEmpty() 方法的可读性更好，并且时间复杂度为 O(1)。

绝大部分我们使用的集合的 size() 方法的时间复杂度也是 O(1)，不过，也有很多复杂度不是 O(1) 的，比如 java.util.concurrent 包下的某些集合（ConcurrentLinkedQueue 、ConcurrentHashMap…）。

下面是 ConcurrentHashMap 的 size() 方法和 isEmpty() 方法的源码。

public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 :
            (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
            (int)n);
}
final 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;
}
public boolean isEmpty() {
    return sumCount() <= 0L; // ignore transient negative values
}

集合转 Map

阿里巴巴 Java 开发手册》的描述如下：

在使用 java.util.stream.Collectors 类的 toMap() 方法转为 Map 集合时，一定要注意当 value 为 null 时会抛 NPE 异常。

class Person {
    private String name;
    private String phoneNumber;
     // getters and setters
}
List<Person> bookList = new ArrayList<>();
bookList.add(new Person("jack","18163138123"));
bookList.add(new Person("martin",null));
// 空指针异常
bookList.stream().collect(Collectors.toMap(Person::getName, Person::getPhoneNumber));

下面我们来解释一下原因。

首先，我们来看 java.util.stream.Collectors 类的 toMap() 方法，可以看到其内部调用了 Map 接口的 merge() 方法。

public static <T, K, U, M extends Map<K, U>>
Collector<T, ?, M> toMap(Function<? super T, ? extends K> keyMapper,
                            Function<? super T, ? extends U> valueMapper,
                            BinaryOperator<U> mergeFunction,
                            Supplier<M> mapSupplier) {
    BiConsumer<M, T> accumulator
            = (map, element) -> map.merge(keyMapper.apply(element),
                                          valueMapper.apply(element), mergeFunction);
    return new CollectorImpl<>(mapSupplier, accumulator, mapMerger(mergeFunction), CH_ID);
}

Map 接口的 merge() 方法如下，这个方法是接口中的默认实现。

default V merge(K key, V value,
        BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
    Objects.requireNonNull(remappingFunction);
    Objects.requireNonNull(value);
    V oldValue = get(key);
    V newValue = (oldValue == null) ? value :
               remappingFunction.apply(oldValue, value);
    if(newValue == null) {
        remove(key);
    } else {
        put(key, newValue);
    }
    return newValue;
}

merge() 方法会先调用 Objects.requireNonNull() 方法判断 value 是否为空。

public static <T> T requireNonNull(T obj) {
    if (obj == null)
        throw new NullPointerException();
    return obj;
}

集合遍历

阿里巴巴 Java 开发手册》的描述如下：

不要在 foreach 循环里进行元素的 remove/add 操作。remove 元素请使用 Iterator 方式，如果并发操作，需要对 Iterator 对象加锁。

通过反编译你会发现 foreach 语法糖底层其实还是依赖 Iterator 。不过， remove/add 操作直接调用的是集合自己的方法，而不是 Iterator 的 remove/add方法

这就导致 Iterator 莫名其妙地发现自己有元素被 remove/add ，然后，它就会抛出一个 ConcurrentModificationException 来提示用户发生了并发修改异常。这就是单线程状态下产生的 fail-fast 机制。

fail-fast 机制 ：多个线程对 fail-fast 集合进行修改的时候，可能会抛出ConcurrentModificationException。即使是单线程下也有可能会出现这种情况，上面已经提到过。

Java8 开始，可以使用 Collection#removeIf()方法删除满足特定条件的元素,如

List<Integer> list = new ArrayList<>();
for (int i = 1; i <= 10; ++i) {
    list.add(i);
}
list.removeIf(filter -> filter % 2 == 0); /* 删除list中的所有偶数 */
System.out.println(list); /* [1, 3, 5, 7, 9] */

除了上面介绍的直接使用 Iterator 进行遍历操作之外，你还可以：

使用普通的 for 循环
使用 fail-safe 的集合类。java.util包下面的所有的集合类都是 fail-fast 的，而java.util.concurrent包下面的所有的类都是 fail-safe 的。
……

集合去重

《阿里巴巴 Java 开发手册》的描述如下：

可以利用 Set 元素唯一的特性，可以快速对一个集合进行去重操作，避免使用 List 的 contains() 进行遍历去重或者判断包含操作。

这里我们以 HashSet 和 ArrayList 为例说明。

// Set 去重代码示例
public static <T> Set<T> removeDuplicateBySet(List<T> data) {
    if (CollectionUtils.isEmpty(data)) {
        return new HashSet<>();
    }
    return new HashSet<>(data);
}
// List 去重代码示例
public static <T> List<T> removeDuplicateByList(List<T> data) {
    if (CollectionUtils.isEmpty(data)) {
        return new ArrayList<>();
    }
    List<T> result = new ArrayList<>(data.size());
    for (T current : data) {
        if (!result.contains(current)) {
            result.add(current);
        }
    }
    return result;
}

两者的核心差别在于 contains() 方法的实现。

HashSet 的 contains() 方法底部依赖的 HashMap 的 containsKey() 方法，时间复杂度接近于 O（1）（没有出现哈希冲突的时候为 O（1））。

private transient HashMap<E,Object> map;
public boolean contains(Object o) {
    return map.containsKey(o);
}

我们有 N 个元素插入进 Set 中，那时间复杂度就接近是 O (n)。

ArrayList 的 contains() 方法是通过遍历所有元素的方法来做的，时间复杂度接近是 O(n)。

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

我们的 List 有 N 个元素，那时间复杂度就接近是 O (n^2)。

集合转数组

《阿里巴巴 Java 开发手册》的描述如下：

使用集合转数组的方法，必须使用集合的 toArray(T[] array)，传入的是类型完全一致、长度为 0 的空数组。

toArray(T[] array) 方法的参数是一个泛型数组，如果 toArray 方法中没有传递任何参数的话返回的是 Object类型数组。

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

由于 JVM 优化，new String[0]作为Collection.toArray()方法的参数现在使用更好，new String[0]就是起一个模板的作用，指定了返回数组的类型，0 是为了节省空间，因为它只是为了说明返回的类型。

数组转集合

阿里巴巴 Java 开发手册》的描述如下：

使用工具类 Arrays.asList() 把数组转换成集合时，不能使用其修改集合相关的方法，它的 add/remove/clear 方法会抛出 UnsupportedOperationException 异常。

我在之前的一个项目中就遇到一个类似的坑。

Arrays.asList()在平时开发中还是比较常见的，我们可以使用它将一个数组转换为一个 List 集合。

String[] myArray = {"Apple", "Banana", "Orange"};
List<String> myList = Arrays.asList(myArray);
//上面两个语句等价于下面一条语句
List<String> myList = Arrays.asList("Apple","Banana", "Orange");

JDK 源码对于这个方法的说明：

/**
  *返回由指定数组支持的固定大小的列表。此方法作为基于数组和基于集合的API之间的桥梁，
  * 与 Collection.toArray()结合使用。返回的List是可序列化并实现RandomAccess接口。
  */
public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}

下面我们来总结一下使用注意事项。

1、Arrays.asList()是泛型方法，传递的数组必须是对象数组，而不是基本类型。

int[] myArray = {1, 2, 3};
List myList = Arrays.asList(myArray);
System.out.println(myList.size());//1
System.out.println(myList.get(0));//数组地址值
System.out.println(myList.get(1));//报错：ArrayIndexOutOfBoundsException
int[] array = (int[]) myList.get(0);
System.out.println(array[0]);//1

当传入一个原生数据类型数组时，Arrays.asList() 的真正得到的参数就不是数组中的元素，而是数组对象本身！此时 List 的唯一元素就是这个数组，这也就解释了上面的代码。

我们使用包装类型数组就可以解决这个问题。

1	Integer[] myArray = {1, 2, 3};

2、使用集合的修改方法: add()、remove()、clear()会抛出异常。

List myList = Arrays.asList(1, 2, 3);
myList.add(4);//运行时报错：UnsupportedOperationException
myList.remove(1);//运行时报错：UnsupportedOperationException
myList.clear();//运行时报错：UnsupportedOperationException

Arrays.asList() 方法返回的并不是 java.util.ArrayList ，而是 java.util.Arrays 的一个内部类,这个内部类并没有实现集合的修改方法或者说并没有重写这些方法。

1 2	List myList = Arrays.asList(1, 2, 3); System.out.println(myList.getClass());//class java.util.Arrays$ArrayList

下图是 java.util.Arrays$ArrayList 的简易源码，我们可以看到这个类重写的方法有哪些。

private static class ArrayList<E> extends AbstractList<E>
      implements RandomAccess, java.io.Serializable
  {
      ...
      @Override
      public E get(int index) {
        ...
      }
      @Override
      public E set(int index, E element) {
        ...
      }
      @Override
      public int indexOf(Object o) {
        ...
      }
      @Override
      public boolean contains(Object o) {
         ...
      }
      @Override
      public void forEach(Consumer<? super E> action) {
        ...
      }
      @Override
      public void replaceAll(UnaryOperator<E> operator) {
        ...
      }
      @Override
      public void sort(Comparator<? super E> c) {
        ...
      }
  }

我们再看一下java.util.AbstractList的 add/remove/clear 方法就知道为什么会抛出 UnsupportedOperationException 了。

public E remove(int index) {
    throw new UnsupportedOperationException();
}
public boolean add(E e) {
    add(size(), e);
    return true;
}
public void add(int index, E element) {
    throw new UnsupportedOperationException();
}
public void clear() {
    removeRange(0, size());
}
protected void removeRange(int fromIndex, int toIndex) {
    ListIterator<E> it = listIterator(fromIndex);
    for (int i=0, n=toIndex-fromIndex; i<n; i++) {
        it.next();
        it.remove();
    }
}

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

1、手动实现工具类

//JDK1.5+
static <T> List<T> arrayToList(final T[] array) {
  final List<T> l = new ArrayList<T>(array.length);
  for (final T s : array) {
    l.add(s);
  }
  return l;
}
Integer [] myArray = { 1, 2, 3 };
System.out.println(arrayToList(myArray).getClass());//class java.util.ArrayList

2、最简便的方法

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

3、使用 Java8 的 Stream(推荐)

Integer [] myArray = { 1, 2, 3 };
List myList = Arrays.stream(myArray).collect(Collectors.toList());
//基本类型也可以实现转换（依赖boxed的装箱操作）
int [] myArray2 = { 1, 2, 3 };
List myList = Arrays.stream(myArray2).boxed().collect(Collectors.toList());

4、使用 Guava

对于不可变集合，你可以使用ImmutableList (opens new window)类及其of() (opens new window)与copyOf() (opens new window)工厂方法：（参数不能为空）

1 2	List<String> il = ImmutableList.of("string", "elements"); // from varargs List<String> il = ImmutableList.copyOf(aStringArray); // from array

对于可变集合，你可以使用Lists (opens new window)类及其newArrayList() (opens new window)工厂方法：

1
2
3

List<String> l1 = Lists.newArrayList(anotherListOrCollection);    // from collection
List<String> l2 = Lists.newArrayList(aStringArray);               // from array
List<String> l3 = Lists.newArrayList("or", "string", "elements"); // from varargs

5、使用 Apache Commons Collections

1 2	List<String> list = new ArrayList<String>(); CollectionUtils.addAll(list, str);

6、使用 Java9 的 List.of()方法

1 2	Integer[] array = {1, 2, 3}; List<Integer> list = List.of(array);