集合容器面试题

哈希算法是指把任意长度的二进制映射为固定长度的较小的二进制值，这个较小的二进制值叫做哈希值。

链表是可以将物理地址上不连续的数据连接起来，通过指针来对物理地址进行操作，实现增删改查等功能。

链表大致分为单链表和双向链表

链表的优点

链表的缺点

HashMap概述: HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

HashMap的数据结构: 在Java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模 拟指针(引用)，所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。 HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

HashMap 基于 Hash 算法实现的

需要注意Jdk 1.8中对HashMap的实现做了优化，当链表中的节点数据超过八个之后，该链表会转 为红黑树来提高查询效率，从原来的O(n)到O(logn)

在Java中，保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址容易，插入和 删除困难;链表的特点是:寻址困难，但插入和删除容易;所以我们将数组和链表结合在一起，发 挥两者各自的优势，使用一种叫做拉链法的方式可以解决哈希冲突。

HashMap JDK1.8之前

HashMap JDK1.8之后

JDK1.7 VS JDK1.8 比较

说道红黑树先讲什么是二叉树

红黑树

当我们put的时候，首先计算 key 的 hash 值，这里调用了 hash 方法， hash 方法实际是让key.hashCode()与key.hashCode()>>>16 进行异或操作，高16bit补0，一个数和0异或不变， 所以 hash 函数大概的作用就是:高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞。按照函数注释，因为bucket数组大小是2的幂，计算下标index=(table.length-1)&hash，如果不做 hash 处理，相当于散列生效的只有几个低 bit 位，为了减少散列的碰撞，设计者综合考虑了速度、作用、质量之后，使用高16bit和低16bit异或来简单处理减少碰撞，而且JDK8中 用了复杂度 O(logn)的树结构来提升碰撞下的性能。

putVal方法执行流程图

在解决这个问题之前，我们首先需要知道什么是哈希冲突，而在了解哈希冲突之前我们还要知道什么是哈希才行。

什么是哈希?

什么是哈希冲突？

HashMap的数据结构？

hash()函数

总结

可以使用任何类作为 Map 的 key，然而在使用之前，需要考虑以下几点:

String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少Hash碰撞的几率

重写 hashCode() 和 equals() 方法

hashCode() 方法返回的是int整数类型，其范围为-(2 ^ 31)~(2 ^ 31 - 1)，约有40亿个映射空 间，而HashMap的容量范围是在16(初始化默认值)~2 ^ 30，HashMap通常情况下是取不到最 大值的，并且设备上也难以提供这么多的存储空间，从而导致通过 hashCode() 计算出的哈希值可 能不在数组大小范围内，进而无法匹配存储位置;

那怎么解决呢?

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。

这个算法应该如何设计呢?

那为什么是两次扰动呢?

1. 线程安全: HashMap 是非线程安全的，HashTable 是线程安全的;HashTable 内部的方法基本 都经过 synchronized 修饰。(如果你要保证线程安全的话就使用 ConcurrentHashMap );

2. 效率: 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被 淘汰，不要在代码中使用它;(如果你要保证线程安全的话就使用 ConcurrentHashMap );

3. 对Null key 和Null value的支持: HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛NullPointerException；

4. 初始容量大小和每次扩充容量大小的不同 ；

5. 创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍；

6. 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其 扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小，后面会介绍到为什么是2的幂次方；

7. 底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值(默认为8)时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制；

8. 推荐使用:在 Hashtable 的类注释可以看到，Hashtable 是保留类不建议使用，推荐在单线程环境下使用 HashMap 替代，如果需要多线程使用则用 ConcurrentHashMap 替代。

TreeMap 是一个有序的key-value集合，它是通过红黑树实现的。

TreeMap基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序，或者根据 创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。

TreeMap是线程非同步的。

对于在Map中插入、删除和定位元素这类操作，HashMap是最好的选择。然而，假如你需要对一 个有序的key集合进行遍历，TreeMap是更好的选择。基于你的collection的大小，也许向 HashMap中添加元素会更快，将map换为TreeMap进行有序key的遍历。

ConcurrentHashMap对整个桶数组进行了分割分段(Segment)，然后在每一个分段上都用lock锁 进行保护，相对于HashTable的synchronized锁的粒度更精细了一些，并发性能更好，而 HashMap没有锁机制，不是线程安全的。(JDK1.8之后ConcurrentHashMap启用了一种全新的 方式实现,利用CAS算法。)

HashMap的键值对允许有null，但是ConCurrentHashMap都不允许。

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

两者的对比图

ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同 步，HashTable 考虑了同步的问题使用了synchronized 关键字，所以 HashTable 在每次同步执行 时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的。

