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知识清单

微信搜：JavaPub，阅读全套系列面试题教程

[toc]

容器是开发中非常重要的一部分知识，本篇尽量以大白话描述各个知识点。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 参考巨人：https://zhuanlan.zhihu.com/p/29421226

2.Collection 和 Collections 有什么区别？

1. java.util.Collection 是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法。Collection 接口在 Java 类库中有很多具体的实现。Collection 接口的意义是为各种具体的集合提供了最大化的统一操作方式。

List，Set，Queue 接口都继承 Collection。

直接实现该接口的类只有 AbstractCollection 类，该类也只是一个抽象类，提供了对集合类操作的一些基本实现。List 和 Set 的具体实现类基本上都直接或间接的继承了该类。

 Collection  ├List  │├LinkedList  │├ArrayList  │└Vector  │　└Stack  └Set 

1. 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。

区别：

1. Hashtable 继承自 Dictionary 类，而 HashMap 继承自 AbstractMap 类。但二者都实现了 Map 接口。

2. HashMap 允许将 null 作为一个 entry 的 key 或者 value，而 Hashtable 不允许。

3. HashMap 把 Hashtable 的 contains 方法去掉了，改成 containsValue 和 containsKey。因为 contains 方法容易让人引起误解。Hashtable 则保留了 contains，containsValue 和 containsKey 三个方法，其中 contains 和 containsValue 功能相同。

4. Hashtable 中的方法是 Synchronize 的，而 HashMap 中的方法在缺省情况下是非 Synchronize 的。在多线程并发的环境下，可以直接使用 Hashtable，不需要自己为它的方法实现同步，但使用 HashMap 时就必须要自己增加同步处理。（结构上的修改是指添加或删除一个或多个映射关系的任何操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的非同步访问，如下所示：

Map m = Collections.synchronizedMap(new HashMap(...));

1. 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 后，只有符号外改变，而后面的位都不变。

1. 内部实现使用的数组初始化和扩容方式不同，

HashTable 在不指定容量的情况下的默认容量为 11，而 HashMap 为 16，Hashtable 不要求底层数组的容量一定要为 2 的整数次幂，而 HashMap 则要求一定为 2 的整数次幂。

Hashtable 扩容时，将容量变为原来的 2 倍加 1，而 HashMap 扩容时，将容量变为原来的 2 倍。

Hashtable 和 HashMap 它们两个内部实现方式的数组的初始大小和扩容的方式。HashTable 中 hash 数组默认大小是 11，增加的方式是 old*2+1。

源码也是非常重要的一点，而且写得非常棒，后面单独写一篇。

JavaPub 参考巨人（包括一部分源码）：https://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 参考巨人：https://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 函数大致的思路为：

1. 对 key 的 hashCode()做 hash，然后再计算 index;

2. 如果没碰撞直接放到 bucket 里；

3. 如果碰撞了，以链表的形式存在 buckets 后；

4. 如果碰撞导致链表过长(大于等于 TREEIFY_THRESHOLD)，就把链表转换成红黑树；

5. 如果节点已经存在就替换 old value(保证 key 的唯一性)

6. 如果 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 就很简单了。大致思路如下：

1. bucket 里的第一个节点，直接命中；

