Java Collection Framework 面试题

1. Collection 部分

List 和 Set 有什么区别？

答：

List 接口和 Set 接口它们都是 Collection 接口的子接口，它们的区别分为以下几个方面：

1. 从历史角度看：List 比 Set 要早。List 出现在 JDK 1.0 ，而 Set 出现在 JDK 1.2 。

2. 从底层实现看：List 的常用实现方式是动态数组和链表，Set 的常用实现方式都是利用 Map 实现的。这个根本原因导致了以下现象：

   • List 允许有重复元素，而 Set 不允许有重复元素。
   • List 允许有多个 null 值，而 Set 只允许有一个 null 值。
   • List 可以保证元素的存储顺序，Set 无法保证元素的存储顺序。

哪种集合可以实现自动排序？

答：TreeSet 。TreeSet 除了实现了 Set 接口之外，还实现了 SortedSet ，而 SortedSet 接口要求它的实现类必须有自动排序能力。TreeSet 自然必须有这种能力。

Vector 和 ArrayList 初始化大小和容量扩充有什么区别？

Vector 和 ArrayList 初始化大小和容量扩充区别，并非它们的核心区别。

答：

• 初始化容量相同。默认都是 10 。
• 容量扩充不同。Vector 是增加 1 倍；ArrayList 是增加 0.5 倍。

Vector、ArrayList、LinkedList 有什么区别？

答：这三者都是 List 的子类，它们的差异如下：

1. 从历史角度看：Vector 出现最早，JDK 1.0 就有了；ArrayList 和 LinkedList 是 JDK 1.2 出现的。

2. 从线程安全角度看：Vector 是线程安全的；ArrayList 和 LinkedList 是线程不安全的。

3. 从底层接口看：Vector 是基于动态数组的；ArrayList 也是基于动态数组的；LinkedList 是基于双向链表的。这也导致了：

   1. Vector 和 ArrayList 内存总开销更小，但需要是连续内存空间；LinkedList 内存总开销更大，但可以利用零碎的内存空间，无需连续内存空间。

   2. Vector 和 ArrayList 访问更快；LinkedList 增删更快。

4. 其它细节上的区别：

   • Vector 扩容是增加 1 倍；ArrayList 扩容是增加 0.5 倍；LinkedList 无需考虑扩容问题。

Vector、ArrayList、LinkedList 使用场景有什么区别？

答：

1. 因为『线程安全』方面的差异导致使用场景的不同：Vector 可以直接用于多线程场景，因为它是线程安全的；ArrayList 和 LinkedList 在多线程场景下则需要我们自己去处理线程安全问题。

2. 因为『底层实现』方面的差异导致使用场景的不同：Vector 和 ArrayList 适合随机访问场景，通过下标索引（位置）直接访问数据；而 LinkedList 则使用频繁增删的场景。

Collection 和 Collections 有什么区别？

答：

常见的工具类的命名风格有 2 种：

1. 以 util 或 utils 结尾；

2. 以 s 结尾。

Collection 是接口，它是 List、Set 和 Queue 接口的父接口，是 Java 集合框架的 2 个顶层接口之一。

Collections 是一个服务于 Collection 的工具类，它提供了一系列静态方法帮我们简化对 Collection（及其子接口的实现类）的操作。例如：Collections.sort() 排序。

以下选项没有继承 Collection 接口的是？

A：List
B：Set
C：Map
D：HashSet

答：C

从『辈分』上讲，Map 和 Collection 是平级的同辈。

LinkedHashSet 如何保证有序和唯一性？

答：LinkedHashSet 底层最终使用到了 LinkedHashMap，所以，这个问题的本质在于：LinkedHashMap 如何保证 key 的有序和唯一性？

• 唯一性：存入到 LinkedHashSet 中的的值最终会作为 key 值（value 值为 null），存入到 LinkedHashMap 中，而 Map 的 key 要求唯一，因此 LinkedHashSet 中的值也就是唯一的。

• 有序性：LinkedHashMap 会用一个双链表按插入顺序，将所有键值对（的键）『串』起来。这样就能够按加入顺序来依次访问各个键值对。因此，LinkedHashMap 自然也就是有序的。

