面试喵

主题

Java 集合框架 已完结 ​

集合概要 ​

常用的集合类及其区别？ ​

集合分为 Collection 容器 和 Map 映射表两种

常见的为：

  • List 顺序表
  • Set：不重复的集合
  • Queue：队列
  • Map：存储键值对

哪些集合类是线程安全的？ ​

Vector、HashTable、Stack 都是线程安全的，其他的是非线程安全的。

在 concurrent 并发包中（java.util.concurrent）有着对应的线程安全类，比如 HashMap 有着对应的 ConcurrentHashMap。

什么是 fail-fast，什么是 fail-safe ​

提示

fail-fast 快速失败：并发修改异常。

fail-safe 失败安全：允许并发修改，遍历前会先复制副本。

  • fail-fast 是快速失败。java.util 包下的集合类都是快速失败机制的。在遍历集合时修改集合，会导致并发修改异常。
  • fail-safe 是失败安全。采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容。java.util.concurrent 包下的容器都是安全失败的。

Collection 和 Collections 的区别 ​

  1. Collection 是集合的一个接口，定义了基本的集合操作。
  2. Collections 是一个工具类，提供了很多静态方法来操作集合。

List、Map、Set 的区别 ​

什么是迭代器 Iterator ​

迭代器是一个用来遍历集合中的元素的对象。

  • 在 fail-fast 机制下，迭代过程中移除元素会抛出异常
  • 在 fail-safe 机制下，允许移除元素并且不会抛出异常

List ​

ArrayList 和 Array 的区别 ​

提示

容量、扩容、API、存储类型

  1. ArrayList 是动态数组，没有长度限制，不需要事先定义长度；Array 是静态数组，需要提前定义数组的长度
  2. ArrayList 可以动态扩容；静态数组不能修改
  3. ArrayList 提供操作 API ，操作方便
  4. ArrayList 只能存储对象，Array 可以存储对象和基本类型

ArrayList 和 Vector 的区别 ​

提示

线程安全、性能、扩容

  1. 线程安全：ArrayList 是线程不安全的，Vector 使用了 Synchronized，是线程安全的。
  2. 性能：ArrayList 强于 Vector
  3. 扩容：ArrayList 每次会增加一半，Vector 会增加一倍

ArrayList 和 LinkedList 的区别 ​

提示

底层数据结构、性能、空间

  1. 数据结构：ArrayList 使用数组，LinkedList 使用双向链表
  2. 性能：ArrayList 对于查询性能高，LinkedList 插入删除性能高
  3. 空间：ArrayList 会存在预留位置，LinkedList 数据需要携带前驱后继。

说一说 ArrayList 的扩容机制 ​

  1. ArrayList 创建时大小为 0，第一次添加元素会使用默认大小 10
  2. 当 ArrayList 存满仍需添加时，会扩容到 1.5 倍，之后拷贝数组

数组和 List 之间的转换 ​

  1. 数组转List：Arrays.asList()
  2. List 转数组：List 自带的 toList() 方法

Array.asList 方法的返回的 ArrayList 不是常见的 ArrayList，没有 add、remove 等操作。

解决方法：使用 new ArrayList() 包裹。

Map ​

说一下 HashMap 的工作原理 ​

HashMap 基于哈希表，将键的哈希值映射到数组的索引。通过链表和红黑树解决哈希冲突。

说一下 HashMap 的 put 的流程 ​

  1. 判断 Table 是否为空，为空则扩容为默认大小 16
  2. 通过 hashCode 获取哈希值计算并 Table 索引，插入到链表或红黑树中
  3. 如果容量达到 64 且链表长度大于 8 时会转换为红黑树（当长度减少到 6 及以下时，红黑树会转换回链表）
  4. 如果现有元素个数大于 (容量 * 扩容因子0.75) 会进行扩容，扩容一倍。

HashMap 的长度为什么时 2 的幂次方 ​

哈希表使用哈希值取模运算来确定元素存储的位置，当 HashMap 长度是 2 的幂次方时，取模操作能转化为位运算，提高操作效率。

并且扩容时，不需要重新计算 hashCode，只需要查看最高位为 1 还是 0。

HashMap 多线程操作导致死循环问题 ​

JDK 1.7 之前的 HashMap 在两个线程同时进行扩容时，由于头插法会导致链表顺序改变，从而形成环形链表，无法查询。

JDK 1.8 修复了这个问题，使用尾插法。仍会造成并发问题，比如值被覆盖等。

多线程操作时应该使用 ConcurrentHashMap。

HashMap 和 HashTable 有什么区别 ​

  1. 线程安全：HashMap 是线程不安全的，HashTable 线程安全
  2. 效率：HashMap 效率比 HashTable 高
  3. 扩容和大小：HashMap 默认 16，扩容到 2 倍；HashTable 默认 12，扩容到 2倍 + 1

LinkedHashMap 是什么？怎么实现的 ​

在 HashMap 的基础上维护一个双向链表，记录插入顺序

为什么 ConcurrentHashMap 比 HashTable 效率要高？ ​

提示

分段锁、分段哈希、读操作不需要锁

  1. ConcurrentHashMap 底层使用了分段 Table，使用分段锁；HashTable 使用全局锁
  2. HashTable 所有方法都获取锁，ConcurrentHashMap 在读操作时不需要获取锁
  3. HashTable 扩容时需要全局哈希，ConcurrentHashMap 可以分段逐步扩容

Set ​

Comparable 和 Comparator 的区别 ​

Comparable 接口和 Comparator 接口都是用于排序的接口。

  • Comparable 内部排序器：类实现接口，实现 compareTo 方法，可实现排序。
  • Comparator 外部排序器：定义单独的实现类，实现 compare 方法，在排序时传入。

HashSet 的实现原理 ​

底层使用 HashMap 实现。集合元素作为 key 保存，value 为静态 Object 对象。

比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同 ​

相同点：

  • 保证元素唯一，线程不安全

不同点：

  • 数据结构：

    • HashSet 是哈希表 + 链表 + 红黑树
    • LinkedHashSet 是双向链表 + 哈希表
    • TreeSet 是红黑树

  • 有序性：HashSet 无序；LinkedHashSet 插入顺序；TreeSet 自定义排序。

Queue ​

Queue 和 Deque 的区别 ​

Queue 是队列，只能先进先出

Deque 是双向队列，两个方向都能添加或删除元素

在 Queue 中 poll 和 remove 有什么区别 ​

  1. 相同点：都是返回第一个元素，并删除。
  2. 差异：如果没有元素，poll 会返回 null，remove 会抛异常。

ArrayDeque 和 LinkedList 的区别 ​

ArrayDeque 和 LinkedList 都实现了 Deque 接口，具有队列的功能。

  1. ArrayDeque 维护了一个环形数组和首尾指针，LinkedList 基于双向链表实现。
  2. ArrayDeque 插入可能需要扩容；LinkedList 插入需要申请新空间，性能较差
  3. ArrayDeque 不支持存储 NULL，LinkedList 支持。

说一说 PriorityQueue ​

PriorityQueue 是优先队列，每次取出的元素都是队列中优先度最大的。

  1. 基于二叉堆结构来实现，使用可变长数组来存储数据。
  2. 通过堆元素的上浮和下沉，实现 O(logn) 复杂度内插入和删除队顶元素。
  3. 非线程安全。
  4. 默认是小顶堆，可以通过传入 Comparator 作为构造参数定义优先级。

Released under the MIT License.

code by wmh