集合容器概述

集合框架的整体架构

两个顶层的接口：Collection 和 Map
Collection 接口下有对应的接口 List、Set、Queue 等

List 接口的实现类有：ArrayList、LinkedList、Vector 等
Set 接口的实现类有：HashSet、TreeSet、LinkedHashSet 等

Map 接口下有对应的实现类 HashMap、TreeMap（二叉树有序）LinkedHashMap（插入有序）、HashTable（HashMap 的线程安全版）、等

集合框架中，各个List、Map、Set 的初始容量，扩容策略

Vector：内部维护数组，默认长度 10，每次扩容 2
ArrayList：内部维护数组，默认长度为 10，每次扩容 1.5
LinkedList：为链表，扩展很容易，默认长度为 0
HashMap：为数组+链表/红黑树，默认长度 16，加载因子为 0.75，每次扩容的时候时候默认是扩原来的2倍（大小只能为2次幂）

HashMap的大小只能是2次幂的，假设你传一个10进去，实际上最终HashMap的大小是16，你传一个7进去，HashMap最终的大小是8
因为只有大小为2次幂时，才能合理用位运算替代取模
负载因子的大小决定着哈希表的扩容和哈希冲突

HashTable：默认长度 11，每次扩充 2N + 1

集合框架中，各个List、Map、Set 的 put、get、resize 方法

ArrayList —> add()：

new ArrayList()的时候，默认会有一个空的Object数组，大小为0
第一次add添加数据的时候，会给这个数组初始化一个大小，这个大小默认值为10
使用ArrayList在每一次add的时候，它都会先去计算这个数组够不够空间
如果空间是够的，那直接追加上去就好了。如果不够，那就得扩容
有个grow方法，每一次扩原来的1.5倍
空间扩完容之后，会调用 arraycopy 来对数组进行拷贝（扩容的本质）

HashMap —> put()

