面试题----集合

概述 

从上图可以看出，在 Java 中除了以 Map 结尾的类之外， 其他类都实现了 Collection 接⼝。 并且，以 Map 结尾的类都实现了 Map 接⼝

List,Set,Map

• List (对付顺序的好帮⼿)： 存储的元素是有序的、可重复的。
• Set (注重独⼀⽆⼆的性质): 存储的元素是⽆序的、不可重复的。
• Map (⽤ Key 来搜索的专家): 使⽤键值对（kye-value）存储，类似于数学上的函数 y=f(x)， “x”代表 key，"y"代表 value，Key 是⽆序的、不可重复的，value 是⽆序的、可重复的，每个键最多映射到⼀个值。

集合框架底层数据结构总结

List

• Arraylist ： Object[] 数组
• Vector ： Object[] 数组
• LinkedList ： 双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)

Set

• HashSet （⽆序，唯⼀）: 基于 HashMap 实现的，底层采⽤ HashMap 来保存元素
• LinkedHashSet ： LinkedHashSet 是 HashSet 的⼦类，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的 LinkedHashMap 其内部是基于 HashMap 实现⼀样，不过还是有⼀点点区别的
• TreeSet （有序，唯⼀）： 红⿊树(⾃平衡的排序⼆叉树)

Map

• HashMap ： JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主 要为了解决哈希冲突⽽存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较⼤ 的变化，当链表⻓度⼤于阈值（默认为 8）（将链表转换成红⿊树前会判断，如果当前数组的⻓ 度⼩于 64，那么会选择先进⾏数组扩容，⽽不是转换为红⿊树）时，将链表转化为红⿊树，以 减少搜索时间
• LinkedHashMap ： LinkedHashMap 继承⾃ HashMap ，所以它的底层仍然是基于拉链式散 列结构即由数组和链表或红⿊树组成。另外， LinkedHashMap 在上⾯结构的基础上，增加了 ⼀条双向链表，使得上⾯的结构可以保持键值对的插⼊顺序。同时通过对链表进⾏相应的操作， 实现了访问顺序相关逻辑。
• Hashtable ： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突 ⽽存在的
• TreeMap ： 红⿊树（⾃平衡的排序⼆叉树）

为什么要使⽤集合？

• 当我们需要保存⼀组类型相同的数据的时候，我们应该是⽤⼀个容器来保存，这个容器就是数组，但是，使⽤数组存储对象具有⼀定的弊端， 因为我们在实际开发中，存储的数据的类型是多种多样的， 于是，就出现了“集合”，集合同样也是⽤来存储多个数据的。
• 数组的缺点是⼀旦声明之后，⻓度就不可变了；同时，声明数组时的数据类型也决定了该数组存储的数据的类型；⽽且，数组存储的数据是有序的、可重复的，特点单⼀。 但是集合提⾼了数据存储的灵活 性，Java 集合不仅可以⽤来存储不同类型不同数量的对象，还可以保存具有映射关系的数据

如何选⽤集合?

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

迭代器 Iterator 是什么？

Iterator 对象称为迭代器（设计模式的⼀种），迭代器可以对集合进⾏遍历，但每⼀个集合内部的数据结构可能是不尽相同的，所以每⼀个集合存和取都很可能是不⼀样的，虽然我们可以⼈为地在每⼀个类中定义 hasNext() 和 next() ⽅法，但这样做会让整个集合体系过于臃肿。于是就有了迭代 器。

迭代器 Iterator 有啥⽤？

Iterator 主要是⽤来遍历集合⽤的，它的特点是更加安全，因为它可以确保，在当前遍历的集合元素被更改的时候，就会抛出 ConcurrentModificationException 异常，触发快速失败机制（fail-fast）。

 有哪些集合是线程不安全的？怎么解决呢？

我们常⽤的 Arraylist , LinkedList , Hashmap , HashSet , TreeSet , TreeMap ， PriorityQueue 都不是线程安全的。

解决办法很简单，可以使⽤线程安全的集合来代替。

如果你要使⽤线程安全的集合的话， java.util.concurrent 包中提供了很多并发容器供你使⽤：

• 1. ConcurrentHashMap : 可以看作是线程安全的 HashMap
• 2. CopyOnWriteArrayList :可以看作是线程安全的 ArrayList ，在读多写少的场合性能⾮常 好，远远好于 Vector .
• 3. ConcurrentLinkedQueue :⾼效的并发队列，使⽤链表实现。可以看做⼀个线程安全的 LinkedList ，这是⼀个⾮阻塞队列。
• 4. BlockingQueue : 这是⼀个接⼝，JDK 内部通过链表、数组等⽅式实现了这个接⼝。表示阻塞 队列，⾮常适合⽤于作为数据共享的通道。
• 5. ConcurrentSkipListMap :跳表的实现。这是⼀个 Map ，使⽤跳表的数据结构进⾏快速查 找。

Arraylist 和 Vector 的区别?

