java集合面试题—java 集合 面试 收藏 0

Java集合面试题汇总大全

每个集合的出现一定是为了解决某种问题的解决方案。

集合流程图

1. JAVA中集合和数组的区别
2. Collection和Collections的区别
3. ArrayList和LinkedList 和Vector的区别
4. list/set/map的区别
5. HashSet和TreeSet和LinkedHashSet区别
6. HashMap和Hashtable的比较
7. HashMap和ConcurrentHashMap区别
8. HashMap 底层实现原理
9. HashMap和LinkedHashMap的区别？
10. ArrayList/LinkedList /HashMap初始大小，add后是多少？(jdk1.8)

– Collection：是集合类的上级接口，继承与它的接口主要有Set、List– Collcetions：针对集合类的一个帮助类，提供了一系列静态方法实现对各种集合的搜索、排序、线程安全等操作

list/set/map都是各自集合的接口。

本文中的有序指的是添加顺序和遍历顺序一致，称为有序。

总结：

1、HashTable 线程安全，HashMap 非线程安全 2、Hashtable 不允许 null 值(key 和 value 都不可以)，HashMap 允许 null 值(key 和 value 都可以)。 3、两者的遍历方式大同小异，Hashtable 仅仅比 HashMap 多一个 elements 方法

总结：1、ConcurrentHashMap是线程安全的，HashMap不是线程安全的2、HashMap允许键和值为null,ConcurrentHashMap不允许3、HashMap在用Iteroctor遍历的同时，不允许修改HashMap，ConcurrentHashMap允许该行为，并且对后续的遍历是可见的（CurrentHashMap使用的是分段锁，效率高于HashTable,且是线程安全）

具体详细可参考：

一、HashMap基本描述 HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。并且不保证映射的顺序。

1.1HashMap的数据结构? 哈希表结构(链表散列:数组+链表)实现,结合数组和链表的优点。当链表长度超过8时,链表转换为红黑树1.2HashMap的工作原理? HashMap（底层采用数组+链表）,采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体，依次来解决Hash冲突的问题，因为HashMap是按照Key的hash值来计算Entry在HashMap中存储的位置的，如果hash值相同，而key内容不相等，那么就用链表来解决这种hash冲突。1.3HashMap的put实现过程? HashMap通过put&get方法存储和获取。我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put(key, value)方法传递键和值时，它先调用key.hashCode()方法，得到hash值，然后结合数组长度,计算得数组下标，用于找到bucket位置，来储存Entry对象。如果hash值在HashMap中不存在,则执行插入,若存在,则发生碰撞，则插入链表的尾部(尾插法)或者红黑树中(树的添加方式)。如果hash值在HashMap中存在,且它们两者equals返回true,则更新键值对。如果HashMap集合中的键值对大于12,调用resize方法进行数组扩容。1.4HashMap的get实现过程? 从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。 底层的数据结构：HashMap的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。1.5 JDK8中什么时候会转为红黑树？ 如果链表的长度超过了8,那么链表将转换为红黑树。(桶的数量必须大于64,小于64的时候只会扩容)。

50道Java集合高频面试题，看完面试成功率99%

这不是秋招马上开始了嘛，这个月我每天会分享一个技术栈的高频面试题，而这些面试题都是取自于我五月份时整理的一些面试文档，希望对最近有面试或者有跳槽打算的同学有所帮助，需要这些文档的同学转发本文后私信【629】三个数字即可获取

目前已经更新了Nginx、MySQL和RabbitMQ等系列，感兴趣的朋友也可以去看一下

废话不多说，开始今天的面试之旅

可以从它们的底层数据结构、效率、开销进行阐述哈

• ArrayList是数组的数据结构，LinkedList是链表的数据结构。
• 随机访问的时候，ArrayList的效率比较高，因为LinkedList要移动指针，而ArrayList是基于索引(index)的数据结构，可以直接映射到。
• 插入、删除数据时，LinkedList的效率比较高，因为ArrayList要移动数据。
• LinkedList比ArrayList开销更大，因为LinkedList的节点除了存储数据，还需要存储引用。

Collection.sort是对list进行排序，Arrays.sort是对数组进行排序。

Collections.sort方法调用了list.sort方法

list.sort方法调用了Arrays.sort的方法

因此，Collections.sort方法底层就是调用的Array.sort方法

Arrays的sort方法，如下：

如果比较器为null，进入sort（a）方法。如下：

