Java集合面试题深度解析

Java集合框架核心体系

Java集合框架（Java Collections Framework, JCF）是Java标准库中最重要的组成部分之一， 它提供了一套性能优良、使用方便的接口和类，用于存储和处理对象集合。 Java集合面试题中，集合框架的基础知识往往是第一道门槛， 理解其整体架构对于深入理解后续的高级特性至关重要。

集合框架类图结构

掌握集合框架的继承关系是回答Java集合面试题的基础。 以下是主要的继承关系梳理：

Map系列高频面试题

Map集合是Java集合面试题中的重中之重，尤其是HashMap， 几乎每场面试都会涉及。以下是对HashMap及相关Map实现类的深度解析。

1. HashMap底层数据结构是什么？

在JDK 1.7及之前，HashMap由数组+链表组成，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的。 在JDK 1.8及之后，引入了红黑树结构，当链表长度超过8且数组长度超过64时，链表会转换为红黑树， 以提高查询效率。红黑树的平均查询时间复杂度为O(log n)，而链表为O(n)。

// JDK 1.8 HashMap核心数据结构
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;
    // 如果是红黑树节点
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
}

2. HashMap的哈希冲突如何解决？

HashMap采用链地址法（Separate Chaining）解决哈希冲突。 当两个不同的键计算出的哈希值相同时，它们会被存储在同一个桶（bucket）的链表中。 在JDK 1.8中，如果链表长度超过8，且数组长度超过64，链表会转换为红黑树， 从而将最坏情况下的查询时间从O(n)降低到O(log n)。

3. HashMap的扩容机制是怎样的？

HashMap的初始容量为16，负载因子为0.75。当元素个数超过容量×负载因子时， HashMap会进行扩容，容量变为原来的2倍（必须是2的幂）。 扩容时需要重新计算所有元素的哈希值，并将其重新分配到新的桶中。 在JDK 1.8中，扩容时可以通过判断高位是否为0来决定元素是留在原位置还是移动到原位置+旧容量的位置， 从而避免了重新计算哈希值。

4. HashMap与HashTable的区别？

List系列高频面试题

List接口是有序的集合，允许重复元素。在Java集合面试题中， ArrayList和LinkedList的区别是经典问题，需要从底层数据结构、增删改查性能、内存占用等方面进行对比。

1. ArrayList与LinkedList的区别？

// ArrayList核心数组
transient Object[] elementData;

// LinkedList节点结构
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

2. ArrayList的扩容机制？

ArrayList的初始容量为10。当添加元素超过当前容量时，会进行扩容。 扩容策略为：新容量 = 旧容量 + 旧容量/2（即1.5倍）。 例如，从10扩容到15，从15扩容到22，依此类推。 如果指定了初始容量，则按指定容量初始化。

Set系列高频面试题

Set接口是不允许重复元素的集合。HashSet、TreeSet、LinkedHashSet是Set接口的三个主要实现类， 它们在Java集合面试题中也经常被考察。

1. HashSet如何保证元素唯一性？

HashSet底层基于HashMap实现，利用HashMap的Key不可重复特性来保证Set元素的唯一性。 当向HashSet中添加元素时，会调用元素的hashCode()方法计算哈希值， 然后根据哈希值确定存储位置。如果该位置已有元素，则调用equals()方法比较， 如果相等则认为元素重复，不添加；否则以链表或红黑树形式存储。

2. HashSet与TreeSet的区别？

并发集合面试题

在高并发场景下，线程安全的集合类是Java集合面试题的难点和重点。 ConcurrentHashMap是面试中的常客，需要深入理解其在不同JDK版本中的实现差异。

1. ConcurrentHashMap在JDK 1.7和1.8中的区别？

2. CopyOnWriteArrayList的特点？

CopyOnWriteArrayList是一种线程安全的List实现，适用于读多写少的场景。 其核心思想是"写入时复制"（Copy-On-Write），每次修改操作都会创建一个新的数组副本， 修改完成后将新数组替换旧数组。这样读操作不需要加锁，性能很高，但写操作成本较大。

核心源码解析

深入理解源码是应对Java集合面试题的关键。 以下是对HashMap和ConcurrentHashMap核心方法的源码级解析。

1. 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. 如果数组为空或长度为0，则初始化数组
    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是否相同
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            // 4. 如果是红黑树节点，调用树插入方法
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 5. 如果是链表，遍历链表
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 6. 如果链表长度超过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;
            }
        }
        // 7. 如果key已存在，更新value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 8. 如果元素个数超过阈值，扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

2. ConcurrentHashMap的put方法流程（JDK 1.8）

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        // 1. 如果数组为空，初始化数组
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        // 2. 如果计算位置为空，使用CAS插入
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                break;
        }
        // 3. 如果该位置节点hash为MOVED，说明正在扩容，协助扩容
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            // 4. 使用synchronized锁定桶头节点
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    // 5. 如果是链表节点，遍历插入
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent) e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key, value, null);
                                break;
                            }
                        }
                    }
                    // 6. 如果是红黑树节点，调用树插入方法
                    else if (f instanceof TreeNode)
                        ((TreeNode<K,V>)f).putTreeVal(this, tab, hash, key, value);
                }
            }
            // 7. 如果链表长度超过8，转换为红黑树
            if (binCount >= 0) {
                if (binCount >= TREEIFY_THRESHOLD - 1)
                    treeifyBin(tab, hash);
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

网友还关心：Java集合高频问答

除了上述核心面试题外，以下问题也是Java集合面试题中经常被提及的周边知识， 建议开发者重点关注。

其他相关问题

• ＜strong＞WeakHashMap的特点？＜/strong＞：键是弱引用，当键不再被其他强引用指向时，会被垃圾回收器回收。
• ＜strong＞LinkedHashMap的访问顺序？＜/strong＞：可以配置为按访问顺序排序，适用于实现LRU缓存。
• ＜strong＞EnumSet的特点？＜/strong＞：专为枚举类型设计的Set实现，内部使用位向量，性能极高。
• ＜strong＞PriorityQueue的排序方式？＜/strong＞：基于堆实现，支持自定义比较器，按优先级出队。