博主只是这篇文章的搬运工，为了加强记忆自己梳理了一遍并扩展了部分内容。

集合拓展链接：集合概述&集合之Collection接口 - 至安 - 博客园 (cnblogs.com)

Java 集合， 也叫作容器，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 和 Queue。

Java 集合框架如下图所示：

注：图中只列举了主要的继承派生关系，并没有列举所有关系。比方省略了AbstractList， NavigableSet等抽象类以及其他的一些辅助类，如想深入了解，可自行查看源码

1. 为什么要使用集合？

当我们需要保存一组类型相同的数据的时候，我们应该是用一个容器来保存，这个容器就是数组，但是，使用数组存储对象具有一定的弊端， 因为我们在实际开发中，存储的数据的类型是多种多样的，于是，就出现了“集合”，集合同样也是用来存储多个数据的。

数组的缺点是一旦声明之后，长度就不可变了；同时，声明数组时的数据类型也决定了该数组存储的数据的类型；而且，数组存储的数据是有序的、可重复的，特点单一。 但是集合提高了数据存储的灵活性，Java 集合不仅可以用来存储不同类型不同数量的对象，还可以保存具有映射关系的数据

2. 说说 List， Set， Queue， Map 四者的区别？

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

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

先来看一下 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 接口下面的集合。

Map

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

4. 如何选用集合?

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

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

5. 两个对象的 hashCode相同，则 equals() 也一定为 true，对吗

不一定，元素调用hashCode()方法，计算出元素的哈希值，此哈希值接着通过某种散列函数计算出在HashSet底层数组中的存放位置（即索引位置)，并不能判断两个对象是否相同

1. Arraylist 和 Vector 的区别?

• ArrayList 是 List 的主要实现类，底层使用 Object[ ]存储，适用于频繁的查找工作，线程不安全 ；
• Vector 是 List 的古老实现类，底层使用Object[ ] 存储，线程安全的。

2. Arraylist 与 LinkedList 区别?

要求

• 能够说清楚 LinkedList 对比 ArrayList 的区别，并重视纠正部分错误的认知

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

LinkedList

1. 基于双向链表，无需连续内存
2. 随机访问慢（要沿着链表遍历）
3. 头尾插入删除性能高，中间元素慢
4. 占用内存多

ArrayList

1. 基于数组，需要连续内存
2. 随机访问快（指根据下标访问）
3. 尾部插入、删除性能可以，其它部分插入、删除都会移动数据，因此性能会低
4. 可以利用 cpu 缓存，局部性原理

补充内容:双向链表和双向循环链表

双向链表： 包含两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点。

另外推荐一篇把双向链表讲清楚的文章：https://juejin.cn/post/6844903648154271757 (opens new window)

双向循环链表： 最后一个节点的 next 指向 head，而 head 的 prev 指向最后一个节点，构成一个环

补充内容:RandomAccess 接口

public interface RandomAccess {
}

查看源码我们发现实际上 RandomAccess 接口中什么都没有定义。所以，在我看来 RandomAccess 接口不过是一个标识罢了。标识什么？ 标识实现这个接口的类具有随机访问功能。

在 binarySearch（) 方法中，它要判断传入的 list 是否 RamdomAccess 的实例，如果是，调用indexedBinarySearch()方法，如果不是，那么调用iteratorBinarySearch()方法

    public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list， T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list， key);
        else
            return Collections.iteratorBinarySearch(list， key);
    }

ArrayList 实现了 RandomAccess 接口， 而 LinkedList 没有实现。为什么呢？我觉得还是和底层数据结构有关！ArrayList 底层是数组，而 LinkedList 底层是链表。数组天然支持随机访问，时间复杂度为 O(1)，所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素，时间复杂度为 O(n)，所以不支持快速随机访问。，ArrayList 实现了 RandomAccess 接口，就表明了他具有快速随机访问功能。 RandomAccess 接口只是标识，并不是说 ArrayList 实现 RandomAccess 接口才具有快速随机访问功能的

3. 说一说 ArrayList 的扩容机制吧

ArrayList核心源码

详见这篇文章:通过源码一步一步分析 ArrayList 扩容机制

先从 ArrayList 的构造函数说起

