www.xservx.com

Java面试题集合与数组|全面解析核心考点与高频真题

从JDK8到JDK17,深度梳理集合框架与数组操作核心知识点,覆盖ArrayList、HashMap、HashSet、TreeSet、LinkedList等高频考点,结合真实面试题、源码剖析、内存模型与性能对比,助你构建系统性知识体系。

⚡ 集合与数组:Java核心数据结构基石

集合(Collection)与数组(Array)是Java中存储和操作数据的两大基础机制。集合提供动态容量、丰富API与类型安全,而数组则以高效内存布局与零开销访问著称。二者在面试中常被结合考察——例如:如何将数组转为List?如何在遍历中安全删除元素?为什么Arrays.asList返回的List不可扩容?

掌握集合框架,需理解三层结构:接口(Collection、Map)、实现类(ArrayList、HashMap)、工具类(Collections、Arrays)。JDK8引入的Stream API、默认方法与JDK9的不可变集合进一步拓展了其能力边界。本文将围绕高频考点,逐层拆解核心机制与易错点,助你突破技术面试瓶颈。

📚核心框架

Collection体系:List(有序可重复)、Set(无序不重复)、Queue(队列)

Map体系:HashMap(哈希表)、TreeMap(红黑树)、LinkedHashMap(LRU)

🔧关键能力

• 线程安全与并发安全方案(Collections.synchronizedList、CopyOnWriteArrayList)
• 扩容机制与性能权衡(初始容量、负载因子)
• 迭代器设计与fail-fast机制

💡高频场景

• 去重与排序组合操作
• 大数据量下的集合选择策略
• 内存泄漏风险规避(弱引用、软引用)

⚙️ 集合框架详解:接口、实现与源码剖析

集合框架以接口为纲,实现为目。理解各接口契约与实现类特性,是应对面试的底层逻辑。

〈ArrayList〉动态数组:线程不安全的高效选择

核心机制:底层为Object[]数组,初始容量10,扩容为1.5倍(旧容量+旧容量>>1)。扩容需调用System.arraycopy,时间复杂度O(n),但摊还后插入操作为O(1)。

public void add(E e) {
  ensureCapacityInternal(size + 1);  // 扩容检查
  elementData[size++] = e;
}
private void grow(int minCapacity) {
  int oldCapacity = elementData.length;
  int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
  elementData = Arrays.copyOf(elementData, newCapacity);
}
面试陷阱:Arrays.asList返回的List是Arrays的内部类(非ArrayList),其add/remove会抛UnsupportedOperationException,因底层数组固定。

〈LinkedList〉双向链表:频繁插入删除的利器

Node节点结构:prev + item + next。插入/删除仅需修改指针,时间复杂度O(1),但随机访问需遍历,为O(n)。JDK8后removeFirst/Last优化为O(1),但contains仍为O(n)。

private static class Node {
    E item;
    Node next;
    Node prev;
    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}
实践建议:需频繁头尾操作(如栈/队列)时,优先选LinkedList;需随机读取时,选ArrayList。

〈Vector〉历史遗留:线程安全的代价

所有方法用synchronized修饰,扩容为2倍,性能远低于ArrayList。现代开发中建议用CopyOnWriteArrayList替代。

〈HashSet〉基于HashMap的无序集合

内部维护HashMap实例,元素作为key存储(value为PRESENT常量)。添加元素时调用HashMap.put,因此要求元素重写hashCode与equals方法。

private static final Object PRESENT = new Object();
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

〈LinkedHashSet〉有序HashSet

继承HashSet,内部使用LinkedHashMap存储,保证插入顺序。

〈TreeSet〉有序集合:红黑树实现

底层为TreeMap,元素需实现Comparable接口或提供Comparator。支持范围查询(subSet、headSet、tailSet),时间复杂度O(log n)。

注意:TreeSet不允许null元素(会抛NullPointerException),因需比较大小。

〈HashMap〉哈希表:JDK8的重大升级

JDK7:数组+链表
JDK8:数组+链表/红黑树(链表≥8且数组≥64时转红黑树)