• ArrayList 是 List 的主要实现类，底层使⽤ Object[ ]存储，适⽤于频繁的查找⼯作，线程不 安全 ；
• Vector 是 List 的古⽼实现类，底层使⽤ Object[ ]存储，线程安全的。

Arraylist 与 LinkedList 区别?

• 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
• 底层数据结构： Arraylist 底层使⽤的是 Object 数组； LinkedList 底层使⽤的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下⾯有介绍到！）
• 插⼊和删除是否受元素位置的影响： ① ArrayList 采⽤数组存储，所以插⼊和删除元素的 时间复杂度受元素位置的影响。 ⽐如：执⾏ add(E e) ⽅法的时候， ArrayList 会默认在 将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插⼊和删除元素的话（ add(int index, E element) ）时间复杂度就为 O(n-i)。因为在进 ⾏上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执⾏向后位/向前移⼀位的 操作。 ② LinkedList 采⽤链表存储，所以对于 add(E e) ⽅法的插⼊，删除元素时间复杂 度不受元素位置的影响，近似 O(1)，如果是要在指定位置 i 插⼊和删除元素的话（ (add(int index, E element) ） 时间复杂度近似为 o(n)) 因为需要先移动到指定位置再插⼊。
• 是否⽀持快速随机访问： LinkedList 不⽀持⾼效的随机元素访问，⽽ ArrayList ⽀持。 快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(int index) ⽅法)。
• 内存空间占⽤： ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留⼀定的容量空 间，⽽ LinkedList 的空间花费则体现在它的每⼀个元素都需要消耗⽐ ArrayList 更多的空间 （因为要存放直接后继和直接前驱以及数据）。

双向链表和双向循环链表

双向链表： 包含两个指针，⼀个 prev 指向前⼀个节点，⼀个 next 指向后⼀个节点

双向循环链表：最后⼀个节点的 next 指向 head，⽽ head 的 prev 指向最后⼀个节点，构成⼀个环。

comparable 和 Comparator 的区别

• comparable 接⼝实际上是出⾃ java.lang 包 它有⼀个 compareTo(Object obj) ⽅法⽤ 来排序
• comparator 接⼝实际上是出⾃ java.util 包它有⼀个 compare(Object obj1, Object obj2) ⽅法⽤来排序

⼀般我们需要对⼀个集合使⽤⾃定义排序时，我们就要重写 compareTo() ⽅法或 compare() ⽅法，当我们需要对某⼀个集合实现两种排序⽅式，⽐如⼀个 song 对象中的歌名和歌⼿名分别采⽤种排序⽅法的话，我们可以重写 compareTo() ⽅法和使⽤⾃制的 Comparator ⽅法或者以两个Comparator 来实现歌名排序和歌星名排序，第⼆种代表我们只能使⽤两个参数版的Collections.sort() .

⽆序性和不可重复性的含义是什么

• 什么是⽆序性？⽆序性不等于随机性 ，⽆序性是指存储的数据在底层数组中并⾮按照数组索引的顺序添加 ，⽽是根据数据的哈希值决定的。
• 什么是不可重复性？不可重复性是指添加的元素按照 equals()判断时 ，返回 false，需要同时重 写 equals()⽅法和 HashCode()⽅法。

⽐较 HashSet、LinkedHashSet 和 TreeSet 三者的异同

• HashSet 是 Set 接⼝的主要实现类 ，HashSet 的底层是 HashMap，线程不安全的，可以存储 null 值；
• LinkedHashSet 是 HashSet 的⼦类，能够按照添加的顺序遍历；
• TreeSet 底层使⽤红⿊树，能够按照添加元素的顺序进⾏遍历，排序的⽅式有⾃然排序和定制排序。

HashMap 和 Hashtable 的区别

• 线程是否安全： HashMap 是⾮线程安全的，HashTable 是线程安全的,因为 HashTable 内部的 ⽅法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使⽤ ConcurrentHashMap 吧！）；
• 效率： 因为线程安全的问题，HashMap 要⽐ HashTable 效率⾼⼀点。另外，HashTable 基本被淘汰，不要在代码中使⽤它；
• 对 Null key 和 Null value 的⽀持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有⼀个，null 作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会 抛出 NullPointerException。
• 初始容量⼤⼩和每次扩充容量⼤⼩的不同 ： ① 创建时如果不指定容量初始值，Hashtable 默 认的初始⼤⼩为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化⼤⼩为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使⽤你给定的⼤⼩，⽽ HashMap 会将其扩充为 2 的幂次⽅⼤⼩（HashMap 中的 tableSizeFor() ⽅法保证，下⾯给出了源代码）。也就是说 HashMap 总是使⽤ 2 的幂作为哈希表的⼤⼩,后⾯会介绍到为什么是 2 的幂次⽅。
• 5. 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较⼤的变化，当链表⻓度⼤于 阈值（默认为 8）（将链表转换成红⿊树前会判断，如果当前数组的⻓度⼩于 64，那么会选择 先进⾏数组扩容，⽽不是转换为红⿊树）时，将链表转化为红⿊树，以减少搜索时间。Hashtable 没有这样的机制。