【Java八股文】02-Java集合面试篇

---

概念

数组与集合区别

• 数组是定长的，集合是动态的
• 数组是可以包含基本数据类型和对象的，而集合只能包含对象
• 数组是可以直接通过下标进行访问元素的，而集合需要通过迭代器等进行访问。

常用集合

• ArrayList：动态数组，add(E e)

• LinkedList：双向链表，add(E e)

• HashMap：哈希map，put(K, V)

• HashSet：哈希set，add(E e)

• ArrayDeque：双向队列

  • 栈：使用 push() 入栈，pop() 出栈，peek() 查看栈顶
  • 队列：使用 offer() 入队尾，poll() 出队头，offerFirst 入队头，pollLast 出队尾

Java中的线程安全的集合是什么？

常用的：

• CopyOnWriteArrayList：读操作无锁，写操作复制新数组，适用于读多写少的场景，如配置管理、黑名单等。写代价高，add每次都会创建新数组。

• ConcurrentHashMap：与 HashTable (也是线程安全的，表级别锁)的主要区别是二者加锁粒度的不同，支持行锁，适合高并发读写。

• ConcurrentLinkedQueue：基于 CAS（无锁队列），高效且支持高并发。适用于生产者-消费者模型（如任务队列）。

Collections和Collection的区别

特点	Collection	Collections
类型	接口	工具类（类）
功能	定义集合的基本操作，如添加、删除、查询等	提供静态方法来操作集合，如排序、查找、同步等
用法	用作集合的父接口，具体集合类实现该接口	用于对集合进行操作，不能实例化

List

java中list的几种实现

• 线程不安全：
  • ArrayList：基于动态数据实现，支持随机访问，初始容量为10，满了会扩容是扩容50%
  • LinkedList：基于双向链表实现，不需要初始容量
• 线程安全：
  • Vector：基于动态数组实现，加上了synchronized关键字，初始容量为10，满了会扩容是扩容1倍。
  • CopyOnWriteArrayList：读操作无锁，写操作复制新数组，适用于读多写少的场景。

把ArrayList变成线程安全的有哪些方法？

• 使用Collections.synchronizedXxx()（包装同步集合），该方法对普通集合进行同步包装，使其线程安全，但在迭代时仍需手动同步。该方法只对集合的操作进行保护，并为队迭代操作及逆行自动加锁，所以迭代荣然需要显式的同步。

  List<String> list = Collections.synchronizedList(new ArrayList<>());
  synchronized (list) { //多线程访问for (String s : list) {System.out.println(s);}
  }
  

• 使用CopyOnWriteArrayList或Vector类代替ArrayList

CopyOnWriteArrayList是如何保证线程安全的？

• 读操作没有锁，因为在每次写操作前都会生成一个快照，读操作读的都是快照。
• 写操作，使用volatile关键字修饰数组，保证顺序和可见性，并且每次写入时都加锁并且会复制整个数组，并将修改后的新数组设置为当前数组。

Map

java中常见map

• 线程不安全：
  • HashMap：基于数组+链表+红黑树实现，支持随机访问，初始容量为16，扩容因子0.75，达到额定容量75%会进行，扩容是扩容一倍。
• 线程安全：
  • HashTable：实现方式与HashMap类似，但是在方法上加上synchronized保证线程安全，同一时刻只能有一个线程访问HashTable的方法，但是锁是表级锁。
  • ConcurrentHashMap：通过分段锁和 CAS 实现细粒度锁，适合高并发环境。

HashMap实现原理介绍一下？

在JDK8之前的HashMap实现中，HashMap使用哈希算法将键（key）映射到数组中的索引位置。如果两个或多个键的哈希值相同，即发生了哈希冲突，HashMap会通过链表解决冲突：将新加入的元素以链表的形式存储在对应的索引位置，成为该位置的链表头节点（链表的第一个元素）。

JDK8之后，如果链表长度超过8就转为红黑树保存，小于6时原转为链表。

解决Hash冲突的办法

• 链表法
• 开放地址：在数组内找个新的地方放：线性探测（+1）、二次探测（+1²⁺²2+3^2）、双重哈希（使用第二个哈希函数）
• 再哈希：当负载因子超过某个阈值重新计算哈希表的大小。

hashmap key可以为null吗？

可以为null，如果为null，那其哈希值直接为0。

重写HashMap的equal和hashcode方法需要注意什么？

• equals() 和 hashCode() 必须保持一致性：相等的对象 equals() 返回 true，则它们的 hashCode() 必须相同。

• 实现 hashCode() 时要确保散列值均匀，避免大量冲突。

ConcurrentHashMap用了悲观锁还是乐观锁?

首先CAS是乐观锁，synchronized 是悲观锁。

• 乐观锁的基本思想是：假设多个线程不会发生冲突，因此在操作数据时，不会立即加锁，而是先进行尝试。如果出现冲突，才进行修正。CAS 是一种硬件支持的机制（通过 CPU 指令实现），它通过比较内存中的值与预期值是否相等，如果相等，就更新值，否则就不做任何操作，返回失败。它是无锁的，因此不会像传统的锁那样造成线程阻塞。

• 悲观锁的基本思想是：假设多个线程一定会发生冲突，因此在访问共享资源时会采取 加锁 的方式，保证同一时刻只有一个线程可以访问该资源。

ConcurrentHashMap 是一种高效的线程安全的 Map实现，它结合了乐观锁和悲观锁的思想，但总体上可以认为它采用的是分段锁（Segment Lock）和乐观锁结合的方式。具体来说，它在不同的操作中使用了不同的锁策略，来优化并发性能。

• JDK8之前是分段锁+synchronized悲观锁。

• JDK8之后ConcurrentHashMap 改进了实现，采用了CAS（乐观锁）与轻量级锁相结合的方式：

  • 读操作不加锁：对于 get 操作，它不加锁，采用乐观锁（通过 CAS）来保证线程安全。
  • 写操作会使用 CAS 尝试更新数据。如果没有发生冲突，CAS 会直接更新值，不需要加锁，这也是一种乐观锁。如果 CAS 失败（即发生竞争），ConcurrentHashMap 会采用 悲观锁（例如使用 ReentrantLock）来保护更新操作，以保证线程安全。这是因为在竞争激烈的情况下，使用悲观锁能够确保写操作的正确性，避免数据不一致。
  • 扩容是会用悲观锁来同步该过程。

Set

map和set插入时都是先用hashCode来判断位置，set使用equals来判断set中集合是否存在值相同的元素，如果存在则不会插入。

有序的set

• TreeSet是基于红黑树实现
• LinkedHashSet是基于双重链表和哈希表的结合来实现元素的有序存储