因此，Arrays的sort方法底层就是：

• legacyMergeSort(a)，归并排序，
• ComparableTimSort.sort()：即Timsort排序。

Timsort排序是结合了合并排序（merge.sort）和插入排序（insertion sort）而得出的排序方法；

1.当数组长度小于某个值，采用的是二分插入排序算法，如下：

1. 找到各个run，并入栈。

1. 按规则合并run。

• HashMap是以键值对存储数据的集合容器
• HashMap是非线性安全的。
• HashMap底层数据结构：数组+(链表、红黑树)，jdk8之前是用数组+链表的方式实现，jdk8引进了红黑树
• Hashmap数组的默认初始长度是16，key和value都允许null的存在
• HashMap的内部实现数组是Node[]数组，上面存放的是key-value键值对的节点。HashMap通过put和get方法存储和获取。
• HashMap的put方法，首先计算key的hashcode值，定位到对应的数组索引，然后再在该索引的单向链表上进行循环遍历，用equals比较key是否存在，如果存在则用新的value覆盖原值，如果没有则向后追加。
• jdk8中put方法：先判断Hashmap是否为空，为空就扩容，不为空计算出key的hash值i，然后看table[i]是否为空，为空就直接插入，不为空判断当前位置的key和table[i]是否相同，相同就覆盖，不相同就查看table[i]是否是红黑树节点，如果是的话就用红黑树直接插入键值对，如果不是开始遍历链表插入，如果遇到重复值就覆盖，否则直接插入，如果链表长度大于8，转为红黑树结构，执行完成后看size是否大于阈值threshold，大于就扩容，否则直接结束。
• Hashmap解决hash冲突，使用的是链地址法，即数组+链表的形式来解决。put执行首先判断table[i]位置，如果为空就直接插入，不为空判断和当前值是否相等，相等就覆盖，如果不相等的话，判断是否是红黑树节点，如果不是，就从table[i]位置开始遍历链表，相等覆盖，不相等插入。
• HashMap的get方法就是计算出要获取元素的hash值，去对应位置获取即可。
• HashMap的扩容机制，Hashmap的扩容中主要进行两步，第一步把数组长度变为原来的两倍，第二部把旧数组的元素重新计算hash插入到新数组中，jdk8时，不用重新计算hash，只用看看原来的hash值新增的一位是零还是1，如果是1这个元素在新数组中的位置，是原数组的位置加原数组长度，如果是零就插入到原数组中。扩容过程第二部一个非常重要的方法是transfer方法，采用头插法，把旧数组的元素插入到新数组中。
• HashMap大小为什么是2的幂次方？效率高+空间分布均匀

有关于HashMap这些常量设计目的，也可以看我这篇文章：面试加分项-HashMap源码中这些常量的设计目的

• List 以索引来存取元素，有序的，元素是允许重复的，可以插入多个null。
• Set 不能存放重复元素，无序的，只允许一个null
• Map 保存键值对映射，映射关系可以一对一、多对一
• List 有基于数组、链表实现两种方式
• Set、Map 容器有基于哈希存储和红黑树两种方式实现
• Set 基于 Map 实现，Set 里的元素值就是 Map的键值

Queue队列中，poll() 和 remove() 都是从队列中取出一个元素，在队列元素为空的情况下，remove() 方法会抛出异常，poll() 方法只会返回 null 。

看一下源码的解释吧：

HashMap

• 底层由链表+数组+红黑树实现
• 可以存储null键和null值
• 线性不安全
• 初始容量为16，扩容每次都是2的n次幂
• 加载因子为0.75，当Map中元素总数超过Entry数组的0.75，触发扩容操作.
• 并发情况下，HashMap进行put操作会引起死循环，导致CPU利用率接近100%
• HashMap是对Map接口的实现

HashTable

• HashTable的底层也是由链表+数组+红黑树实现。
• 无论key还是value都不能为null
• 它是线性安全的，使用了synchronized关键字。
• HashTable实现了Map接口和Dictionary抽象类
• Hashtable初始容量为11

ConcurrentHashMap

• ConcurrentHashMap的底层是数组+链表+红黑树
• 不能存储null键和值
• ConcurrentHashMap是线程安全的
• ConcurrentHashMap使用锁分段技术确保线性安全
• JDK8为何又放弃分段锁，是因为多个分段锁浪费内存空间，竞争同一个锁的概率非常小，分段锁反而会造成效率低。