2. 如果有冲突，则通过 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(http://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 的元素时，基本分两步：

1. 首先根据 hashCode()做 hash，然后确定 bucket 的 index；

2. 如果 bucket 的节点的 key 不是我们需要的，则通过 keys.equals()在链中找。

在 Java 8 之前的实现中是用链表解决冲突的，在产生碰撞的情况下，进行 get 时，两步的时间复杂度是 O(1)+O(n)。因此，当碰撞很厉害的时候 n 很大，O(n)的速度显然是影响速度的。

因此在 Java 8 中，利用红黑树替换链表，这样复杂度就变成了 O(1)+O(logn)了，这样在 n 很大的时候，能够比较理想的解决这个问题，在 Java 8：HashMap 的性能提升(http://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参考巨人：https://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 参考巨人：

https://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/

https://segmentfault.com/a/1190000023388339

7.说一下 HashSet 的实现原理？

1. HashSet 类是按照哈希算法（离散函数）来存储集合中的元素，他当中的元素是无序的，允许且最多一个元素为 null 。它是 Set 的一个实现，所以没有重复元素。

2. 在 HashSet 类中实现了 Collection 接口中的所有方法

3. HashSet 是基于 HashMap 实现的，默认构造函数是构建一个初始容量为 16，负载因子为 0.75 的 HashMap。封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Oject 对象。

4. 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 底层数组扩容方法：https://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 参考巨人：https://www.cnblogs.com/junjiang3/p/8686290.html

14.迭代器 Iterator 是什么？

标准答案：

迭代器是一种设计模式，它是一个对象，它可以遍历并选择序列中的对象，而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象，因为创建它的代价小。迭代器设计模式案例演示、讲解，wx 订阅：JavaPub

简单来说，迭代器是用于顺序访问集合对象的元素，无需知道集合对象的底层实现。Iterator 是可以遍历集合的对象，为各种容器提供了公共的操作接口，隔离对容器的遍历操作和底层实现，从而解耦。

Java 中的 Iterator 功能比较简单，并且只能单向移动：

1. 使用方法 iterator()要求容器返回一个 Iterator。第一次调用 Iterator 的 next()方法时，它返回序列的第一个元素。注意：iterator()方法是 java.lang.Iterable 接口,被 Collection 继承。

1. 使用 next()获得序列中的下一个元素。

1. 使用 hasNext()检查序列中是否还有元素。

1. 使用 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 参考巨人：https://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);			}					});	}}

打印结果：

111222333 111222333 111333

注意事项：

• 在迭代过程中调用集合的 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));    }}-----------------------------------------------------------------------输出为：0123456789

这是预料之中的结果。那继续看下面代码：

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));            }}-----------------------------------------------------------------------
这时输出为：0123456789

明明调用了迭代器两个遍历方法，怎么会只遍历一次呢？

问题就出在剩余里，当第一次调用迭代器的经过集合实现的抽象方法遍历集合元素时，迭代器就已经将元素遍历完毕，也就是说迭代器中已经没有剩余元素了，因此这时调用 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));            }}-----------------------------------------------------------------------这时输出：01234--------------56789

可以看到，当我们第一次用迭代器遍历时，只让它遍历五次就跳出循环，那么就还剩下五个元素，再调用 forEachRemaining() 方法，就可以看到输出后五个元素了。

JavaPub 参考巨人：

https://www.cnblogs.com/it-deepinmind/p/13376544.html

16.Iterator 和 ListIterator 有什么区别？

在使用 Java 集合的时候，都需要使用 Iterator。但是 java 集合中还有一个迭代器 ListIterator,在使用 List、ArrayList、LinkedList 和 Vector 的时候可以使用。这两种迭代器有什么区别呢？下面我们详细分析。这里有一点需要明确的时候，迭代器指向的位置是元素之前的位置。

1. ListIterator 有 add()方法，可以向 List 中添加对象，而 Iterator 不能

1. ListIterator 和 Iterator 都有 hasNext()和 next()方法，可以实现顺序向后遍历，但是 ListIterator 有 hasPrevious()和 previous()方法，可以实现逆向（顺序向前）遍历。Iterator 就不可以。

1. ListIterator 可以定位当前的索引位置，nextIndex()和 previousIndex()可以实现。Iterator 没有此功能。

1. 都可实现删除对象，但是 ListIterator 可以实现对象的修改，set()方法可以实现。Iierator 仅能遍历，不能修改。

JavPub 参考巨人：https://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 参考巨人-包括源码解读（篇幅较长）：https://javapub.blog.csdn.net/article/details/113768605

恭喜你看到了最后，这篇文章整理用了四天时间。再看和转发是对我最大的鼓励，我的 pub 哥，欢迎关注 JavaPub。