关键参数:

  • 初始容量:16(2的幂)
  • 负载因子:0.75(空间与时间平衡点)
  • 树化阈值:8
  • 退化阈值:6
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

putVal核心逻辑:

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
else {
    Node e; K k;
    if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
    else if (p instanceof TreeNode)
        e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
    else {
        for (int binCount = 0; ; ++binCount) {
            if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);
                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    treeifyBin(tab, hash);
                break;
            }
            if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            p = e;
        }
    }
}
面试高频:为什么容量是2的幂?→ 便于位运算计算索引:(n - 1) & hash,避免取模运算。

〈ConcurrentHashMap〉线程安全的HashMap

JDK7:Segment分段锁(数组+HashEntry)
JDK8:CAS+synchronized(Node数组+链表/红黑树)

核心改进:取消Segment,锁粒度细化到桶级别,且仅在hash冲突时加synchronized,大幅提升并发性能。

〈LinkedList〉双端队列:Queue与Deque的实现

支持FIFO队列操作(offer/poll)与LIFO栈操作(push/pop)。

〈PriorityQueue〉堆结构:优先级队列

底层为Object[]数组实现的最小堆,元素需实现Comparable或提供Comparator。插入/删除为O(log n),但peek为O(1)。

public boolean offer(E e) {
    if (e == null) throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}

〔数组〕静态容器:零开销访问的底层基石

数组是Java中效率最高的数据结构,但容量固定。掌握其初始化、拷贝、排序技巧是基础能力。

初始化方式对比

方式 示例 特点
声明+赋值 int[] arr = {1,2,3}; 编译时确定,不可变
new指定长度 int[] arr = new int[5]; 默认值:int为0,对象为null
new动态初始化 int[] arr = new int[]{1,2,3}; 运行时创建,灵活
注意:声明时不能指定长度(如int[5] arr),否则编译错误。

数组拷贝:三种方式性能对比

方法 时间复杂度 是否支持类型转换 适用场景
System.arraycopy O(n) ✓(源/目标类型可不同) 高性能场景首选
Arrays.copyOf O(n) ✗(返回新数组) 扩容/截断操作
for循环 O(n) ✗ 复杂逻辑拷贝
// System.arraycopy: native方法,直接内存拷贝
System.arraycopy(src, srcPos, dest, destPos, length);
// Arrays.copyOf:内部调用System.arraycopy
int[] copy = Arrays.copyOf(original, newLength);

排序:Arrays.sort的双引擎机制

JDK7+:Dual-Pivot Quicksort(双轴快排),平均O(n log n),比传统快排快10-20%

JDK8+:对象排序使用TimSort(归并+插入),稳定排序;基本类型仍用Dual-Pivot Quicksort

int[] arr = {5,2,8,1,9};
Arrays.sort(arr); // 原地排序
// 自定义排序(降序)
Integer[] arr2 = {5,2,8,1,9};
Arrays.sort(arr2, Collections.reverseOrder());
陷阱:对象数组需实现Comparable,否则抛ClassCastException。

多维数组:不规则数组的灵活应用

Java多维数组本质是“数组的数组”,可不等长:

int[][] arr = new int[3][]; // 3行,每行列数可不同
arr[0] = new int[2];
arr[1] = new int[5];
arr[2] = new int[1];
// 初始化示例
int[][] matrix = {
    {1,2,3},
    {4,5},
    {6}
};
实用技巧:遍历时用增强for循环更简洁,但需注意空指针风险。

↔️ 集合 vs 数组:核心差异与选择策略

二者在容量、类型、性能、API上的差异决定其适用场景。

核心差异对比表

维度 数组 集合(List)
容量 固定 动态增长
类型 基本类型/对象 仅对象(需包装类)
内存占用 低(无额外对象开销) 高(对象头+引用)
随机访问 O(1) ArrayList: O(1)
LinkedList: O(n)
插入/删除 O(n)(需移动) ArrayList: O(n)
LinkedList: O(1)
API丰富度 基础操作 丰富(流、排序、过滤)