因为foreach删除会导致快速失败问题，fori顺序遍历会导致重复元素没删除，所以正确解法如下：

第一种遍历，倒叙遍历删除

第二种，迭代器删除

数组是不能直接打印的哈，如下:

打印数组可以用流的方式Strem.of().foreach()，如下:

打印数组，最优雅的方式可以用这个APi,Arrays.toString()

• TreeMap实现了SotredMap接口，它是有序的集合。
• TreeMap底层数据结构是一个红黑树，每个key-value都作为一个红黑树的节点。
• 如果在调用TreeMap的构造函数时没有指定比较器，则根据key执行自然排序。

Hashmap的扩容：

• 第一步把数组长度变为原来的两倍，
• 第二步把旧数组的元素重新计算hash插入到新数组中。
• jdk8时，不用重新计算hash，只用看看原来的hash值新增的一位是零还是1，如果是1这个元素在新数组中的位置，是原数组的位置加原数组长度，如果是零就插入到原数组中。扩容过程第二步一个非常重要的方法是transfer方法，采用头插法，把旧数组的元素插入到新数组中。

可以看一下HashSet的add方法，元素E作为HashMap的key，我们都知道HashMap的可以是不允许重复的，哈哈。

不是线性安全的。

并发的情况下，扩容可能导致死循环问题。

• LinkedHashMap维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序（insert-order）或者是访问顺序，其中默认的迭代访问顺序就是插入顺序，即可以按插入的顺序遍历元素，这点和HashMap有很大的不同。
• LRU算法可以用LinkedHashMap实现。

线性安全的

• Vector：比Arraylist多了个同步化机制。
• Hashtable：比Hashmap多了个线程安全。
• ConcurrentHashMap:是一种高效但是线程安全的集合。
• Stack：栈，也是线程安全的，继承于Vector。

线性不安全的

• Hashmap
• Arraylist
• LinkedList
• HashSet
• TreeSet
• TreeMap

• Vector是线程安全的，ArrayList不是线程安全的。
• ArrayList在底层数组不够用时在原来的基础上扩展0.5倍，Vector是扩展1倍。
• Vector只要是关键性的操作，方法前面都加了synchronized关键字，来保证线程的安全性。

• Collection是Java集合框架中的基本接口，如List接口也是继承于它

• Collections是Java集合框架提供的一个工具类，其中包含了大量用于操作或返回集合的静态方法。如下：

这个点，主要考察HashMap和TreeMap的区别。

TreeMap实现SortMap接口，能够把它保存的记录根据键排序，默认是按key的升序排序，也可以指定排序的比较器。当用Iterator遍历TreeMap时，得到的记录是排过序的。

List 转Array，必须使用集合的 toArray(T[] array)，如下：

如果直接使用 toArray 无参方法，返回值只能是 Object[] 类，强转其他类型可能有问题，demo如下：

运行结果：

使用Arrays.asList() 把数组转换成集合时，不能使用修改集合相关的方法啦，如下：

运行结果如下：

因为 Arrays.asList不是返回java.util.ArrayList,而是一个内部类ArrayList。

可以这样使用弥补这个缺点：

方法如下：

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

使用demo如下：

• ListIterator 比 Iterator有更多的方法。
• ListIterator只能用于遍历List及其子类，Iterator可用来遍历所有集合，
• ListIterator遍历可以是逆向的，因为有previous()和hasPrevious()方法，而Iterator不可以。
• ListIterator有add()方法，可以向List添加对象，而Iterator却不能。
• ListIterator可以定位当前的索引位置，因为有nextIndex()和previousIndex()方法，而Iterator不可以。
• ListIterator可以实现对象的修改，set()方法可以实现。Iierator仅能遍历，不能修改哦。

很多朋友很可能想到用final关键字进行修饰，final修饰的这个成员变量，如果是基本数据类型，表示这个变量的值是不可改变的，如果是引用类型，则表示这个引用的地址值是不能改变的，但是这个引用所指向的对象里面的内容还是可以改变滴~验证一下，如下：

运行结果如下:

嘻嘻，那么，到底怎么确保一个集合不能被修改呢，看以下这三哥们~

• unmodifiableMap
• unmodifiableList
• unmodifiableSet

再看一下demo吧

运行结果：

在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。

运行结果：

采用安全失败机制的集合容器，在遍历时不是直接在集合内容问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

运行结果：

其实，在java.util.concurrent 并发包的集合，如 ConcurrentHashMap, CopyOnWriteArrayList等，默认为都是安全失败的。

