集合框架面试题和解析

为什么要设计出迭代器

迭代器本质是一种设计模式，为了解决为不同的集合类提供统一的遍历操作接口。

List、Set、Map 之间的区别

List

1.可以允许重复的对象。
2.可以插入多个null元素。
3.是一个有序容器，保持了每个元素的插入顺序，输出的顺序就是插入的顺序。
4.常用的实现类有 ArrayList、LinkedList 和 Vector。

Set：

1.不允许重复对象
2.无序容器，无法保证每个元素的存储顺序，TreeSet通过 Comparator 或者 Comparable 维护了一个排序顺序。
3.只允许一个 null 元素
4.Set 接口最流行的几个实现类是 HashSet、LinkedHashSet 以及 TreeSet。

Map：

1.Map不是collection的子接口或者实现类。Map是一个接口。
2.Map 的每个 Entry 都持有两个对象，也就是一个键一个值（键值对），Map 可能会持有相同的值对象但键对象必须是唯一的。
3.TreeMap 也通过 Comparator 或者 Comparable 维护了一个排序顺序。
4.Map 里你可以拥有随意个 null 值但最多只能有一个 null 键。
5.Map 接口最流行的几个实现类是 HashMap、LinkedHashMap、Hashtable 和 TreeMap。（HashMap、TreeMap最常用）

Arraylist 与 LinkedList 的区别

1. 底层数据结构： Arraylist 底层使用的是动态数组；LinkedList 底层使用的是 双向链表 数据结构

2.插入删除数据方式： ArrayList插入删除元素时分两种情况：①把元素添加到末尾所需的时间复杂度是O(1)，②在指定位置添加删除元素时就需要移动整个数组，操作代价就比较大了；LinkedList 对于添加删除方法只需要断链然后更改指向，所需的消耗就很小了。

3.是否支持快速随机访问： ArrayList 支持高效的随机元素访问而LinkedList 不支持。

4. 内存空间占用： ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

ArrayList 和 Vector 的区别

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

Arraylist不是同步的，所以在不需要保证线程安全时建议使用Arraylist，需要时使用 CopyOnWriteArrayList 。Arraylist一次扩容为1.5倍。

ArrayList 的扩容机制？

前提：以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。

流程：

当我们要 add 进第1个元素到 ArrayList 时，数组长度为0 （因为还是一个空的 list），因为执行了 ensureCapacityInternal() 方法，所以更改了 minCapacity，此时为10（默认最小容量）。此时，就会执行grow 方法把容量扩大为10，然后一直add到第11个元素时，会对旧数组位移运算得到新数组，然后把旧数组整个复制到新数组上，是旧容量的 1.5 倍。

如何实现数组和 List 之间的转换？

List转换成为数组：调用ArrayList的toArray方法。
数组转换成为List：调用Arrays的asList方法。

Array 和 ArrayList 有何区别？

Array可以容纳基本类型和对象，而ArrayList只能容纳对象。
Array是指定大小的，而ArrayList大小是固定的。
Array没有提供ArrayList那么多功能，比如addAll、removeAll和iterator等。

HashMap 和 Hashtable 的区别

线程是否安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过synchronized 修饰。（如果保证线程安全的话使用 ConcurrentHashMap ）；
效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛出 NullPointerException。
初始容量大小和每次扩充容量大小的不同： ①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小；
底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

说说 HashMap

1.内部存储结构：数组+链表+红黑树（JDK8）

2.默认容量16（数组长度），默认装载因子0.75。

3.key 和 value 对数据类型的要求都是泛型。

4.key 可以为 null，放在 table[0] 中。

5.hashcode：计算键的hashcode作为存储键信息的数组下标用于查找键对象的存储位置。equals：HashMap 使用 equals() 判断当前的键是否与表中存在的键相同。

HashMap 的结构