map = (((HashSet<?>)this) instanceof LinkedHashSet ?
      	new LinkedHashMap<E,Object>(capacity, loadFactor) :
      	new HashMap<E,Object>(capacity, loadFactor));

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

答：

HashSet 底层最终使用到了 HashMap ，所以，这个问题的本质在于：HashMap 是如何保证数据不重复的？

添加到 Set 中的值，会作为一个键值对的 key（value 为null）添加到 HashMap 中，而 HashMap 对键值对的键的要求是唯一，因此 HashSet 的键自然就是要求唯一。

执行以下程序会输出什么结果？为什么？

Integer num = 10;
Integer num2 = 5;
System.out.println(num.compareTo(num2));

num.compareTo(num2) 表达的逻辑就是 num - num2 的逻辑，当然，它的值并不是实际相减的值，而是代表 大、小、相等的 1、-1 和 0 。

因此，上面的值自然就是 1 。

如何用程序实现后进先出的栈结构？

答：

1. 线程安全的方案：使用 Stack 。

    Stack<Integer> stack = new Stack();
    stack.push(10);
    stack.push(20);
    stack.push(30);
    for (int i = 0; i < 3; i++) {
        System.out.print(stack.pop() + " ");
    }
   

2. 线程不安全的方案：使用 LinkedList（它实现了 Deque 接口）。

   LinkedList<Integer> list = new LinkedList<>();
   
   list.addFirst(10);
   list.addFirst(20);
   list.addFirst(30);
   
   for (int i = 0; i < 3; i++) {
       System.out.print(list.removeFirst() + " ");
   }
   

程序执行结果：c b a

LinkedList 中的 peek() 和 poll() 有什么区别？

答：peek 方法是在查询头部元素，poll 方法是删除头部元素，并返回删除的那个元素。

虽然返回值一样，但是执行完 peek 方法后，LinkedList 中元素不会少，而执行完 poll 方法后，会少一个。

Comparable 和 Comparator 有哪些区别？

答：Comparable 和 Comparator 的主要区别如下：

• Comparable 位于 java.lang 包下，而 Comparator 位于 java.util 包下；
• Comparable 在排序类的内部实现，而 Comparator 在排序类的外部实现；
• Comparable 需要重写 CompareTo() 方法，而 Comparator 需要重写 Compare() 方法；
• Comparator 在类的外部实现，更加灵活和方便。

2. Map 部分

Map 常见实现类有哪些？

答：Map 的常见实现类如下列表：

Map                    (jdk 1.0)
|── Hashtable          (jdk 1.0)
|── TreeMap            (jdk 1.2)
|── HashMap            (jdk 1.2)
|   └── LinkedHashMap  (jdk 1.4)
└── ConcurrentHashMap  (jdk 1.5)

使用 HashMap 可能会遇到什么问题？如何避免？

答：

在 JDK 1.8 之前，在并发场景中，如果有两个线程对同一个 HashMap 进行扩容，会出现循环依赖，造成死循环。

这是因为 HashMap 在扩容的时候会对链表进行一次倒序处理，假设两个线程同时执行扩容操作，第一个线程正在执行 B→A 的时候，第二个线程又执行了 A→B ，这个时候就会出现 B→A→B 的问题，造成死循环。

多线程场景，本就不应该使用 HashMap，因该使用多线程版本 ConcurrentHashMap 。

另外，JDK 1.8 中上述算法有变动，也不会出现这个问题。

以下说法正确的是？

A：Hashtable 和 HashMap 都是非线程安全的
B：ConcurrentHashMap 允许 null 作为 key
C：HashMap 允许 null 作为 key
D：Hashtable 允许 null 作为 key

答：C

	线程安全	允许 null-key	允许 null-val
Hashtable	Yes	No	No
HashMap	No	Yes	Yes
ConcurrentHashMap	yes	No	No

TreeMap 怎么实现根据 value 值倒序？