选择策略指南

  • ✓ 数据量固定且需高频随机读取 → 数组
  • ✓ 需动态增删且元素为对象 → ArrayList
  • ✓ 需频繁头尾插入/删除 → LinkedList
  • ✓ 需去重且无序 → HashSet
  • ✓ 需排序且有序 → TreeSet
  • ✓ 需键值对映射 → HashMap
最佳实践:数组与集合常配合使用——如集合转数组(toArray)、数组转集合(Arrays.asList),但需注意转换后的集合是否可修改。

⚡ 性能优化:高频场景下的容量与算法权衡

合理预估容量、选择数据结构,可显著提升性能。

容量预估:避免频繁扩容

HashMap默认负载因子0.75,若预知元素数量为N,建议初始容量设为:
capacity = (int)(N / 0.75f) + 1

// 示例:预存100个元素
Map map = new HashMap<>((int)(100 / 0.75f) + 1);

内存优化技巧

  • ✓ 使用Arrays.asList转List时,避免后续修改操作
  • ✓ 大数据量下用IntStream.range替代循环创建Integer对象
  • ✓ 优先用基本类型数组而非包装类集合(如int[] vs List<Integer>)

并发场景性能对比

集合类型
ArrayList 线程不安全,单线程高性能
Vector 线程安全,但性能差(全方法同步)
CopyOnWriteArrayList 读写分离,适合读多写少场景
ConcurrentHashMap 高并发键值对存储,JDK8性能接近HashMap
性能测试工具:用JMH(Java Microbenchmark Harness)进行精确微基准测试,避免JIT、GC等干扰。

📝 真题实战:高频面试题与解题思路

精选10道典型题目,覆盖核心知识点与易错点。

题1:ArrayList与LinkedList选择依据

考点:数据结构特性与时间复杂度
答案:若需频繁随机访问(如get(index)),选ArrayList;若需频繁插入/删除(尤其中间位置),选LinkedList。但注意:LinkedList的插入删除需先定位节点(O(n)),仅头尾操作为O(1)。

题2:HashMap扩容机制详解

考点:源码理解与扩容陷阱
答案:JDK8中,当链表长度≥8且数组容量≥64时转红黑树;否则仅扩容。扩容时需rehash,因容量变化导致索引计算方式改变。注意:HashMap非线程安全,扩容时可能形成环形链表(JDK7),JDK8已修复此问题。

题3:如何安全遍历并删除元素?

考点:fail-fast机制与迭代器使用
错误示例:

for (String s : list) {
    if (s.equals("a")) list.remove(s); // 抛ConcurrentModificationException
}

正确做法:

// 方式1:使用Iterator
Iterator it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("a")) it.remove();
}
// 方式2:倒序遍历(仅限ArrayList)
for (int i = list.size()-1; i >=0; i--) {
    if (list.get(i).equals("a")) list.remove(i);
}

题4:TreeSet去重与排序原理

考点:比较器与红黑树
答案:TreeSet通过元素的compareTo或Comparator决定顺序。若元素未实现Comparable且未提供Comparator,会抛ClassCastException。注意:equals相同但compareTo返回非0的元素会被视为不同元素(违反Set契约)。

题5:Arrays.asList的常见陷阱

考点:集合与数组转换
陷阱:

int[] arr = {1,2,3};
List list = Arrays.asList(arr);
System.out.println(list.size()); // 输出1!因arr是int[]对象,非int元素

正确做法:使用包装类数组或Stream

Integer[] arr = {1,2,3};
List list = Arrays.asList(arr); // size=3
// 或使用Stream
List list = Arrays.stream(arr).boxed().collect(Collectors.toList());

题6:HashMap的key为何推荐不可变对象?

考点:hashCode稳定性
答案:若key的hashCode在存入后改变(如String修改),会导致无法通过原key定位到value。String、Integer等不可变类天然满足此要求。

题7:CopyOnWriteArrayList的适用场景