在 JDK 1.7 中 HashMap 是以数组加链表的形式组成的，JDK 1.8 之后新增了红黑树的组成结构，当链表大于 8 并且容量大于 64 时，链表结构会转换成红黑树结构，添加红黑树是因为一旦链表过长，会严重影响 HashMap 的性能，而红黑树具有快速增删改查的特点，这样就可以有效的解决链表过长时操作比较慢的问题。

HashMap 的长度为什么是2的幂次方

HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法；这个算法实际就是取模，hash%length，计算机中直接求余效率不如位移运算，源码中做了优化hash&(length-1)，

hash%length==hash&(length-1)的前提是 length 是2的 n 次方；

什么是 HashMap 的加载因子？加载因子为什么是 0.75？

判断什么时候进行扩容的，假如加载因子是 0.5，HashMap 的初始化容量是 16，那么当 HashMap 中有 16*0.5=8 个元素时，HashMap 就会进行扩容。

这其实是出于容量和性能之间平衡的结果：

当加载因子设置比较大的时候，扩容的门槛就被提高了，扩容发生的频率比较低，占用的空间会比较小，但此时发生Hash冲突的几率就会提升，因此需要更复杂的数据结构来存储元素，这样对元素的操作时间就会增加，运行效率也会因此降低；
而当加载因子值比较小的时候，扩容的门槛会比较低，因此会占用更多的空间，多次扩容也会影响性能。
HashMap的容量有一个固定的要求就是一定是2的幂次方。所以，如果负载因子是3/4的话，那么和capacity的乘积结果就可以是一个整数。

所以综合了以上情况就取了一个 0.5 到 1.0 的平均数 0.75 作为加载因子。

put 方法流程

map.put(“a”,“b”)的整个流程：

  	1. 先判断散列表是否没有初始化或者为空，如果是就扩容
            	2. 根据键值 key 计算 hash 值，得到要插入的数组索引 
         	3. 判断要插入的那个数组是否为空：
                           	1. 如果为空直接插入。
                           	2. 如果不为空，判断 key 的值是否是重复（用 equals 方法）：
                   	1. 如果是就直接覆盖
                   	2. 如果不重复就再判断此节点是否已经是红黑树节点：
                   	1. 如果是红黑树节点就把新增节点放入树中
                             	2. 如果不是，就开始遍历链表：
                                 1. 循环判断直到链表最底部，到达底部就插入节点，然后判断是否大于链表长度是否大于8：
                                    1. 如果大于8就转换为红黑树
                                    2. 如果不大于8就继续下一步
                                       2. 到底部之前发现有重复的值，就覆盖。
       	4. 判断是否需要扩容，如果需要就扩容。

HashMap 的扩容机制

扩容时机：当size大于threshold的时候，并不一定会触发扩容机制，只要有一个新建的节点出现哈希冲突，则立刻resize。

size记录的是map中包含的Entry的数量
而threshold记录的是需要resize的阈值且 threshold = loadFactor * capacity
capacity 其实就是桶的长度

步骤：

数组，阈值都扩大一倍
如果旧数组不为空，开始遍历旧数组
遍历到的数组上只有一个元素，就直接迁移
如果是红黑树就使用 split 方法
如果是链表就把链表拆成两个，按照高位运算的结果放到新数组中并且保留顺序

JDK 1.8 在扩容方面对 HashMap 做了哪些优化？

1.7创建一个容量的新数组，重新计算每个元素在数组中的位置并且进行迁移。

1.8中在扩容HashMap的时候，不需要像1.7中去重新计算元素的hash，只需要看看原来的hash值新增的哪个二进制数是1还是0就好了，如果是0的话表示索引没有变，是1的话表示索引变成“oldCap+原索引”，这样即省去了重新计算hash值的时间，并且扩容后链表元素位置不会倒置。

HashMap 1.7和1.8版本区别