JDK1.7

JDK1.8

Array 可以存储基本数据类型和对象，ArrayList 只能存储对象。

Array 是指定固定大小的，而 ArrayList 大小是自动扩展的。

Array 内置方法没有 ArrayList 多，比如 addAll、removeAll、iteration 等方法只有 ArrayList 有。

Array 转 List: Arrays. asList(array) 

List 转 Array:List 的 toArray() 方法

comparable接口实际上是出自java.lang包，它有一个 compareTo(Object obj)方法用来排序

comparator接口实际上是出自 java.util 包，它有一个compare(Object obj1, Object obj2)方法用 来排序

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

java.util.Collection 是一个集合接口(集合类的一个顶级接口)。它提供了对集合对象进行基本操 作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为 各种具体的集合提供了最大化的统一操作方式，其直接继承接口有List与Set。

Collections则是集合类的一个工具类/帮助类，其中提供了一系列静态方法，用于对集合中元素进 行排序、搜索以及线程安全等各种操作。

TreeSet 要求存放的对象所属的类必须实现 Comparable 接口，该接口提供了比较元素的 compareTo()方法，当插入元素时会回调该方法比较元素的大小。TreeMap 要求存放的键值对映 射的键必须实现 Comparable 接口从而根据键对元素进 行排序。

Collections 工具类的 sort 方法有两种重载的形式

java.util.Collection 是一个集合接口(集合类的一个顶级接口)。它提供了对集合对象进行基本操 作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为 各种具体的集合提供了最大化的统一操作方式，其直接继承接口有List与Set。

Collections则是集合类的一个工具类/帮助类，其中提供了一系列静态方法，用于对集合中元素进 行排序、搜索以及线程安全等各种操作。

集合就是一个放数据的容器，准确的说是放数据对象引用的容器

集合类存放的都是对象的引用，而不是对象的本身

集合类型主要有3种：set(集)、list(列表)和map(映射)

集合用于存储对象的容器，对象是用来封装数据，对象多了也需要存储集中式管理

和数组对比对象的大小不确定。因为集合是可变长度的。数组需要提前定义大小

数组是固定长度的;集合可变长度的。

数组可以存储基本数据类型，也可以存储引用数据类型;集合只能存储引用数据类型。

数组存储的元素必须是同一个数据类型;集合存储的对象可以是不同数据类型。

容量自增长

提供了高性能的数据结构和算法，使编码更轻松，提高了程序速度和质量

可以方便地扩展或改写集合，提高代码复用性和可操作性

通过使用JDK自带的集合类，可以降低代码维护和学习新API成本

Collection接口的子接口包括:Set接口和List接口

Map接口的实现类主要有:HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等

Set接口的实现类主要有:HashSet、TreeSet、LinkedHashSet等

List接口的实现类主要有:ArrayList、LinkedList、Stack以及Vector等

Java 容器分为 Collection 和 Map 两大类，Collection集合的子接口有Set、List、Queue三种子接 口。我们比较常用的是Set、List，Map接口不是collection的子接口。

Collection集合主要有List和Set两大接口

Map是一个键值对集合，存储键、值和之间的映射。 Key无序，唯一;value 不要求有序，允许重 复。Map没有继承于Collection接口，从Map集合中检索元素时，只要给出键对象，就会返回对应 的值对象。

Collection

Map

Vector：就比Arraylist多了个 synchronized (线程安全)，因为效率较低，现在已经不太建议使用。

hashTable：就比hashMap多了个synchronized (线程安全)，不建议使用。

ConcurrentHashMap：是Java5中支持高并发、高吞吐量的线程安全HashMap实现。它由 Segment数组结构和HashEntry数组结构组成。Segment数组在ConcurrentHashMap里扮演锁的 角色，HashEntry则用于存储键-值对数据。一个ConcurrentHashMap里包含一个Segment数组， Segment的结构和HashMap类似，是一种数组和链表结构;一个Segment里包含一个HashEntry 数组，每个HashEntry是一个链表结构的元素;每个Segment守护着一个HashEntry数组里的元 素，当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁。(推荐使用)

是java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast 机制。

例如：假设存在两个线程(线程1、线程2)，线程1通过Iterator在遍历集合A中的元素，在某个时 候线程2修改了集合A的结构(是结构上面的修改，而不是简单的修改集合元素的内容)，那么这 个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。

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

解决办法：
1. 在遍历过程中，所有涉及到改变modCount值得地方全部加上synchronized。
2. 使用CopyOnWriteArrayList来替换ArrayList

可以使用 Collections. unmodifiableCollection(Collection c) 方法来创建一个只读集合，这样改变 集合的任何操作都会抛出 Java. lang. UnsupportedOperationException 异常。

