Java面试八股文-集合篇

1. 集合框架概览

1.1 Java集合框架的结构？

Java集合框架主要分为三大类：

• Collection：存储单个元素的集合
  • List：有序、可重复的集合
  • Set：无序、不可重复的集合
  • Queue：队列，先进先出
• Map：存储键值对的集合
• Tools：工具类，如Collections、Arrays等

1.2 Collection和Collections的区别？

• Collection是一个接口，是所有集合类的父接口
• Collections是一个工具类，提供了操作集合的静态方法

1.3 集合框架中的线程安全集合有哪些？

线程安全的集合包括：

• Vector
• Hashtable
• Collections.synchronizedList()
• Collections.synchronizedSet()
• Collections.synchronizedMap()
• ConcurrentHashMap
• CopyOnWriteArrayList
• CopyOnWriteArraySet
• BlockingQueue的实现类

2. List接口

2.1 ArrayList和LinkedList的区别？

ArrayList和LinkedList是List接口的两个主要实现类，它们的区别主要体现在以下几个方面：

特性	ArrayList	LinkedList
底层实现	基于动态数组	基于双向链表
随机访问	快（O(1)），直接通过索引访问	慢（O(n)），需要遍历链表
插入删除	慢（O(n)），需要移动元素	快（O(1)），只需要修改指针
内存占用	较小，只存储元素本身	较大，需要存储元素和前后指针
遍历效率	高，适合for循环遍历	低，适合foreach遍历
扩容机制	当容量不足时，自动扩容为原来的1.5倍	不需要扩容，动态添加

ArrayList示例：

import java.util.ArrayList;
import java.util.List;

public class ArrayListExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        
        // 添加元素
        list.add("Java");
        list.add("Python");
        list.add("C++");
        
        // 随机访问（快）
        System.out.println("Element at index 1: " + list.get(1)); // 输出: Python
        
        // 遍历（适合for循环）
        System.out.println("Using for loop:");
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
        
        // 插入元素（慢）
        list.add(1, "JavaScript");
        System.out.println("After insertion: " + list); // 输出: [Java, JavaScript, Python, C++]
        
        // 删除元素（慢）
        list.remove(2);
        System.out.println("After removal: " + list); // 输出: [Java, JavaScript, C++]
    }
}

LinkedList示例：

import java.util.LinkedList;
import java.util.List;

public class LinkedListExample {
    public static void main(String[] args) {
        List<String> list = new LinkedList<>();
        
        // 添加元素
        list.add("Java");
        list.add("Python");
        list.add("C++");
        
        // 随机访问（慢）
        System.out.println("Element at index 1: " + list.get(1)); // 输出: Python
        
        // 遍历（适合foreach）
        System.out.println("Using foreach:");
        for (String element : list) {
            System.out.println(element);
        }
        
        // 插入元素（快）
        list.add(1, "JavaScript");
        System.out.println("After insertion: " + list); // 输出: [Java, JavaScript, Python, C++]
        
        // 删除元素（快）
        list.remove(2);
        System.out.println("After removal: " + list); // 输出: [Java, JavaScript, C++]
        
        // LinkedList还实现了Deque接口，可以作为队列使用
        LinkedList<String> queue = new LinkedList<>();
        queue.offer("First");
        queue.offer("Second");
        queue.offer("Third");
        
        System.out.println("Queue elements:");
        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
    }
}

使用场景选择：

• ArrayList：适合需要频繁随机访问元素的场景，如通过索引访问元素。
• LinkedList：适合需要频繁插入和删除操作的场景，如队列、栈等数据结构的实现。
• 插入删除：ArrayList插入删除速度慢，LinkedList插入删除速度快
• 内存占用：ArrayList内存占用小，LinkedList内存占用大
• 遍历效率：ArrayList适合使用for循环遍历，LinkedList适合使用迭代器遍历

2.2 ArrayList的扩容机制？

ArrayList的默认初始容量是10。当元素数量超过容量时，会进行扩容：

• 扩容后的容量是原来的1.5倍（oldCapacity + oldCapacity >> 1）
• 扩容时会创建一个新的数组，将原数组的元素复制到新数组中
• 扩容操作的时间复杂度是O(n)

2.3 Vector和ArrayList的区别？

• 线程安全：Vector是线程安全的，ArrayList不是
• 扩容机制：Vector默认扩容为原来的2倍，ArrayList默认扩容为原来的1.5倍
• 性能：ArrayList性能优于Vector
• 历史：Vector是Java 1.0引入的，ArrayList是Java 1.2引入的

2.4 CopyOnWriteArrayList的原理？

CopyOnWriteArrayList是一种线程安全的List实现，它的原理是：

• 当需要修改列表时，先复制一份原数组
• 在复制的数组上进行修改
• 修改完成后，将引用指向新数组
• 读取操作不需要加锁，写入操作需要加锁

优点：

• 读取操作不需要加锁，性能高
• 适合读多写少的场景
  缺点：
• 内存占用大
• 写入操作性能低
• 不能保证数据的实时一致性

3. Set接口

3.1 HashSet、LinkedHashSet和TreeSet的区别？

• HashSet：基于哈希表实现，无序，不可重复
• LinkedHashSet：基于哈希表和链表实现，有序（插入顺序），不可重复
• TreeSet：基于红黑树实现，有序（自然排序或自定义排序），不可重复

3.2 HashSet的去重原理？

HashSet的去重原理是：

• 先计算元素的hashCode()
• 然后根据hashCode找到对应的桶
• 再使用equals()方法比较桶中的元素
• 如果hashCode相同且equals()返回true，则认为元素重复

3.3 如何实现一个自定义对象可以在HashSet中去重？

需要重写对象的hashCode()和equals()方法：

• hashCode()方法：返回对象的哈希值，相同对象应该返回相同的哈希值
• equals()方法：比较对象是否相等，相同对象应该返回true

3.4 TreeSet的排序原理？

TreeSet的排序原理是：

• 基于红黑树实现
• 元素必须实现Comparable接口，或者在构造TreeSet时提供Comparator
• 根据compareTo()方法或compare()方法进行排序

4. Map接口

4.1 HashMap、LinkedHashMap和TreeMap的区别？

• HashMap：基于哈希表实现，无序，键不可重复
• LinkedHashMap：基于哈希表和链表实现，有序（插入顺序或访问顺序），键不可重复
• TreeMap：基于红黑树实现，有序（自然排序或自定义排序），键不可重复

4.2 HashMap的底层实现？

HashMap的底层实现：

• JDK 1.7及之前：基于数组+链表
• JDK 1.8及之后：基于数组+链表+红黑树
• 当链表长度超过8时，会将链表转换为红黑树
• 当红黑树节点数少于6时，会将红黑树转换为链表

4.3 HashMap的扩容机制？

HashMap的扩容机制：

• 默认初始容量是16，负载因子是0.75
• 当元素数量超过容量*负载因子时，会进行扩容
• 扩容后的容量是原来的2倍
• 扩容时会重新计算元素的位置，将元素转移到新的数组中

4.4 ConcurrentHashMap的底层实现？

ConcurrentHashMap是Java中线程安全的HashMap实现，它的底层实现在JDK 1.7和JDK 1.8中有很大的区别：

4.4.1 JDK 1.7实现

基于分段锁（Segment）：

• 将整个Map分为多个Segment，每个Segment是一个小的HashMap
• 每个Segment拥有自己的锁，不同Segment之间的操作可以并发执行
• 结构：Segment[] → HashEntry[] → 链表

优点：

• 并发度高，多个线程可以同时操作不同的Segment

缺点：

• 结构复杂
• 内存占用较大
• 当Segment数量固定时，并发度有限

4.4.2 JDK 1.8实现

基于CAS和synchronized：

• 取消了Segment，直接使用Node[]数组
• 对数组的每个桶使用synchronized锁
• 结合CAS操作，提高并发性能
• 结构：Node[] → 链表/红黑树

核心改进：

1. 锁粒度更细：从Segment级别的锁细化到桶级别的锁
2. 使用CAS操作：对一些简单操作（如插入头节点）使用CAS，减少锁的使用
3. 红黑树优化：当链表长度超过8时，转为红黑树，提高查询效率
4. 读操作无锁：读操作不需要加锁，使用volatile保证可见性

示例：