答：使用 Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() 自定义比较器实现，先把 TreeMap 转换为 ArrayList，在使用 Collections.sort() 根据 value 进行倒序，完整的实现代码如下。

TreeMap<String, Integer> treeMap = new TreeMap();
treeMap.put("1", 1);
treeMap.put("2", 2);
treeMap.put("3", 3);
treeMap.put("4", 4);

// map.entrySet() 转成 List
List<Map.Entry<String, Integer>> list = new ArrayList<>(treeMap.entrySet());

// 通过比较器实现比较排序
Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
    public int compare(Map.Entry<String, Integer> m1, Map.Entry<String, Integer> m2) {
        return m2.getValue().compareTo(m1.getValue());
    }
});

// 打印结果，验证
for (Map.Entry<String, Integer> item : list) {
    System.out.println(item.getKey() + ":" + item.getValue());
}

程序执行结果：

4:4
3:3
2:2
1:1 

以下哪个 Set 实现了自动排序？

A：LinedHashSet
B：HashSet
C：TreeSet
D：AbstractSet

答：C

TreeSet 实现了 SortedSet 接口，而 内部有序 是 SortedSet 对它的实现类的要求。

以下程序运行的结果是什么？

Hashtable hashtable = new Hashtable();
hashtable.put("table", null);
System.out.println(hashtable.get("table"));

答：

程序执行报错：java.lang.NullPointerException。

Hashtable 不允许 null-key 和 null-value 。它的替代者 ConcurrentHashMap 和它保持一致，也不允许 null-key 和 null-value 。

HashMap 有哪些重要的参数？用途分别是什么？

答：HashMap 有两个重要的参数：容量（Capacity）和负载因子（LoadFactor）。

• 容量（Capacity）：是指 HashMap 中桶（也就是数组的单元）的数量，默认的初始值为 16。

• 负载因子（LoadFactor）：也被称为装载因子，用于 Map 的扩容。

HashMap 和 Hashtable 有什么区别？

答：

• 从历史角度看：Hashtable 要早于 HashMap 出现（1.0 VS 1.2）。

• 从线程安全角度看：Hashtable 是线程安全的；HashMap 是线程不安全的。

• 从底层数据结构看：从 JDK 1.8 之前，两者底层数据结构一样，都是数组+链表，但是 JDK 1.8 中 HashMap 有变动（升级），底层数据结构变成了数组+链表+红黑树。

• 从其他的一些零碎细节看：

  • Hashtalbe 不允许 null-key 和 null-value，而 HashMap 允许。

  • Hashtable 还继承了 Dictonary 类，而 HashMap（和其它 Map 实现类）则没有。

什么是哈希冲突？

答：

当输入两个不同值（对象），根据同一散列函数计算出相同的散列值的现象，我们就把它叫做哈希冲突，也叫哈希碰撞。

哈希冲突是现象，不是问题。

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

答：

Hashtable、HashMap 它们采用的处理方式叫『链地址法』。

这种方法的基本思想是将所有哈希地址为 i 的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第 i 个单元中，因而查找、插入和删除主要在同义词链（红黑树）中进行。链地址法适用于经常进行插入和删除的情况。

还有其它的一些处理方式。

HashMap 的扩容为什么是 2^n ？

答：这样做的目的是为了让散列更加均匀，从而减少哈希碰撞，以提供代码的执行效率。

有哈希冲突的情况下 HashMap 如何取值？

答：

遍历链表（红黑树）。

以下程序会输出什么结果？

class Person {
    private Integer age;
    // getter /setter

    public boolean equals(Object o) {
        if (o == null || !(o instanceof Person)) {
            return false;
        } else {
            return this.getAge().equals(((Person) o).getAge());
        }
    }

    public static void main(String[] args) {
        HashMap<Person, Integer> hashMap = new HashMap<>();
        Person person = new Person(18);
        hashMap.put(person, 1);
        System.out.println(hashMap.get(new Person(18)));
    }
}

答：1

题目解析：因为 Person 重写了 equals 和 hashCode 方法，所有 person 对象和 new Person(18) 的键值相同，所以结果就是 1。

为什么重写 equals() 时一定要重写 hashCode()？

答：因为 Java 规定：如果两个对象 equals 比较相等（结果为 true），那么调用 hashCode 也必须相等。

如果重写了 equals() 但没有重写 hashCode()，就会与规定相违背。

HashMap 在 JDK 7 多线程中使用会导致什么问题？

答：HashMap 在 JDK 7 中会导致循环引用，从而造成死循环的问题。

因为在 JDK 7 中，多线程进行 HashMap 扩容时会导致链表的循环引用，这个时候使用 get() 获取元素时就会导致死循环，造成 CPU 100% 的情况。

HashMap 在 JDK 7 和 JDK 8 中有哪些不同？

答：HashMap 在 JDK 7 和 JDK 8 的主要区别如下。

• 存储结构：JDK 7 使用的是数组 + 链表；JDK 8 使用的是数组 + 链表 + 红黑树。
• 存放数据的规则：JDK 7 无冲突时，存放数组；冲突时，存放链表；JDK 8 在没有冲突的情况下直接存放数组，有冲突时，当链表长度小于 8 时，存放在单链表结构中，当链表长度大于 8 时，树化并存放至红黑树的数据结构中。
• 插入数据方式：JDK 7 使用的是头插法（先将原位置的数据移到后 1 位，再插入数据到该位置）；JDK 8 使用的是尾插法（直接插入到链表尾部/红黑树）。

3. Queue

ArrayBlockingQueue 和 LinkedBlockingQueue 的区别是什么？

答：

从底层实现角度看：ArrayBlockingQueue 是基于数组实现的；LinkedBlockingQueue 是基于链表实现的。这个根本原因导致了如下现象：

• ArrayBlockingQueue 使用时必须指定容量值，LinkedBlockingQueue 可以不用指定；
• ArrayBlockingQueue 的最大容量值是使用时指定的，并且指定之后就不允许修改；而 LinkedBlockingQueue 最大的容量为 Integer.MAX_VALUE；

LinkedList 中 add() 和 offer() 有什么关系？

答：add() 和 offer() 都是添加元素到队列尾部。offer 方法是基于 add 方法实现的，Offer 的源码如下：

public boolean offer(E e) {
   return add(e);
}

Queue 和 Deque 有什么区别？

答：Deque 是双端队列，Queue 则是一般队列（单端队列）。Deque 功能比 Queue 功能更多。

一般队列是先进先出，也就是只有先进的才能先出；而双端队列则是两端都能插入和删除元素。

LinkedList 属于一般队列还是双端队列？

答：LinkedList 实现了 Deque 接口，属于双端队列。

以下说法错误的是？

A：DelayQueue 内部是基于 PriorityQueue 实现的
B：PriorityBlockingQueue 不是先进先出的数据存储方式
C：LinkedBlockingQueue 默认容量是无限大的
D：ArrayBlockingQueue 内部的存储单元是数组，初始化时必须指定队列容量

答：C

LinkedBlockingQueue 默认容量是 Integer.MAX_VALUE，并不是无限大的。

关于 ArrayBlockingQueue 说法不正确的是？

A：ArrayBlockingQueue 是线程安全的
B：ArrayBlockingQueue 元素允许为 null
C：ArrayBlockingQueue 主要应用场景是“生产者-消费者”模型
D：ArrayBlockingQueue 必须显示地设置容量

答：B

ArrayBlockingQueue 不允许元素为 null，如果添加一个 null 元素，会抛 NullPointerException 异常。

以下程序执行的结果是什么？

PriorityQueue priorityQueue = new PriorityQueue();
priorityQueue.add(null);
System.out.println(priorityQueue.size());

答：程序执行报错，PriorityQueue 不能插入 null。

Java 中常见的阻塞队列有哪些？

答：Java 中常见的阻塞队列如下：

• ArrayBlockingQueue，由数组结构组成的有界阻塞队列；
• PriorityBlockingQueue，支持优先级排序的无界阻塞队列；
• LinkedBlockingQueue，由链表结构组成的阻塞队列；

有界队列和无界队列有哪些区别？

答：有界队列和无界队列的区别如下：

• 有界队列：有固定大小的队列叫做有界队列，比如：new ArrayBlockingQueue(6)，6 就是队列的大小。

• 无界队列：指的是没有设置固定大小的队列，这些队列的特点是可以直接入列，直到溢出。它们并不是真的无界，它们最大值通常为 Integer.MAX_VALUE，只是平常很少能用到这么大的容量（超过 Integer.MAX_VALUE），因此从使用者的体验上，就相当于 “无界”。

如何手动实现一个延迟消息队列？

答：说到延迟消息队列，我们应该可以第一时间想到要使用 DelayQueue 延迟队列来解决这个问题。实现思路，消息队列分为生产者和消费者，生产者用于增加消息，消费者用于获取并消费消息，我们只需要生产者把消息放入到 DelayQueue 队列并设置延迟时间，消费者循环使用 take() 阻塞获取消息即可。完整的实现代码如下：

public class CustomDelayQueue {
    // 消息编号
    static AtomicInteger MESSAGENO = new AtomicInteger(1);

    public static void main(String[] args) throws InterruptedException {
        DelayQueue<DelayedElement> delayQueue = new DelayQueue<>();
        // 生产者1
        producer(delayQueue, "生产者1");
        // 生产者2
        producer(delayQueue, "生产者2");
        // 消费者
        consumer(delayQueue);
    }

    //生产者
    private static void producer(DelayQueue<DelayedElement> delayQueue, String name) {
        new Thread(new Runnable() {
            @Override
            public void run() {
                while (true) {
                    // 产生 1~5 秒的随机数
                    long time = 1000L * (new Random().nextInt(5) + 1);
                    try {
                        Thread.sleep(time);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    // 组合消息体
                    String message = String.format("%s，消息编号：%s 发送时间：%s 延迟：%s 秒",
                            name, MESSAGENO.getAndIncrement(), DateFormat.getDateTimeInstance().format(new Date()), time / 1000);
                    // 生产消息
                    delayQueue.put(new DelayedElement(message, time));
                }
            }
        }).start();
    }

    //消费者
    private static void consumer(DelayQueue<DelayedElement> delayQueue) {
        new Thread(new Runnable() {
            @Override
            public void run() {
                while (true) {
                    DelayedElement element = null;
                    try {
                        // 消费消息
                        element = delayQueue.take();
                        System.out.println(element);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }).start();
    }

    // 延迟队列对象
    static class DelayedElement implements Delayed {
        // 过期时间（单位：毫秒）
        long time = System.currentTimeMillis();
        // 消息体
        String message;
        // 参数：delayTime 延迟时间（单位毫秒）
        public DelayedElement(String message, long delayTime) {
            this.time += delayTime;
            this.message = message;
        }
        @Override
        // 获取过期时间
        public long getDelay(TimeUnit unit) {
            return unit.convert(time - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
        }
        @Override
        // 队列元素排序
        public int compareTo(Delayed o) {
            if (this.getDelay(TimeUnit.MILLISECONDS) > o.getDelay(TimeUnit.MILLISECONDS))
                return 1;
            else if (this.getDelay(TimeUnit.MILLISECONDS) < o.getDelay(TimeUnit.MILLISECONDS))
                return -1;
            else
                return 0;
        }
        @Override
        public String toString() {
            // 打印消息
            return message + " |执行时间：" + DateFormat.getDateTimeInstance().format(new Date());
        }
    }
}

以上程序支持多生产者，执行的结果如下：

生产者1，消息编号：1 发送时间：2019-6-12 20:38:37 延迟：2 秒 |执行时间：2019-6-12 20:38:39

生产者2，消息编号：2 发送时间：2019-6-12 20:38:37 延迟：2 秒 |执行时间：2019-6-12 20:38:39

生产者1，消息编号：3 发送时间：2019-6-12 20:38:41 延迟：4 秒 |执行时间：2019-6-12 20:38:45

生产者1，消息编号：5 发送时间：2019-6-12 20:38:43 延迟：2 秒 |执行时间：2019-6-12 20:38:45

......