**数据结构：**1.7：数组+链表，1.8：数组+链表+红黑树
**新节点插入方式：**1.7：头插法，1.8：直接在尾部插入
**扰动运算次数：**1.7：运算多，1.8：运算少
**插入和扩容的判断：**1.7：先扩容后插入，1.8：先插入后扩容
- 为什么？1.8增加了判断是否为红黑树节点，先扩容的话不知道到底扩链表节点还是红黑树。

HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标？

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

怎么解决呢？

1.HashMap自己实现了自己的hash()方法，通过两次扰动使得它自己的哈希值高低位自行进行异或运算，降低哈希碰撞概率也使得数据分布更平均；

2.保证数组长度为2的幂次方的时候，使用hash()运算之后的值与运算（&）（数组长度 - 1）来获取数组下标的方式进行存储。

那为什么是两次扰动呢？

这样就是加大哈希值低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性&均匀性，最终减少Hash冲突，两次就够了，已经达到了高位低位同时参与运算的目的；

HashMap1.7为什么不安全？⭐

HashMap在rehash的时候，这个会重新将原数组的内容重新hash到新的扩容数组中，在多线程的环境下，存在同时其他put操作，如果hash值相同，把值插入同一个链表，会因为头插法的特性造成闭环，导致在get时会出现死循环，所以HashMap是线程不安全的。

高并发下HashMap1.7的环是如何产生的

若当前线程一此时获得ertry节点，但是被线程中断无法继续执行，此时线程二进入transfer函数，并把函数顺利执行，此时新表中的某个位置有了节点，之后线程一获得执行权继续执行，在tranfer方法中会把next指向自己造成闭环，然后在get时会出现死循环。

为什么HashMap中String、Integer这样的包装类适合作为Key？⭐

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

都是final类型，即不可变性，保证key的不可更改性，不会存在获取hash值不同的情况
内部已重写了equals()、hashCode()等方法，遵守了HashMap内部的规范，不容易出现Hash值计算错误的情况。

如果我想要让自己的Object作为K应该怎么办呢？

重写hashCode()和equals()方法。 重写hashCode()是因为需要计算存储数据的存储位置， 重写equals()方法 目的是为了保证key在哈希表中的唯一性；

ConcurrentHashMap线程安全的实现方式/数据结构⭐

在JDK1.7版本中，ConcurrentHashMap维护了一个Segment数组，Segment这个类继承了重入锁ReentrantLock，在该类里面维护了一个 HashEntry<K,V>[] table数组，在写操作put，remove，扩容的时候，会对Segment加锁，所以仅仅影响这个Segment，不同的Segment还是可以并发的，所以解决了线程的安全问题，同时又采用了分段锁也提升了并发的效率。在JDK1.8版本中，ConcurrentHashMap摒弃了Segment的概念，而是直接用Node数组+链表+红黑树的数据结构来实现，并发控制使用Synchronized和CAS来操作，整个看起来就像是优化过且线程安全的HashMap。

详见java容器总结篇。

BlockingQueue是什么？

Java.util.concurrent.BlockingQueue是一个队列，在进行检索或移除一个元素的时候，它会等待队列变为非空；当在添加一个元素时，它会等待队列中的可用空间。BlockingQueue接口是Java集合框架的一部分，主要用于实现生产者-消费者模式。我们不需要担心等待生产者有可用的空间，或消费者有可用的对象，因为它都在BlockingQueue的实现类中被处理了。Java提供了集中BlockingQueue的实现，比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue等。

在 Queue 中 poll()和 remove()有什么区别？

poll() 和 remove() 都是从队列中取出一个元素，但是 poll() 在获取元素失败的时候会返回空，但是 remove() 失败的时候会抛出异常。

如果觉得文章对你有用，请随意赞赏

集合框架哈哈屋社 runwsh

集合框架面试知识点

http://localhost:8080/archives/ji-he-kuang-jia-mian-shi-zhi-shi-dian

作者

Administrator

发布于

2022-06-27

更新于

2024-08-03

许可协议

CC BY 4.0