JAVA中集合面试题

【】 ArrayList vs LinkedList 深度辨析

在讨论JAVA中集合面试题时，List接口的两个主要实现类——ArrayList和LinkedList，是考察频率最高的知识点之一。许多初学者仅知道ArrayList基于数组，LinkedList基于链表，但往往忽略其底层结构对性能的具体影响。

⚡ 面试官追问：ArrayList扩容机制详解

当ArrayList添加元素时，如果当前数组容量不足，会触发扩容机制。在JDK 1.8中，默认初始容量为10，扩容因子为0.5（即新容量 = 旧容量 1.5）。扩容过程中，会使用Arrays.copyOf()方法创建新数组并复制数据，这是一个相对耗时的操作。因此，在已知数据量的场景下，建议在实例化ArrayList时指定初始容量，以避免不必要的扩容开销。

// 推荐写法：预分配容量
List<String> list = new ArrayList<>(100);
// 避免写法：频繁扩容
List<String> list = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
    list.add("item" + i);
}

《》 HashMap 源码级解析

HashMap是Java开发中使用最频繁的集合类之一，也是JAVA中集合面试题中的“重头戏”。理解HashMap的工作原理，需要掌握其底层数据结构、哈希冲突解决机制以及JDK 1.7与1.8的差异。

1. 底层数据结构演变

在JDK 1.7中，HashMap由数组+链表组成。当发生哈希冲突时，元素以链表形式挂载在数组节点上。而在JDK 1.8中，引入了红黑树结构。当链表长度超过阈值（默认为8）且数组长度超过64时，链表会转换为红黑树，从而将查找复杂度从O(n)降低到O(log n)，提升了极端情况下的性能。

2. 哈希冲突解决方案

HashMap通过计算Key的hashCode()，再经过扰动函数（hash()）处理后，确定元素在数组中的索引位置。如果两个不同的Key计算出的索引相同，即发生哈希冲突。HashMap采用“链地址法”解决冲突，即在同一个索引位置形成链表或红黑树。

3. 为什么HashMap线程不安全？

在多线程环境下，HashMap可能存在以下问题：

• 〓 数据覆盖：两个线程同时插入元素，可能因扩容导致数据丢失。
• 〓 死循环：JDK 1.7中，并发扩容可能导致链表形成环，造成CPU 100%。
• 〓 元素丢失：JDK 1.8中，虽然解决了死循环，但仍存在元素覆盖的风险。

因此，在多线程环境中，应使用ConcurrentHashMap替代HashMap。

『』 ConcurrentHashMap 并发安全机制

针对HashMap的线程安全问题，Java提供了ConcurrentHashMap。它是Java并发包中性能极高的线程安全集合，其设计思想经历了从JDK 1.7的分段锁到JDK 1.8的CAS+synchronized的重大演变。

【】 Collection 与 Collections 的区别

这是一个看似简单但极易混淆的概念，常出现在JAVA中集合面试题的初级考察中。

• Collection：是Java集合框架的根接口，位于java.util包。它定义了集合的基本操作，如add、remove、contains、iterator等。List、Set、Queue都是其子接口。
• Collections：是一个工具类，位于java.util包。它提供了一系列静态方法，用于对集合进行排序、查找、同步包装等操作，如sort()、binarySearch()、synchronizedList()等。

// Collections工具类示例
List<Integer> list = new ArrayList<>();
list.add(3);
list.add(1);
list.add(2);
// 排序
Collections.sort(list);
System.out.println(list); // [1, 2, 3]
// 转线程安全集合
List<Integer> syncList = Collections.synchronizedList(list);

⚡ 高频面试真题实战

以下是基于真实面试场景整理的三道深度题目，涵盖算法思维与底层原理。

Q1: 如何高效实现LRU缓存？

解析：LRU（Least Recently Used）缓存淘汰策略要求我们在获取数据时标记为最近使用，并在容量满时淘汰最久未使用的数据。Java中可以使用LinkedHashMap实现，通过重写removeEldestEntry()方法控制淘汰逻辑。更深层的考察是手写链表+HashMap结构，实现O(1)的get和put操作。

public class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // true表示按访问顺序排序
        this.capacity = capacity;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

Q2: HashMap中Key和Value允许为null吗？

解析：HashMap允许一个Key为null，value可以为null。Key为null时，会被存放在数组索引0的位置。而Hashtable不允许Key或Value为null，否则会抛出NullPointerException。

Q3: 如何遍历ArrayList并删除元素？

解析：直接在使用for-each或普通for循环中调用remove()方法会抛出ConcurrentModificationException。正确做法是使用Iterator的remove()方法，或者使用Java 8的removeIf()方法。

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (condition) {
        it.remove();
    }
}