import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentHashMapExample {
    public static void main(String[] args) {
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
        
        // 多线程并发操作
        Runnable task = () -> {
            for (int i = 0; i < 1000; i++) {
                map.put(Thread.currentThread().getName() + "-" + i, i);
                map.get(Thread.currentThread().getName() + "-" + i);
            }
        };
        
        Thread thread1 = new Thread(task, "Thread-1");
        Thread thread2 = new Thread(task, "Thread-2");
        Thread thread3 = new Thread(task, "Thread-3");
        
        thread1.start();
        thread2.start();
        thread3.start();
        
        try {
            thread1.join();
            thread2.join();
            thread3.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        
        System.out.println("Map size: " + map.size());
    }
}

ConcurrentHashMap的优点：

• 线程安全：支持多线程并发操作
• 高性能：读操作无锁，写操作锁粒度细
• 支持null值：与HashMap一样，允许值为null
• 支持并发迭代：迭代过程中不会抛出ConcurrentModificationException

适用场景：

• 多线程环境下需要频繁读写的场景
• 对性能要求较高的场景
• 替代Hashtable的场景

4.5 HashMap和Hashtable的区别？

HashMap和Hashtable是Java中常用的Map实现，它们的区别如下：

特性	HashMap	Hashtable
线程安全	非线程安全	线程安全（使用synchronized修饰方法）
效率	高（无同步开销）	低（同步开销大）
null值	允许键和值为null	不允许键或值为null
扩容机制	扩容为原来的2倍	扩容为原来的2倍+1
遍历方式	使用Iterator（快速失败）	使用Enumeration（安全失败）
继承关系	继承自AbstractMap	继承自Dictionary
历史	Java 1.2引入	Java 1.0引入
性能	适合单线程环境	适合多线程环境（但推荐使用ConcurrentHashMap）

示例：

// HashMap示例
import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        
        // 允许null键和null值
        map.put(null, 1);
        map.put("key", null);
        
        // 遍历
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }
    }
}

// Hashtable示例
import java.util.Hashtable;
import java.util.Map;

public class HashtableExample {
    public static void main(String[] args) {
        Map<String, Integer> table = new Hashtable<>();
        
        // 不允许null键或null值
        // table.put(null, 1); // 抛出NullPointerException
        // table.put("key", null); // 抛出NullPointerException
        
        table.put("key1", 1);
        table.put("key2", 2);
        
        // 遍历
        for (Map.Entry<String, Integer> entry : table.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }
    }
}

使用场景：

• HashMap：单线程环境下的键值对存储
• Hashtable：多线程环境下的键值对存储（但推荐使用ConcurrentHashMap）
• ConcurrentHashMap：多线程环境下的高性能键值对存储（推荐）

5. 其他集合相关问题

5.1 什么是迭代器？如何使用迭代器？

迭代器是一种设计模式，用于遍历集合中的元素。使用迭代器的步骤：

• 获取集合的迭代器：iterator()
• 使用hasNext()检查是否有下一个元素
• 使用next()获取下一个元素
• 使用remove()删除当前元素（可选）

5.2 什么是快速失败（fail-fast）和安全失败（fail-safe）？

• 快速失败（fail-fast）：在迭代过程中，如果集合被修改（除了通过迭代器的remove()方法），会抛出ConcurrentModificationException
• 安全失败（fail-safe）：在迭代过程中，会创建集合的副本进行遍历，不会抛出ConcurrentModificationException

5.3 如何选择合适的集合？

选择集合的依据：

• 如果需要有序且可重复的集合，使用List
  • 如果需要随机访问，使用ArrayList
  • 如果需要频繁插入删除，使用LinkedList
• 如果需要无序且不可重复的集合，使用Set
  • 如果需要快速查找，使用HashSet
  • 如果需要有序，使用TreeSet或LinkedHashSet
• 如果需要键值对映射，使用Map
  • 如果需要快速查找，使用HashMap
  • 如果需要有序，使用TreeMap或LinkedHashMap
  • 如果需要线程安全，使用ConcurrentHashMap

5.4 集合的遍历方式有哪些？

集合的遍历方式：

• for循环（适用于List）
• 增强for循环（适用于所有集合）
• 迭代器（适用于所有集合）
• forEach方法（Java 8+，适用于所有集合）
• 流（Stream）API（Java 8+，适用于所有集合）