Java集合框架面试题

常见集合

集合可以看作是一种容器，用来存储对象信息。
数组和集合的区别：
（1）数组长度不可变化而且无法保存具有映射关系的数据；集合类用于保存数量不确定的数据，以及保存具有映射关系的数据。
（2）数组元素既可以是基本类型的值，也可以是对象；集合只能保存对象。
Java集合类主要由两个接口Collection和Map。
Collection接口派生出来的常用集合有：

• （主要）ArrayList、LinkedList
• （次要）HashSet、TreeSet、Vector(过去式)
  Map接口派生出来的常用集合有：
• （主要）HashMap
• （次要）TreeMap

简要说明List、Set、Map的区别
List集合：有序、可重复集合，集合中每个元素都有其对应的顺序索引。
实现List接口的集合主要有：ArrayList、LinkedList、Vector。

Set集合：有序，不可重复集合，重复元素会覆盖掉。
实现Set接口的集合主要有：HashSet、TreeSet。

Map集合：以键值对的方式存储，元素无存入顺序，元素不可重复，重复元素会覆盖掉，key、value都可以为null
实现Map接口的集合主要有：HashMap、HashTable、TreeMap。

（1）ArrayList
ArrayList是一个动态数组，也是我们最常用的集合，是List类的典型实现。它允许任何符合规则的元素插入甚至包括null。每一个ArrayList都有一个初始容量10，该容量代表了数组的大小。随着容器中的元素不断增加，容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。

（2）LinkedList
LinkedList是List接口的另一个实现，除了可以根据索引访问集合元素外，LinkedList还实现了Deque接口，可以当作双端队列来使用，也就是说，既可以当作“栈”使用，又可以当作队列使用。

（3）Vector
与ArrayList相似，但是Vector是同步的。所以说Vector是线程安全的动态数组。它的操作与ArrayList几乎一样。

（4）HashSet
HashSet是不能保证元素的顺序，不是线程同步的集合，如果多线程操作HashSet集合，则应通过代码来保证其同步，集合元素值可以是null

（5）TreeSet
TreeSet可以保证元素处于排序状态，它采用红黑树的数据结构来存储集合元素。TreeSet支持两种排序方法：自然排序和定制排序，默认采用自然排序。

（6）HashMap
HashMap基于hashing原理，通过put()和get()方法存储和获取对象。当我们将键值对传递给put()方法时，它调用建对象的hashCode()方法来计算hashCode值，然后找到bucket位置来储存值对象。当获取对象时，通过建对象的equals()方法找到正确的键值对，然后返回对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会存储在链表的下一个节点中。

（7）HashTable
与HashMap的关系完全类似于ArrayList与Vertor，HashMap是线程不安全，HashTable是线程安全的，HashMap可以使用null值最为key或value；Hashtable不允许使用null值作为key和value，如果把null放进HashTable中，将会发生空指针异常。

（8）TreeMap
一个红黑树的数据结构，每个key-value对作为红黑树的一个节点。TreeMap存储key-value对时，需要根据key对节点进行排序。

面试常问

1. ArrayList和Vector的区别。

Vector：线程安全，数据增长原来的2倍。
ArrayList：非线程安全，数据增长没有明确规定，从源码来看是增长原来的1.5倍。

2. HashMap和HashTable的区别。

• 线程安全性不同：HashMap非线程安全，HashTable线程安全
• 继承的父类不同：Hashtable继承自Dictionary类，而HashMap继承自AbstractMap类。但二者都实现了Map接口。
• key和value是否允许null值：Hashtable中，key和value都不允许出现null值
• 两个遍历方式的内部实现上不同：链接: Map集合遍历

3. ArrayList,Vector,LinkedList的存储性能和特性。

ArrayList和Vector都是使用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢，Vector由于使用了synchronized方法线程安全，性能上比ArrayList差。
而LinkedList使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，所以索引数据较慢，但是插入数据时只需要记录本项的前后项即可，所以插入速度较快。

4. HashMap的数据结构。

jdk1.7：Hashmap实际上是一个数组和链表的散列表
jdk1.8：当链表中的元素超过了 8 个以后，会将链表转换为红黑树