示例代码如下：

Iterator 接口提供遍历任何 Collection 的接口。我们可以从一个 Collection 中使用迭代器方法来 获取迭代器实例。迭代器取代了 Java 集合框架中的 Enumeration，迭代器允许调用者在迭代过程中移除元素。

因为所有Collection接继承了Iterator迭代器

Iterator 使用代码如下：

Iterator 的特点是只能单向遍历，但是更加安全，因为它可以确保，在当前遍历的集合元素被更改 的时候，就会抛出 ConcurrentModificationException 异常。

边遍历边修改 Collection 的唯一正确方式是使用 Iterator.remove() 方法，如下:

一种最常见的错误代码如下:

运行以上错误代码会报 ConcurrentModificationException 异常。这是因为当使用 foreach(for(Integer i : list)) 语句时，会自动生成一个iterator 来遍历该 list，但同时该 list 正在被 Iterator.remove() 修改。Java 一般不允许一个线程在遍历 Collection 时另一个线程修改它。

Iterator 可以遍历 Set 和 List 集合，而 ListIterator 只能遍历 List。

Iterator 只能单向遍历，而 ListIterator 可以双向遍历(向前/后遍历)。

ListIterator 实现 Iterator 接口，然后添加了一些额外的功能，比如添加一个元素、替换一个元 素、获取前面或后面元素的索引位置。

遍历方式有以下几种：

最佳实践：Java Collections 框架中提供了一个 RandomAccess 接口，用来标记 List 实现是否支 持 Random Access。

ArrayList的优点如下

ArrayList 的缺点如下

ArrayList 比较适合顺序添加、随机访问的场景

数组转 List:使用 Arrays. asList(array) 进行转换。

List 转数组:使用 List 自带的 toArray() 方法。

代码示例:

数据结构实现:ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实现。

随机访问效率:ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。

增加和删除效率:在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为 ArrayList 增删操作要影响数组内的其他数据的下标。

内存空间占用:LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。

线程安全:ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全。

综合来说，在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推荐使用 LinkedList。

LinkedList 的双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向 直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结 点和后继结点。

这两个类都实现了 List 接口(List 接口继承了 Collection 接口)，他们都是有序集合

Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问 Vector的话代码要在同步操作上耗费大量的时间。

Arraylist不是同步的，所以在不需要保证线程安全时时建议使用Arraylist。

ArrayList和Vector 底层的实现都是使用数组方式存储数据。数组元素数大于实际存储的数据以便 增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢。

Vector 中的方法由于加了 synchronized 修饰，因此 Vector 是线程安全容器，但性能上较 ArrayList差。

LinkedList 使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，但插入数据时只需 要记录当前项的前后项即可，所以 LinkedList 插入速度较快。

ArrayList 不是线程安全的，如果遇到多线程场景，可以通过 Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用。例如像下面这样:

ArrayList 中的数组定义如下:
private transient Object[] elementData;

再看一下 ArrayList 的定义:

可以看到 ArrayList 实现了 Serializable 接口，这意味着 ArrayList 支持序列化。transient 的作用 是说不希望 elementData 数组被序列化，重写了 writeObject 实现:

每次序列化时，先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素，然后 遍历 elementData，只序列化已存入的元素，这样既加快了序列化的速度，又减小了序列化之后 的文件大小。

List , Set 都是继承自Collection 接口

List 特点：一个有序(元素存入集合的顺序和取出的顺序一致)容器，元素可以重复，可以插入多 个null元素，元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。

Set 特点：一个无序(存入和取出顺序有可能不一致)容器，不可以存储重复元素，只允许存入一 个null元素，必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。

另外 List 支持for循环，也就是通过下标来遍历，也可以用迭代器，但是set只能用迭代，因为他无 序，无法用下标来取得想要的值。

Set和List对比

HashSet 是基于 HashMap 实现的，HashSet的值存放于HashMap的key上，HashMap的value统 一为present，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层 HashMap 的相关方法来完成，HashSet 不允许重复的值。

向HashSet 中add ()元素时，判断元素是否存在的依据，不仅要比较hash值，同时还要结合equles 方法比较。

HashSet 中的add ()方法会使用HashMap 的put()方法。

HashMap 的 key 是唯一的，由源码可以看出 HashSet 添加进去的值就是作为HashMap 的key， 并且在HashMap中如果K/V相同时，会用新的V覆盖掉旧的V，然后返回旧的V。所以不会重复( HashMap 比较key是否相等是先比较hashcode 再比较equals )。

以下是HashSet 部分源码:

hashCode()与equals()的相关规定: