Java集合框架面试题详解

引言

Java集合框架是Java编程中最常用的工具类库之一，也是面试中的高频考点。本文将系统地梳理Java集合框架的核心知识点和常见面试题，帮助你深入理解集合框架的底层原理。

一、集合框架概述

1.1 集合框架的层次结构

Collection
├── List (有序，可重复)
│   ├── ArrayList
│   ├── LinkedList
│   └── Vector
├── Set (无序，不可重复)
│   ├── HashSet
│   ├── LinkedHashSet
│   └── TreeSet
└── Queue (队列)
    ├── LinkedList
    └── PriorityQueue

Map (键值对)
├── HashMap
├── LinkedHashMap
├── TreeMap
└── Hashtable

1.2 核心接口说明

• Collection：所有单列集合的根接口
• List：有序、可重复的集合
• Set：无序、不可重复的集合
• Map：键值对映射，key不可重复

二、ArrayList相关面试题

2.1 ArrayList的底层实现原理

答案：

ArrayList底层基于动态数组实现：

public class ArrayList<E> extends AbstractList<E> {
    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 10;
    
    // 存储元素的数组
    transient Object[] elementData;
    
    // 实际元素个数
    private int size;
}

关键特点：

1. 底层是Object数组
2. 默认初始容量为10
3. 支持动态扩容
4. 查询快（O(1)），插入删除慢（O(n)）

2.2 ArrayList的扩容机制

扩容流程：

public boolean add(E e) {
    // 1. 确保容量足够
    ensureCapacityInternal(size + 1);
    // 2. 添加元素
    elementData[size++] = e;
    return true;
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 新容量 = 旧容量 * 1.5
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    if (newCapacity < minCapacity)
        newCapacity = minCapacity;
    
    // 创建新数组并复制
    elementData = Arrays.copyOf(elementData, newCapacity);
}

扩容机制总结：

• 每次扩容为原来的1.5倍
• 使用位运算提高效率：oldCapacity >> 1 相当于除以2
• 扩容需要复制数组，成本较高

2.3 ArrayList与LinkedList的区别

特性	ArrayList	LinkedList
底层结构	动态数组	双向链表
随机访问	O(1)	O(n)
插入删除（头部）	O(n)	O(1)
插入删除（尾部）	O(1)	O(1)
内存占用	连续内存	非连续，额外指针开销
适用场景	查询多	插入删除多

代码示例：

// ArrayList：适合随机访问
List<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
String item = arrayList.get(0); // O(1) 快速访问

// LinkedList：适合频繁插入删除
List<String> linkedList = new LinkedList<>();
linkedList.add(0, "New"); // 在头部插入，O(1)
linkedList.remove(0);      // 删除头部，O(1)

三、HashMap相关面试题

3.1 HashMap的底层实现原理

答案：

HashMap在JDK 1.8中采用数组+链表+红黑树结构：

public class HashMap<K,V> {
    // 哈希表数组
    transient Node<K,V>[] table;
    
    // 节点定义
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    }
    
    // 默认初始容量（必须是2的幂）
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    
    // 默认负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    // 链表转红黑树阈值
    static final int TREEIFY_THRESHOLD = 8;
}

核心机制：

1. 计算key的hash值
2. 通过hash值定位到数组索引
3. 如果发生冲突，采用链地址法（链表或红黑树）

3.2 HashMap的put流程

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 1. 如果table为空，进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // 2. 计算索引位置，如果该位置为空，直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        
        // 3. 如果key已存在，替换value
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        
        // 4. 如果是红黑树节点，使用树的插入方法
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        
        // 5. 链表处理
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 链表长度超过8，转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 6. 替换旧值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            return oldValue;
        }
    }
    
    // 7. 检查是否需要扩容
    if (++size > threshold)
        resize();
    
    return null;
}

3.3 HashMap为什么线程不安全？

主要问题：

1. 数据覆盖：多线程同时put时可能覆盖数据
2. 扩容死循环（JDK 1.7）：并发扩容时可能形成环形链表
3. size不准确：并发修改size变量

示例代码：

// 线程不安全示例
HashMap<String, Integer> map = new HashMap<>();

// 两个线程同时执行
Thread t1 = new Thread(() -> {
    for (int i = 0; i < 1000; i++) {
        map.put("key" + i, i);
    }
});

Thread t2 = new Thread(() -> {
    for (int i = 0; i < 1000; i++) {
        map.put("key" + i, i);
    }
});

t1.start();
t2.start();
// 可能导致数据丢失或死循环

解决方案：

• 使用ConcurrentHashMap
• 使用Collections.synchronizedMap()
• 外部加锁

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

原因：

1. 高效的取模运算

// 传统取模
int index = hash % length;

// 当length是2的幂时，可以用位运算替代
int index = hash & (length - 1);
// 位运算比取模快得多

2. 扩容时元素重新分配更高效

// 扩容前：length = 16，hash & 15
// 扩容后：length = 32，hash & 31
// 每个元素要么在原位置，要么在 原位置+oldCap

3.5 HashMap的hash函数设计

static final int hash(Object key) {
    int h;
    // 高16位和低16位异或，减少碰撞
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

设计目的：

• 让hash值的高位也参与到索引计算中
• 减少哈希冲突
• 提高hash的随机性

四、ConcurrentHashMap相关面试题

4.1 ConcurrentHashMap的实现原理

JDK 1.7：Segment分段锁

// JDK 1.7
class ConcurrentHashMap<K,V> {
    final Segment<K,V>[] segments;
    
    static class Segment<K,V> extends ReentrantLock {
        transient volatile HashEntry<K,V>[] table;
    }
}

JDK 1.8：CAS + synchronized

// JDK 1.8
class ConcurrentHashMap<K,V> {
    transient volatile Node<K,V>[] table;
    
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        // ...
        for (Node<K,V>[] tab = table;;) {
            // 1. 如果桶为空，使用CAS插入
            if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                    break;
            }
            // 2. 如果桶不为空，使用synchronized
            else {
                synchronized (f) {
                    // 插入节点
                }
            }
        }
    }
}

4.2 JDK 1.7和1.8的区别

特性	JDK 1.7	JDK 1.8
底层结构	Segment数组 + HashEntry数组	Node数组 + 链表/红黑树
锁机制	分段锁（ReentrantLock）	CAS + synchronized
锁粒度	Segment级别	节点级别
并发度	Segment个数（默认16）	更高，可达数组长度

五、Set相关面试题

5.1 HashSet的实现原理

答案：

HashSet底层基于HashMap实现：

public class HashSet<E> {
    private transient HashMap<E,Object> map;
    
    // 虚拟值
    private static final Object PRESENT = new Object();
    
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
    
    public boolean contains(Object o) {
        return map.containsKey(o);
    }
}

关键点：

• 元素作为HashMap的key
• value统一使用PRESENT对象
• 利用HashMap的key不重复特性

5.2 TreeSet如何保证有序和不重复？

答案：

TreeSet基于TreeMap（红黑树）实现：

public class TreeSet<E> extends AbstractSet<E> {
    private transient NavigableMap<E,Object> m;
    
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
    
    public boolean add(E e) {
        return m.put(e, PRESENT) == null;
    }
}

有序性保证：

• 红黑树是自平衡的二叉搜索树
• 中序遍历得到有序序列

使用示例：

// 自然排序
TreeSet<Integer> set1 = new TreeSet<>();
set1.add(5);
set1.add(2);
set1.add(8);
// 输出：[2, 5, 8]

// 自定义排序
TreeSet<String> set2 = new TreeSet<>((a, b) -> b.compareTo(a));
set2.add("apple");
set2.add("banana");
set2.add("cherry");
// 输出：[cherry, banana, apple]

六、面试高频问题汇总

6.1 如何选择合适的集合类？

选择标准：

// 1. 需要键值对映射？
if (需要键值对) {
    if (需要线程安全) return ConcurrentHashMap;
    if (需要排序) return TreeMap;
    if (需要保持插入顺序) return LinkedHashMap;
    return HashMap;
}

// 2. 需要去重？
if (需要去重) {
    if (需要排序) return TreeSet;
    if (需要保持插入顺序) return LinkedHashSet;
    return HashSet;
}

// 3. 需要有序列表？
if (查询操作多) return ArrayList;
if (插入删除操作多) return LinkedList;

6.2 fail-fast和fail-safe的区别

fail-fast（快速失败）：

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");

// 抛出ConcurrentModificationException
for (String item : list) {
    list.remove(item); // 遍历时修改，快速失败
}

fail-safe（安全失败）：

CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("A");
list.add("B");

// 不会抛异常，但可能读到旧数据
for (String item : list) {
    list.remove(item); // 安全，但操作的是副本
}

6.3 如何实现ArrayList的线程安全？

方法1：使用Collections.synchronizedList()

List<String> list = Collections.synchronizedList(new ArrayList<>());

方法2：使用CopyOnWriteArrayList

List<String> list = new CopyOnWriteArrayList<>();

方法3：手动加锁

List<String> list = new ArrayList<>();
synchronized(list) {
    list.add("item");
}

性能对比：

• CopyOnWriteArrayList：读多写少场景
• Collections.synchronizedList：读写均衡场景
• 手动加锁：灵活性高，但容易出错

总结

Java集合框架是Java开发的基础，掌握其底层原理对于编写高效代码和通过面试至关重要。重点需要掌握：

1. ArrayList：动态数组，扩容机制
2. LinkedList：双向链表，适合插入删除
3. HashMap：数组+链表/红黑树，hash算法
4. ConcurrentHashMap：线程安全，CAS+synchronized
5. HashSet/TreeSet：基于Map实现，去重和排序

参考资料

• Java集合框架官方文档
• 《Java核心技术 卷I》
• 《Effective Java》第三版