5. HashMap的工作原理是什么？

以键值对(key-value)的形式存储元素的。HashMap需要一个hash函数，它使用hashCode()和equals()方法来向集合/从集合添加和检索元素。当调用put()方法的时候，HashMap会计算key的hash值，然后把键值对存储在集合中合适的索引上。如果key已经存在了，value会被更新成新值。HashMap的一些重要的特性是它的容量(capacity)，负载因子(loadfactor)和扩容极限(thresholdresizing)

6. HashMap什么时候进行扩容呢？

当hashmap中的元素个数超过数组大小loadFactor（加载因子）时，就会进行数组扩容，loadFactor的默认值为0.75。

7. List、Map、Set三个接口，存取元素时，各有什么特点？

List与Set具有相似性，它们都是单列元素的集合
Map与List和Set不同，它是双列的集合
List表示有先后顺序的集合
Set无法拥有重复元素
Map保存key-value值，value可多值

8. Set里的元素是不能重复的，那么用什么方法来区分重复与否呢?是用==还是equals()?它们有何区别?

Set里的元素是不能重复的，元素重复与否是使用equals()方法进行判断的。equals()和==方法决定引用值是否指向同一对象equals()在类中被覆盖，为的是当两个分离的对象的内容和类型相配的话，返回真值。

9. 两个对象值相同(x.equals(y)==true)，但却可有不同的hashcode，这句话对不对？

对，如果对象要保存在HashSet或HashMap中，它们的equals相等，那么，它们的hashcode值就必须相等。如果不是要保存在HashSet或HashMap，则与hashcode没有什么关系了，这时候hashcode不等是可以的，例如arrayList存储的对象就不用实现hashcode，当然，我们没有理由不实现，通常都会去实现的。

10. Java集合类框架的基本接口有哪些？

Collection：代表一组对象，每一个对象都是它的子元素。
Set：不包含重复元素的Collection。
List：有顺序的collection，并且可以包含重复元素。
Map：可以把键(key)映射到值(value)的对象，键不能重复。

11. HashSet的底层实现是什么？

通过看源码知道HashSet的实现是依赖于HashMap的，HashSet的值都是存储在HashMap中的。在HashSet的构造法中会初始化一个HashMap对象，HashSet不允许值重复，因此，HashSet的值是作为HashMap的key存储在HashMap中的，当存储的值已经存在时返回false。

12. HashSet和TreeSet有什么区别？

HashSet是由一个hash表来实现的，因此，它的元素是无序的。add()，remove()，contains()TreeSet是由一个树形的结构来实现的，它里面的元素是有序的。因此，add()，remove()，contains()方法的时间复杂度是O(logn)

13. 为什么集合类没有实现Cloneable和Serializable接口？

克隆(cloning)或者是序列化(serialization)的语义和含义是跟具体的实现相关的。因此，应该由集合类的具体实现来决定如何被克隆或者是序列化。

14. 数组(Array)和列表(ArrayList)有什么区别？什么时候应该使用Array而不是ArrayList？

Array可以包含基本类型和对象类型，ArrayList只能包含对象类型。Array大小是固定的，ArrayList的大小是动态变化的。ArrayList处理固定大小的基本数据类型的时候，这种方式相对比较慢。

15. Collection和Collections的区别。

collection是集合类的上级接口,继承与它的接口主要是set和list。collections类是针对集合类的一个帮助类.它提供一系列的静态方法对各种集合的搜索,排序,线程安全化等操作。

16. Comparable和Comparator接口是干什么的？列出它们的区别。

Java提供了只包含一个compareTo()方法的Comparable接口。这个方法可以个给两个对象排序。具体来说，它返回负数，0，正数来表明输入对象小于，等于，大于已经存在的对象。
Java提供了包含compare()和equals()两个方法的Comparator接口。compare()方法用来给两个输入参数排序，返回负数，0，正数表明第一个参数是小于，等于，大于第二个参数。equals()方法需要一个对象作为参数，它用来决定输入参数是否和comparator相等。只有当输入参数也是一个comparator并且输入参数和当前comparator的排序结果是相同的时候，这个方法才返回true。