Java集合重点详解+高频面试题——面试和学习都必备！

一、Java集合概述

1.1 什么是Java集合？

Java集合类存放于java.util包内，是一个用来存放数据的容器；
（这里的数据是一个个的对象，如果存入基本数据类型的数据，会自动装箱成包装类；并且集合存放的是对象的引用，而不是对象本身。）

1.2 集合主要有哪些？

集合主要分为 Collection 和 Map(映射) 接口；

而 Collection 接口又有 List(列表) 、Set(集)、Queue(队列) 子接口；

这些接口的主要实现及优缺点可以看图：

1.3 集合框架详解图

二、集合相关高频面试题

2.01 ArrayList 和 Vector 的区别/异同？

Vector类是List接口的古老实现类(JDK1.0就有了)，ArrayList类是List接口的主要的常用的实现类(JDK1.2新增的)。
Vector类的方法全都是同步的，两个线程可以安全的访问一个Vector对象；
但是如果一个线程访问Vector对象的话，要在同步操作上花费大量时间；
而 ArrayList 不是同步的，如果不需要保证线程的安全，建议使用ArrayList，效率较高；
（或者直接简单点说：Vector 线程安全但效率低，ArrayList 线程不安全但效率高。）
Vector扩容方式默认是当前容量的1倍；ArrayList扩容是当前容量×1.5+1 。

2.02 ArrayList 和 LinkedList 的区别/异同？

ArrayList 底层使用的是数组实现，LinkedList 底层使用的是双向链表实现。
ArrayList 随机查找和遍历速度快，插入删除速度慢；LinkedList 随机查找和遍历速度快，插入和删除速度快。
ArrayList 插入和删除元素的速度会受插入位置的影响；LinkedList 插入和删除元素的速度不会受插入位置的影响。
ArrayList 内存空间会耗费在列表后面的预留空间；LinkedList 内存空间会耗费在每个数据要多存储一个前驱和后继。
ArrayList 需要扩容，扩容是当前容量×1.5+1 ； LinkedList 无需扩容。
ArrayList 和 LinkedList 都不是同步的，都是不保证线程安全。

2.03 HashMap的底层实现原理？

jdk7及jdk7之前
底层是用数组+链表来实现的；

实现过程：

1. new HashMap() 之后，底层会创建一个长度为 16 的一维数组（ Entry[] table ）。

2. put 数据时（ .put(key,value) ），会先调用 key 所在类的 hashCode 方法，计算出此key的哈希值，再将此哈希值经过处理计算后，得到该数据在数组table上的位置。

然后根据此位置来分情况判断是否存储：

情况一：
此位置为空，直接在此位置上存储put的数据。

情况二：
此位置不为空，则说明此位置上已有一个或多个数据了（多个数据以链表形式存储）；
那么将 put数据的key的哈希值与此位置上已有数据的key的哈希值进行依次比较；
如果和它们都不同，则存储put的数据；
将put的数据放在此位置上，原有数据以链表形式存储：

情况三：
此位置不为空，且 put数据的key (假设为 key1) 的哈希值与此位置上已有的某个数据的key (假设为 key2 ) 的哈希值相同；
则调用 key1 所在类的 equals() 方法与 key2 比较；（此 equals() 方法是重写过的，比较的是值；）
若不同 (既返回false)，则存储put的数据；
同样，将put的数据放在此位置上，原有数据以链表形式存储。

情况四：
若情况三中，key1，key2 equals()方法比较后的结果是相同 (既返回true)，
则用 key1 的value1 替换 key2 的value2。

3.扩容，当存储的数据超出临界值，且要存放数据的位置非空时，则扩容，扩容为原来容量的2倍。
临界值 = 当前容量 x 填充因子
(填充因子是 0.75)

jdk8及jdk8之后
底层是用数组+链表+红黑树来实现的；

实现过程：

1. new HashMap() 之后，底层并不会直接创建数组。而是等 put 数据时才会创建数组。

2. put 数据时（ .put(key,value) ），会先创建一个长度为 16 的一维数组（ Node[] table ），然后存储数据。

存储数据的过程和 jdk7及之前基本一样，既先计算哈希值，然后分4种情况判断。

不同点在于用链表存储数据时：
jdk7 是将新数据放在数组位置上，原有数据以链表形式存储在后面；
jdk8 是原有数据位置不变，而新数据以链表形式存储在最后。
可看图：

对比图：