（JDK8）ArrayList 有三种方式来初始化，构造方法源码如下：

   /**
     * 默认初始容量大小10
     */
    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

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

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

细心的同学一定会发现 ：以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。 下面在我们分析 ArrayList 扩容时会讲到这一点内容！

补充：JDK6 new 无参构造的 ArrayList 对象时，直接创建了长度是 10 的 Object[] 数组 elementData

add()

    /**
     * 将指定的元素追加到此列表的末尾。
     */
public boolean add(E e) {
    //添加元素之前，先调用ensureCapacityInternal方法
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //这里看到ArrayList添加元素的实质就相当于为数组赋值
    elementData[size++] = e;
    return true;
}

ensureCapacityInternal()

（JDK7）可以看到 add 方法 首先调用了ensureCapacityInternal(size + 1)

   //得到最小扩容量
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
              // 获取默认的容量和传入参数的较大值
            minCapacity = Math.max(DEFAULT_CAPACITY， minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

如果调用 ensureCapacityInternal() 方法就一定会进入（执行）这个方法，下面我们来研究一下这个方法的源码！

  //判断是否需要扩容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            //调用grow方法进行扩容，调用此方法代表已经开始扩容了
            grow(minCapacity);
    }

仔细分析一下：

• 当我们要 add 进第 1 个元素到 ArrayList 时，elementData.length 为 0 （因为还是一个空的 list），然后执行了 ensureCapacityInternal() 方法 ，所以 minCapacity 此时为 10。此时，minCapacity - elementData.length > 0成立，所以会进入 grow(minCapacity) 方法。
• 当 add 第 2 个元素时，minCapacity 为 2，此时 e lementData.length(容量)在添加第一个元素后扩容成 10 了。此时，minCapacity - elementData.length > 0 不成立，所以不会进入 （执行）grow(minCapacity) 方法。
• 添加第 3、4···到第 10 个元素时，依然不会执行 grow 方法，数组容量都为 10。

直到添加第 11 个元素，minCapacity(为 11)比 elementData.length（为 10）要大。进入 grow 方法进行扩容。

grow()

    /**
     * 要分配的最大数组大小
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * ArrayList扩容的核心方法。
     */
    private void grow(int minCapacity) {
        // oldCapacity为旧容量，newCapacity为新容量
        int oldCapacity = elementData.length;
        //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
        //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
       // 如果新容量大于 MAX_ARRAY_SIZE，进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，
       //如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size， so this is a win:
        elementData = Arrays.copyOf(elementData， newCapacity);
    }

int newCapacity = oldCapacity + (oldCapacity >> 1)，所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）！ 奇偶不同，比如 ：10+10/2 = 15， 33+33/2=49。如果是奇数的话会丢掉小数.

>（移位运算符）：>>1 右移一位相当于除 2，右移 n 位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了 1 位所以相当于 oldCapacity /2。对于大数据的 2 进制运算，位移运算符比那些普通运算符的运算要快很多，因为程序仅仅移动一下而已，不去计算，这样提高了效率，节省了资源

我们再来通过例子探究一下grow() 方法 ：

• 当 add 第 1 个元素时，oldCapacity 为 0，经比较后第一个 if 判断成立，newCapacity = minCapacity(为 10)。但是第二个 if 判断不会成立，即 newCapacity 不比 MAX_ARRAY_SIZE 大，则不会进入 hugeCapacity 方法。数组容量为 10，add 方法中 return true，size 增为 1。
• 当 add 第 11 个元素进入 grow 方法时，newCapacity 为 15，比 minCapacity（为 11）大，第一个 if 判断不成立。新容量没有大于数组最大 size，不会进入 hugeCapacity 方法。数组容量扩为 15，add 方法中 return true，size 增为 11。
• 当第16个元素进入容器时再次扩容

这里补充一点比较重要，但是容易被忽视掉的知识点：

• java 中的 length属性是针对数组说的，比如说你声明了一个数组，想知道这个数组的长度则用到了 length 这个属性.
• java 中的 length() 方法是针对字符串说，如果想看这个字符串的长度则用到 length() 这个方法.
• java 中的 size() 方法是针对泛型集合说的，如果想看这个泛型有多少个元素，就调用此方法来查看!

