当前位置：首页 > news >正文

Java高频面试题2：集合框架

news 来源：原创 2025/9/8 21:05:59

一、集合框架概述

1. 常见的集合框架有哪些？

Collection：存储单个元素的集合。
- List（有序、可重复）：ArrayList（动态数组）、LinkedList（双向链表）。
- Set（无序、唯一）：HashSet（基于HashMap）、TreeSet（红黑树）。
- Queue（队列）：ArrayDeque（双端队列）、PriorityQueue（优先级队列）。
Map：存储键值对。
- HashMap（数组+链表/红黑树）、LinkedHashMap（保持插入顺序）、TreeMap（红黑树，按Key排序）。

二、List

2. ArrayList和LinkedList的区别？

特性	ArrayList	LinkedList
数据结构	动态数组	双向链表
增删效率	尾部O(1)，中间O(n)	头尾O(1)，中间O(n)
查找效率	随机访问O(1)	顺序访问O(n)
内存占用	连续内存，紧凑	非连续内存，每个节点含前驱/后继指针
线程安全	非线程安全	非线程安全

3. ArrayList的扩容机制？

初始容量：默认16。
扩容触发：当元素个数超过当前容量的loadFactor（默认0.75）时。
扩容逻辑：新容量为原容量的1.5倍，通过Arrays.copyOf()复制旧数组到新数组。

4. 如何实现ArrayList的线程安全？

使⽤ Ve c t o r ：不推荐， Ve c t o r 是⼀个历史遗留类。
使用Collections.synchronizedList()：通过synchronized关键字保证线程安全。
使用CopyOnWriteArrayList：写时复制，读操作无锁，适合读多写少场景。
在使⽤ A r r a y L i s t 时，应⽤程序通过同步机制去控制 A r r a y L i s t 的读写。

三、Map

5. HashMap的底层数据结构？

JDK7：数组+链表。
JDK8：数组+链表/红黑树（链表长度≥8且数组长度≥64时转换为红黑树）。

6. HashMap的`put`流程？

计算哈希值：通过hash(key)方法（hashCode()异或高16位）。
确定桶位置：(n-1) & hash（n为数组长度）。
处理冲突：
- 若桶为空，直接插入。
- 若桶不为空，遍历链表/红黑树：
  - 若Key存在，覆盖Value。
  - 若Key不存在，链表尾插（JDK8），红黑树插入。
扩容检查：若元素个数超过阈值（capacity * loadFactor），触发扩容（2倍）。

7. HashMap的哈希函数设计？

扰动函数：(h = key.hashCode()) ^ (h >>> 16)，混合高低位信息，减少哈希冲突。
数组长度：必须为2的幂，保证(n-1) & hash均匀分布。

8. 为什么链表转红黑树的阈值是8？

泊松分布：链表长度超过8的概率极低（约0.00000006），树化是为极端情况优化。
空间权衡：红黑树节点占用更多内存，避免频繁转换。

9. JDK8对HashMap的优化？

红黑树：链表过长时转换为红黑树，提升查询效率。
尾插法：避免JDK7头插法导致的扩容死循环。
扩容优化：节点位置仅可能是原位置或原位置+旧容量，减少重新计算哈希的开销。

10. HashMap的线程安全问题及解决方案？

问题：多线程下扩容可能导致死循环、数据覆盖或丢失。
解决方案：
- Hashtable：方法级synchronized，性能差。
- ConcurrentHashMap：JDK7分段锁，JDK8 CAS+synchronized，高并发场景首选。
- Collections.synchronizedMap：同步包装器，适合低并发。

11. LinkedHashMap如何保持有序？

双向链表：维护插入顺序或访问顺序（通过accessOrder参数）。
实现LRU缓存：重写removeEldestEntry方法。

12. TreeMap如何实现有序？

红黑树：基于Key的自然排序（实现Comparable）或自定义Comparator。
范围查询：支持subMap、headMap等方法。