考点:读写分离策略
答案:适用于读操作远多于写操作的场景(如配置列表)。写时复制整个数组,保证读无锁,但写开销大(O(n))。内存占用高,不适合大数据量。

题8:如何反转数组?

考点:数组操作技巧
解法:

public static void reverse(int[] arr) {
    for (int i = 0; i < arr.length/2; i++) {
        int temp = arr[i];
        arr[i] = arr[arr.length-1-i];
        arr[arr.length-1-i] = temp;
    }
}

题9:TreeMap与HashMap性能对比

考点:时间复杂度权衡
答案:

操作 HashMap TreeMap
put/get O(1)平均 O(log n)
遍历(有序) O(n) O(n)(中序遍历)
范围查询 需全遍历 O(log n + k)(k为结果数)

题10:如何判断数组有重复元素?

考点:空间换时间策略
解法1:排序后遍历(O(n log n))

Arrays.sort(arr);
for (int i = 1; i < arr.length; i++)
    if (arr[i] == arr[i-1]) return true;

解法2:HashSet(O(n))

Set set = new HashSet<>();
for (int num : arr) {
    if (!set.add(num)) return true;
}

▲ 进阶主题:内存模型与并发安全

深入JVM层面,理解集合与数组的内存布局与线程安全机制。

堆内存中的对象布局

数组在堆中以连续内存块存储,对象数组的每个元素为引用(4/8字节)。HashMap的Node节点分散存储,通过哈希值定位桶位置。

内存示例:int[10]占用44字节(16对象头+40数据+4填充),而Integer[10]占用约80字节(16对象头+10*8引用+10*16Integer对象)。

线程安全机制对比

机制 原理 适用场景
synchronized 悲观锁,独占资源 写多读少
CAS 乐观锁,无锁竞争 低冲突场景
读写锁 读共享,写独占 读多写少
CopyOnWrite 写时复制 读极多、写极少

弱引用与内存泄漏

ThreadLocal、WeakHashMap等依赖弱引用避免内存泄漏。例如:WeakHashMap的key为弱引用,当key不再被强引用时,条目自动被GC回收。

WeakHashMap map = new WeakHashMap<>();
String key = new String("test");
map.put(key, new Object());
key = null; // 移除强引用
System.gc(); // 下次GC时条目被清除

❓ 常见问题FAQ:高频误区澄清

整理开发者最常困惑的10个问题,给出权威解答。

Q1:为什么HashMap的容量必须是2的幂?

A:(n-1) & hash 可替代取模运算,提升性能。若容量非2的幂,哈希分布不均,冲突率上升。

Q2:ArrayList和Vector哪个更快?

A:ArrayList远快于Vector。Vector的synchronized方法带来巨大性能损耗,且无实际必要(单线程场景)。

Q3:TreeSet能否存储null?

A:不能。TreeSet需比较元素大小,null无法比较,会抛NullPointerException。

Q4:Arrays.asList返回的List能扩容吗?

A:不能。它是Arrays的内部类,底层是固定数组,add/remove会抛UnsupportedOperationException。

Q5:如何高效拼接字符串?

A:频繁拼接用StringBuilder(单线程)或StringBuffer(多线程),避免用+号(每次创建新对象)。

Q6:ConcurrentHashMap的get需要加锁吗?

A:不需要。JDK8中,get操作通过volatile语义保证可见性,结合CAS保证原子性。

Q7:LinkedList的get(index)复杂度?

A:O(n)。需从头/尾遍历到指定位置,JDK8通过index < size/2判断从哪端遍历。

Q8:Arrays.sort对对象数组用什么算法?

A:TimSort(归并+插入),稳定排序;基本类型用Dual-Pivot Quicksort(不稳定)。

Q9:HashSet如何保证元素唯一?

A:通过HashMap的key唯一性实现。添加元素时,若hashCode相同且equals返回true,则视为重复。

Q10:数组转List后修改原数组会影响List吗?

A:会!Arrays.asList返回的List与原数组共享数据。修改数组元素,List中对应值同步变化。