hugeCapacity()

从上面 grow() 方法源码我们知道： 如果新容量大于 MAX_ARRAY_SIZE，进入(执行) hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，如果 minCapacity 大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //对minCapacity和MAX_ARRAY_SIZE进行比较
        //若minCapacity大，将Integer.MAX_VALUE作为新数组的大小
        //若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小
        //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

System.arraycopy() 和 Arrays.copyOf()

阅读源码的话，我们就会发现 ArrayList 中大量调用了这两个方法。比如：我们上面讲的扩容操作以及add(int index， E element)、toArray() 等方法中都用到了该方法！

    // 我们发现 arraycopy 是一个 native 方法，接下来我们解释一下各个参数的具体意义
    /**
    *   复制数组
    * @param src 源数组
    * @param srcPos 源数组中的起始位置
    * @param dest 目标数组
    * @param destPos 目标数组中的起始位置
    * @param length 要复制的数组元素的数量
    */
    public static native void arraycopy(Object src，  int  srcPos，
                                        Object dest， int destPos，
                                        int length);

场景：

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

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

我们写一个简单的方法测试以下：

例如：

String[] arr = {"A"，"B"，"C"，"D"，"E"，"F"};
System.arraycopy(arr ，3，arr，2，2);

从下标为3的位置开始复制，复制的长度为2(复制D、E)，从下标为2的位置开始替换为D、E

复制后的数组为:

String[] arr = {"A"，"B"，"D"，"E"，"E"，"F"};

Arrays.copyOf()源码

    public static int[] copyOf(int[] original， int newLength) {
        // 申请一个新的数组
        int[] copy = new int[newLength];
    // 调用System.arraycopy，将源数组中的数据进行拷贝，并返回新的数组
        System.arraycopy(original， 0， copy， 0，
                         Math.min(original.length， newLength));
        return copy;
    }Copy to clipboardErrorCopied

场景：

   /**
     以正确的顺序返回一个包含此列表中所有元素的数组（从第一个到最后一个元素）; 返回的数组的运行时类型是指定数组的运行时类型。
     */
    public Object[] toArray() {
    //elementData：要复制的数组；size：要复制的长度
        return Arrays.copyOf(elementData， size);
    }

个人觉得使用 Arrays.copyOf()方法主要是为了给原有数组扩容，测试代码如下：

public class ArrayscopyOfTest {

    public static void main(String[] args) {
        int[] a = new int[3];
        a[0] = 0;
        a[1] = 1;
        a[2] = 2;
        int[] b = Arrays.copyOf(a， 10);
        System.out.println("b.length"+b.length);
    }
}

结果：

10

扩容规则总结

1. ArrayList() 初始化长度为零的数组

2. ArrayList(int initialCapacity) 会使用指定容量的数组

3. public ArrayList(Collection c) 会使用 c 的大小作为数组容量

4. add(Object o) 首次扩容为 10，再次扩容为上次容量的 1.5 倍

5. addAll(Collection c) 没有元素时，扩容为 Math.max(10, 实际元素个数)，有元素时为 Math.max(原容量 1.5 倍, 实际元素个数)

其中第 4 点必须知道，其它几点视个人情况而定

1. 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);

打印结果

原始数组:
[-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;
    }
}


    public static void main(String[] args) {
        TreeMap<Person， String> pdata = new TreeMap<Person， String>();
        pdata.put(new Person("张三"， 30)， "zhangsan");
        pdata.put(new Person("李四"， 20)， "lisi");
        pdata.put(new Person("王五"， 10)， "wangwu");
        pdata.put(new Person("小红"， 5)， "xiaohong");
        // 得到key的值的同时得到key所对应的值
        Set<Person> keys = pdata.keySet();
        for (Person key : keys) {
            System.out.println(key.getAge() + "-" + key.getName());

        }
    }

Output：

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

2. 无序性和不可重复性的含义是什么

什么是无序性？无序性不等于随机性 ，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ，而是根据数据的哈希值决定的。

什么是不可重复性？不可重复性是指添加的元素按照 equals()判断时 ，返回 false，需要同时重写 equals()方法和 HashCode()方法。

3. 比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同

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

4. Collection 子接口之 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() 等其他方法，可用于模拟栈。

