面试之Java基础问题（1）

本文介绍一些和List、Set、Map面试常问问题。
在 Java 中除了以 Map 结尾的类之外，其他类都实现了 Collection 接口。并且以 Map 结尾的类都实现了 Map 接口。
注意：文中提到的线程安全，并发，Sychronized等知识点，如果不太清楚，作者会在后面的Java并发面试题中会有所整理和解释。

问题1：List和Set和Map的区别？

List可以有重复的对象，Set不可以有重复的对象；
List元素是有序的，Set没法保证有序；
List可以插入多个null值，Set只能插入一个；
Map,key-value的键值对，entry对象形式，key是无序，不可重复的；value是无序，可重复的；

问题2：List和Set和Map的实现方式分别由哪些？

List的实现方式：数据结构
1）ArrayList ： Object[]数组
2）Vector： Object[]数组
3）LinkedList：双向链表
Set的实现方式：数据结构
1）HashSet（无序，唯一）: 基于 HashMap 实现的，底层采用 HashMap 来保存元素
2）LinkedHashSet：LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。
3）TreeSet（有序，唯一）：红黑树(自平衡的排序二叉树)
Map的实现方式：数据结构
1）HashMap： JDK1.8 之前 HashMap 由数组+链表组成的。JDK1.8 以后，将链表转化为红黑树
2）LinkedHashMap： LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成
3）Hashtable：数组+链表组成的
4）TreeMap：红黑树

问题3：ArrayList 和 Vector 和 LinkedList 的区别？

线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；Vector是线程安全的；
底层数据结构： Arraylist 和Vector 底层使用的是 Object 数组；LinkedList 底层使用的是双向链表；
插入和删除： ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响；LinkedList 采用链表存储，所以对于add(E e)方法的插入，删除元素时间复杂度不受元素位置的影响；
支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。
内存空间： LinkedList 比ArrayList的空间花费更多的空间（因为要存放直接后继和直接前驱以及数据）。

问题4：HashSet 和 LinkedHashSet 和 TreeSet 的区别？

HashSet 是 Set 接口的主要实现类，HashSet 的底层是 HashMap，线程不安全的，可以存储 null 值；
LinkedHashSet 是 HashSet 的子类，能够按照添加的顺序遍历；
TreeSet 底层使用红黑树，能够按照添加元素的顺序进行遍历，排序的方式有自然排序和定制排序。

问题5：HashMap 和 HashTable 的区别？

线程安全： HashMap 是非线程安全的，HashTable 是线程安全的。因为 HashTable 内部的方法基本都经过synchronized 修饰。
效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高。另外，HashTable 基本被淘汰，不要在代码中使用它；
key / value 为 null ： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
初始容量和扩容：1）创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。2）创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小。
底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。

从以上几个问题可以总结出，当问到这些集合之间的区别的时候，一般要答这几点：线程安全、底层数据结构、有序无序、可否存null值、效率等。

问题6：如何选择该使用哪些集合？

当要保存一组同类型数据时，首先想到的容器可能就时数组，但用数组存储对象存在弊端，因为我们在实际开发中，存储的数据的类型是多种多样的，“集合”的出现就使得数据存储更加灵活，集合同样也是用来存储多个数据的。

数组的缺点是声明时要初始化大小；声明数组时的数据类型也决定了该数组存储的数据的类型；而且，数组存储的数据是有序的、可重复的，特点单一。集合灵活性更高，Java 中集合可用来存储不同类型不同数量的对象，也可保存具有映射关系的数据。

1）根据集合的特点来选，如我们需要根据键值获取到元素值时就选用 Map 接口下的集合，需要排序时选择 TreeMap,不需要排序时就选择HashMap,需要保证线程安全就选用 ConcurrentHashMap。
2）只需要存放元素值时，就选择实现Collection 接口的集合，需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet，不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList，然后再根据实现这些接口的集合的特点来选用。