首先对key做hash运算，计算出该key所在的index
如果没碰撞，直接放到数组中
如果碰撞了，需要判断目前数据结构是链表还是红黑树，根据不同的情况来进行插入
1. 数组的大小大于64且链表的大小大于8的时候才会将链表改为红黑树，当红黑树大小为6时，会退化为链表
假设key是相同的，则替换到原来的值
最后判断哈希表是否满了(当前哈希表大小*负载因子），如果满了，则扩容
集合框架中，各个List、Map、Set 的线程安全策略
List —> CopyOnWriteArrayList —> 底层是通过复制数组的方式来实现的 —> 读不加锁，写加锁

add() 方法其实他会加lock锁，然后会复制出一个新的数组，往新的数组里边add真正的元素，最后把array的指向改变为新的数组
get() 方法又或是 size() 方法只是获取 array 所指向的数组的元素或者大小。

ConcurrentHashMap —> 通过加锁来实现

JDK7 —> 使用分段锁 —> segment（默认分配16个Segment），每一段一个锁
- 一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素
- 每个Segment守护着一个HashEntry数组里的元素，当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁
JDK8 —> Synchronized + CAS + Node，将锁的级别细分到了hash表的每一个节点
- 线程写时先通过CAS，一旦自旋则升级为 synchronized
- Java集合的快速失败机制 “fail-fast”
  是java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生 fail-fast 机制。

例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。

原因：

迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。
集合在被遍历期间如果内容发生变化，就会改变modCount的值。
每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。

解决办法：

在遍历过程中，所有涉及到改变modCount值得地方全部加上synchronized。
使用CopyOnWriteArrayList来替换ArrayList

怎么确保一个集合不能被修改? —> 变成只读
可以使用 Collections. **unmodifiableCollection**(Collection c) 方法来创建一个只读集合，这样改变集合的任何操作都会抛出 Java. lang. UnsupportedOperationException 异常
```
List<String> list = new ArrayList<>();
list. add("x");
Collection<String> clist = Collections. unmodifiableCollection(list);
clist. add("y"); // 运行时此行报错
System. out. println(list. size());
```
Collection接口

迭代器 Iterator 是什么？
Iterator 是面向对象的一个设计模式，目的是屏蔽不同数据集合的特点，统一遍历集合的接口
Iterator 接口提供遍历任何 Collection 的接口，因为所有Collection接继承了Iterator迭代器

作用：

可以从一个 Collection 中使用迭代器方法来获取迭代器实例

List<String> list = new ArrayList<>();
Iterator<String> it = list. iterator();
while(it. hasNext()){
String obj = it. next();
System. out. println(obj);
}

迭代器允许调用者在迭代过程中移除元素
```
Iterator<Integer> it = list.iterator();
while(it.hasNext()){
 *// do something*
 it.remove();
}
```
一种最常见的错误代码如下：
```
for(Integer i : list){
 list.remove(i)
}
```
运行以上错误代码会报 ConcurrentModificationException 异常。这是因为当使用 foreach(for(Integer i : list)) 语句时，会自动生成一个iterator 来遍历该 list，但同时该 list 正在被 Iterator.remove() 修改。Java 一般不允许一个线程在遍历 Collection 时另一个线程修改它。

List 接口

Iterator 和 ListIterator 有什么区别？

Iterator 可以遍历 Set 和 List 集合，而 ListIterator 只能遍历 List。
Iterator 只能单向遍历，而 ListIterator 可以双向遍历（向前/后遍历）。
ListIterator 实现 Iterator 接口，然后添加了一些额外的功能，比如添加一个元素、替换一个元素、获取前面或后面元素的索引位置。

遍历一个 List 有哪些不同的方式？每种方法的实现原理是什么？Java 中 List 遍历的最佳实践是什么？

遍历方式有以下几种：
1. for 循环遍历，基于计数器。在集合外部维护一个计数器，然后依次读取每一个位置的元素，当读取到最后一个元素后停止。
2. 迭代器遍历（Iterator）。Iterator 是面向对象的一个设计模式，目的是屏蔽不同数据集合的特点，统一遍历集合的接口。Java 在 Collections 中支持了 Iterator 模式。
3. foreach 循环遍历。foreach 内部也是采用了 Iterator 的方式实现，使用时不需要显式声明 Iterator 或计数器。优点是代码简洁，不易出错；缺点是只能做简单的遍历，不能在遍历过程中操作数据集合，例如删除、替换。

最佳实践：Java Collections 框架中提供了一个 RandomAccess 接口，用来标记 List 实现是否支持 Random Access。

如果一个数据集合实现了该接口，就意味着它支持 Random Access，按位置读取元素的平均时间复杂度为 O(1)，如ArrayList。
如果没有实现该接口，表示不支持 Random Access，如LinkedList。
推荐的做法就是，支持 Random Access 的列表可用 for 循环遍历，否则建议用 Iterator 或 foreach 遍历。
说一下 ArrayList 的优缺点
ArrayList 的优缺点其实也就是数组这种形式的优缺点

ArrayList的优点如下：

ArrayList 底层以数组实现，是一种随机访问模式。ArrayList 实现了 RandomAccess 接口，因此查找的时候非常快。
ArrayList 在顺序添加一个元素的时候非常方便。

ArrayList 的缺点如下：

删除元素的时候，需要做一次元素复制操作。如果要复制的元素很多，那么就会比较耗费性能。
插入元素的时候，也需要做一次元素复制操作，缺点同上。

ArrayList 比较适合顺序添加、随机访问的场景。

ArrayList 和 LinkedList 的区别是什么？

其实也就是数组和链表的区别

数据结构实现：ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实现。
随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。
增加和删除效率：在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为 ArrayList 增删操作要影响数组内的其他数据的下标。
内存空间占用：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。
线程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；

综合来说，在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推荐使用 LinkedList。

LinkedList 的双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

ArrayList 和 Vector 的区别是什么？

这两个类都实现了 List 接口（List 接口继承了 Collection 接口），他们都是有序集合

线程安全：Vector 使用了 Synchronized 来实现线程同步，是线程安全的，而 ArrayList 是非线程安全的。
性能：ArrayList 在性能方面要优于 Vector。
扩容：ArrayList 和 Vector 都会根据实际的需要动态的调整容量，只不过在 Vector 扩容每次会增加 1 倍，而 ArrayList 只会增加 50%。

Vector类的所有方法都是线程安全的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。
Arraylist不是线程安全的，所以在不需要保证线程安全时时建议使用Arraylist。

多线程场景下如何使用List

需要使用线程安全的List，有两种

使用 List<String> synchronizedList = Collections.synchronizedList(list);封装一下
使用 CopyOnWriteArrayList
为什么 ArrayList 的 elementData 加上 transient 修饰？
ArrayList 实现了 Serializable 接口，这意味着 ArrayList 支持序列化。
transient 的作用是说不希望 elementData 数组被序列化。在重写的 writeObject 实现中

每次序列化时，先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素
然后遍历 elementData，只序列化已存入的元素，这样既加快了序列化的速度，又减小了序列化之后的文件大小。
Set 接口
说一下 HashSet 的实现原理？

HashSet 是基于 HashMap 实现的
HashSet的值存放于HashMap的key上，HashMap的value统一为present。因此HashSet 不允许重复的值
相关 HashSet 的操作，基本上都是直接调用底层 HashMap 的相关方法来完成

HashSet如何检查重复？HashSet是如何保证数据不可重复的？
在 HashSet 的 add() 方法中，就是调用的 HashMap 的 put() 方法
比较两个的 hashCode() 方法返回的值
如果相同，再比较 equals() 方法的值
两者都相同，则为重复的值
hashCode() 与 equals() 的相关规定
如果两个对象相等，则 hashcode 一定也是相同的

hashCode 默认是 jdk 根据对象的地址或者字符串或者数字算出来的 int 类型的数值

两个对象相等，对两个equals方法返回true
两个对象有相同的 hashcode 值，它们也不一定是相等的

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

==与equals的区别

==是判断两个变量或实例是不是指向同一个内存空间，equals是判断两个变量或实例所指向的内存空间的值是不是相同
==是指对内存地址进行比较，equals()是对字符串的内容进行比较

Map 接口

什么是Hash算法

哈希算法是指把任意长度的二进制映射为固定长度的较小的二进制值，这个较小的二进制值叫做哈希值

说一下HashMap的实现原理？

HashMap概述：
- HashMap是基于哈希表的Map接口的非同步实现。
- 此实现提供所有可选的映射操作，并允许使用null值和null键。
- 此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
HashMap的数据结构：在Java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体
HashMap 基于 Hash 算法实现的
1. 当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
2. 存储时，如果出现hash值相同的key（hashcode() 方法的值相同），此时有两种情况。
  1. 如果key相同（equals() 方法的值相同），则覆盖原始值；
  2. 如果key不同（出现冲突），则将当前的key-value放入链表中
3. 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。
4. 理解了以上过程就不难明白HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。

需要注意Jdk 1.8中对HashMap的实现做了优化，当链表中的节点数据超过八个之后，该链表会转为红黑树来提高查询效率，从原来的O(n)到O(logn)

HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底层实现

HashMap JDK1.8之前

JDK1.8之前采用的是拉链法。拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

HashMap JDK1.8之后

相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。

HashMap的put方法的具体流程？

当我们put的时候，首先计算 key的hash值，这里调用了 hash方法，hash方法实际是让key.hashCode()与key.hashCode()>>>16进行异或操作，高16bit补0，一个数和0异或不变，所以 hash 函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞。按照函数注释，因为bucket数组大小是2的幂，计算下标index = (table.length - 1) & hash，如果不做 hash 处理，相当于散列生效的只有几个低 bit 位，为了减少散列的碰撞，设计者综合考虑了速度、作用、质量之后，使用高16bit和低16bit异或来简单处理减少碰撞，而且JDK8中用了复杂度 O（logn）的树结构来提升碰撞下的性能。
集合框架面试题 - 图9

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//实现Map.put和相关方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 步骤①：tab为空则创建 
    // table未初始化或者长度为0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 步骤②：计算index，并对null做处理  
    // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 桶中已经存在元素
    else {
        Node<K,V> e; K k;
        // 步骤③：节点key存在，直接覆盖value 
        // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 将第一个元素赋值给e，用e来记录
            e = p;
        // 步骤④：判断该链为红黑树 
        // hash值不相等，即key不相等；为红黑树结点
        // 如果当前元素类型为TreeNode，表示为红黑树，putTreeVal返回待存放的node, e可能为null
        else if (p instanceof TreeNode)
            // 放入树中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 步骤⑤：该链为链表 
        // 为链表结点
        else {
            // 在链表最末插入结点
            for (int binCount = 0; ; ++binCount) {
                // 到达链表的尾部
                //判断该链表尾部指针是不是空的
                if ((e = p.next) == null) {
                    // 在尾部插入新结点
                    p.next = newNode(hash, key, value, null);
                    //判断链表的长度是否达到转化红黑树的临界值，临界值为8
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //链表结构转树形结构
                        treeifyBin(tab, hash);
                    // 跳出循环
                    break;
                }
                // 判断链表中结点的key值与插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循环
                    break;
                // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                p = e;
            }
        }
        //判断当前的key已经存在的情况下，再来一个相同的hash值、key值时，返回新来的value这个值
        if (e != null) { 
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替换旧值
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 结构性修改
    ++modCount;
    // 步骤⑥：超过最大容量就扩容 
    // 实际大小大于阈值则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向5；
遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

HashMap的扩容操作是怎么实现的？
在jdk1.8中，resize方法是在hashmap中的键值对大于阀值时或者初始化时，就调用resize方法进行扩容；
每次扩展的时候，都是扩展2倍；
扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置。

在putVal()中，我们看到在这个函数里面使用到了2次resize()方法，resize()方法表示的在进行第一次初始化时会对其进行扩容，或者当该数组的实际大小大于其临界值值(第一次为12)，这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发，这也是JDK1.8版本的一个优化的地方，在1.7中，扩容之后需要重新去计算其Hash值，根据Hash值对其进行分发，但在1.8版本中，则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0，重新进行hash分配后，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;//oldTab指向hash桶数组
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {//如果oldCap不为空的话，就是hash桶数组不为空
        if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量了，就赋值为整数最大的阀值
            threshold = Integer.MAX_VALUE;
            return oldTab;//返回
        }//如果当前hash桶数组的长度在扩容后仍然小于最大容量 并且oldCap大于默认值16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold 双倍扩容阀值threshold
    }
    // 旧的容量为0，但threshold大于零，代表有参构造有cap传入，threshold已经被初始化成最小2的n次幂
    // 直接将该值赋给新的容量
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 无参构造创建的map，给出默认容量和threshold 16, 16*0.75
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 新的threshold = 新的cap * 0.75
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    // 计算出新的数组长度后赋给当前成员变量table
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//新建hash桶数组
    table = newTab;//将新数组的值复制给旧的hash桶数组
    // 如果原先的数组没有初始化，那么resize的初始化工作到此结束，否则进入扩容元素重排逻辑，使其均匀的分散
    if (oldTab != null) {
        // 遍历新数组的所有桶下标
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 旧数组的桶下标赋给临时变量e，并且解除旧数组中的引用，否则就数组无法被GC回收
                oldTab[j] = null;
                // 如果e.next==null，代表桶中就一个元素，不存在链表或者红黑树
                if (e.next == null)
                    // 用同样的hash映射算法把该元素加入新的数组
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果e是TreeNode并且e.next!=null，那么处理树中元素的重排
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // e是链表的头并且e.next!=null，那么处理链表中元素重排
                else { // preserve order
                    // loHead,loTail 代表扩容后不用变换下标，见注1
                    Node<K,V> loHead = null, loTail = null;
                    // hiHead,hiTail 代表扩容后变换下标，见注1
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 遍历链表
                    do {             
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                // 初始化head指向链表当前元素e，e不一定是链表的第一个元素，初始化后loHead
                                // 代表下标保持不变的链表的头元素
                                loHead = e;
                            else                                
                                // loTail.next指向当前e
                                loTail.next = e;
                            // loTail指向当前的元素e
                            // 初始化后，loTail和loHead指向相同的内存，所以当loTail.next指向下一个元素时，
                            // 底层数组中的元素的next引用也相应发生变化，造成lowHead.next.next.....
                            // 跟随loTail同步，使得lowHead可以链接到所有属于该链表的元素。
                            loTail = e;                           
                        }
                        else {
                            if (hiTail == null)
                                // 初始化head指向链表当前元素e, 初始化后hiHead代表下标更改的链表头元素
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 遍历结束, 将tail指向null，并把链表头放入新数组的相应下标，形成新的映射。
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

HashMap是怎么解决哈希冲突的？

相比于hashCode返回的int类型，我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4（即2的四次方16）要远小于int类型的范围，所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率，并且最坏情况下还会将HashMap变成一个单链表，所以我们还需要对hashCode作一定的优化
hash()函数

上面提到的问题，主要是因为如果使用hashCode取余，那么相当于参与运算的只有hashCode的低位，高位是没有起到任何作用的，所以我们的思路就是让hashCode取值出的高位也参与运算，进一步降低hash碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动，在JDK 1.8中的hash()函数如下：
```
static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算（高低位异或）
}
```
这比在JDK 1.7中，更为简洁，相比在1.7中的4次位运算，5次异或运算（9次扰动），在1.8中，只进行了1次位运算和1次异或运算（2次扰动）；

作者：小杰要吃蛋
链接：https://juejin.cn/post/6844904125939843079
来源：稀土掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

重新整理：https://juejin.cn/post/6844904125939843079

Java 集合框架的基础接口有哪些？

Collection ，为集合层级的根接口。一个集合代表一组对象，这些对象即为它的元素。Java 平台不提供这个接口任何直接的实现。
- Set ，是一个不能包含重复元素的集合。这个接口对数学集合抽象进行建模，被用来代表集合，就如一副牌。
- List ，是一个有序集合，可以包含重复元素。你可以通过它的索引来访问任何元素。List 更像长度动态变换的数组。
Map ，是一个将 key 映射到 value 的对象。一个 Map 不能包含重复的 key，每个 key 最多只能映射一个 value 。
一些其它的接口有 Queue、Dequeue、SortedSet、SortedMap 和 ListIterator 。

🦅 集合框架中的泛型有什么优点？
Java5 引入了泛型，所有的集合接口和实现都大量地使用它。泛型允许我们为集合提供一个可以容纳的对象类型。因此，如果你添加其它类型的任何元素，它会在编译时报错。这避免了在运行时出现 ClassCastException，因为你将会在编译时得到报错信息。
泛型也使得代码整洁，我们不需要使用显式转换和 instanceOf 操作符。它也给运行时带来好处，因为不会产生类型检查的字节码指令。
🦅 为何 Collection 不从 Cloneable 和 Serializable 接口继承？
Collection 接口指定一组对象，对象即为它的元素。

如何维护这些元素由 Collection 的具体实现决定。例如，一些如 List 的 Collection 实现允许重复的元素，而其它的如 Set 就不允许。
很多 Collection 实现有一个公有的 clone 方法。然而，把它放到集合的所有实现中也是没有意义的。这是因为 Collection 是一个抽象表现，重要的是实现。

当与具体实现打交道的时候，克隆或序列化的语义和含义才发挥作用。所以，具体实现应该决定如何对它进行克隆或序列化，或它是否可以被克隆或序列化。在所有的实现中授权克隆和序列化，最终导致更少的灵活性和更多的限制，特定的实现应该决定它是否可以被克隆和序列化。
🦅 为何 Map 接口不继承 Collection 接口？
尽管 Map 接口和它的实现也是集合框架的一部分，但 Map 不是集合，集合也不是 Map。因此，Map 继承 Collection 毫无意义，反之亦然。
如果 Map 继承 Collection 接口，那么元素去哪儿？Map 包含 key-value 对，它提供抽取 key 或 value 列表集合( Collection )的方法，但是它不适合“一组对象”规范。
🦅 Collection 和 Collections 的区别？

Collection ，是集合类的上级接口，继承与他的接口主要有 Set 和List 。
Collections ，是针对集合类的一个工具类，它提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。

🦅 集合框架里实现的通用算法有哪些？
Java 集合框架提供常用的算法实现，比如排序和搜索。
Collections类包含这些方法实现。大部分算法是操作 List 的，但一部分对所有类型的集合都是可用的。部分算法有排序、搜索、混编、最大最小值。
🦅 集合框架底层数据结构总结
1）List

ArrayList ：Object 数组。
Vector ：Object 数组。
LinkedList ：双向链表(JDK6 之前为循环链表，JDK7 取消了循环)。

2）Map

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

3）Set

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

什么是迭代器(Iterator)？
Iterator 接口，提供了很多对集合元素进行迭代的方法。每一个集合类都包含了可以返回迭代器实例的迭代方法。迭代器可以在迭代的过程中删除底层集合的元素，但是不可以直接调用集合的 #remove(Object Obj) 方法删除，可以通过迭代器的 #remove() 方法删除。
🦅 Iterator 和 ListIterator 的区别是什么？
Iterator 可用来遍历 Set 和 List 集合，但是 ListIterator 只能用来遍历 List。
Iterator 对集合只能是前向遍历，ListIterator 既可以前向也可以后向。
ListIterator 实现了 Iterator 接口，并包含其他的功能。比如：增加元素，替换元素，获取前一个和后一个元素的索引等等。

🦅 快速失败（fail-fast）和安全失败（fail-safe）的区别是什么？
差别在于 ConcurrentModification 异常：

快速失败：当你在迭代一个集合的时候，如果有另一个线程正在修改你正在访问的那个集合时，就会抛出一个 ConcurrentModification 异常。在 java.util 包下的都是快速失败。
安全失败：你在迭代的时候会去底层集合做一个拷贝，所以你在修改上层集合的时候是不会受影响的，不会抛出 ConcurrentModification 异常。在 java.util.concurrent 包下的全是安全失败的。

🦅 如何删除 List 中的某个元素？
有两种方式，分别如下：

方式一，使用 Iterator ，顺序向下，如果找到元素，则使用 remove 方法进行移除。
方式二，倒序遍历 List ，如果找到元素，则使用 remove 方法进行移除。

🦅 Enumeration 和 Iterator 接口有什么不同？

Enumeration 跟 Iterator 相比较快两倍，而且占用更少的内存。
但是，Iterator 相对于 Enumeration 更安全，因为其他线程不能修改当前迭代器遍历的集合对象。同时，Iterators 允许调用者从底层集合中移除元素，这些 Enumerations 都没法完成。

对于很多胖友，可能并未使用过 Enumeration 类，所以可以看看《Java Enumeration 接口》文章。
🦅 为何 Iterator 接口没有具体的实现？
Iterator 接口，定义了遍历集合的方法，但它的实现则是集合实现类的责任。每个能够返回用于遍历的 Iterator 的集合类都有它自己的 Iterator 实现内部类。
这就允许集合类去选择迭代器是 fail-fast 还是 fail-safe 的。比如，ArrayList 迭代器是 fail-fast 的，而 CopyOnWriteArrayList 迭代器是 fail-safe 的。

Comparable 和 Comparator 的区别?

Comparable 接口，在 java.lang 包下，用于当前对象和其它对象的比较，所以它有一个 #compareTo(Object obj) 方法用来排序，该方法只有一个参数。
Comparator 接口，在 java.util 包下，用于传入的两个对象的比较，所以它有一个 #compare(Object obj1, Object obj2) 方法用来排序，该方法有两个参数。

详细的，可以看看《Java 自定义比较器》文章，重点是如何自己实现 Comparable 和 Comparator的方法。
🦅 compareTo 方法的返回值表示的意思？

大于 0 ，表示对象大于参数对象。
小于 0 ，表示对象小于参数对象
等于 0 ，表示两者相等。

🦅 如何对 Object 的 List 排序？

对 Object[] 数组进行排序时，我们可以用 Arrays#sort(...) 方法。
对 List<Object> 数组进行排序时，我们可以用 Collections#sort(...) 方法。

有哪些关于 Java 集合框架的最佳实践？
基于应用的需求来选择使用正确类型的集合，这对性能来说是非常重要的。例如，如果元素的大小是固定的，并且知道优先级，我们将会使用一个 Array ，而不是 ArrayList 。
一些集合类允许我们指定他们的初始容量。因此，如果我们知道存储数据的大概数值，就可以避免重散列或者大小的调整。
总是使用泛型来保证类型安全，可靠性和健壮性。同时，使用泛型还可以避免运行时的 ClassCastException 异常。
在 Map 中使用 JDK 提供的不可变类作为一个 key，这样可以避免 hashcode 的实现和我们自定义类的 equals 方法。
应该依照接口而不是实现来编程。
返回零长度的集合或者数组，而不是返回一个 null ，这样可以防止底层集合是空的。

区别

List 和 Set 区别？
List，Set 都是继承自 Collection 接口。
List 特点：元素有放入顺序，元素可重复。
Set 特点：元素无放入顺序，元素不可重复，重复元素会覆盖掉。

注意：元素虽然无放入顺序，但是元素在 Set 中的位置是有该元素的 hashcode 决定的，其位置其实是固定的。另外 List 支持 for 循环，也就是通过下标来遍历，也可以用迭代器，但是 Set 只能用迭代，因为他无序，无法用下标来取得想要的值。

Set 和 List 对比：

Set：检索元素效率高，删除和插入效率低，插入和删除不会引起元素位置改变。
List：和数组类似，List 可以动态增长，查找元素效率低，插入删除元素效率，因为可能会引起其他元素位置改变。

List 和 Map 区别？
List 是对象集合，允许对象重复。
Map 是键值对的集合，不允许 key 重复。

Array 和 ArrayList 有何区别？什么时候更适合用 Array？
Array 可以容纳基本类型和对象，而 ArrayList 只能容纳对象。
Array 是指定大小的，而 ArrayList 大小是固定的，可自动扩容。
Array 没有提供 ArrayList 那么多功能，比如 addAll、removeAll 和 iterator 等。

尽管 ArrayList 明显是更好的选择，但也有些时候 Array 比较好用，比如下面的三种情况。

1、如果列表的大小已经指定，大部分情况下是存储和遍历它们
2、对于遍历基本数据类型，尽管 Collections 使用自动装箱来减轻编码任务，在指定大小的基本类型的列表上工作也会变得很慢。
3、如果你要使用多维数组，使用 [][] 比 List 会方便。

ArrayList 与 LinkedList 区别？
🦅 ArrayList
优点：ArrayList 是实现了基于动态数组的数据结构，因为地址连续，一旦数据存储好了，查询操作效率会比较高（在内存里是连着放的）。
缺点：因为地址连续，ArrayList 要移动数据，所以插入和删除操作效率比较低。

🦅 LinkedList

优点：LinkedList 基于链表的数据结构，地址是任意的，所以在开辟内存空间的时候不需要等一个连续的地址。对于新增和删除操作 add 和 remove ，LinedList 比较占优势。LinkedList 适用于要头尾操作或插入指定位置的场景。
缺点：因为 LinkedList 要移动指针，所以查询操作性能比较低。

🦅 适用场景分析：

当需要对数据进行对随机访问的情况下，选用 ArrayList 。
当需要对数据进行多次增加删除修改时，采用 LinkedList 。

如果容量固定，并且只会添加到尾部，不会引起扩容，优先采用 ArrayList 。
当然，绝大数业务的场景下，使用 ArrayList 就够了。主要是，注意好避免 ArrayList 的扩容，以及非顺序的插入。

🦅 ArrayList 是如何扩容的？
直接看《ArrayList 动态扩容详解》文章，很详细。主要结论如下：

如果通过无参构造的话，初始数组容量为 0 ，当真正对数组进行添加时，才真正分配容量。每次按照 1.5 倍（位运算）的比率通过 copeOf 的方式扩容。
在 JKD6 中实现是，如果通过无参构造的话，初始数组容量为10，每次通过 copeOf 的方式扩容后容量为原来的 1.5 倍。

重点是 1.5 倍扩容，这是和 HashMap 2 倍扩容不同的地方。

🦅 ArrayList 集合加入 1 万条数据，应该怎么提高效率？
ArrayList 的默认初始容量为 10 ，要插入大量数据的时候需要不断扩容，而扩容是非常影响性能的。因此，现在明确了 10 万条数据了，我们可以直接在初始化的时候就设置 ArrayList 的容量！
这样就可以提高效率了~

ArrayList 与 Vector 区别？

ArrayList 和 Vector 都是用数组实现的，主要有这么三个区别：

1、Vector 是多线程安全的，线程安全就是说多线程访问同一代码，不会产生不确定的结果，而 ArrayList 不是。这个可以从源码中看出，Vector 类中的方法很多有 synchronized 进行修饰，这样就导致了 Vector 在效率上无法与 ArrayList 相比。

Vector 是一种老的动态数组，是线程同步的，效率很低，一般不赞成使用。
2、两个都是采用的线性连续空间存储元素，但是当空间不足的时候，两个类的增加方式是不同。
3、Vector 可以设置增长因子，而 ArrayList 不可以。

适用场景分析：

1、Vector 是线程同步的，所以它也是线程安全的，而 ArrayList 是线程无需同步的，是不安全的。如果不考虑到线程的安全因素，一般用 ArrayList 效率比较高。

实际场景下，如果需要多线程访问安全的数组，使用 CopyOnWriteArrayList 。
2、如果集合中的元素的数目大于目前集合数组的长度时，在集合中使用数据量比较大的数据，用 Vector 有一定的优势。

这种情况下，使用 LinkedList 更合适。

HashMap 和 Hashtable 的区别？

Hashtable 是在 Java 1.0 的时候创建的，而集合的统一规范命名是在后来的 Java2.0 开始约定的，而当时其他一部分集合类的发布构成了新的集合框架。

Hashtable 继承 Dictionary ，HashMap 继承的是 Java2 出现的 Map 接口。
2、HashMap 去掉了 Hashtable 的 contains 方法，但是加上了 containsValue 和 containsKey 方法。
3、HashMap 允许空键值，而 Hashtable 不允许。
【重点】4、HashTable 是同步的，而 HashMap 是非同步的，效率上比 HashTable 要高。也因此，HashMap 更适合于单线程环境，而 HashTable 适合于多线程环境。
5、HashMap 的迭代器（Iterator）是 fail-fast 迭代器，HashTable的 enumerator 迭代器不是 fail-fast 的。
6、HashTable 中数组默认大小是 11 ，扩容方法是 old * 2 + 1 ，HashMap 默认大小是 16 ，扩容每次为 2 的指数大小。

一般现在不建议用 HashTable 。主要原因是两点：

一是，HashTable 是遗留类，内部实现很多没优化和冗余。
二是，即使在多线程环境下，现在也有同步的 ConcurrentHashMap 替代，没有必要因为是多线程而用 Hashtable 。

🦅 Hashtable 的 **#size()** 方法中明明只有一条语句 **"return count;"** ，为什么还要做同步？
同一时间只能有一条线程执行固定类的同步方法，但是对于类的非同步方法，可以多条线程同时访问。所以，这样就有问题了，可能线程 A 在执行 Hashtable 的 put 方法添加数据，线程 B 则可以正常调用 #size() 方法读取 Hashtable 中当前元素的个数，那读取到的值可能不是最新的，可能线程 A 添加了完了数据，但是没有对 count++ ，线程 B 就已经读取 count 了，那么对于线程 B 来说读取到的 count 一定是不准确的。
而给 **#size()** 方法加了同步之后，意味着线程 B 调用 **#size()** 方法只有在线程 A 调用 put 方法完毕之后才可以调用，这样就保证了线程安全性。

HashSet 和 HashMap 的区别？

Set 是线性结构，值不能重复。HashSet 是 Set 的 hash 实现，HashSet 中值不能重复是用 HashMap 的 key 来实现的。
Map 是键值对映射，可以空键空值。HashMap 是 Map 的 hash 实现，key 的唯一性是通过 key 值 hashcode 的唯一来确定，value 值是则是链表结构。

因为不同的 key 值，可能有相同的 hashcode ，所以 value 值需要是链表结构。

他们的共同点都是 hash 算法实现的唯一性，他们都不能持有基本类型，只能持有对象。

为了更好的性能，Netty 自己实现了 key 为基本类型的 HashMap ，例如 IntObjectHashMap 。

HashSet 和 TreeSet 的区别？

HashSet 是用一个 hash 表来实现的，因此，它的元素是无序的。添加，删除和 HashSet 包括的方法的持续时间复杂度是 O(1) 。
TreeSet 是用一个树形结构实现的，因此，它是有序的。添加，删除和 TreeSet 包含的方法的持续时间复杂度是 O(logn) 。

🦅 如何决定选用 HashMap 还是 TreeMap？

对于在 Map 中插入、删除和定位元素这类操作，HashMap 是最好的选择。
然而，假如你需要对一个有序的 key 集合进行遍历， TreeMap 是更好的选择。

基于你的 collection 的大小，也许向 HashMap 中添加元素会更快，再将 HashMap 换为 TreeMap 进行有序 key 的遍历。

HashMap 和 ConcurrentHashMap 的区别？

ConcurrentHashMap 是线程安全的 HashMap 的实现。主要区别如下：

1、ConcurrentHashMap 对整个桶数组进行了分割分段(Segment)，然后在每一个分段上都用 lock 锁进行保护，相对于Hashtable 的 syn 关键字锁的粒度更精细了一些，并发性能更好。而 HashMap 没有锁机制，不是线程安全的。

JDK8 之后，ConcurrentHashMap 启用了一种全新的方式实现,利用 CAS 算法。
2、HashMap 的键值对允许有 null ，但是 ConCurrentHashMap 都不允许。

队列和栈是什么，列出它们的区别？
栈和队列两者都被用来预存储数据。
java.util.Queue 是一个接口，它的实现类在Java并发包中。
- 队列允许先进先出（FIFO）检索元素，但并非总是这样。
- Deque 接口允许从两端检索元素。
栈与队列很相似，但它允许对元素进行后进先出（LIFO）进行检索。
- Stack 是一个扩展自 Vector 的类，而 Queue 是一个接口。
  原理
  HashMap 的工作原理是什么？
  我们知道在 Java 中最常用的两种结构是数组和模拟指针（引用），几乎所有的数据结构都可以利用这两种来组合实现，HashMap 也是如此。实际上 HashMap 是一个“链表散列”。
  HashMap 是基于 hashing 的原理。
  HashMap 图解
我们使用 #put(key, value) 方法来存储对象到 HashMap 中，使用 get(key) 方法从 HashMap 中获取对象。
当我们给 #put(key, value) 方法传递键和值时，我们先对键调用 #hashCode() 方法，返回的 hashCode 用于找到 bucket 位置来储存 Entry 对象。

🦅 当两个对象的 hashCode 相同会发生什么？
因为 hashcode 相同，所以它们的 bucket 位置相同，“碰撞”会发生。
因为 HashMap 使用链表存储对象，这个 Entry（包含有键值对的 Map.Entry 对象）会存储在链表中。
🦅 hashCode 和 equals 方法有何重要性？
HashMap 使用 key 对象的 #hashCode() 和 #equals(Object obj) 方法去决定 key-value 对的索引。当我们试着从 HashMap 中获取值的时候，这些方法也会被用到。

如果这两个方法没有被正确地实现，在这种情况下，两个不同 Key 也许会产生相同的 #hashCode() 和 #equals(Object obj) 输出，HashMap 将会认为它们是相同的，然后覆盖它们，而非把它们存储到不同的地方。

同样的，所有不允许存储重复数据的集合类都使用 #hashCode() 和 #equals(Object obj) 去查找重复，所以正确实现它们非常重要。#hashCode() 和 #equals(Object obj) 方法的实现，应该遵循以下规则：

如果 o1.equals(o2) ，那么 o1.hashCode() == o2.hashCode() 总是为 true 的。
如果 o1.hashCode() == o2.hashCode() ，并不意味 o1.equals(o2) 会为 true 。

🦅 HashMap 默认容量是多少？
默认容量都是 16 ，负载因子是 0.75 。就是当 HashMap 填充了 75% 的 busket 是就会扩容，最小的可能性是（16 * 0.75 = 12），一般为原内存的 2 倍。
🦅 有哪些顺序的 HashMap 实现类？

LinkedHashMap ，是基于元素进入集合的顺序或者被访问的先后顺序排序。
TreeMap ，是基于元素的固有顺序 (由 Comparator 或者 Comparable 确定)。

🦅 我们能否使用任何类作为 Map 的 key？
我们可以使用任何类作为 Map 的 key ，然而在使用它们之前，需要考虑以下几点：

1、如果类重写了 equals 方法，它也应该重写 hashcode 方法。
2、类的所有实例需要遵循与 equals 和 hashcode 相关的规则。
3、如果一个类没有使用 equals ，你不应该在 hashcode 中使用它。
4、用户自定义 key 类的最佳实践是使之为不可变的，这样，hashcode 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保hashcode 和 equals 在未来不会改变，这样就会解决与可变相关的问题了。

比如，我有一个类MyKey ，在 HashMap 中使用它。代码如下：

//传递给MyKey的name参数被用于equals()和hashCode()中
MyKey key = new MyKey('Pankaj'); //assume hashCode=1234
myHashMap.put(key, 'Value');
// 以下的代码会改变key的hashCode()和equals()值
key.setName('Amit'); //assume new hashCode=7890
//下面会返回null，因为HashMap会尝试查找存储同样索引的key，而key已被改变了，匹配失败，返回null
myHashMap.get(new MyKey('Pankaj'));

那就是为何 String 和 Integer 被作为 HashMap 的 key 大量使用。

🦅 HashMap 的长度为什么是 2 的幂次方？
为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。
这个算法应该如何设计呢？我们首先可能会想到采用 % 取余的操作来实现。但是，重点来了：

取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作（也就是说 hash % length == hash & (length - 1) 的前提是 length 是 2 的 n 次方；）。
并且，采用二进制位操作 &，相对于 % 能够提高运算效率，

这就解释了 HashMap 的长度为什么是 2 的幂次方。

HashSet 的工作原理是什么？

HashSet 是构建在 HashMap 之上的 Set hashing 实现类。让我们直接撸下源码，代码如下：

// HashSet.java
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

map 属性，当我们创建一个 HashMap 对象时，其内部也会创建一个 map 对象。后续 HashSet 所有的操作，实际都是基于这个 map 之上的封装。
PRESENT 静态属性，所有 map 中 KEY 对应的值，都是它，避免重复创建。

OK ，再来看一眼 add 方法，代码如下：

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

是不是一目了然。

🦅 HashSet 如何检查重复？

艿艿：正如我们上面看到 HashSet 的实现原理，我们自然可以推导出，HashMap 也是如何检查重复滴。

如下摘取自《Head First Java》第二版：
当你把对象加入 HashSet 时，HashSet会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较。

如果没有相符的 hashcode ，HashSet会假设对象没有重复出现。
但是如果发现有相同 hashcode 值的对象，这时会调用 equals 方法来检查 hashcode 相等的对象是否真的相同。
- 如果两者相同，HashSet 就不会让加入操作成功。
- 如果两者不同，HashSet 就会让加入操作成功。
  EnumSet 是什么？
  java.util.EnumSet ，是使用枚举类型的集合实现。
当集合创建时，枚举集合中的所有元素必须来自单个指定的枚举类型，可以是显示的或隐示的。EnumSet 是不同步的，不允许值为 null 的元素。
它也提供了一些有用的方法，比如 #copyOf(Collection c)、#of(E first, E... rest) 和 #complementOf(EnumSet s) 方法。

关于 EnumSet 的源码解析，见《EnumSet 源码分析》文章。

TODO TreeMap 原理

Java 中的 TreeMap 是使用红黑树实现的。
TODO TreeMap和TreeSet在排序时如何比较元素？Collections工具类中的sort()方法如何比较元素？
等到源码解析后，在进行补充。

Java Priority Queue 是什么?

PriorityQueue 是一个基于优先级堆的无界队列，它的元素都以他们的自然顺序有序排列。

在它创建的时候，我们可以可以提供一个比较器 Comparator 来负责PriorityQueue 中元素的排序。
PriorityQueue 不允许 `` null元素，不允许不提供自然排序的对象，也不允许没有任何关联 Comparator 的对象。
最后，PriorityQueue 不是线程安全的，在执行入队和出队操作它需要 O(log(n)) 的时间复杂度。

🦅 poll 方法和 remove 方法的区别？
poll 和 remove 方法，都是从队列中取出一个元素，差别在于：

poll 方法，在获取元素失败的时候会返回空
remove() 方法，失败的时候会抛出异常。

🦅 LinkedHashMap 和 PriorityQueue 的区别是什么？

PriorityQueue 保证最高或者最低优先级的的元素总是在队列头部，LinkedHashMap 维持的顺序是元素插入的顺序。
当遍历一个 PriorityQueue 时，没有任何顺序保证，但是 LinkedHashMap 课保证遍历顺序是元素插入的顺序。

彩蛋
参考与推荐如下文章：
《2018 年最新 Java 面试题及答案整理》
《互联网常见的 14 个 Java 面试题》

集合框架面试题

集合容器概述

集合框架的整体架构

集合框架中，各个List、Map、Set 的初始容量，扩容策略

集合框架中，各个List、Map、Set 的 put、get、resize 方法

集合框架中，各个List、Map、Set 的线程安全策略

Java集合的快速失败机制 “fail-fast”

怎么确保一个集合不能被修改? —> 变成只读

Collection接口

迭代器 Iterator 是什么？

List 接口

Iterator 和 ListIterator 有什么区别？

遍历一个 List 有哪些不同的方式？每种方法的实现原理是什么？Java 中 List 遍历的最佳实践是什么？

说一下 ArrayList 的优缺点

ArrayList 和 LinkedList 的区别是什么？

ArrayList 和 Vector 的区别是什么？

多线程场景下如何使用List

为什么 ArrayList 的 elementData 加上 transient 修饰？

Set 接口

说一下 HashSet 的实现原理？

HashSet如何检查重复？HashSet是如何保证数据不可重复的？

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

==与equals的区别

Map 接口

什么是Hash算法

说一下HashMap的实现原理？

HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底层实现

HashMap的put方法的具体流程？

HashMap的扩容操作是怎么实现的？

HashMap是怎么解决哈希冲突的？

Java 集合框架的基础接口有哪些？

什么是迭代器(Iterator)？

Comparable 和 Comparator 的区别?

有哪些关于 Java 集合框架的最佳实践？

区别

List 和 Set 区别？

List 和 Map 区别？

Array 和 ArrayList 有何区别？什么时候更适合用 Array？

ArrayList 与 LinkedList 区别？