优先队列PriorityQueue是Queue接口的实现，可以对其中元素进行排序

• 优先队列中元素默认排列顺序是升序排列
• 但对于自己定义的类来说，需要自己定义比较器

方法：

特点：

• 1.基于优先级堆
• 2.不允许null值
• 3.线程不安全
• 4.出入队时间复杂度O(log(n))
• 5.调用remove()返回堆内最小值

jdk8 放弃了分段锁而是用了Node锁，减低锁的粒度，提高性能，并使用CAS操作来确保Node的一些操作的原子性，取代了锁。

可以跟面试官聊聊悲观锁和CAS乐观锁的区别，优缺点哈~

ArrayBlockingQueue是数组实现的线程安全的有界的阻塞队列，继承自AbstractBlockingQueue,间接的实现了Queue接口和Collection接口。底层以数组的形式保存数据(实际上可看作一个循环数组)。常用的操作包括 add ,offer,put，remove,poll,take,peek。

可以结合线程池跟面试官讲一下哦~

哈哈，看源码吧，是双向链表

ArrayList扩容的本质就是计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去。

为了能让HashMap存取高效，数据分配均匀。

看着呢，以下等式相等，但是位移运算比取余效率高很多呢~

聊到ConcurrenHashMap，需要跟面试官聊到安全性，分段锁segment，为什么放弃了分段锁，与及选择CAS，其实就是都是从效率和安全性触发，嘻嘻~

ArrayList 的默认大小是 10 个元素

Collection表示一个集合，包含了一组对象元素。如何维护它的元素对象是由具体实现来决定的。因为集合的具体形式多种多样，例如list允许重复，set则不允许。而克隆（clone）和序列化（serializable）只对于具体的实体，对象有意义，你不能说去把一个接口，抽象类克隆，序列化甚至反序列化。所以具体的collection实现类是否可以克隆，是否可以序列化应该由其自身决定，而不能由其超类强行赋予。

如果collection继承了clone和serializable，那么所有的集合实现都会实现这两个接口，而如果某个实现它不需要被克隆，甚至不允许它序列化（序列化有风险），那么就与collection矛盾了。

• 函数接口不同
• Enumeration速度快，占用内存少，但是不是快速失败的，线程不安全。
• Iterator允许删除底层数据，枚举不允许
• Iterator安全性高，因为其他线程不能够修改正在被Iterator遍历的集合里面的对象。

可以用 Collections.sort（）+ Comparator.comparing（），因为对对象排序，实际上是对对象的属性排序哈~

这个跟之前那个不可变集合一样道理哈~

在作为参数传递之前，使用Collections.unmodifiableCollection(Collection c)方法创建一个只读集合，这将确保改变集合的任何操作都会抛出UnsupportedOperationException。

• 不能保证元素的排列顺序，顺序有可能发生变化。
• 元素可以为null
• hashset保证元素不重复~ （这个面试官很可能会问什么原理，这个跟HashMap有关的哦）
• HashSet，需要谈谈它俩hashcode()和equles()哦~
• 实际是基于HashMap实现的，HashSet 底层使用HashMap来保存所有元素的

看看它的add方法吧~

• 定义一个 Array 时，必须指定数组的数据类型及数组长度，即数组中存放的元素个数固定并且类型相同。
• ArrayList 是动态数组，长度动态可变，会自动扩容。不使用泛型的时候，可以添加不同类型元素。

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

因为

• 它们都是final修饰的类，不可变性，保证key的不可更改性，不会存在获取hash值不同的情况~
• 它们内部已重写了equals()、hashCode()等方法，遵守了HashMap内部的规范

重写hashCode()和equals()方法啦~ (这个答案来自互联网哈~)

重写hashCode()是因为需要计算存储数据的存储位置，需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能，这样虽然能更快但可能会导致更多的Hash碰撞；

重写equals()方法，需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x，x.equals(null)必须返回false的这几个特性，目的是为了保证key在哈希表中的唯一性；

