Java容器–2021面试题系列教程（附答案解析）–大白话解读–JavaPub版本
Java容器–2021面试题系列教程（附答案解析）–大白话解读–JavaPub版本
前言
序言
再高大上的框架，也需要扎实的基础才能玩转，高频面试问题更是基础中的高频实战要点。
适合阅读人群
Java 学习者和爱好者，有一定工作经验的技术人，准面试官等。
阅读建议
本教程是系列教程，包含 Java 基础，JVM，容器，多线程，反射，异常，网络，对象拷贝，JavaWeb，设计模式，Spring-Spring MVC，Spring Boot / Spring Cloud，Mybatis / Hibernate，Kafka，RocketMQ，Zookeeper，MySQL，Redis，Elasticsearch，Lucene。订阅不迷路，2021奥利给。
微信搜：JavaPub，阅读全套系列面试题教程
- 前言
- 题目
- 前言
- 1.java 容器都有哪些？
- 2.Collection 和 Collections 有什么区别？
- 3.List、Set、Map 之间的区别是什么？
- 4.HashMap 和 Hashtable 有什么区别？
- 5.如何决定使用 HashMap 还是 TreeMap？
- 6.说一下 HashMap 的实现原理？
- 7.说一下 HashSet 的实现原理？
- 8.ArrayList 和 LinkedList 的区别是什么？
- 9.如何实现数组和 List 之间的转换？
- 10.ArrayList 和 Vector 的区别是什么？
- 11.Array 和 ArrayList 有何区别？
- 12.在 Queue 中 poll()和 remove()有什么区别？
- 13.哪些集合类是线程安全的？
- 14.迭代器 Iterator 是什么？
- 15.Iterator 怎么使用？有什么特点？
- 16.Iterator 和 ListIterator 有什么区别？
- 17.怎么确保一个集合不能被修改？
容器是开发中非常重要的一部分知识，本篇尽量以大白话描述各个知识点。HashMap 实现原理是非常重要的一个知识点，我们在日常设计代码时也会涉及到这个思想，推荐第6题，会让你使用起来更得心应手。
题目
前言
先对 Java 容器做一个简单介绍
首先放一张官方的图：
从上面的集合框架图可以看到，Java 集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。Collection 接口又有 3 种子类型，List、Set 和 Queue，再下面是一些抽象类，最后是具体实现类，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。
接口：是代表集合的抽象数据类型。例如 Collection、List、Set、Map 等。之所以定义多个接口，是为了以不同的方式操作集合对象
实现（类）：是集合接口的具体实现。从本质上讲，它们是可重复使用的数据结构，例如：ArrayList、LinkedList、HashSet、HashMap。
算法：是实现集合接口的对象里的方法执行的一些有用的计算，例如：搜索和排序。这些算法被称为多态，那是因为相同的方法可以在相似的接口上有着不同的实现。
除了集合，该框架也定义了几个 Map 接口和类。Map 里存储的是键/值对。尽管 Map 不是集合，但是它们完全整合在集合中。
集合框架体系如图所示：
Java 集合框架提供了一套性能优良，使用方便的接口和类，java集合框架位于java.util包中。
1.java 容器都有哪些？
常用容器图录：
从图上可以看到，Java容器分为两大阵营：Collection和Map
Collection：主要是单个元素的集合，由List、Queue、Set三个接口区分不同的集合特征，然后由下面的具体的类来实现对应的功能。
Map：有一组键值对的存储形式来保存，可以用键对象来查找值。
JavaPub参考巨人：//zhuanlan.zhihu.com/p/29421226
2.Collection 和 Collections 有什么区别？
java.util.Collection是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法。Collection 接口在 Java 类库中有很多具体的实现。Collection 接口的意义是为各种具体的集合提供了最大化的统一操作方式。
List，Set，Queue接口都继承Collection。
直接实现该接口的类只有AbstractCollection类，该类也只是一个抽象类，提供了对集合类操作的一些基本实现。List和Set的具体实现类基本上都直接或间接的继承了该类。
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
java.util.Collections是一个包装类。它包含有各种有关集合操作的静态方法（对集合的搜索、排序、线程安全化等），大多数方法都是用来处理线性表的。此类不能实例化，就像一个工具类，服务于 Java 的 Collection 框架。
3.List、Set、Map 之间的区别是什么？
-
List：有序集合，元素可重复
-
Set：不重复集合，LinkedHashSet 按照插入排序，SortedSet 可排序，HashSet 无序
-
Map：键值对集合，存储键、值和之间的映射；Key 无序，唯一；value 不要求有序，允许重复
List 、Set、 Map都有哪些子类
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
|-HashSet
└TreeSet
Map
├Hashtable
├HashMap
└WeakHashMap
4.HashMap 和 Hashtable 有什么区别？
HashMap 不是线程安全的
HashMap 是 map 接口的实现类，是将键映射到值的对象，其中键和值都是对象，并且不能包含重复键，但可以包含重复值。HashMap 允许 null key 和 null value，而 HashTable 不允许。
HashTable 是线程安全 Collection。
HashMap 是 HashTable 的轻量级实现，他们都完成了Map 接口，主要区别在于 HashMap 允许 null key 和 null value,由于非线程安全，效率上可能高于 Hashtable。
区别：
- Hashtable 继承自 Dictionary 类，而 HashMap 继承自 AbstractMap 类。但二者都实现了 Map 接口。
- HashMap 允许将 null 作为一个 entry 的 key 或者 value，而 Hashtable 不允许。
- HashMap 把 Hashtable 的 contains 方法去掉了，改成 containsValue 和 containsKey。因为 contains 方法容易让人引起误解。Hashtable 则保留了 contains，containsValue 和containsKey 三个方法，其中 contains 和 containsValue 功能相同。
- Hashtable 中的方法是 Synchronize 的，而 HashMap 中的方法在缺省情况下是非 Synchronize 的。在多线程并发的环境下，可以直接使用 Hashtable，不需要自己为它的方法实现同步，但使用 HashMap 时就必须要自己增加同步处理。（结构上的修改是指添加或删除一个或多个映射关系的任何操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的非同步访问，如下所示：
Map m = Collections.synchronizedMap(new HashMap(...)); - hash值不同，哈希值的使用不同，HashTable直接使用对象的hashCode。而HashMap重新计算hash值。
hashCode是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值。
Hashtable计算hash值，直接用key的hashCode()，而HashMap重新计算了key的hash值，Hashtable在求hash值对应的位置索引时，用取模运算，而HashMap在求位置索引时，则用与运算，且这里一般先用hash&0x7FFFFFFF后，再对length取模，&0x7FFFFFFF的目的是为了将负的hash值转化为正值，因为hash值有可能为负数，而&0x7FFFFFFF后，只有符号外改变，而后面的位都不变。
- 内部实现使用的数组初始化和扩容方式不同，
HashTable在不指定容量的情况下的默认容量为11，而HashMap为16，Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。
Hashtable扩容时，将容量变为原来的2倍加1，而HashMap扩容时，将容量变为原来的2倍。
Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式。HashTable中hash数组默认大小是11，增加的方式是 old*2+1。
源码也是非常重要的一点，而且写得非常棒，后面单独写一篇。
JavaPub参考巨人（包括一部分源码）：//www.cnblogs.com/williamjie/p/9099141.html
5.如何决定使用 HashMap 还是 TreeMap？
TreeMap<K,V> 的 Key 值是要求实现 java.lang.Comparable，所以迭代的时候TreeMap 默认是按照 Key 值升序排序的；TreeMap 的实现是基于红黑树结构。适用于按自然顺序或自定义顺序遍历键（key）。
HashMap<K,V> 的 Key 值实现散列 hashCode()，分布是散列的、均匀的，不支持排序；数据结构主要是桶(数组)，链表或红黑树。适用于在 Map 中插入、删除和定位元素。
结论：
如果你需要得到一个有序的结果时就应该使用 TreeMap（因为 HashMap 中元素的排列顺序是不固定的）。除此之外，由于 HashMap 有更好的性能，所以大多不需要排序的时候我们会使用 HashMap。
JavaPub参考巨人：//javapub.blog.csdn.net/article/details/113482689
6.说一下 HashMap 的实现原理？
HashMap 的重要性就不说了。说到原理，就要说它的数据结构和实现原理。
官方文档是这样描述HashMap的：
Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.
几个关键的信息：基于 Map 接口实现、允许 null键/值、非同步、不保证有序(比如插入的顺序)、也不保证序不随时间变化。
两个重要的参数
在HashMap中有两个很重要的参数，容量(Capacity)和负载因子(Load factor)
Initial capacity The capacity is the number of buckets in the hash table, The initial capacity is simply the capacity at the time the hash table is created.
Load factor The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.
简单的说，Capacity 就是 buckets 的数目，Load factor 就是 buckets 填满程度的最大比例。如果对迭代性能要求很高的话不要把 capacit 设置过大，也不要把 load factor 设置过小。当 bucket 填充的数目（即hashmap中元素的个数）大于 capacity*load factor 时就需要调整 buckets 的数目为当前的2倍。
put函数的实现
jdk8的思路
put函数大致的思路为：
- 对key的hashCode()做hash，然后再计算index;
- 如果没碰撞直接放到bucket里；
- 如果碰撞了，以链表的形式存在buckets后；
- 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
- 如果节点已经存在就替换old value(保证key的唯一性)
- 如果bucket满了(超过load factor*current capacity)，就要resize。
具体代码实现：
public V put(K key, V value) {
// 对key的hashCode()做hash
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// tab为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 计算index，并对null做处理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 节点存在
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 该链为树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 该链为链表
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 写入
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 超过load factor*current capacity，resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
get函数的实现
在理解了put之后，get就很简单了。大致思路如下：
- bucket里的第一个节点，直接命中；
- 如果有冲突，则通过key.equals(k)去查找对应的entry
若为树，则在树中通过key.equals(k)查找，O(logn)；
若为链表，则在链表中通过key.equals(k)查找，O(n)。
具体代码的实现如下：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 直接命中
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 未命中
if ((e = first.next) != null) {
// 在树中get
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在链表中get
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
hash函数的实现
在get和put的过程中，计算下标时，先对hashCode进行hash操作，然后再通过hash值进一步计算下标，如下图所示：
在对hashCode()计算hash时具体实现是这样的：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
可以看到这个函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或。其中代码注释是这样写的：
Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don’t benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.
在设计hash函数时，因为目前的table长度n为2的幂，而计算下标的时候，是这样实现的(使用 & 位操作，而非 % 求余)：
(n - 1) & hash
(n - 1) & hash
设计者认为这方法很容易发生碰撞。为什么这么说呢？不妨思考一下，在n – 1为15(0x1111)时，其实散列真正生效的只是低4bit的有效位，当然容易碰撞了。
因此，设计者想了一个顾全大局的方法(综合考虑了速度、作用、质量)，就是把高16bit和低16bit异或了一下。设计者还解释到因为现在大多数的hashCode的分布已经很不错了，就算是发生了碰撞也用O(logn)的tree去做了。仅仅异或一下，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。
如果还是产生了频繁的碰撞，会发生什么问题呢？作者注释说，他们使用树来处理频繁的碰撞(we use trees to handle large sets of collisions in bins)，在 JEP-180(//openjdk.java.net/jeps/180)中，描述了这个问题：
Improve the performance of java.util.HashMap under high hash-collision conditions by using balanced trees rather than linked lists to store map entries. Implement the same improvement in the LinkedHashMap class.
之前已经提过，在获取HashMap的元素时，基本分两步：
- 首先根据hashCode()做hash，然后确定bucket的index；
- 如果bucket的节点的key不是我们需要的，则通过keys.equals()在链中找。
在Java 8之前的实现中是用链表解决冲突的，在产生碰撞的情况下，进行get时，两步的时间复杂度是O(1)+O(n)。因此，当碰撞很厉害的时候n很大，O(n)的速度显然是影响速度的。
因此在Java 8中，利用红黑树替换链表，这样复杂度就变成了O(1)+O(logn)了，这样在n很大的时候，能够比较理想的解决这个问题，在 ** Java 8：HashMap的性能提升**(//www.importnew.com/14417.html)一文中有性能测试的结果。
resize的实现（非常有趣又重要的一节）
当put时，如果发现目前的bucket占用程度已经超过了Load Factor所希望的比例，那么就会发生resize。在resize的过程，简单的说就是把bucket扩充为2倍，之后重新计算index，把节点再放到新的bucket中。resize的注释是这样描述的：
Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.
大致意思就是说，当超过限制的时候会resize，然而又因为我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。
怎么理解呢？例如我们从16扩展为32时，具体的变化如下所示：
因此元素在重新计算 hash 之后，因为 n 变为 2 倍，那么 n-1 的 mask 范围在高位多 1bit(红色)，因此新的 index 就会发生这样的变化：
因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。可以看看下图为16扩充为32的resize示意图：
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。
下面是代码的具体实现：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 超过最大值就不再扩充了，就只好随你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 没超过最大值，就扩充为原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把每个bucket都移动到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
jdk7和jdk8中HashMap的大致变化？
这也是很重要的一点，因为JDK7、JDK8依然是市场上的主流版本。还是像开篇说的一样，高频面试题是Java中的重中之重，都是前辈技术人员总结出的工作经验，必会基础。
jdk1.7
在 jdk1.7 版本的时候采用的是 数组+链表 的形式，也就是采用了 拉链法。
Java 标准库的 HashMap 基本上就是用 拉链法 实现的。 拉链法 的实现比较简单，将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
将哈希冲突值加入到每个数组的链表中，他的插入采用的是头插法的形式(这种方法最大的弊端就是会使插入值产生环，从而无限循环，后面我们将详细讲解这种方法的弊端操作)，在进行hash值计算的时候，jdk1.7则采用的是9次扰动(4次位运算+5次异或运算)的方式进行处理（因为本人目前暂时用的jdk1.8所以无法利用源码进行讲解，望见谅），除此之外在扩容上也有所不同，在jdk1.7中采用的全部按照原来的方式进行计算（即hashCode ->> 扰动函数 ->> (h&length-1)），而在jdk1.8 中则采用按照扩容后的规律计算（即扩容后的位置=原位置 or 原位置 + 旧容量）。
关于头插法的拓展：
1. 头插法（头是靠近数组的一端）
2. JDK8以前是头插法，JDK8后是尾插法
3. 为什么要从头插法改成尾插法？
A.因为头插法会造成死链，
B.JDK7用头插是考虑到了一个所谓的热点数据的点(新插入的数据可能会更早用到)，但这其实是个伪命题,因为JDK7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置(就是因为头插) 所以最后的结果 还是打乱了插入的顺序 所以总的来看支撑JDK7使用头插的这点原因也不足以支撑下去了 所以就干脆换成尾插 一举多得。
你可以面试这样回答（JavaPub本人经供参考，更详细阅读下面的参考巨人）：hashmap用数组+链表。数组是固定长度，链表太长就需要扩充数组长度进行rehash减少链表长度。如果两个线程同时触发扩容，在移动节点时会导致一个链表中的2个节点相互引用，从而生成环链表。
JavaPub参考巨人：//blog.csdn.net/chenyiminnanjing/article/details/82706942
jdk1.8
jdk1.8 的版本则采用 数组+链表+红黑树 的方式，如下图：
Java集合小抄是这样描述的：
以Entry[]数组实现的哈希桶数组，用Key的哈希值取模桶数组的大小可得到数组下标。
插入元素时，如果两条Key落在同一个桶（比如哈希值1和17取模16后都属于第一个哈希桶），我们称之为哈希冲突。
JDK的做法是链表法，Entry用一个next属性实现多个Entry以单向链表存放。查找哈希值为17的key时，先定位到哈希桶，然后链表遍历桶里所有元素，逐个比较其Hash值然后key值。
在JDK8里，新增默认为8的阈值，当一个桶里的Entry超过閥值，就不以单向链表而以红黑树来存放以加快Key的查找速度。
当然，最好还是桶里只有一个元素，不用去比较。所以默认当Entry数量达到桶数量的75%时，哈希冲突已比较严重，就会成倍扩容桶数组，并重新分配所有原来的Entry。扩容成本不低，所以也最好有个预估值。
取模用与操作（hash & （arrayLength-1））会比较快，所以数组的大小永远是2的N次方， 你随便给一个初始值比如17会转为32。默认第一次放入元素时的初始值是16。
iterator（）时顺着哈希桶数组来遍历，看起来是个乱序
你知道HashMap工作原理吗
通过 hash 的方法，通过 put 和 get 存储和获取对象。存储对象时，我们将 K/V 传给 put 方法时，它调用 hashCode 计算 hash 从而得到 bucket 位置，进一步存储，HashMap会根据当前 bucket 的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给 get，它调用 hashCode 计算 hash 从而得到bucket位置，并进一步调用 equals() 方法确定键值对。如果发生碰撞的时候，Hashmap 通过链表将产生碰撞冲突的元素组织起来，在 Java 8 中，如果一个 bucket 中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。
JavaPub在写HashMap参考巨人：
//yikun.github.io/2015/04/01/Java-HashMap工作原理及实现/
//segmentfault.com/a/1190000023388339
7.说一下 HashSet 的实现原理？
- HashSet 类是按照哈希算法（离散函数）来存储集合中的元素，他当中的元素是无序的，允许且最多一个元素为 null 。它是Set 的一个实现，所以没有重复元素。
- 在 HashSet 类中实现了 Collection 接口中的所有方法
- HashSet 是基于 HashMap 实现的，默认构造函数是构建一个初始容量为16，负载因子为 0.75 的 HashMap。封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Oject 对象。
- HashSet的其他操作都是基于HashMap的。
8.ArrayList 和 LinkedList 的区别是什么？
学过 Java 基础的同学都能快速回答出，ArrayList 数组实现，所以查询快；LinkedList 列表实现，所以增删快。
为什么快？
掌握这个问题，才能更好的理解这个知识点。
数组
列表
那么为什么数组查询就快了呢?因为假设数组里面保存的是一组对象,每个对象都有内存大小,例如对象中有一个字段是int类型占用4个字节(只考虑实际数据占用的内存),数组在堆上的内存在数组被创建出来就被确定了是40个字节.如果我们要查找第9个对象,可以通过(9-1)*4=32,从33到36字节就是我们要找的对象.是不是很快呢?而链表却不能做到这样的效率.如上图,我们要找到A4,必须先找到A3,再先找到A2,再先找到A1.这样的查找效率会大大降低.
好了,说了查找,再说说插入,数组的插入也相当的浪费效率,如果要在数组内的某一个位置进行插入,需要先将插入位置的前面复制一份,然后在新的数组后面添加新的元素,最后将旧的数组后半部分添加的新的数组后面,而在链表中插入就变得相当简单了,比如我要在A3和A4中插入B,只需定位到A3的指针和A4的数据即可,将A3的指针指向B的值,将B的指针指向A4的值,B就插入进了链表.
JavaPub 推荐关于 ArrayList 底层数组扩容方法：//javapub.blog.csdn.net/article/details/113686651
9.如何实现数组和 List 之间的转换？
数组转 List ，使用 JDK 中 java.util.Arrays 工具类的 asList 方法
public static void testArray2List() {
String[] strs = new String[] {"aaa", "bbb", "ccc"};
List<String> list = Arrays.asList(strs);
for (String s : list) {
System.out.println(s);
}
}
List 转数组，使用 List 的 toArray 方法。无参 toArray 方法返回 Object 数组，传入初始化长度的数组对象，返回该对象数组。
public static void testList2Array() {
List<String> list = Arrays.asList("aaa", "bbb", "ccc");
String[] array = list.toArray(new String[list.size()]);
for (String s : array) {
System.out.println(s);
}
}
10.ArrayList 和 Vector 的区别是什么？
-
线程安全：Vector 使用了 Synchronized 来实现线程同步，是线程安全的，而 ArrayList 是非线程安全的。
-
性能：ArrayList 在性能方面要优于 Vector。
-
扩容：ArrayList 和 Vector 都会根据实际的需要动态的调整容量，都采用线性连续存储空。
只不过在 Vector 扩容每次会增加 1 倍，而 ArrayList 只会增加 50%。
- Vector 可以设置 capacityIncrement ，而 ArrayList 不可以，从字面理解就是 capacity 容量，Increment 增加，容量增长的参数。
11.Array 和 ArrayList 有何区别？
Array：它是数组，申明数组的时候就要初始化并确定长度，长度不可变，而且它只能存储同一类型的数据，比如申明为 String 类型的数组，那么它只能存储 String 类型数据
ArrayList：它是一个集合，需要先申明，然后再添加数据，长度是根据内容的多少而改变的， ArrayList 可以存放不同类型的数据，在存储基本类型数据的时候要使用基本数据类型的包装类
当能确定长度并且数据类型一致的时候就可以用数组，其他时候使用 ArrayList。
12.在 Queue 中 poll()和 remove()有什么区别？
队列（Queue） 是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。
/**
* Retrieves and removes the head of this queue. This method differs
* from {@link #poll poll} only in that it throws an exception if this
* queue is empty.
*
* @return the head of this queue
* @throws NoSuchElementException if this queue is empty
*/
E remove();
/**
* Retrieves and removes the head of this queue,
* or returns {@code null} if this queue is empty.
*
* @return the head of this queue, or {@code null} if this queue is empty
*/
E poll();
从源码描述可以知道，remove() 如果队列为空的时候，则会抛出异常，poll() 会返回 null。
13.哪些集合类是线程安全的？
- Vector，实现 List 接口，与 ArrayList 相比几乎相同，但是是线程安全的。底层是数组。
- Stack，继承 Vector 类，先进后出。
- HashTable，实现 Map 接口，与 HashMap 几乎完全相同，但是是线程安全的。
- java.util.concurrent包下的所有集合类，例如：ConcurrentHashMap。（ConcurrentLinkedQueue、ConcurrentLinkedDueue 等）
拓展：java.util.concurrent包下的集合类如何保证线程安全
JavaPub参考巨人：//www.cnblogs.com/junjiang3/p/8686290.html
14.迭代器 Iterator 是什么？
标准答案：
迭代器是一种设计模式，它是一个对象，它可以遍历并选择序列中的对象，而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象，因为创建它的代价小。迭代器设计模式案例演示、讲解，wx订阅：JavaPub
简单来说，迭代器是用于顺序访问集合对象的元素，无需知道集合对象的底层实现。Iterator 是可以遍历集合的对象，为各种容器提供了公共的操作接口，隔离对容器的遍历操作和底层实现，从而解耦。
Java中的Iterator功能比较简单，并且只能单向移动：
-
使用方法iterator()要求容器返回一个Iterator。第一次调用Iterator的next()方法时，它返回序列的第一个元素。注意：iterator()方法是java.lang.Iterable接口,被Collection继承。
-
使用next()获得序列中的下一个元素。
-
使用hasNext()检查序列中是否还有元素。
-
使用remove()将迭代器新返回的元素删除。
简单栗子：
import java.util.*;
public class Muster {
public static void main(String[] args) {
ArrayList list = new ArrayList();
list.add("a");
list.add("b");
list.add("c");
Iterator it = list.iterator();
while(it.hasNext()){
String str = (String) it.next();
System.out.println(str);
}
}
}
JavaPub参考巨人：//www.cnblogs.com/hasse/p/5024193.html
15.Iterator 怎么使用？有什么特点？
接口源码：
//是否有下一个元素
boolean hasNext();
//下一个元素
E next();
//从迭代器指向的集合中删除迭代器返回的最后一个元素
default void remove() {
throw new UnsupportedOperationException("remove");
}
/**
* Performs the given action for each remaining element until all elements have been processed or the action throws an exception. Actions are performed in the order of iteration, if that order is specified. Exceptions thrown by the action are relayed to the caller.
*
* 简单来说，就是对集合中剩余的元素进行操作，直到元素完毕或者抛出异常。这里重要的是剩余元素，怎么理解呢，下面就来用代码解释
*
* @since 1.8
*/
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
使用案例：
public class TestIterator {
static List<String> list = new ArrayList<String>();
static {
list.add("111");
list.add("222");
list.add("333");
}
public static void main(String[] args) {
testIteratorNext();
System.out.println();
testForEachRemaining();
System.out.println();
testIteratorRemove();
}
//使用 hasNext 和 next遍历
public static void testIteratorNext() {
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String str = iterator.next();
System.out.println(str);
}
}
//使用 Iterator 删除元素
public static void testIteratorRemove() {
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String str = iterator.next();
if ("222".equals(str)) {
iterator.remove();
}
}
System.out.println(list);
}
//使用 forEachRemaining 遍历
public static void testForEachRemaining() {
final Iterator<String> iterator = list.iterator();
iterator.forEachRemaining(new Consumer<String>() {
public void accept(String t) {
System.out.println(t);
}
});
}
}
打印结果：
111
222
333
111
222
333
111
333
注意事项：
-
在迭代过程中调用集合的 remove(Object o) 可能会报 java.util.ConcurrentModificationException 异常
-
forEachRemaining 方法中 调用Iterator 的 remove 方法会报 java.lang.IllegalStateException 异常
forEachRemaining() 用法：
import java.util.*;
public class Test{
public static void main(String[] args){
//创建一个元素类型为Integer的集合
Collection<Integer> collection = new HashSet<>();
for (int i=0;i<10 ;i++ ){
//向集合中添加元素
collection.add(i);
}
//获取该集合的迭代器
Iterator<Integer> iterator= collection.iterator();
//调用forEachRemaining()方法遍历集合元素
iterator.forEachRemaining(ele -> System.out.println(ele));
}
}
-----------------------------------------------------------------------
输出为：
0
1
2
3
4
5
6
7
8
9
这是预料之中的结果。那继续看下面代码：
import java.util.*;
public class Test
{
public static void main(String[] args)
{
//创建一个元素类型为Integer的集合
Collection<Integer> collection = new HashSet<>();
for (int i=0;i<10 ;i++ )
{
//向集合中添加元素
collection.add(i);
}
//获取该集合的迭代器
Iterator<Integer> iterator= collection.iterator();
//调用迭代器的经过集合实现的抽象方法遍历集合元素
while(iterator.hasNext())
{
System.out.println(iterator.next());
}
System.out.println("--------------");
//调用forEachRemaining()方法遍历集合元素
iterator.forEachRemaining(ele -> System.out.println(ele));
}
}
-----------------------------------------------------------------------
这时输出为：
0
1
2
3
4
5
6
7
8
9
明明调用了迭代器两个遍历方法，怎么会只遍历一次呢？
问题就出在剩余里，当第一次调用迭代器的经过集合实现的抽象方法遍历集合元素时，迭代器就已经将元素遍历完毕，也就是说迭代器中已经没有剩余元素了，因此这时调用forEachRemaining()方法，就什么也不输出了，为了验证，再来看下面代码：
//获取该集合的迭代器
Iterator<Integer> iterator= collection.iterator();
//调用forEachRemaining()方法遍历集合元素
int i=0;
while(iterator.hasNext())
{
System.out.println(iterator.next());
i++;
if (i==5)
{
break;
}
}
System.out.println("--------------");
//调用forEachRemaining()方法遍历集合元素
iterator.forEachRemaining(ele -> System.out.println(ele));
}
}
-----------------------------------------------------------------------
这时输出：
0
1
2
3
4
--------------
5
6
7
8
9
可以看到，当我们第一次用迭代器遍历时，只让它遍历五次就跳出循环，那么就还剩下五个元素，再调用 forEachRemaining() 方法，就可以看到输出后五个元素了。
JavaPub参考巨人：
//www.cnblogs.com/it-deepinmind/p/13376544.html
16.Iterator 和 ListIterator 有什么区别？
在使用Java集合的时候，都需要使用Iterator。但是java集合中还有一个迭代器ListIterator,在使用List、ArrayList、LinkedList和Vector的时候可以使用。这两种迭代器有什么区别呢？下面我们详细分析。这里有一点需要明确的时候，迭代器指向的位置是元素之前的位置。
-
ListIterator有add()方法，可以向List中添加对象，而Iterator不能
-
ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历。Iterator就不可以。
-
ListIterator可以定位当前的索引位置，nextIndex()和previousIndex()可以实现。Iterator没有此功能。
-
都可实现删除对象，但是ListIterator可以实现对象的修改，set()方法可以实现。Iierator仅能遍历，不能修改。
JavPub参考巨人：//www.cnblogs.com/lijia0511/p/4960033.html
包含方法
Iterator迭代器包含的方法有：
hasNext()：如果迭代器指向位置后面还有元素，则返回 true，否则返回false
next()：返回集合中Iterator指向位置后面的元素
remove()：删除集合中Iterator指向位置后面的元素
ListIterator迭代器包含的方法有：
add(E e): 将指定的元素插入列表，插入位置为迭代器当前位置之前
hasNext()：以正向遍历列表时，如果列表迭代器后面还有元素，则返回 true，否则返回false
hasPrevious():如果以逆向遍历列表，列表迭代器前面还有元素，则返回 true，否则返回false
next()：返回列表中ListIterator指向位置后面的元素
nextIndex():返回列表中ListIterator所需位置后面元素的索引
previous():返回列表中ListIterator指向位置前面的元素
previousIndex()：返回列表中ListIterator所需位置前面元素的索引
remove():从列表中删除next()或previous()返回的最后一个元素（有点拗口，意思就是对迭代器使用hasNext()方法时，删除ListIterator指向位置后面的元素；当对迭代器使用hasPrevious()方法时，删除ListIterator指向位置前面的元素）
set(E e)：从列表中将next()或previous()返回的最后一个元素返回的最后一个元素更改为指定元素e
17.怎么确保一个集合不能被修改？
1.Collections. unmodifiableCollection(Collection c) 方法
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Collection<Integer> readOnlyList = Collections.unmodifiableCollection(list);
readOnlyList.add(4); // 会报错
2.使用Arrays.asList创建的集合
List<Integer> integers = Arrays.asList(11, 22, 33, 44);
integers.add(55);
参考地址有详细的源码debug解析步骤。
JavaPub参考巨人-包括源码解读（篇幅较长）：//javapub.blog.csdn.net/article/details/113768605
恭喜你看到了最后，这篇文章整理用了四天时间。再看和转发是对我最大的鼓励，我的pub哥，欢迎关注JavaPub。