ArrayDeque 与 LinkedList 的区别

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？

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

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

说一说 PriorityQueue

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

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

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

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

要求

• 掌握 HashMap 的基本数据结构
• 掌握树化、退化时机
• 理解索引计算方法、二次 hash 的意义、容量对索引计算的影响
• 掌握 put 流程、扩容、扩容因子
• 理解并发使用 HashMap 可能导致的问题
• 理解 key 的设计

HashMap

HashMap 的基本数据结构

• 1.7： 数组 + 链表

• 1.8： 数组 + （链表 | 红黑树）

树化与退化

树化规则：当链表长度超过树化阈值 8 时，先尝试扩容来减少链表长度，如果此时数组容量大于 64 才会进行树化

树化的意义

• 红黑树用来避免 DoS 攻击，防止链表超长时性能下降，树化应当是偶然情况，是保底策略
• hash 表的查找、更新的时间复杂度是 O(1)，而红黑树的查找、更新的时间复杂度是 O(log_2⁡n )，TreeNode 占用空间也比普通 Node 的大，如非必要，尽量还是使用链表
• hash 值如果足够随机，则在 hash 表内按泊松分布，在负载因子 0.75 的情况下，长度超过 8 的链表出现概率是 0.00000006，树化阈值选择 8 就是为了让树化几率足够小

退化规则

• 情况1：在扩容时会拆分树，当树元素个数小于6则会退化成链表
• 情况2：删除树节点时，若 root、root.left、root.right、root.left.left 有一个为 null ，也会退化为链表

索引计算

索引计算方法

• 首先，计算对象的 hashCode()
• 再调用 HashMap 的 hash() 方法进行二次哈希：二次 hash() 是为了让哈希分布更为均匀
• 最后 & (capacity – 1) 得到索引

数组容量为何是 2 的 n 次幂

1. 计算索引时效率更高：如果是 2 的 n 次幂可以使用位与运算代替取模
2. 扩容时重新计算索引效率更高： hash & oldCap == 0 的元素留在原来位置 ，否则新位置 = 旧位置 + oldCap

注意

• 二次 hash 是为了配合 容量是 2 的 n 次幂 这一设计前提，如果 hash 表的容量不是 2 的 n 次幂，则不必二次 hash
• 容量是 2 的 n 次幂 这一设计计算索引效率更好，但 hash 的分散性就不好，需要二次 hash 来作为补偿，没有采用这一设计的典型例子是 Hashtable

put 与扩容

put 流程

1. HashMap 是懒惰创建数组的，首次使用才创建数组

2. 计算索引（桶下标）

3. 如果桶下标还没人占用，创建 Node 占位返回

4. 如果桶下标已经有人占用

5. 返回前检查容量是否超过阈值，一旦超过进行扩容

1.7 与 1.8 的区别

1. 链表插入节点时，1.7 是头插法，1.8 是尾插法

2. 1.7 是大于等于阈值且没有空位时才扩容，而 1.8 是大于阈值就扩容

3. 1.8 在扩容计算 Node 索引时，会优化

扩容（加载）因子为何默认是 0.75f

1. 在空间占用与查询时间之间取得较好的权衡
2. 大于这个值，空间节省了，但链表就会比较长影响性能
3. 小于这个值，冲突减少了，但扩容就会更频繁，空间占用也更多

并发问题

• 扩容死链（1.7 会存在）: 原因是1.7头插法会改变元素顺序
• 数据错误（1.7和1.8）：并发环境下若多个待插入元素计算出来的索引下标相同则会产生覆盖问题

key 的设计

key 的设计要求

1. HashMap 的 key 可以为 null，但 Map 的其他实现则不然
2. 作为 key 的对象，必须实现 hashCode 和 equals，并且 key 的内容不能修改（不可变）
3. key 的 hashCode 应该有良好的散列性

如果 key 可变，例如修改了 age 会导致再次查询时查询不到

几种Map接口实现类的区别

1. HashMap 和 Hashtable 的区别

1. 线程是否安全： HashMap 是非线程安全的，Hashtable 是线程安全的，因为 Hashtable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；

2. 效率： 因为线程安全的问题，HashMap 要比 Hashtable 效率高一点。另外，Hashtable 基本被淘汰，不要在代码中使用它；