• 每个节点或者是黑色，或者是红色。
• 根节点是黑色。
• 每个叶子节点（NIL）是黑色。[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
• 如果一个节点是红色的，则它的子节点必须是黑色的。
• 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

其实这些点，结合平时工作，代码总结讲出来，更容易吸引到面试官呢 (这个答案来自互联网哈~)

1.根据应用需要正确选择要使用的集合类型对性能非常重要，比如：假如知道元素的大小是固定的，那么选用Array类型而不是ArrayList类型更为合适。

2.有些集合类型允许指定初始容量。因此，如果我们能估计出存储的元素的数目，我们可以指定初始容量来避免重新计算hash值或者扩容等。

3.为了类型安全、可读性和健壮性等原因总是要使用泛型。同时，使用泛型还可以避免运行时的ClassCastException。

4.使用JDK提供的不变类(immutable class)作为Map的键可以避免为我们自己的类实现hashCode()和equals()方法。

5.编程的时候接口优于实现

6.底层的集合实际上是空的情况下，返回为长度是0的集合或数组而不是null。

• ArrayBlockingQueue
• LinkedBlockingQueue
• DelayQueue
• PriorityBlockingQueue
• SynchronousQueue

ArrayBlockingQueue： （有界队列）是一个用数组实现的有界阻塞队列，按FIFO排序量。

LinkedBlockingQueue： （可设置容量队列）基于链表结构的阻塞队列，按FIFO排序任务，容量可以选择进行设置，不设置的话，将是一个无边界的阻塞队列，最大长度为Integer.MAX_VALUE，吞吐量通常要高于ArrayBlockingQuene；newFixedThreadPool线程池使用了这个队列

DelayQueue：（延迟队列）是一个任务定时周期的延迟执行的队列。根据指定的执行时间从小到大排序，否则根据插入到队列的先后排序。newScheduledThreadPool线程池使用了这个队列。

PriorityBlockingQueue：（优先级队列）是具有优先级的阻塞队列；

SynchronousQueue：（同步队列）一个不存储元素的阻塞队列，每个插入操作必须等到另一个线程调用移除操作，否则插入操作一直处于阻塞状态，吞吐量通常要高于LinkedBlockingQuene，newCachedThreadPool线程池使用了这个队列。针对面试题：线程池都有哪几种工作队列？

我觉得，回答以上几种ArrayBlockingQueue，LinkedBlockingQueue，SynchronousQueue等，说出它们的特点，并结合使用到对应队列的常用线程池(如newFixedThreadPool线程池使用LinkedBlockingQueue)，进行展开阐述， 就可以啦。

• Hashset 的底层是由哈希表实现的，Treeset 底层是由红黑树实现的。
• HashSet中的元素没有顺序，TreeSet保存的元素有顺序性（实现Comparable接口）
• HashSet的add()，remove()，contains()方法的时间复杂度是O(1);TreeSet中，add()，remove()，contains()方法的时间复杂度是O(logn)

元素重复与否是使用equals()方法进行判断的，这个可以跟面试官说说==和equals()的区别，hashcode()和equals

这道面试题，跟ArrayList,LinkedList，就是换汤不换药的~

• ArrayList,使用数组方式存储数据，查询时，ArrayList是基于索引(index)的数据结构，可以直接映射到，速度较快；但是插入数据需要移动数据，效率就比LinkedList慢一点~
• LinkedList,使用双向链表实现存储,按索引数据需要进行前向或后向遍历，查询相对ArrayList慢一点；但是插入数据速度较快。
• LinkedList比ArrayList开销更大，因为LinkedList的节点除了存储数据，还需要存储引用。

互联网上这个答案太详细啦（https://www.jianshu.com/p/939b8a672070）

因为ArrayList的底层是数组实现,并且数组的默认值是10,如果插入10000条要不断的扩容,耗费时间,所以我们调用ArrayList的指定容量的构造器方法ArrayList(int size) 就可以实现不扩容,就提高了性能。

看例子吧，哈哈，这个跟对象排序也是一样的呢~

在 Java 7 中，ArrayList 的默认大小是 10 个元素，HashMap 的默认大小是16个元素（必须是2的幂）。

• Hashmap和Hashtable 都不是有序的。
• TreeMap和LinkedHashmap都是有序的。（TreeMap默认是key升序，LinkedHashmap默认是数据插入顺序）
• TreeMap是基于比较器Comparator来实现有序的。
• LinkedHashmap是基于链表来实现数据插入有序的。

Hashmap解决hash冲突，使用的是链地址法，即数组+链表的形式来解决。put执行首先判断table[i]位置，如果为空就直接插入，不为空判断和当前值是否相等，相等就覆盖，如果不相等的话，判断是否是红黑树节点，如果不是，就从table[i]位置开始遍历链表，相等覆盖，不相等插入

本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com