3 . 容量扩充
如果使用的是默认初始容量，每次扩充，容量变为原来的 2 倍；
如果使用的是自己指定的初始容量，会先将这个容量扩充为 2 的幂次方大小。

4. jdk8还有一点不同的是，当数组的某一索引位置上的以链表形式存储的数据大于 8 个，
且当前数组长度大于64时，此索引位置上所有数据改为红黑树存储，这样可以减少搜索查找的时间。

2.04 HsahMap 和 Hashtable 的区别/异同？

HashMap 是线程不安全的，但效率高一些；Hashtable 是线程安全的，但效率低，现在基本不使用Hashtable。
HashMap 键和值都可以为null；Hashtable 键和值都不可以为null。
HashMap 默认初始容量为 16，扩充容量时会变为原来的2倍；而指定初始容量后，会先将指定的容量扩充成2的幂次方大小；
Hashtable 默认初始容量为 16，扩充容量时会变为原来的2倍+1 ；而指定初始容量后，会直接使用这个容量。
HashMap 当存储数组的某一索引位置上的以链表形式存储的数据大于 8 个，且当前数组长度大于64时，此索引位置上所有数据改为红黑树存储，减少搜索时间。
Hashtable 不会转为红黑树。

2.05 HashMap 容量的长度为什么总是2的幂次方？

为了让HashMap存取高效，要尽量减少碰撞，就是要尽量把数据分配均匀。
Hash值大概有40亿的映射空间，只要哈希函数映射得比较均匀松散，一般来说是很难有碰撞得。
但是解决碰撞之后，新的问题也出现了，内存放不下这40亿长度得数组。
所以用之前需要先对数组的长度取模运算，得到的余数才能作为要存放的位置(既对应的数组下标)。
运算方法：
我们可以用 hash值和数组长度取模，也就是 hash%n；
但这样的运算速度不够快，而如果我们保证数组长度为 2的幂次方时，我们就可以将式子改成 (n-1)&hash ，运算速度会大幅提升；
而源码中也是用 (n-1)&hash 运算的，所以就要保证HashMap 的容量长度是2的幂次方。

2.06 HashSet 和 HashMap 的区别？

HashMap是实现了Map接口，存储的是键值对；HashSet 是实现了Set接口，只存储对象。
HashMap 使用键来计算哈希值；HashSet 是使用成员对象来计算哈希值；
HashMap 比 HashSet 快。
HashSet 的底层其实是基于 HashMap 实现的，大部分方法都是直接调用 HashMap中的方法。
看下源码：
HashSet是基于HashMap实现的：

HashSet大部分方法是直接调用HashMap中的方法：

HashSet的少数方法是自己实现的：

2.07 ConcurrentHashMap 是如何保证线程安全的(线程安全的实现方式)？

jdk1.7
采用Segment分段锁方式保证线程安全，将数据分成一段一段的存储，然后每一段数据单独一个锁；
所以当一个线程占用一个锁访问其中的一段数据时，其他段的数据可以被其他线程访问；
（jdk1.7 ConcurrentHashMap底层结构由 Segment数组和 HashEntry数组组成。一个ConcurrentHashMap里包含一个 Segment数组，数组中的每个Segment都包含一个HashEntry数组，每个HashEntry是一个链表结构的元素。）

jdk1.8
取消了Segment分段锁方式，改成了用 CAS 和 synchronized 来保证线程安全。
synchronized 只锁定当前链表或红黑树的首节点，这样只要hash不冲突，就不会有线程安全问题，效率大幅提升。
（jdk1.8 ConcurrentHashMap 底层结构由数组+链表+红黑树实现。）

网上看到的一个对比图，感觉很好的展示了 ConcurrentHashMap jdk1.7 和 jdk1.8 的特点和不同，能让我们更好的理解，
给大家分享一下：

2.08 ConcurrentHashMap 和 Hashtable 的区别/异同？

1.底层数据结构不同：
ConcurrentHashMap jdk1.7 是用分段数组+链表实现，jdk1.8 是用数组+链表+红黑树实现；
Hashtable 是用数组+链表实现。

2.保证线程安全的方式不同：
ConcurrentHashMap jdk1.7 是用分段锁的方式保证线程安全，jdk1.8 是用 synchronized 和 CAS 保证线程安全；
Hashtable 是用全表锁来保证线程安全（既一个Hashtable 只用一把锁），这种的方式的效率非常低。

ConcurrentHashMap jdk1.7 和 jdk1.8 的线程安全实现示意图：

Hashtable 线程安全实现示意图：