Java集合常见面试题

面试题

参见原文
1. Java集合框架面试题
2. java面试题------40个Java集合面试问题和答案

介绍Collection框架的结构

集合是Java中的一个非常重要的一个知识点，主要分为List、Set、Map、Queue三大数据结构。它们在Java中的结构关系如下：

• Collection接口是List、Set、Queue的父级接口。
• Set接口有两个常用的实现类：HashSet和TreeSet。List接口的常用接口有ArrayList和Vector接口。
• Map接口有两个常用的实现类：Hashtable和HashMap。

Collecntion和Map区别？（数据结构、存储特点）

1. 存储特点：

   • List存储的是单列数据的集合。
   • Map存储的是key、value类型的数据集合。

2. 数据存储方面

   • List存储的数据是有序（存储顺序和取出顺序一致）且可以重复的。
   • Map中存储的数据是无序且key值不能重复。（但value值可以重复）。

简单介绍一下Collection 常见子类

• Set是不允许有重复元素的集合。
• List是允许有重复元素的集合。
• Queue JDK1.5新增，与上面两个集合类主要是的区分在于Queue主要用于存储数据，而不是处理数据。

List

无序，可重复

1. ArrayList
   线程不安全，底层使用数组来实现，随机访问比较快，而对于中间元素的插入删除效率比较低，而且还需要考虑扩容问题。
2. LinkedList
   线程不安全的，基于链表实现的，随机访问慢，但是对于中间元素的插入和删除效率更高。
3. Vector：
   线程安，底层使用数组实现的。多线程环境下 需要同步加锁，性能比较低。

set

不允许有重复元素的集合。是否是重复是根据equals方法来判定的。

1. HashSet
   底层是由HashMap实现的，通过对象的HashCode方法与equals方法来保证插入元素的唯一性，无序。

2. LinkedHashSet
   底层数据结构由哈希表和链表组成。哈希表保证元素的唯一性，链表保证元素有序。

3. TreeSet
   基于 TreeMap 的 NavigableSet 实现。使用元素的自然顺序对元素进行排序，或者根据创建 set 时提供的Comparator 进行排序，具体取决于使用的构造方法。 元素唯一。

Queue

Queue用于模拟"队列"这种数据结构(先进先出 FIFO)。队列的头部保存着队列中存放时间最长的元素，队列的尾部保存着队列中存放时间最短的元素。新元素插入(offer)到队列的尾部，访问元素(poll)操作会返回队列头部的元素，队列不允许随机访问队列中的元素。结合生活中常见的排队就会很好理解这个概念

1. PriorityQueue
   PriorityQueue并不是一个比较标准的队列实现，PriorityQueue保存队列元素的顺序并不是按照加入队列的顺序，而是按照队列元素的大小进行重新排序，这点从它的类名也可以看出来。

2. Deque
   Deque接口代表一个"双端队列"，双端队列可以同时从两端来添加、删除元素，因此Deque的实现类既可以当成队列使用、也可以当成栈使用。

3. ArrayDeque
   是一个基于数组的双端队列，和ArrayList类似，它们的底层都采用一个动态的、可重分配的Object[]数组来存储集合元素，当集合元素超出该数组的容量时，系统会在底层重新分配一个Object[]数组来存储集合元素

HashSet和TreeSet有什么区别，什么时候用它们？

1. HashSet中的元素不能重复，没有顺序。
2. TreeSet中的元素不能重复，但有顺序，可以在构造TreeSet的时候传入Comparator比较器，来让加入TreeSet的元素自动排序。

所以，一般当集合中的元素需要排序时，用TreeSet。其他情况一般都用HashSet，因为没有默认排序，速度比TreeSet块。

fail-fast 与 fail-safe的区别？

快速失败（fail—fast）

在用迭代器遍历一个集合对象时，如果遍历过程中集合对象中的内容发生了修改（增加、删除、修改），则会抛出ConcurrentModificationException。

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

注意：这里异常的抛出条件是检测到 modCount！=expectedmodCount这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。

场景：java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）。

安全失败（fail—safe）

采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发ConcurrentModificationException。

缺点：基于拷贝内容的优点是避免了ConcurrentModificationException，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。

场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。

HashMap和HashTable的区别？

HashMap和Hashtable都实现了Map接口，看起来很相似，但它们之间有如下的区别：

• HashMap的键值对均可为null，而Hashtable不允许键或值为null。
• Hashtable是线程安全的，而HashMap则不是线程安全的。因此，HashMap适用于单线程环境下，Hashtable适合在多线程环境下使用。
• 在Java1.4中引入了LinkedHashMap，HashMap的一个子类，假如你想要遍历顺序，你很容易从HashMap转向LinkedHashMap，但是HashTable不是这样的，它的顺序是不可预知的。
• HashMap提供对key的Set进行遍历，因此它是fail-fast的，但HashTable提供对key的Enumeration进行遍历，它不支持fail-fast。
• Hashtable是一种比较古老的类，应该尽量使用 ConcurrentHashMap。

怎样决定何时使用HashMap何时使用TreeMap?

对于插入、删除、定位元素频繁的操作，HashMap提供了最好的效率。如果想要按key的排序来遍历，那么TreeMap是不二选择。某些情况下，依赖集合的大小，先向HashMap中添加元素，然后转换为TreeMap再按key的排序进行遍历也许会带来效率上的提高。

ArrayList和Vector的相同点和不同点？

ArrayList和Vector都是基于数据实现的，但是ArrayList是线程不安全的，而Vector是线程安全的。因而ArrayList的性能更好，不同考虑同步。

HashMap怎么实现有序？

可以转化放入TreeMap里面。

在List里面怎么去掉重复的元素？

通过把List里面的数据放入HashSet就可以去除重复。

在List里面有几种排序？

想要对数组内的对象进行排序，只需调用Arrays.sort()方法。想要对list中的对象进行排序，只需调用Collections.sort()方 法。但是，这两种方法要么实现了Comparable接口的sort()方法，对集合进行自然排序，要么实现了Comparator接口中的sort() 方法，能按某些条件(criteria)进行排序。其实Collections内部会调用Array的排序方法，因此除了在排序前Collections 类会将list中的元素先复制到数组中消耗点时间外，它们在排序性能上几乎没有差别。

ArrayList集合加入1万条数据，应该怎么提高效率

因为ArrayList的底层是数组实现，并且数组的默认值是10，如果插入10000条要不断的扩容，耗费时间，所以我们调用ArrayList的指定容量的构造器方法ArrayList(int size) 就可以实现不扩容，就提高了性能。

如果我要存储很多的数据，但是有不需要重复的，要选择什么容器？

Set容器，它是不允许重复的。

当集合作为参数传入方法中时，如何确保方法不会修改它？

我们可以通过调用Collections.unmodifiableCollection(Collection c)方法来创建一个只读的集合，然后再将它传入函数中，这样就会确保任何企图修改集合的操作都会引起 UnsupportedOperationException异常。

根据给定的集合如何创建一个synchronized的集合？

可以调用Collections.synchronizedCollection(Collection c)方法，会返回一个同步的集合。