3. 对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。

4. 初始容量大小和每次扩充容量大小的不同 ：

   ① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。

   ② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小，后面会介绍到为什么是 2 的幂次方。

5. 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

HashMap 中带有初始容量的构造函数：

public HashMap(int initialCapacity， float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
    this(initialCapacity， DEFAULT_LOAD_FACTOR);
}

下面这个方法保证了 HashMap 总是使用 2 的幂作为哈希表的大小。

    /**
     * Returns a power of two size for the given target capacity.
     */
    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;
    }

2. 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()方法用来判断对象的相等性

3. HashMap 和 TreeMap 区别

TreeMap 和HashMap 都继承自AbstractMap ，但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap 接口。

实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。

实现SortedMap接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。示例代码如下：

/**
 * @author shuang.kou
 * @createTime 2020年06月15日 17:02:00
 */
public class Person {
    private Integer age;

    public Person(Integer age) {
        this.age = age;
    }

    public Integer getAge() {
        return age;
    }

    public static void main(String[] args) {
        TreeMap<Person， String> treeMap = new TreeMap<>(new Comparator<Person>() {
            @Override
            public int compare(Person person1， Person person2) {
                int num = person1.getAge() - person2.getAge();
                return Integer.compare(num， 0);
            }
        });
        treeMap.put(new Person(3)， "person1");
        treeMap.put(new Person(18)， "person2");
        treeMap.put(new Person(35)， "person3");
        treeMap.put(new Person(16)， "person4");
        treeMap.entrySet().stream().forEach(personStringEntry -> {
            System.out.println(personStringEntry.getValue());
        });
    }
}

输出:

person1
person4
person2
person3

可以看出，TreeMap 中的元素已经是按照 Person 的 age 字段的升序来排列了。

上面，我们是通过传入匿名内部类的方式实现的，你可以将代码替换成 Lambda 表达式实现的方式：

TreeMap<Person， String> treeMap = new TreeMap<>((person1， person2) -> {
  int num = person1.getAge() - person2.getAge();
  return Integer.compare(num， 0);
});

综上，相比于HashMap来说 TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。

HashSet 如何检查重复

以下内容摘自《Head first java》第二版：

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

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

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

DK1.8 之后

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

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

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

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

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

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

HashMap 多线程操作导致死循环问题

主要原因在于并发下的 Rehash 会造成元素之间会形成一个循环链表。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使用 HashMap，因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。

ConcurrentHashMap 和 Hashtable 的区别

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

• 底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；

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

  ① 在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后 对 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；

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

两者的对比图：

Hashtable:

https://www.cnblogs.com/chengxiao/p/6842045.html>

JDK1.7 的 ConcurrentHashMap：

JDK1.8 的 ConcurrentHashMap：

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

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

JDK1.7（上面有示意图）

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

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

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

static class Segment<K，V> extends ReentrantLock implements Serializable {
}

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

JDK1.8 （上面有示意图）

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

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

这篇文章根据《阿里巴巴 Java 开发手册》总结了关于集合使用常见的注意事项以及其具体原理。

强烈建议小伙伴们多多阅读几遍，避免自己写代码的时候出现这些低级的问题

1. 集合判空

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

判断所有集合内部的元素是否为空，使用 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
}

2. 集合转 Map

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

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

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() 方法如下，这个方法是接口中的默认实现。

如果你还不了解 Java 8 新特性的话，请看这篇文章：《Java8 新特性总结》 (opens new window) 。

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

解决方案

使用Java8提供的Optional类优雅地处理空指针问题

//如果值为null则赋默认值空串
Map<String, String> collect = bookList.stream().
                collect(Collectors.toMap(Person::getName, t -> Optional.ofNullable(t.getPhoneNumber()).orElse("")

3. 集合遍历

《阿里巴巴 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 的。

4. 集合去重

《阿里巴巴 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);
}

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)。

5. 数组转集合

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

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

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

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

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

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 的唯一元素就是这个数组，这也就解释了上面的运行结果。

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

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 的一个内部类，这个内部类并没有实现集合的修改方法或者说并没有重写这些方法。

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、最简便的方法

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