13.为什么HashMap的容量是2的幂次方？

保证通过位运算(n-1)&hash高效计算索引，避免哈希冲突。
扩容时只需检查高位，减少重新哈希的开销。

14.ConcurrentHashMap与Hashtable的区别？

锁粒度：在 JDK 1.7 中，采用分段锁（Segment）机制，将数据分成多个段，每个段独立加锁。在 JDK 1.8 中，进一步优化为使用 CAS（Compare-And-Swap）和 synchronized 锁单个桶（bucket），减少了锁的粒度。Hashtable全表锁。
性能：ConcurrentHashMap吞吐量更高。
空键值：Hashtable不允许null键值，ConcurrentHashMap允许。

四、Set

15. HashSet的底层实现？

基于HashMap：值为固定对象PRESENT，利用HashMap的Key唯一性。
去重逻辑：依赖hashCode()和equals()方法。

五、其他高频问题

16. 快速失败（Fail-Fast）与安全失败（Fail-Safe）？

快速失败：遍历时若集合被修改（非预期），抛出ConcurrentModificationException（如ArrayList）。
安全失败：遍历拷贝的集合副本，不反映原集合的修改（如CopyOnWriteArrayList）。

17. 如何选择集合类？

需要随机访问：选ArrayList。
频繁增删：选LinkedList。
键值对存储：
- 无序：HashMap。
- 插入顺序：LinkedHashMap。
- 排序：TreeMap。
线程安全：ConcurrentHashMap或CopyOnWriteArrayList。

六、代码实战

18. 手写简易HashMap（数组+链表版）？

public class SimpleHashMap<K, V> {private static final int DEFAULT_CAPACITY = 16;private Node<K, V>[] table;private int size;static class Node<K, V> {K key;V value;Node<K, V> next;Node(K key, V value) {this.key = key;this.value = value;}}public void put(K key, V value) {int index = hash(key) & (DEFAULT_CAPACITY - 1);Node<K, V> node = table[index];if (node == null) {table[index] = new Node<>(key, value);size++;} else {while (node != null) {if (node.key.equals(key)) {node.value = value;return;}if (node.next == null) {node.next = new Node<>(key, value);size++;return;}node = node.next;}}}public V get(K key) {int index = hash(key) & (DEFAULT_CAPACITY - 1);Node<K, V> node = table[index];while (node != null) {if (node.key.equals(key)) return node.value;node = node.next;}return null;}private int hash(K key) {int h = key.hashCode();return h ^ (h >>> 16);}
}

19. `LinkedHashMap` 实现 LRU（Least Recently Used，最近最少使用）缓存

import java.util.LinkedHashMap;
import java.util.Map;public class LRUCache<K, V> extends LinkedHashMap<K, V> {private final int capacity;public LRUCache(int capacity) {// 调用父类构造函数，设置初始容量、负载因子和访问顺序super(capacity, 0.75f, true) {@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {// 当缓存大小超过容量时，移除最旧的元素return size() > capacity;}};this.capacity = capacity;}public static void main(String[] args) {LRUCache<Integer, String> cache = new LRUCache<>(3);cache.put(1, "one");cache.put(2, "two");cache.put(3, "three");System.out.println(cache.get(1)); cache.put(4, "four"); System.out.println(cache.get(2)); }
}

此代码定义了一个 LRUCache 类，它继承自 LinkedHashMap。在构造函数里，借助 LinkedHashMap 的特性，把访问顺序设为 true，这意味着访问元素时会将其移到链表尾部。同时，重写了 removeEldestEntry 方法，当缓存大小超出容量时，就会移除最旧的元素。在 main 方法里，对 LRUCache 的功能进行了简单测试。

总结：以上题目覆盖Java集合框架核心知识点，建议重点掌握HashMap的底层实现、扩容机制、线程安全方案以及List/Set的特性对比。面试时需结合源码和实际场景说明设计原理，体现对细节的理解。